描述:
在阅读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
:
- 因子和期限有什么区别?使用相同的示例
- 为什么递归下降解析器不能处理左递归产生式?(解释第二个引用)。