个人文档网

author：运维 date：2020-09-18 14:04展示PPT

>title: 用Parser实现简易加减乘除解析器
  
本文简单的实现了加减乘除计算器解析器，我们用到了haskell重要的概念从Functor,Applicative, Monad, MonadTrans。

# 我们的目标
1. `(+ 1 1)` 表示 `1 + 1`, `(/ 10 4)` 表示 `10 / 4`
2. 那么我们本文就来解析这样的表达式，如：`(+ 1 (* 10 5))`
3. 解析这样的表达式应该是比较简单，本文主要是用`Haskell`,并且可以看到`Haskell`的一些简单用法

# 数据结构
1. 一般来说我们的计算器要么是一个数字，要么是一个表达式如:`(+ 10 10)`, 要么就是基本表达式的组合
2. 那么我们可以用以下数据结构来表示
```haskell
Data Exp = Exp Double --数字
       | Add Exp Exp -- 加法
       | Div Exp Exp
       | Mul Exp Exp
       | Sub Exp Exp deriving Show
```
3. `Add Exp Exp` 就是 (+ 表达式1 表达式2) 表达式可能就是简单的数字

# 求解表达式
1. 这个比较简单，我们就直接写代码
```haskell
eval :: Exp -> Double
eval (Add e1 e2) = eval e1 + eval e2
eval (Mul e1 e2) = eval e1 * eval e2
eval (Div e1 e2) = eval e1 / eval e2
eval (Sub e1 e2) = eval e1 - eval e2
eval (Exp n)     = n
```
2. 就是个简单的递归求值

# Parser
## Parser 类型定义
```haskell
newtype Parser a = Parser {runParser :: String -> (Maybe a, String)}
```
1. 我们来看看`Maybe a`, 我们可以把`maybe`看成一个盒子，里面要么装一个类型`Int`，比如`Just 10`，要么什么都没有`Nothing`
2. newtype后面的`Parser a`也是一个盒子，里面装了一个`String -> (Maybe a, String)`的函数
3. = (等号)后面的`Parser`可以把函数`String -> (Maybe a, String)`装到盒子里面。　标注：这样的解释并不准确。
4. `runParser`就是把函数从盒子里面拿出来
5. 我们来看一个例子
```haskell
char :: Parser Char
char = Parser $ \s -> case s of
                        [] -> (Nothing, [])
                        (x:xs) -> (Just x, xs)
```
6. 上面的例子就是说char是一个`Parser Char`的类型，这个盒子里面装了一个函数，函数接收一个`String`
  如果`String`是空，那么就返回一个`(Nothing, [])`如果不为空`(x:xs) = s`就拿出第一个字符`(Just x, xs)`
7. 从我个人理解实际上`Parser a`跟`state s a`挺像的。定义Monad类型类中`>>=`也是对输入`String`状态变化的转递
```haskell
newtype State s a = State {runState :: s -> (a, s)}
```

## Functor
1. Functor是个类型类。类型类大体看起来像是java当中的接口。
2. Functor中定义了一个fmap的函数，那么我们Parser a也要实现fmap
3. `fmap :: (a -> b) -> f a -> f b`
4. 上面可以这样理解。 `(a -> b)`是一个函数把a变成b， `f a` 表示 盒子f里面装了一个`a`，
  `fmap`就是要把盒子里面的a拿出来应用上函数`(a->b)`变成盒子`f`里面装了一个`b`。
5. 代码

``` haskell
instance Functor Parser where
 fmap f (Parser p) = Parser $ \s -> let p' = p s in
                                     case p' of
                                       (Just a, s')  -> (Just (f a), s')
                                       (Nothing, s') -> (Nothing, s)
```

6. (Parser p) p就是那个(String -> (Maybe a, String)), p'就是把String 给函数 p 产生的结果
7. 然后就是简单判断把a拿出来，应用上函数f返回，如果出来的结果啥都没有就返回啥都没有吧

