从零开始的编译器前端之Monadic Parsing

这是第二篇文章。这篇文章试图介绍一下Monadic Parsing的基本概念。

主要的内容来自于Programming in Haskell，虽然也加上了一些自己的个人理解。

提到编译器，就不可避免的要提到Parser了。那么，什么是Parser呢？

抽象而言，Parser是一种输入字符串输出树状的数据结构的程序。一段含有特定的结构的文本（某个语言里面的程序的代码）被解析后生成对应的抽象语法树（AST）。这个AST可以表达出许多在原始文本中没有表现出来的文法结构，以方便编译器进行下一步的操作。

例如，2+3*4在解析后生成的AST，明确的表示出*和+作为具有两个操作元的操作符，同时*具有更高的优先级。

Parser在计算机科学里面是一种很常见的东西，不仅仅是用于实现编程语言的编译器，也可以用来解析一些相对简单的文法。把文本处理过程抽离成生成AST的Parser和对AST进行处理的业务逻辑，虽然看起来比直接处理字符串或者正则要麻烦许多，但是通常有更好的可读性、维护性而且也能较为简单地处理（在字符串处理中）需要很复杂的算法的问题。在OO中，Parser也是一种设计模式的重要构成部分。

Parser作为函数

自然而然的，在Haskell中，Parser可以看作是一种函数：接收字符串作为参数，生成一个树状结构。假设具有生成的AST的结构AST，那么则有：

1	`type Parser = String -> AST`

通常来说，并不一定希望Parser消费整个输入，比如说一个数字紧跟着一串词汇的情况，会希望先用对应的Parser处理了这些数字，再交由下一个Parser去处理剩下的部分。可以使用Tuple来同时返回「剩下的文本」和当前的AST：

1	`type Parser = String -> (Tree, String)`

除此之外，一个Parser也有可能失败，通常用一个数组来表示是否失败的状态：如果解析成功，则返回一个只有这个AST的数组，否则返回一个空数组^[1]：

1	`type Parser = String -> [(Tree, String)]`

最后，不同的Parser会返回不同的类型的AST，或者，对应的说，不同的值。所以通常还会把具体的返回类型抽象出来，用一个泛型参数表示：

1	`type Parser a = String -> [(a, String)]`

总结起来就是，A数据类型的Parser类型是一个输入字符串后，输出一个列表，其中每一列都是一组包含一个返回类型A和一个字符串作为输出的函数。

看起来Parser和State Monad（State -> (a, State)）也很像，不同之处在于这里操作的不是一个状态而是一个字符串^[2]，除此之外，Parser是可以失败的（返回空列表）。

基本定义

首先用newtype来声明代表Parser函数的数据结构：

newtype Parser a = P (String -> [(a, String)])

parse :: Parser a -> String -> [(a, String)]
parse (P p) input = p input

parse函数在给定一个Parser和输入字符串的情况下输出解析出的AST和剩下的字符串^[3]。

item是第一个基本组合子（其实也许并不算是？），如果当前的字符串是个空字符串，那么它会失败，否则会输出第一个字符作为返回值：

item :: Parser Char
item = P (\input -> case input of
                       []     -> []
                       (x:xs) -> [(x, xs)])

所有其他的组合子都是以此构建起来的。item的行为如下：

> parse item ""
[]
> parse item "abc"
[('a', "bc")]

Parser的顺序组合

顺序组合起来的Parser使用do-notation表示。为了能够使用do-notation，首先要把Parser变成Functor、Applicative和Monad的instance。

首先是Functor。

instance Functor Parser where
    -- fmap :: (a -> b) -> Parser a -> Parser b
    fmap g p = P (\input -> case parse p input of
                               []        -> []
                               [(v,out)] -> [(g v, out)])

fmap的作用是（在解析成功的时候）把作为参数的函数应用到Parser的返回值上，否则把失败值向外扩散，从一个给定的Parser构造一个这样的新的Parser。

例如：

> parse (fmap toUpper item) "abc"
[('A',"bc")]
> parse (fmap toUpper item) ""
[]

然后是Applicative。

