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

第三章：語法分析

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

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

Predict(A)Predict(A)=

1.LL(1)語法分析原理語法分析的動作

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

匹配分析棧第一個符號是VT時,與輸入流中的第一個符號進行匹配

成功

出錯、失敗1.LL(1)語法分析原理StackInput#cba驅(qū)動程序棧為空情形的處理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否則特殊的：#作為一個終極符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ū)動程序的設(shè)計分析的初始格局（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，則報錯。若格局為（#，#），則分析成功其他情況報錯分析棧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注意的一些問題錯誤的處理LL(1)方法對文法的限制假如不滿足限定：進行文法等價變換，使其滿足我們的限定不是所有的文法都適用于該方法，有時進行文法等價變換會破壞其可讀性通常來說，對于高級語言的語法分析也足夠用了。判斷是否為LL(1)文法S(SS'| S')|S(S|S' S'(S’)|Predict(S(SS’)={(}Predict(S)={),#}Predict(S’))={)}Predict(S’)={),#}Predict(S(S)={(}