## Applicative
1. 同上，Applicative是个类型了，定义了两个需要实现的接口（pure， <\*>)
2. `pure :: a -> f a`
3. `<*> :: f (a->b) -> f a -> f b`
4. 我们这边的例子就是`<*> :: Parser (a->b) -> Parser a -> Parser b`
5. 代码
```haskell
instance Applicative Parser where
  pure a = Parser $ \s -> (Just a, s)
  (Parser f) <*> (Parser p) =
     Parser $ \s -> let (f', s') = f s in
                       case f' of
                         Nothing -> (Nothing, s)
                         Just pf -> let (p', s'') = p s' in
                                        case p' of
                                          Nothing -> (Nothing, s)
                                          Just pp -> (Just (pf pp), s'')
```

## Alternative
1. 同上，Alternative是个类型类，我们要实现几个比较有意思的函数
2. 要实现的主要有`empty`, `<|>`, `many`, `some`
3. 代码如下
  ```haskell
instance Alternative Parser where
  empty = Parser $ \s -> (Nothing, s)
  (Parser a) <|> (Parser b) = Parser $ \s -> let (p, s') = a s in
                                                 case p of
                                                   Nothing -> b s
                                                   Just x  -> (p, s')
  many :: Parser a -> Parser [a]
  many p = Parser $ \s -> go s
    where go s = let (a, s') = runParser p s in
                     case a of
                       Nothing -> (Just [], s)
                       Just a' -> let (as, s'') = go s' in (fmap (a':) as, s'')

some :: Parser a -> Parser [a]
  some p = Parser $ \s -> go s
    where go s = let (a, s') = runParser p s in
                     case a of
                       Nothing -> (Nothing, s)
                       Just a' -> let (as, s'') = go s' in
                                      case as of
                                        Nothing  -> (Just [a'], s')
                                        Just as' -> (Just (a':as'), s'')
 ```
4. `many`的意思就是比如我们有一个`Parser`是用来匹配`Char`的，那么`many`就是表示取0个或者多个
5. `some`的意思就是取1个或者多个，如同正则表达式的+
6. `<|>`这边就是假如第一个匹配不到就匹配第二个，如果匹配第一个就是第一个，相当于`OR`操作

## Monad
1. `>>= :: Parser a -> (a -> Parser b) -> Parser b`
  ```haskell
 instance Monad Parser where
  return = pure
  (Parser p) >>= f = Parser $ \s -> let (p', s') = p s in
                                        case p' of
                                          Nothing -> (Nothing, s')
                                          Just pp -> runParser (f pp) s'
  ```

2. Monad单子也是类型类，解释起来非常麻烦，从上面定义中我们可以看到，其实是对`a`的链式处理，并且也是`s`的传递。

# 写个例子
1. 需要几个辅助函数

```haskell
  satisfy :: ( Char -> Bool) -> Parser Char
  satisfy f = Parser $ \s -> case s of
                            [] -> (Nothing, [])
                            (x:xs) -> if f x then
                                             (Just x, xs)
                                             else
                                               (Nothing, x:xs)
  withspace :: Parser a -> Parser a
  withspace p = do
    void spaces
    a <- p
    void spaces
    return a

pint :: Parser Int
  pint = pure read <*> some (satisfy isDigit)

spaces = many $ satisfy (\`elem\` "\r\n \t")
```

2. `satisfy`就是说看一下取出来的第一个字符如果是符合函数f的就取出来，否则返回Nothing
3. 如`satisfy isDigit`表示是数字的`char`取出来
4. `some (satisfy isDigit)`表示取出多个数字
5. `pint`就是取出数字变成Int

6. 实现