instance Applicative Parser where
    -- pure :: a -> Parser a
    pure v = P (\input -> [(v,input)])

    -- <*> :: Parser (a -> b) -> Parser a -> Parser b
    pg <*> px = P (\input -> case parse pg input of
                             []        -> []
                             [(g,out)] -> parse (fmap g px) out)

pure把一个单独的值转换为「永远成功并且把这个值作为返回值」的Parser，这个Parser不消耗任何输入。例如：

1 2	`> parse (pure 1) "abc" [(1,"abc")]`

<*>把一个关于函数的Parser应用到另一个关于值的Parser上，返回新的Parser，这个新的Parser的作用是把这个函数应用到值上，并且只有所有部分都成功的时候才成功。一个例子是消耗三个字符，返回第一个和最后一个字符，忽略中间字符的Parser，可以用Applicative style来定义：

1
2
3

three :: Parser (Char, Char)
three = pure g <*> item <*> item <*> item
    where g x y z = (x, z)

使用如下^[4]：

> parse three "abcdef"
[(('a','c'), "def")]
> parse three "ab"
[]

最后是Monad：

instance Monad Parser where
    -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    p >>= f = P (\input -> case parse p input of
                            [] -> []
                            [(v, out)] -> parse (f v) out)

换句话说，p >>= f这个Parser只在parse p input这个函数失败的时候失败，否则会把函数f应用到返回值v上，得到另外一个Parser f v，然后应用这个Parser到out字符串上，获得最后输出的结果。

这时候就可以用do-notation来重写连续进行的Parser了，例如前面的three函数：

three :: Parser (Char, Char)
three = do x <- item
           item
           z <- item
           return (x, z)

一般来说do-notation和Applicative style是等价的。

分支

do-notation用顺序的方式组合不同的Parser，如果一个Parser成功，那么剩余的输出会作为下一个Parser的输入，以此类推。另一个常见的情况是把Parser并联起来，如果一个Parser失败了，那么用同样的输入去匹配另一个Parser。

这种choice的思路并不是Parser独有的，也可以扩大到许多其他的Applicative类型，在Haskell里面，这种行为特征被叫做Alternative。

1
2
3

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a

这里empty表示一个失败了的Alternative，<|>则是choice运算符。Alternative也需要满足以下的法则：

empty <|> p = p
p <|> empty = p
p <|> (q <|> r) = (p <|> q) <|> r

让Parser也成为Alternative的：

instance Alternative Parser where
    -- empty :: Parser a
    empty = P (\input -> [])

    -- <|> :: Parser a -> Parser a -> Parser a
    p <|> q = P (\input -> case parse p input of
                                []        -> parse q input
                                [(v,out)] -> [(v,out)])

这里empty是一个无论输入如何永远失败的Parser，<|>会在第一个Parser成功的时候返回它的解析结果，否则将会使用第二个Parser。例如：

> parse empty "abc"
[]
> parse (item <|> pure 'd') "abc"
[('a',"bc")]
> parse (empty <|> pure 'd') "abc"
[('d',"abc")]

其他的组合子

有了item和empty，再和顺序组合还有分支选择结合起来，可以定义许多有用的组合子了。首先定义一个判断单个字符是否满足条件的组合子sat:

1
2
3

sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then pure x else empty

使用sat可以进一步定义更多的组合子：

digit :: Parser Char
digit = sat isDigit

lower :: Parser Char
lower = sat isLower

upper :: Parser Char
upper = sat isUpper

letter :: Parser Char
letter = sat isAlpha

alphanum :: Parser Char
alphanum = sat isAlphaNum

char :: Char -> Parser Char
char x = sat (== x)

也可以定义一个消耗指定的字符串并且返回这个字符串的Parser：

str :: String -> Parser String
str []     = pure []
str (x:xs) = do char x
                str xs
                pure (x:xs)

空字符串会始终被解析成功。字符串非空的时候，只有整个字符串都被消费成功的时候才会解析成功：

> parse (string "abc") "abcdef"
[("abc","def")]
> parse (string "abc") "ab1234" 
[]

