递归下降语法分析

Question

有没有一种简单的方法来判断一个简单的语法是否适合递归下降？消除左递归和左因子分解语法是否足以实现这一点？

Answer 1

不一定。

要构建递归下降解析器(无回溯(，需要消除或解决所有预测冲突。因此，一个决定性的测试是看语法是否为LL(1(；根据定义，LL(1(语法没有预测冲突。左因子分解和左递归消除对于这项任务是必要的，但它们可能还不够，因为预测冲突可能隐藏在两个竞争的非终端后面：

list  ::= item list'
list' ::= ε 
| ';' item list'
item  ::= expr1
| expr2
expr1 ::= ID '+' ID
expr2 ::= ID '(' list ')

上面的问题(或者至少是一个问题(是，当解析器期望item而看到ID时，它不知道应该尝试expr1和expr2中的哪一个。(这是一个预测冲突：两个非终端都可以预测。(在完整的语法中，这可能是摘录自，组合两个非终端可能会困难得多。(

在一般情况下，没有算法可以将任意语法转换为LL(1(语法，甚至可以判断该语法识别的语言是否也具有LL(1，1(语法。(然而，很容易判断语法本身是否为LL(1(。(因此，总会有一些艺术和/或实验参与其中。

我认为值得补充的是，在实际的递归下降语法分析器中，您不需要真正消除左递归，因为您通常可以将其转换为while循环，而不是递归。例如，抛开上面两种expr类型的问题不谈，带有重复运算符的扩展BNF中的原始语法可能类似于

list ::= item (';' item)*

翻译成：

def parse_list():
parse_item()
while peek(';'):
match(';')
parse_item()

(省略了错误检查和AST构建。(