parsing - 左递归解析

Question

描述:

阅读时Compiler Design in C在书中我发现了以下规则来描述上下文无关语法:

a grammar that recognizes a list of one or more statements, each of which is an arithmetic expression followed by a semicolon. Statements are made up of a series of semicolon-delimited expressions, each comprising a series of numbers separated either by asterisks (for multiplication) or plus signs (for addition).

语法如下:

1. statements ::= expression;
2.                | expression; statements
3. expression ::= expression + term
4.                | term
5. term       ::= term * factor
6.                | factor
7. factor     ::= number
8.                | (expression)

书中指出，这种递归语法有一个重大问题。多个产生式的右侧出现在左侧，如产生式 3(此属性称为左递归)和某些解析器，例如递归下降解析器无法处理左递归产生式。它们只是永远循环。

You can understand the problem by considering how the parser decides to apply a particular production when it is replacing a non-terminal that has more than one right hand side. The simple case is evident in Productions 7 and 8. The parser can choose which production to apply when it's expanding a factor by looking at the next input symbol. If this symbol is a number, then the compiler applies Production 7 and replaces the factor with a number. If the next input symbol was an open parenthesis, the parser would use Production 8. The choice between Productions 5 and 6 cannot be solved in this way, however. In the case of Production 6, the right-hand side of term starts with a factor which, in tum, starts with either a number or left parenthesis. Consequently, the parser would like to apply Production 6 when a term is being replaced and the next input symbol is a number or left parenthesis. Production 5-the other right-hand side-starts with a term, which can start with a factor, which can start with a number or left parenthesis, and these are the same symbols that were used to choose Production 6.

<小时/>

问题:

书中的第二句话让我完全迷失了。因此，通过使用一些语句的示例(例如)5 + (7*4) + 14:

1. 因子和术语有什么区别？使用相同的示例
2. 为什么递归下降解析器不能处理左递归产生式？ (解释第二句话)。

Answer 1

1. What's the difference between factor and term? using the same example

我不会给出相同的例子，因为它不会让你清楚地了解你所怀疑的内容!

给定，

term       ::= term * factor | factor
factor     ::= number | (expression)

现在，假设我要求你找出表达式 2*3*4 中的因数和项。 现在，乘法是左结合的，将被评估为:-

(2*3)*4

如您所见，这里的项是 (2*3)，因子是 4(数字)。同样，您可以将此方法扩展到任何级别以绘制有关术语的想法。

根据给定的语法，如果给定的表达式中有一个乘法链，那么它的子部分(留下一个因子)是一个项，它又产生另一个子部分——另一个项，留下另一个单因素等。这就是表达式的求值方式。

2. Why can't a recursive-descent parser handle left-recursion productions? (Explain second quote).

你的第二句话本质上很清楚。递归下降解析器是一种自上而下的解析器，由一组相互递归过程(或非递归等效过程)构建，其中每个这样的过程通常实现语法的一个产生式。

之所以这么说，是因为很明显，如果非终结符继续向自身扩展，递归下降解析器将进入无限循环。

类似地，谈论递归下降解析器，即使有回溯——当我们尝试扩展非终端时，我们最终可能会发现自己再次尝试扩展相同的非终端而不消耗任何输入。

A-> Ab

这里，扩展非终结符A的同时可以继续扩展为

A-> AAb -> AAAb -> ... -> infinite loop of A.

因此，我们在使用递归下降解析器时防止左递归产生式。