左递归解析

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:

factor 和 term 有什么区别？使用相同的示例
为什么递归下降解析器不能处理左递归产生式？（解释第二个引用）。

Answer 1

规则因子匹配字符串“1*3”，规则项不匹配（尽管它会匹配“(1*3)”）。本质上，每个规则代表一个优先级别。 expression 包含优先级最低的运算符，factor 次低，term 最高。如果你在学期并且想使用优先级较低的运算符，则需要添加括号。

如果您使用递归函数实现递归下降解析器，则像 a ::= b "*" c | d 这样的规则可能会像这样实现：

// Takes the entire input string and the index at which we currently are
// Returns the index after the rule was matched or throws an exception
// if the rule failed
parse_a(input, index) {
  try {
    after_b = parse_b(input, index)
    after_star = parse_string("*", input, after_b)
    after_c = parse_c(input, after_star)
    return after_c
  } catch(ParseFailure) {
    // If one of the rules b, "*" or c did not match, try d instead
    return parse_d(input, index)
  }
}

这样的事情会很好（在实践中你可能实际上不想使用递归函数，但你使用的方法仍然会表现相似）。现在，让我们考虑左递归规则 a ::= a "*" b | c 代替：

parse_a(input, index) {
  try {
    after_a = parse_a(input, index)
    after_star = parse_string("*", input, after_a)
    after_b = parse_c(input, after_star)
    return after_b
  } catch(ParseFailure) {
    // If one of the rules a, "*" or b did not match, try c instead
    return parse_c(input, index)
  }
}

现在函数 parse_a 做的第一件事是在同一索引处再次调用自身。此递归调用将再次调用自身。这将无限期地继续下去，或者更确切地说，直到堆栈溢出并且整个程序崩溃。如果我们使用更有效的方法而不是递归函数，我们实际上会得到一个无限循环而不是堆栈溢出。无论哪种方式，我们都得不到我们想要的结果。

Answer 2

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（一个数字）。同样，您可以将此方法扩展到任何级别，以得出有关术语的想法。

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

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

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

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

同样，谈论递归下降解析器，即使有回溯---当我们尝试扩展一个非终结符时，我们最终可能会发现自己再次尝试扩展同一个非终结符而没有消耗任何输入。

A-> Ab

这里，在扩充非终结符A的同时可以一直扩充成

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

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

左递归解析

Left recursion parsing

compiler-construction

recursion

parsing

recursive-descent

left-recursion

描述：

问题：