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

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 (a Python implementation of yacc) 为语法创建一个自下而上的解析器。

为了进行比较，我现在想尝试为相同的语言构建一个自上而下的递归下降解析器。我已经转换了语法，删除了左递归并应用了左因式分解：

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).

是否有此语法的 "LL" 分类（例如 LL(k)、LL(*)）？
是否可以为此文法编写递归下降解析器？那将如何完成？（需要回溯吗？）
是否可以简化此语法以简化递归下降方法？

Answer 1

语法不是具有有限前瞻性的 LL，但语言是 LL(1)，因为存在 LL(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 发明的解析策略的名称，而不是 class 语法的公认名称。）我只想说语法不是 LL(k) 对于任何 k.

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) 语法的基础。

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

Answer 2

要生成语法 LL(1)，您需要完成左因式分解 top_level。您停在：

top_level   : expression top_level1
            | term top_level2
            | NUMBER

expression 和 term 在他们的第一个集合中都有 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

请注意，这仍然不是 LL(1)，因为存在具有重叠的 FIRST 和 FOLLOW 集的 epsilon 规则 (term1, expression1)。因此，您也需要将这些因素排除在外，使其成为 LL(1)

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

Is it possible to write a recursive-descent parser for this grammar?

grammar

parsing

context-free-grammar

ll

lr