```haskell
toDouble :: Parser Exp
toDouble = withspace $ do
  num1 <- pint
  dot  <- satisfy (=='.')
  num2 <- pint
  let nums = show num1 ++ "." ++ show num2
  return $ Exp (read nums :: Double)

toInt :: Parser Exp
toInt = do
  nums <- withspace pint
  return (Exp (fromIntegral nums))

toAction :: Char -> (Exp -> Exp -> Exp) -> Parser Exp
toAction n f = do
  void . withspace $ satisfy (== '(')
  void . withspace $ satisfy (== n)
  -- void . withspace $ satisfy (== '(')
  n1 <- toExp
  n2 <- toExp
  -- void . withspace $ satisfy (== ')')
  void . withspace $ satisfy (== ')')
  return (f n1 n2)

toDiv :: Parser Exp
toDiv = toAction '/' Div

toAdd :: Parser Exp
toAdd = toAction '+' Add

toSub :: Parser Exp
toSub  = toAction '-' Sub

toMul :: Parser Exp
toMul = toAction '*' Mul

# 测试一下

```haskell
λ> fst $ runParser toExp "(* 1000 (- 10 (+ 102.13453323123 1)))"
Just (Mul (Exp 1000.0) (Sub (Exp 10.0) (Add (Exp 102.13453323123) (Exp 1.0))))
λ> fmap eval $ fst $ runParser toExp "(* 1000 (- 10 (+ 102.13453323123 1)))"
Just (-93134.53323123)
```

# ParserT (MonadTrans)
1. show u code

```haskell
import Control.Monad.Trans
import Control.Applicative
import Data.Char
import Data.List
newtype ParserT m a = ParserT {runParserT :: String -> m (Maybe a, String)}

instance Monad m => Functor (ParserT m) where
  fmap f (ParserT p)  = ParserT $ \s -> do
    (a', s')  <- p s
    case a' of
      Nothing -> return (Nothing, s)
      _ -> return (fmap f a', s')

instance Monad m => Applicative (ParserT m) where
  pure a = ParserT $ \s -> return (Just a, s)
  (ParserT pf) <*> (ParserT p) = ParserT $ \s -> do
    (f, s') <- pf s
    case f of
      Nothing -> return (Nothing, s)
      _ -> do
        (a', s'') <- p s'
        case a' of
          Nothing -> return (Nothing, s)
          _ -> return (f <*> a', s'')

instance Monad m => Monad (ParserT m) where
  return = pure
  (ParserT p) >>= f = ParserT $ \s -> do
    (a', s') <- p s
    case a' of
      Nothing -> return (Nothing, s)
      Just x -> runParserT (f x) s'

instance Monad m => Control.Applicative.Alternative (ParserT m) where
  empty = ParserT $ \s -> return (Nothing, s)
  (ParserT p1) <|> (ParserT p2) = ParserT $ \s -> do
    (a1, s1) <- p1 s
    case a1 of
      Nothing -> p2 s
      _ -> return (a1, s1)

instance MonadTrans ParserT where
  lift m = ParserT $ \s -> do
    x <- m
    return (Just x, s)

satisfy :: Monad m => (Char -> Bool) -> ParserT m Char
satisfy f = ParserT $ \s -> case s of
  [] -> return (Nothing, s)
  (x:xs) -> if f x then return (Just x, xs) else return (Nothing, s)

char :: Monad m => ParserT m Char
char = satisfy (`elem` ['a'..'z'])
num :: Monad m => ParserT m Int
num = fmap read $ some $ satisfy isDigit

string ::Monad m => ParserT m String
string = some char

myApp :: ParserT IO (String, Int)
myApp = do
  satisfy (=='(')
  s <- string
  satisfy (==':')
  n <- num
  satisfy (==')')
  lift $ do print s; print n -- wo can do IO monad here
  return (s, n)

```

2. 测试ParserT
```stack
λ> runParserT (many myApp)   "(xucanjie:100000)(zhoucat:2000)"
"xucanjie"
100000
"zhoucat"
2000
(Just [("xucanjie",100000),("zhoucat",2000)],"")
```

3. `ParserT` 是单子变换，从定义上看，当`runParser`的时候，给出来是另外一个`monad`的类型。也说明我们在`ParserT`中，可以使用`monad m`类型类的定义，通过`lift`将`monad m`提升到`ParserT`。我们可以通过monadTrans来嵌套包裹，如：
```haskell
type App = ReaderT AppConfig (StateT AppState IO)
//type App  a = ReaderT AppConfig (StateT AppState IO) a
```

# 总结
实际上Parser可以做很多有意思的事情。大家不妨深究一下。可以看到haskell基本就是采用递归方式，函数可以当作参数传递,函数的名称可以是`<|>`, `>>=`非常灵活。

# 
<a href="https://beian.miit.gov.cn" target="_blank" rel="nofollow">ICP证：闽ICP备12001234号-1</a>

目 录

目录