parsing - 是否可以为此语法编写递归下降解析器？

Question

来自 this 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. 是否可以简化此语法以简化递归下降方法？

Answer 1

文法不是有限前瞻的 LL，但语言是 LL(1)，因为存在 LL(1) 文法。从实用的角度来说，即使不修改语法，递归下降解析器也很容易编写。

1. Is there an "LL" classification for this grammar (e.g. LL(k), LL(*))?

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

2. Is it possible to write a recursive-descent parser for this grammar? How would that be done? (Is backtracking required?)

当然。甚至没有那么难。

第一个符号必须是 NUMBER 或 (。如果它是 NUMBER，我们预测(调用) expression。如果是(，我们消费它，调用expression，消费后面的)(或者声明错误，如果下一个符号不是右括号)，然后调用 expression1 或 term1，然后调用 expression1，具体取决于下一个符号是什么。同样，如果下一个符号与 expression1 或 term1 的第一组不匹配，我们将声明语法错误。请注意，上述策略不需要 top_level* 作品。

由于这显然不需要回溯就可以工作，因此它可以作为编写 LL(1) 语法的基础。

3. Is it possible to simplify this grammar to ease the recursive-descent approach?

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

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)文法更易读，与语言句法结构的对应更清晰。生成的递归下降解析器的逻辑可能更容易理解，但对我来说这似乎是次要的。