編譯原理及實(shí)現(xiàn)技術(shù)：9-語(yǔ)法分析-LL(1)語(yǔ)法分析

第三章：語(yǔ)法分析

LL(1)語(yǔ)法分析1.LL(1)語(yǔ)法分析原理基本思想從左到右掃描，按最左推導(dǎo)的方式推出輸入流LL(1)文法定義：

對(duì)于文法G中任一非終極符A，其任意兩個(gè)產(chǎn)生式A和A，都要滿足下面條件：

Predict(A)Predict(A)=

1.LL(1)語(yǔ)法分析原理語(yǔ)法分析的動(dòng)作

替換當(dāng)分析棧的第一個(gè)符號(hào)是VN時(shí),就要用規(guī)則進(jìn)行推導(dǎo),用規(guī)則右部將其替換

匹配分析棧第一個(gè)符號(hào)是VT時(shí),與輸入流中的第一個(gè)符號(hào)進(jìn)行匹配

成功

出錯(cuò)、失敗1.LL(1)語(yǔ)法分析原理StackInput#cba驅(qū)動(dòng)程序棧為空情形的處理XVT情形的處理XVN情形的處理X1X2...Xn#LL[1]分析表2.LL(1)分析表的構(gòu)造構(gòu)造的目的是為了讓分析更方便結(jié)構(gòu)：T：VN

VT

P{Error}

具體：T(A,t)=A

若tPredict(A)

T(A,t)=Error否則特殊的：#作為一個(gè)終極符2.LL(1)分析表的構(gòu)造【1】ETE'【2】E'+TE'【3】E'

【4】TFT'【5】T'*FT'【6】T'

【7】F(E)

【8】Fi{i,(}{+}{#,)}{i,(}{*}{+,#,)}{(}{i}i+*（）#E11E'233T44T'6566F873.1驅(qū)動(dòng)程序的設(shè)計(jì)分析的初始格局（S#,a1...an#）一般格局（X1...Xm#,ai...an#）設(shè)存在格局為（X1...Xm#,a1...an#）若X1VT&X1=a1則有（X2...Xm#,a2...an#）若X1VN則查表，若T(X1,a1)=X1,格局為（X2...Xm#,a1...an#），若T(X1,a1)=error，則報(bào)錯(cuò)。若格局為（#，#），則分析成功其他情況報(bào)錯(cuò)分析棧S輸入流T矩陣元素

E# i+i*i#T[E,i]=[1]

TE’#i+i*i#

T[T,i]=[4]FT’E’#i+i*i#T[F,i]=[8]iT’E’#i+i*i#MatchT’E’#+i*i#T[T’,+]=[6]E’#+i*i#T[E’,+]=[2]+TE’#+i*i#MatchTE’#i*i#T[T,i]=[4]FT’E’#i*i#T[F,i]=[8]iT’E’#i*i#MatchT’E’#*i#T[T’,*]=[5]*FT’E’#*i#MatchFT’E’#i#T[F,i]=[8]iT’E’#i#MatchT’E’##T[T’,#]=[6]E’##T[E’,#]=[3]##

ok3.2注意的一些問(wèn)題錯(cuò)誤的處理LL(1)方法對(duì)文法的限制假如不滿足限定：進(jìn)行文法等價(jià)變換，使其滿足我們的限定不是所有的文法都適用于該方法，有時(shí)進(jìn)行文法等價(jià)變換會(huì)破壞其可讀性通常來(lái)說(shuō)，對(duì)于高級(jí)語(yǔ)言的語(yǔ)法分析也足夠用了。判斷是否為L(zhǎng)L(1)文法S(SS'| S')|S(S|S' S'(S’)|Predict(S(SS’)={(}Predict(S)={),#}Predict(S’))={)}Predict(S’)={),#}Predict(S(S)={(}