編譯原理，如何消除文法的左遞歸？1.A->Aa2.A->BaB->Ab (A和B屬于非終結(jié)符，a和b屬于終結(jié)符)通俗點(diǎn)講：左遞歸就是情況1所說的“->”兩邊都含有同一個非終結(jié)符；情

編譯原理，如何消除文法的左遞歸？

1.A->Aa

2.A->Ba

B->Ab (A和B屬于非終結(jié)符，a和b屬于終結(jié)符)

通俗點(diǎn)講：左遞歸就是情況1所說的“->”兩邊都含有同一個非終結(jié)符；

情況2所說的A->Ba中“->”后面的B 與 B->Ab中“->”前面的B是相同的非終結(jié)符

這兩種情況就叫作左遞歸。

編譯原理的消除左遞歸是怎么回事??？

如果一個CFG像這樣A -> AbA -> e就是有左遞歸，語法分析里的遞歸下降法和LL（1）就不能處理啦，因?yàn)槌绦驎萑脒f歸而無法前進(jìn)。而CFGA -> bA"A" -> bA"|e和前面一個表達(dá)的語言是一樣的，但所有語法的第一項(xiàng)都是終結(jié)符，就消除了左遞歸。有消除左遞歸的算法，一般編譯原理書上會有介紹，不是很復(fù)雜。

如何消除左遞歸？

將S->Aa|b代入A->Ac|Sd|ε，得A->Ac|Aad|bd|ε，然后消除直接左遞歸：A->bdA"|A"A"->cA"|asA"|ε所以選A

【編譯原理】自頂向下LL（1）分析中，消除左遞歸和提取左因子的目的是什么？

通常LL(1) 是以函數(shù)遞歸調(diào)用來實(shí)現(xiàn)的

如文法: A -> A a | a

代碼實(shí)現(xiàn)則為:

function A()

{

A()

match(" ")

Term(a)

}

這樣你可以看得出死循環(huán)了吧...?

將文法消除左遞歸后

A -> aA"

A" -> aA"

則可以避免這一問題

提出公因式 就像樓上說的一樣，避免程序回溯，消除二義性.

樓上高手啊，求搞基.