接下来的两个组合子some和many，应用Parser尽可能多次。不同的是many对应0或多次，some则需要至少一次成功的解析。例如：

> parse (many digit) "123abc" 
[("123","abc")]
> parse (many digit) "abc" 
[("","abc")]
> parse (some digit) "abc" 
[]

不过其实并不需要专门定义这两个组合子，因为已经在标准库的Alternative typeclass里面被定义过了，注意这两个函数的定义使用了互递归：

many ::f a -> f [a]
some ::f a -> f [a]
many x = some x <|> pure []
some x = pure (:) <*> x <*> many x

使用many和some可以进一步定义更多的组合子，例如「变量名」（小写字母开头紧接若干字母/数字组合）、自然数、空格……

ident :: Parser String
ident = do  x <- lower
            xs <- many alphanum
            pure (x:xs)

nat :: Parser Int
nat = do xs <- some digit
         pure (read xs :: Int)

space :: Parser ()
space = do many (sat isSpace)
           pure ()

> parse ident "abc def" 
[("abc"," def")]
> parse nat "123 abc" 
[(123," abc")]
> parse space " abc" 
[((),"abc")]

这里space用到的()通常被用来表示并不关心返回的值是什么（其实就是Unit）。

进一步的，还可以定义出代表正负整数的组合子：

int :: Parser Int
int = do char '-'
         n <- nat
         pure (-n)
     <|> nat

处理空格

实际使用中的Parser往往都需要处理空格。例如1+2和1 + 2。为了处理这种情况，需要再定义一个基本组合子来丢弃所有的空格，又叫「tokenization」^[5]：

token :: Parser a -> Parser a
token p = do space
             v <- p
             space
             pure v

用token就可以定义出具有语义的组合子：

identifier :: Parser String
identifier = token ident

natural :: Parser Int
natural = token nat

integer :: Parser Int
integer = token int

symbol :: String -> Parser String
symbol xs = token (str xs)

一个例子是一个解析非空自然数的列表的Parser，忽略所有的空格：

nats :: Parser [Int]
nats = do
        symbol "["
        n <- natural
        ns <- many (do
                        symbol ","
                        natural)
        symbol "]"
        pure (n:ns)

运行如下：

> parse nats " [1, 2, 3] "
[([1,2,3],"")]
> parse nats "[1,2,]"
[]

小结

简单的介绍了一下Monadic Parsing的基本原理。

其实这里提到的组合子也还是有一些局限性的，比如说对空格的处理很弱，也并不支持对于/* */或者//这样的注释写法。

比较好的写法是把Tokenization抽离出来，用专门的Lexer来处理这些有关字符串、空格和注释的事情，然后再把输出的[Token]流传给Parser进行解析处理。相比之下，许多之前很难实现甚至在ANTLR里都无法实现的功能，也会显得很简单了。之后会专门提到Lexer的部分。

需要注意的是，即使Monadic Parsing允许一定程度上的回溯，但是设计不好的语法（比如说有循环）还是会导致无法解析，比如说卡死在死循环里。所以实际使用的时候，还是最好先把语法变成LL(1)的。

备注

也可以用Maybe或者Either来取代[]，其中Either允许携带错误信息，当然[]也有好处：允许返回多个不同的AST，虽然这个需求并不常见。 ↩︎
实际上也不一定是字符串，可以是其他的数据类型，比如说一个[Token]，下一章会讲到。 ↩︎
也有可能会失败，这里不再重复。 ↩︎
Applicative的机制决定了如果输入太短的话Parser会失败，不需要额外的corner case的测试和排除。 ↩︎
实际上tokenization并不是这样的，有些时候文法是空格敏感的，而且用组合子来处理空格也会遇到非确定性和性能上的问题。 ↩︎

笔记

#Haskell #编译器 #Monad

从零开始的编译器前端之Monadic Parsing

http://inori.moe/2022/02/13/compiler-from-scratch-monadic-parsing/

作者

inori

发布于

2022年2月13日

许可协议

换了一个主题上一篇

从零开始的编译器前端之前置知识点下一篇