左递归解析

Question

描述:

在阅读C book中的Compiler Design时,我遇到了以下规则来描述无上下文语法:

识别一个或多个语句列表的语法,每个语句都是一个后跟分号的算术表达式.语句由一系列以分号分隔的表达式组成,每个表达式包含一系列由星号(用于乘法)或加号(用于加法)分隔的数字.

这是语法:

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并用数字替换该因子.如果下一个输入符号是一个左括号,则解析器将使用Production 8.但是,Productions 5和6之间的选择无法以这种方式解决.在生产6的情况下,术语的右侧以一个因子开始,该因子以数字或左括号开始.因此,解析器希望在替换术语时应用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.

因此,我们在使用递归下降解析器时会阻止左递归生成.