编译原理消除二义性 编译原理，如何消除文法的左递归？

编译原理，如何消除文法的左递归？

1.A->Aa

2.A->Ba

B->Ab (A和B属于非终结符，a和b属于终结符)

通俗点讲：左递归就是情况1所说的“->”两边都含有同一个非终结符；

情况2所说的A->Ba中“->”后面的B 与 B->Ab中“->”前面的B是相同的非终结符

这两种情况就叫作左递归。

编译原理的消除左递归是怎么回事啊？

如果一个CFG像这样A -> AbA -> e就是有左递归，语法分析里的递归下降法和LL（1）就不能处理啦，因为程序会陷入递归而无法前进。而CFGA -> bA"A" -> bA"|e和前面一个表达的语言是一样的，但所有语法的第一项都是终结符，就消除了左递归。有消除左递归的算法，一般编译原理书上会有介绍，不是很复杂。

如何消除左递归？

将S->Aa|b代入A->Ac|Sd|ε，得A->Ac|Aad|bd|ε，然后消除直接左递归：A->bdA"|A"A"->cA"|asA"|ε所以选A

【编译原理】自顶向下LL（1）分析中，消除左递归和提取左因子的目的是什么？

通常LL(1) 是以函数递归调用来实现的

如文法: A -> A a | a

代码实现则为:

function A()

{

A()

match(" ")

Term(a)

}

这样你可以看得出死循环了吧...?

将文法消除左递归后

A -> aA"

A" -> aA"

则可以避免这一问题

提出公因式 就像楼上说的一样，避免程序回溯，消除二义性.

楼上高手啊，求搞基.

编译原理消除二义性 为什么要消除左递归 左递归和右递归

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。