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

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

1.A->Aa

2.A->Ba

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

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

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

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

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

如果一個(gè)CFG像這樣A -> AbA -> e就是有左遞歸，語(yǔ)法分析里的遞歸下降法和LL（1）就不能處理啦，因?yàn)槌绦驎?huì)陷入遞歸而無(wú)法前進(jìn)。而CFGA -> bA"A" -> bA"|e和前面一個(gè)表達(dá)的語(yǔ)言是一樣的，但所有語(yǔ)法的第一項(xiàng)都是終結(jié)符，就消除了左遞歸。有消除左遞歸的算法，一般編譯原理書上會(huì)有介紹，不是很復(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)用來(lái)實(shí)現(xiàn)的

如文法: A -> A a | a

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

function A()

{

A()

match(" ")

Term(a)

}

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

將文法消除左遞歸后

A -> aA"

A" -> aA"

則可以避免這一問(wèn)題

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

樓上高手啊，求搞基.