parsing - 左递归解析

Question

描述：

在阅读Compiler Design in C book 时，我遇到了以下描述上下文无关语法的规则：

一种语法，它识别一个或多个语句的列表，每个语句都是一个算术表达式，后跟一个分号。语句由一系列以分号分隔的表达式组成，每个表达式都包含一系列由星号（用于乘法）或加号（用于加法）分隔的数字。

这是语法：

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

该书指出，这种递归语法有一个主要问题。几个产生式的右侧出现在左侧，如产生式 3 中（并且此属性称为左递归），并且某些解析器（例如递归下降解析器）无法处理左递归产生式。他们只是永远循环。

您可以通过考虑解析器在替换具有多个右手边的非终端时如何决定应用特定产生式来理解问题。简单的情况在产生式 7 和 8 中很明显。解析器可以通过查看下一个输入符号来选择在扩展因子时应用哪个产生式。如果此符号是数字，则编译器将应用 Production 7 并用数字替换因子。如果下一个输入符号是一个左括号，则解析器将使用产生式 8。但是，无法通过这种方式解决产生式 5 和 6 之间的选择。在产生式 6 的情况下，术语的右侧以一个因子开头，而该因子又以一个数字或左括号开头。最后，当一个术语被替换并且下一个输入符号是一个数字或左括号时，解析器希望应用 Production 6。生产 5 - 另一个右手边 - 以一个术语开始，它可以以一个因子开始，它可以以数字或左括号开始，这些符号与用于选择生产 6 的符号相同。

问题：

这本书的第二句话让我完全迷失了。因此，通过使用一些语句的示例作为（例如）5 + (7*4) + 14：

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

score 5 · Accepted Answer

因子和期限有什么区别？使用相同的示例

我没有给出相同的例子，因为它不会让你清楚地了解你有什么疑问！

鉴于，

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

现在，假设我让你找出表达式 2*3*4 中的因子和项。现在，乘法保持关联，将被评估为：-

(2*3)*4

如您所见，这里 (2*3) 是项，因子是 4（一个数字）。同样，您可以将此方法扩展到任何级别以得出有关术语的概念。

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

为什么递归下降解析器不能处理左递归产生式？（解释第二个引用）。

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

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

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

A-> Ab

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

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

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

score 3 · Accepted Answer

规则因子匹配字符串“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所做的第一件事就是在同一索引处再次调用自己。这个递归调用将再次调用它自己。这将无限期地继续下去，或者更确切地说，直到堆栈溢出并且整个程序崩溃为止。如果我们使用更有效的方法而不是递归函数，我们实际上会得到一个无限循环而不是堆栈溢出。无论哪种方式，我们都没有得到我们想要的结果。

parsing - 左递归解析

描述：

问题：

2 回答 2

Related

Reference