这个语法可以编写递归下降解析器吗？

Question

从这个问题中，涉及二元运算符（+ - * /）的表达式语法不允许使用外层括号：

top_level   : expression PLUS term
            | expression MINUS term
            | term TIMES factor
            | term DIVIDE factor
            | NUMBER
expression  : expression PLUS term
            | expression MINUS term
            | term
term        : term TIMES factor
            | term DIVIDE factor
            | factor
factor      : NUMBER
            | LPAREN expression RPAREN

这个语法是LALR(1)。因此我能够使用PLY（yacc的Python实现）为该语法创建自底向上的解析器。

为了比较，现在我想尝试为同一语言构建一个自顶向下的递归下降解析器。我已经转换了语法，消除了左递归并应用了左公因式化方法：

top_level   : expression top_level1
            | term top_level2
            | NUMBER
top_level1  : PLUS term
            | MINUS term
top_level2  : TIMES factor
            | DIVIDE factor
expression  : term expression1
expression1 : PLUS term expression1
            | MINUS term expression1
            | empty
term        : factor term1
term1       : TIMES factor term1
            | DIVIDE factor term1
            | empty
factor      : NUMBER
            | LPAREN expression RPAREN

没有top_level规则时，这个语法是LL(1)的，因此编写递归下降解析器将会相当简单。不幸的是，包括top_level，这个语法不是LL(1)。

1. 这个语法是否有"LL"分类（例如LL(k), LL(*)）？
2. 是否可能为这个语法编写递归下降解析器？如何实现？（需要回溯吗？）
3. 是否可能简化这个语法以便于递归下降方法？

- user200783

Answer 1

语法不具有有限向前查看的LL分类，但是由于存在LL(1)语法，因此该语言是LL(1)。从实用角度来看，即使不修改语法，递归下降解析器也很容易编写。

1. 这个语法是否有“LL”分类（例如LL(k)，LL(*)）？

如果α是表达式的派生，β是项的派生，γ是因子的派生，则top_level可以派生出句子(α)+β和句子(α)*γ（但它无法派生句子(α)）。然而，(α)是expression和term的可能派生，因此在遇到)后面的符号之前，无法决定使用top_level的哪个产生式。由于α的长度可以任意，因此没有k足以区分这两个产生式的前瞻。有些人可能称其为LL(∞)，但我认为这不是一个非常有用的语法类别。（LL(*)是Terence Parr发明的一种解析策略的名称，不是一类语法的公认名称。）我只会说这个语法不是LL(k)的任何k。

2. 是否可以为这个语法编写递归下降解析器？该如何做？（需要回溯吗？）

当第一个符号为NUMBER或(时，必须预测（调用）expression。如果它是NUMBER，我们预测（调用）expression。如果是(，则消耗它，调用expression，消耗后面的)（或者如果下一个符号不是右括号，则声明错误），然后根据下一个符号调用expression1或term1和expression1。同样，如果下一个符号与expression1或term1的FIRST集不匹配，则声明语法错误。请注意，上述策略根本不需要使用top_level*产生式。

由于这显然可以在不回溯的情况下工作，因此可以作为编写LL(1)语法的基础。

3. 是否可能简化此语法以便于递归下降方法？

我不确定以下语法是否更简单，但它与上面描述的递归下降解析器相对应。

top_level   : NUMBER optional_expression_or_term_1
            | LPAREN expression RPAREN expression_or_term_1
optional_expression_or_term_1: empty
            | expression_or_term_1
expression_or_term_1
            : PLUS term expression1
            | MINUS term expression1
            | TIMES factor term1 expression1
            | DIVIDE factor term1 expression1
expression  : term expression1
expression1 : PLUS term expression1
            | MINUS term expression1
            | empty
term        : factor term1
term1       : TIMES factor term1
            | DIVIDE factor term1
            | empty
factor      : NUMBER
            | LPAREN expression RPAREN

---

我有两个观察，你完全可以忽略其中的第二个（尤其是第二个，因为它是100％的个人意见）。

第一个观察是，禁止(1+2)，但允许(((1)))+2或((1+2))+3，对我来说似乎有些奇怪。但毫无疑问您有自己的理由。（当然，您可以通过在factor的第二个产生式中将expression替换为top_level来轻松地禁止多余的双括号。

其次，对我来说，在第三部分的LL（1）语法中涉及的跳跃操作似乎只是再次询问为什么有任何理由使用LL语法的一个原因。LR（1）语法更易于阅读，并且其与语言的语法结构的对应关系更清晰。生成的递归下降解析器的逻辑可能更容易理解，但对我来说，这似乎是次要的。

- rici

---

有另一种简单的方法可以拒绝（...），基于这样一个观察结果：任何一种语言的有用语法都必须至少接受该语言，并且可能接受更多（很难做到完美）。因此，我们通常使用解析器来“接受（稍微）过多的内容，并拒绝多余的内容”（通过使用解析器外部的某些机制）。现在拒绝解析（...）变得很容易：使用允许它的简单语法进行解析，并拒绝任何具有（...）的解析。 - Ira Baxter

在你的最终语法中，expression_or_term1 -> expression1 -> empty，因此 top_level -> '(' expression ')'，这不是原始语法中的内容... - Chris Dodd

@chrisdodd：发现得好。这也造成了歧义。我会修复它，但不会很美观。 - rici

非常感谢您提供这个详尽的答案！以下是我的几点想法：

1. 感谢您确认了我“语法对于任何k都不是LL(k)” 的猜测。
2. 您的递归下降解析器似乎等同于使用“expression: LPAREN expression RPAREN term1 expression1”来处理初始的“（”，并最终断言“term1”和“expression1”不会同时为空。这似乎与Ira Baxter建议的将整个输入解析为“expression”，并最终断言没有外部括号的方法非常相似。两种方法都“接受了稍微多一些，而拒绝了多余的”。

- user200783

@paul：由于LALR解析器是为我生成的，它的简单性或复杂性并不重要。（我也不会根据生成代码的可理解性来选择编译器。）与您特定的问题无关，我认为LL语法较差。f: t | t '+' f 捕获了算术语法的语法和语义； f: t f'; f': | '+' f'则没有。 - rici

Answer 2

为使语法成为LL(1)，需要完成左因子分解top_level。你的停止点是：

top_level   : expression top_level1
            | term top_level2
            | NUMBER

expression和term的FIRST集合中都有NUMBER，因此必须先进行左因子分解：

top_level   : NUMBER term1 expression1 top_level1
            | NUMBER term1 top_level2
            | NUMBER
            | LPAREN expression RPAREN term1 expression1 top_level1
            | LPAREN expression RPAREN term1 top_level2

然后您可以将其左因式分解为

top_level   : NUMBER term1 top_level3
            | LPAREN expression RPAREN term1 top_level4

top_level3  : expression1 top_level1
            | top_level2
            | empty

top_level4  : expression1 top_level1
            | top_level2

请注意，由于存在具有重叠FIRST和FOLLOW集的epsilon规则（term1，expression1），因此仍然不是LL（1）。 因此，您需要将它们分解以使其成为LL（1）。

- Chris Dodd

---

谢谢。看起来，如果左因子分解稍微不同（使得top_level3和top_level4都以term1开头），进一步的转换将导致由rici给出的LL(1)语法（top_level3变为optional_expression_or_term_1，top_level4变为expression_or_term_1）。 - user200783