by

# some 与 many

``````-- | one or more
spacesP :: Parser String
spacesP = some \$ oneOf " \n\r\t"

-- | zero or more
spaces0P :: Parser String
spaces0P = many \$ oneOf " \n\r\t"
``````

## 其他小工具

``````import Data.Char

stringP :: String -> Parser String
stringP [      ] = return []
stringP (c : cs) = do
charP c
stringP cs
return \$ c : cs
--

reservedP :: String -> Parser String
reservedP = tokenP . stringP

natP :: Parser Int
natP = read <\$> some digitP

digitP :: Parser Char
digitP = satisfy isDigit

tokenP :: Parser a -> Parser a
tokenP p = do
a <- p
spaces0P
return a
--
``````

# chainl1 与 chainr1

1. 解析一个运算单元
2. 解析一个运算符

``````-- the parsers
numberP :: Parser String
numberP = do
s <- stringP "-" <|> return []
cs <- some digitP
spaces0P
return \$ s ++ cs
--

plusSymbolP :: Parser String
plusSymbolP = do
stringP "+"
spaces0P
return "+"
``````

## AST

``````{-# LANGUAGE DeriveFunctor #-}

data OpTree a b = Term b
| Op (OpTree a b) a (OpTree a b)
deriving (Show, Eq, Functor)
``````

``````Op (Term "1") "+" (Term "1")
``````

## 问题

``````p = do
n1 <- numberP
plusSymbolP
n2 <- numberP
plusSymbolP
n3 <- numberP
plusSymbolP
n4 <- numberP
return \$ Op (Op (Op (Term "1") "+" (Term "1")) "+" (Term "1")) "+" (Term "1")
``````

## 抽象

``````-- | binary operators
binOp :: String -> (b -> b -> b) -> Parser (b -> b -> b)
binOp sym func = do
stringP sym
return func
``````

``````-- | binary operators
binOp :: String -> (b -> b -> b) -> Parser (b -> b -> b)
binOp s = (stringP s >>) . return
``````

1. 拿到运算符和 通过结合运算符左右的两个语法树节点生成新的语法树节点的函数（此处是 `\l r -> Op l "+" r`
2. 解析运算符
3. 如果解析成功，那么返回这个函数

## 重写

``````addOp = binOp "+" \$ \x y -> Op x "+" y
subOp = binOp "-" \$ \x y -> Op x "-" y
mulOp = binOp "*" \$ \x y -> Op x "*" y
divOp = binOp "/" \$ \x y -> Op x "/" y
``````

``````operatorP :: Parser (a -> a -> a) -> Parser a
operatorP op = do
l <- numberP
o <- op
r <- numberP
return \$ o l r
``````

## 左结合

``````chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = do
a <- p
rest a
where
rest a = (do
f <- op
b <- p
rest \$ f a b)
<|> return a
--
``````

``````adds = chainl1 numberP addOp
``````

``````Main> parseCode adds "1+1+1+1"
Op (Op (Op (Term "1") "+" (Term "1")) "+" (Term "1")) "+" (Term "1")
Op (Op (Term "1") "+" (Term "1")) "+" (Term "1")
Op (Term "1") "+" (Term "1")
``````

``````addAndSubs = chainl1 numberP \$ addOp <|> subOp
``````

## 右结合

``````chainr1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainr1 p op = scan
where
scan = do
a <- p
rest a
rest a = (do
f <- op
b <- scan
rest \$ f a b)
<|> return a
--
``````

``````sq = chainr1 numberP \$ binOp "^" \$ \x y -> Op x "^" y
``````

## 优先级

``````addP = chainl1 mulP \$ binOp "+" \$ \x y -> Op x "+" y
mulP = chainl1 oneP \$ binOp "*" \$ \x y -> Op x "*" y
oneP = numberP
``````

# 杂话

## 关于 Applicative

``````parseUsingMonad = do
x <- itemP
o <- operatorP
y <- itemP
return \$ Op x o y
``````

``````parseUsingApplicative = Op <\$> itemP <*> operatorP <*> itemP
``````

``````{-# LANGUAGE ApplicativeDo #-}
``````

# CodeWars Challenges

## Tiny Three Pass Compiler

Tweet this
Top

Create an issue to apply for commentary