左递归分析

Question

描述：

在阅读C书中的编译器设计时，我遇到了以下规则来描述上下文无关语法：

识别一个或多个语句列表的语法，每个语句其是后跟分号的算术表达式。报表由一系列分号分隔的表达式，每个表达式都包含一系列数字用星号(表示乘法(或加号(表示加法(分隔。

语法如下：

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

这本书指出这种递归语法有一个主要问题。几个乘积的右手边出现在左手边，如乘积3(此属性称为左递归(，某些解析器(如递归下降解析器(无法处理左递归乘积。它们只是永远循环。

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

---

问题：

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

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

Answer 1

1. 因子和术语之间有什么区别？使用相同的示例

我不是在举同样的例子，因为它不会让你清楚地了解你所怀疑的事情！

给定

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

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

(2*3)*4

正如你所看到的，这里(2*3(是项，因子是4(一个数字(。同样，你可以将这种方法扩展到任何级别，以得出关于术语的想法。

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

2. 为什么递归下降解析器不能处理左递归生成？(解释第二句话(

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

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

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

A-> Ab

这里，在扩展非终端A的同时，可以继续扩展到

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

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

Answer 2

1. 规则因子与字符串"1*3"匹配，但规则项不匹配(尽管它将与"(1*3("匹配(。从本质上讲，每条规则代表一个优先级。expression包含优先级最低的运算符，factor次低，term最高。如果您在术语中，并且希望使用优先级较低的运算符，则需要添加括号。

2. 如果您使用递归函数实现递归下降解析器，那么像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所做的第一件事就是在同一索引处再次调用自己。此递归调用将再次调用自身。这种情况将无限期地持续下去，或者更确切地说，直到堆栈溢出，整个程序崩溃。如果我们使用更有效的方法而不是递归函数，我们实际上会得到一个无限循环，而不是堆栈溢出。不管怎样，我们都得不到我们想要的结果。