从零开始的编译器前端之LL(1)语法与Parser Combinator

写完了Lexer（其实没有），就可以开始准备写Parser了。为了方便调试，首先用ANTLR的语法来写，这样就可以在IDEA里面使用插件来实时调试语法的正确性。

不过，ANTLR的语法属于EBNF等价的，需要首先转化为BNF语法，这样才可以进行消除左递归和提取左公因子等操作转化为LL(1)文法。

之所以要转化为LL(1)的原因，还是跟Parser Combinator的缺陷有关。实际上，作为一种递归下降解析器的实现，大部分Parser Combinator的简易实现（包括这里我实现的这个），都会在处理左递归的情况下陷入死循环。一个简单的办法就是把文法本身（尽可能）变成LL(1)的，也就是不含左递归的文法。

所谓的左递归，分为直接左递归和间接左递归。

直接就是形如 $A Aa | b $ 这样，在一个文法产生式中，左边的非终结符同时被包含在右边任意分支中作为该分支的第一个替换符号，这样的情况。

一个典型的例子是四则运算的语法：

expr:   factor | expr '+' factor;
factor: term   | factor '*' term;
term:   NUM    | '(' expr ')';

在简单的递归下降解析器里，这样的文法会在比如解析NUM的时候，不断进入expr的expr + factor这个分支然后不断跳入expr解析器中，从而产生死循环。

间接左递归则是，形如 \[ \begin{eqnarray} A \space \rightarrow \space Ba \space | \space C \\ B \space \rightarrow \space Ab \space | \space D \\ \end{eqnarray} \] 这种在多个产生式之间互相递归的情况。

ANTLR的文法可以处理直接左递归但不能处理间接左递归，所以只要能够写出一个IDEA不报错的文法，就已经消除了间接左递归了。

接下来，把ANTLR的文法转化为LL(1)大概分成这么几步：

• 把ANTLR文法转化为BNF文法
• 把转化后的BNF文法变成LL(1)的

这个网站提供了一个分析BNF文法的工具，并且可以尝试把文法转换成LL(1)的，那么接下来需要的就是把ANTLR的文法变成BNF的文法。简单说来，ANTLR的文法是在BNF的文法上增加了星号（0或多个）、加号（1或多个）、问号（0或1个）还有内联的分支（比如说a (ba | cd) e这种情况）。其实相当于EBNF文法。

把EBNF文法转化为BNF文法其实还是很简单的，可以参考这里，大致上，是这样的过程：

\[\begin{eqnarray} S ::= X \space A^? \space Y \space. &\Downarrow \\ A_1 &::= A \space | \space. \\ S &::= X \space A_1 \space Y \space . \\ \\ S ::= X \space A^+ \space Y \space. &\Downarrow \\ A_1 &::= A \space | \space A_1 \space A \space. \\ S &::= X \space A_1 \space Y \space . \\ \\ S ::= X \space A^* \space Y \space. &\Downarrow \\ A_1 &::= \space | \space A_1 \space A \space . \\ S &::= X \space A_1 \space Y \space . \\ \\ S ::= X \space (A \space C \space | \space B \space D) \space Y \space. &\Downarrow \\ U &::= A \space C \space | \space B \space D \space . \\ S &::= X \space U \space Y \space . \\ \end{eqnarray}\]

需要注意的是，这里的A+和A*转换后的A₁是左递归的。当然，这种程度的左递归还是很好处理的。之后会提到。

于是为了偷懒就简单写了个从ANTLR文法生成对应的BNF文法的转换器了：看这里（结果为了调试花的时间比手写还多，但是确实方便了不少）

另一个值得注意的地方是二元符号的左结合还有右结合。在ANTLR里面，有<assoc=right>来指明当前的产生式是右结合，手写的话，该怎么区分呢。

其实区分的方式大概是看 \(A \rightarrow B \space | \space ...\) 里面右边的到底是 \(A \space x \space B\) 还是 \(B \space x \space A\) 。左结合就是 \(A \space x \space B\) ，反之则是右结合。比如说

• 表达式 \(B \space x \space B \space x \space B \space x \space B\) 在 \(A \rightarrow B \space |\space A \space x \space B\) （左结合）情况下的生成树是 \((((B) \space x \space B) \space x \space B) \space x \space B\)。
• 而在 \(A \rightarrow B \space | \space B \space x \space A\) （右结合）情况下生成树则是 \(B \space x \space (B \space x \space (B \space x \space (B)))\)。

