Parser Combinator

Parser Combinator

前面的废话

这篇文章讲了什么

讲了一些基础的 Parser Combinator 的实现,和一个简单的例子。

谁需要看这篇文章

对 Haskell 和 Parser 有简单但不是很深入的了解的人

什么是 Parser Combinator

Parser Combinator(解析器组合子) 是一种很简单的 Parser 实现方法,基本基于递归下降,但

Parser Combinator 在正经的编译相关研究没有提及,是因为它没有解决任何新的算法问题,只是换了一种方式来编写非左递归文法。换言之,它在语法解析算法研究领域里没有价值。

所以它的效率问题我们在这里不做讨论。

为什么要用 Parser Combinator

可以用来理解 monad (可能)

bnf 语法基本是一一对应的关系,写起来很方便 (大概吧)

我不会别的写法 (该学学了)

用什么语言写

用 Haskell 写起来好看一些 ,那就用 Haskell 吧 (可能是只会 Haskell

下面我们将从头开始一步一步地搭出一个能用的 Parser

Parser Combinator 的实现

Parser 类的定义

首先我们定义 Parser 的类型

1
newtype Parser a = Parser (String -> Maybe (a, String))

这里实际上是没有实现 Tokenizer 而是直接让 Parser 处理输入的代码,所以输入类型是 String ,而 Maybe (a, String) 表示如果解析成功则会得到解析出来的值和剩下的代码、而如果没有成功则是 Nothing

我们需要一个 parse 动作来使用一个 Parser :

1
2
parse :: Parser a -> String -> Maybe (a, String)
parse (Parser p) = p

显然的,Parser 是一个 Functor

1
2
3
4
5
6
instance Functor Parser where

-- fmap :: (a -> b) -> Parser a -> Parser b
fmap f p = Parser $ \ st -> case parse p st of
Nothing -> Nothing
Just (a, s2) -> Just (f a, s2)

通过 fmap 我们可以把一个 Parser 变换成另一个 Parser

同样的,Parser 也是一个 Applicative Functor

1
2
3
4
5
6
7
8
9
instance Applicative Parser where

-- pure :: a -> Parser a
pure v = Parser $ \ st -> Just (v, st)

-- (<*>) :: Parser (a -> b) -> Parser a -> Parser b
pab <*> pa = Parser $ \ st -> case parse pab st of
Nothing -> Nothing
Just (v, out) -> parse (fmap v pa) out

然后就是最核心的 monad

1
2
3
4
5
6
instance Monad Parser where

-- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
pa >>= apb = Parser (\ st -> case parse pa st of
Nothing -> Nothing
Just (a, out) -> parse (apb a) out)

实现了 Monad 我们就能通过 do-notation 来简化很多东西

然后是来实现Alternative

1
2
3
4
5
6
7
8
9
instance Alternative Parser where

-- empty :: Parser a
empty = Parser $ const Nothing

-- <|> :: Parser a -> Parser a -> Parser a
pa <|> pa2 = Parser (\ st -> case parse pa st of
Nothing -> parse pa2 st
Just x -> Just x)

Alternative 提供了 <|> 来表示两者之一,somemany 分别表示重复解析一次或多次和零次或多次,以及 empty 来返回一个空 Parser

实现基础的功能

首先是 item

1
2
3
4
item :: Parser Char
item = Parser $ \ st -> case st of
[] -> Nothing
(x : xs) -> Just (x , xs)

item 是整个 Parser Combinator 中最基础的元素,它读取待解析字符串的第一个字符并放入结果中

然后通过 item 我们能得到一个解析特定字符的 Parser

1
2
sat :: (Char -> Bool) -> Parser Char
sat f = item >>= (\x -> if f x then return x else empty)

当然我们可以用 do-notation 这样写

1
2
3
4
sat :: (Char -> Bool) -> Parser Char
sat f = do
x <- item
if f x then return x else empty

于是我们可以通过 sat 来获得很多常见种类的字符的 Parser

1
2
3
4
5
6
7
8
9
10
11
12
13
14
digit :: Parser Char
digit = sat isDigit

lower :: Parser Char
lower = sat isLower

upper :: Parser Char
upper = sat isUpper

letter :: Parser Char
letter = sat isLetter

alphanum :: Parser Char
alphanum = sat isAlphaNum

后面的那些函数都来自 Data.Char

然后我们可以获得单个字符和字符串的 Parser

1
2
3
4
5
6
char :: Char -> Parser Char
char x = sat (==x)

string :: String -> Parser String
string [] = return []
string xs'@(x : xs) = char x >> string xs >> return xs'

在解析表达式的时候经常要处理空格,所以我们有

1
2
space :: Parser ()
space = void $ many $ sat isSpace

这里的 voidControl.Monad 里的一个函数,类型为 Functor f => f a -> f ()

基本的元素大概就是这么多,通过这些元素,我们可以实现一些较为复杂的解析。我们将在下面的例子中继续讲解。

使用 Parser Combinator 解析 LisP 语句

这里是一道很标准的 PC 题目,我们通过这道题来学习 Parser Combinator 的使用。

LisP 的 BNF 语法非常简单:

1
2
3
4
5
6
7
8
9
10
nodes    ::= "(" expr expr* ")"
nulls ::= "(" ")"
| "null"
booleans ::= "true"
| "false"
expr ::= symbols
| numbers
| booleans
| nulls
| nodes

我们写的 Parser 需要把给出的 LisP 代码解析成一颗抽象语法树 (Abstract Syntax Tree) ,给出了它的定义:

1
2
3
4
5
6
7
8
data AST = I32 Int       -- numbers
| Sym String -- symbols
| Nul -- nulls
| Lst [AST] -- lists
| Boo Bool -- booleans
| Err -- errors
| Nod AST [AST] -- nodes
deriving (Eq, Show)

我们的首先写的东西是 token

1
2
3
4
5
6
token :: Parser a -> Parser a
token p = do
_ <- space
v <- p
_ <- space
return v

我们在解析时会忽略掉一个东西前后的空格

然后是对于字面量的解析 symbol

1
2
symbol :: String -> Parser String
symbol xs = token $ string xs

然后我们开始对着 AST 来写 Parser

首先是 number
我们定义

1
2
3
4
5
nat :: Parser Int
nat = read <$> some digit

natural :: Parser Int
natural = token nat

于是有

1
2
parseNumber :: Parser AST
parseNumber = fmap I32 natural

然后是 Bool 字面量

1
2
3
parseBoolean :: Parser AST
parseBoolean = (symbol "true" >> return (Boo True))
<|> (symbol "false" >> return (Boo False))

这里我们头一次用到了之前定义的 Alternative 实例中的 <|> 方法,通过 <|> 我们可以让第一个匹配失败之后能够继续试验第二个,就像 parseBoolean 中如果当前 symbol 不是 "true" 的话就会继续尝试下一个直到失败或者结束。

然后是

1
2
3
4
5
6
7
8
9
10
parseList :: Parser AST
parseList = do
_ <- symbol "(" >> symbol "list"
xs <- some parseExpression
_ <- symbol ")"
return $ Lst xs

parseNull :: Parser AST
parseNull = (symbol "(" >> symbol ")" >> return Nul)
<|> (symbol "null" >> return Nul )

和 LisP 中的 Symbol

1
2
3
string' :: String -> Parser AST
string' [] = failure
string' xs'@(x : xs) = char x >> string xs >> return (Sym xs')

最后就是对S-表达式的解析

1
2
3
4
5
6
7
8
9
10
parseExpression = parseNull
<|> parseNumber
<|> parseBoolean
<|> parseList
<|> parseSymbol
<|> do
_ <- symbol "("
(s : xs)<- some parseExpression
_ <- symbol ")"
return (Nod s xs)

这样我们的解析就完成了~
这道题剩下的部分就是一些简单的体力活了。

最后的一些废话

我学到了什么

用 Haskell 实现的 Parser Combinator 的简单用法、递归下降和一点 monad 的实践。