需要注意的是，右结合情况下的B是左公因子，左结合情况下A会形成左递归，两者都不是LL(1)。

解决方法倒也不复杂，右结合提取公因子就行了： \[ \begin{eqnarray} A ::= B \space | \space B \space x \space A \space. &\Downarrow \\ A_{factor} &::= | \space x \space A \space. \\ A &::= B \space A_{factor} \space . \\ \\ \end{eqnarray} \] 左结合的话，需要消除左递归，这里把左递归变成右递归： \[ \begin{eqnarray} A ::= B \space | \space A \space x \space B \space. &\Downarrow \\ A_{next} &::= | \space x \space B \space A_{next} \space . \\ A &::= B \space A_{next} \space . \\ \\ \end{eqnarray} \] 对于复杂的文法，可以使用前面提到的UCalgary的那个工具来做文法的处理。

并不是所有的冲突都能被修复，例如这个，在这里switch_statement后尾接一个rbrace，而一个switch_statement里面可以有多个switch_case，一个switch_case又可以尾接一个rbrace，从而导致了first set和follow set的冲突。不过这里的冲突是可以被Parser Combinator所handle的，而且实际上读入的lbrace和rbrace必须是对应的，所以这个问题其实也不严重了。

实际上，在Parser Combinator里面并不一定严格遵守LL(1)的文法的写法，在一些例如A B A B A的地方可以使用诸如sepBy1这样的组合子，对于左公因子的提取也可以就地提取而不是单独写个规则来提取。因为Parser Combinator基于回溯，可以在一定程度上处理超过LL(1)的文法。当然效率上就是另一个故事了……

Parser Combinator最大的特点大概就是可以反复使用已有的组合子去根据不同的规则去定义更复杂的组合子了。

这里稍微介绍一下几个会用到的组合子，首先是比较常见的sepBy系列：

• sepBy

  诸如a b a b a之类的0或者多个a，被b分隔

  sepBy :: Parser a -> Parser b -> Parser [a]
  sepBy p sep = sepBy1 p sep <|> pure []

• sepBy1

  类似a b a b a之类的1或者多个a，被b分隔

  sepBy1 :: Parser a -> Parser b -> Parser [a]
  sepBy1 p sep = do x <- p
                    xs <- many (sep >> p)
                    pure (x:xs)

  注意到sepBy是通过sepBy1来定义的

• sepEndBy

  sepBy后可选地紧接着一个b

  sepEndBy :: Parser a -> Parser b -> Parser [a]
  sepEndBy p sep = do xs <- sepBy p sep
                      (do _ <- sep
                          pure xs) <|> pure xs

• sepEndBy1

  sepBy1后可选地紧接着一个b，定义和前面一个基本相同

然后专门为左结合定义了一个组合子，大概的意思是，把next当成一个(a, b)的列表来处理，分别接受一个Parser a和Parser [(b, a)]后，再传入一个把b和两边的a组合起来的函数，从而生成一个a的组合子，按照这样的方式把一组由b分隔开的a「折叠」起来。

leftAssociate :: Parser a -> Parser [(b, a)] -> (b -> a -> a -> a) -> Parser a
leftAssociate beg p2 tf = do x <- beg
                             xs <- p2
                             if null xs then
                                pure x
                             else
                                let (hb, ha) = head xs in
                                let rev = reverse $ tail xs in
                                    pure $ foldl (\acc (bx, ax) -> tf bx acc ax) (tf hb x ha) rev

需要注意的是这个组合子用到了回溯的特性。

提取左公因子的方法可以参考endOptional的写法：

endOptional :: Parser a -> Parser b -> Parser a
endOptional p sep = do x <- p
                       (do sep
                           pure x)
                            <|> pure x

当然了，Parser Combinator还是有许多局限性的。最大的缺点大概就是依赖回溯了。之前篇幅里面提到的报错机制在回溯情况下会失效，因为报错内容会停止在最后一个尝试的产生式。

也就是说，比如

A: b B | c C | d D;
B: c C | d D;
C: c | d | e;
d: f | h;

在匹配任意无法匹配的表达式的时候，都会以匹配d h时候的错误报告作为返回结果。而一般情况下，会希望在读到b的时候接下来只会读c和d。

虽然有办法使得Parser Combinator不回溯，但是在这个情况下如果读到c和d会直接匹配失败，所以也不是想要的结果。如果使用try组合子的话，那就又回到开了回溯的状态了。

因为这样的原因，报错机制算是没法用了。这也是最大的一个遗憾吧。