資源描述：
《語法分析-自下而上分析.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第五章語法分析-自下而上分析5.1自下而上分析的基本問題Figure5.5LR演示自下而上分析i+(i+i)*i原理:自左向右掃描，自下而上分析從輸入符號串入手，通過反復(fù)查找當(dāng)前句型的可歸約串，并使用文法的產(chǎn)生式把它歸約成相應(yīng)的非終結(jié)符來一步步地進(jìn)行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。任何自下而上分析方法的關(guān)鍵就是要找出當(dāng)前句型的可歸約串，然后根據(jù)產(chǎn)生式判別將它歸約成什么樣的非終結(jié)符。規(guī)范歸約基本概念如果A=>β，則稱β是句型αβδ相對于非終結(jié)符A的直接短語。G為文法，S為開始符號，假
2、定αβδ是G的一個句型，如果則稱β是句型αβδ相對于非終結(jié)符A的短語。表達(dá)式文法的例子i+i*i,找出所有短語，直接短語和句柄最左直接短語稱為句柄。從句子到開始符號的歸約序列，如果每一步都是把句柄替換為相應(yīng)產(chǎn)生式的左部符號而得到的，則稱為規(guī)范歸約。規(guī)范歸約是最右推導(dǎo)（規(guī)范推導(dǎo)）的逆過程。例：考慮文法G(E)：E→E+T
3、T T→T*F
4、F F→i
5、(E)并假定輸入串為（i+i)*i，考察自下而上的分析過程。分析過程圖表：步驟分析棧輸入串動作#(i+i)*i#移進(jìn)#(i+i)*i#移進(jìn)#(i+i)*i#歸約
6、#(F+i)*i#歸約#(T+i)*i#歸約#(E+i)*i#移進(jìn)#(E+i)*i#移進(jìn)#(E+i)*i#歸約#(E+F)*i#歸約步驟分析棧輸入串動作10#(E+T)*i#歸約11#(E)*i#移進(jìn)12#(E)*i#歸約13#F*i#歸約14#T*i#移進(jìn)15#T*i#移進(jìn)16#T*i#歸約17#T*F#歸約18#T#歸約19#E#接受棧上的候選式不一定是句柄。例如，在第14步對棧頂為T，它是E的一候選式，但它不是句柄，不能歸約成E。判定候選式是極為簡單的事情，但判定句柄就不那么容易。而不同的自底向上方
7、法給出不同的判定方法。自下而上方法包括四個動作：移進(jìn)：把輸入流的頭符讀到分析棧中。歸約：把分析棧頂?shù)木浔鷼w約為一非終極符。接受：分析成功。報(bào)錯：處理錯誤。首先規(guī)定文法符號之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后再利用這種關(guān)系，通過比較兩個相鄰的符號之間的優(yōu)先順序來確定可歸約串。算符文法：任何產(chǎn)生式的右部都不含兩個相繼的非終結(jié)符5.2算符優(yōu)先分析例：考慮文法G(E)：E→E+T
8、T T→T*F
9、F F→i
10、(E)是否是算符文法？優(yōu)先關(guān)系：終結(jié)符ab的三種優(yōu)先關(guān)系：當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式U→…ab…或U→…aQb
11、…當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式U→…aW…的生產(chǎn)式，且有Wb…當(dāng)且僅當(dāng)存在形如U→…Vb…的產(chǎn)生式且有V…a或V…aQababab如果一個算符文法的任何終結(jié)符對至多只滿足三種關(guān)系之一，稱為算符優(yōu)先文法。驗(yàn)證終結(jié)符對之間的優(yōu)先關(guān)系(p90優(yōu)先表)例：考慮文法G(E)：E→E+T
12、T T→T*F
13、F F→i
14、(E)是否是算符優(yōu)先文法？如何從文法構(gòu)造優(yōu)先關(guān)系表？檢查文法產(chǎn)生式的每個候選，可找出所有滿足的終結(jié)符對。如何找出滿足和終結(jié)符對？對每個非終結(jié)符P構(gòu)造兩個集合FIRSTVT(P)和LASTVT(P)FIRS
15、TVT(P)=LASTVT(P)=檢查每個產(chǎn)生式候選，若形為...aP...,則對任何b∈FIRSTVT(P)，我們有ab。若形為...Pb...,則對任何a∈LASTVT(P)，我們有ab。對表達(dá)式文法的非終結(jié)符構(gòu)造FIRSTVT和LASTVT并建立優(yōu)先關(guān)系表算符優(yōu)先分析算法素短語：這樣的一個短語，它至少含一個終結(jié)符，不含比自身更小的素短語。最左素短語：句型最左邊的素短語。定理：算符優(yōu)先文法的句型#N1a1N2a2...NnanNn+1#的最左素短語是滿足如下條件的最左子串Njaj...NiaiNi+1
16、aj-1ajajaj+1...aiaiai+1演示SuanFuYouXian優(yōu)先函數(shù)利用兩個函數(shù)f和g，對每個終結(jié)符θ，映射為兩個數(shù)f(θ)和g(θ)，使得：若θ1θ2則f(θ1)g(θ2)有的關(guān)系表不存在優(yōu)先函數(shù)！對于存在優(yōu)先函數(shù)的關(guān)系表，如何構(gòu)造優(yōu)先函數(shù)？請自學(xué)p94~95優(yōu)先函數(shù)的構(gòu)造方法。5.3LR分析法1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技術(shù)。LR(K)分析是指自左向右掃描和自下而上的語法分析，且
17、在分析的每一步，只須根據(jù)分析棧中當(dāng)前已移進(jìn)和歸約出的全部文法符號，并至多再向前查看K個輸入符號，就能確定相當(dāng)于某一產(chǎn)生式右部符號的句柄是否已在分析棧的頂部形成。從而也就可以確定所應(yīng)采取的分析動作（是移進(jìn)輸入符號還是按某產(chǎn)生式進(jìn)行歸約）。當(dāng)前掃描到Xn+1,向前查看k個符號，來確定是把Xn+1移進(jìn)棧，還是把Xi…Xn作為句柄進(jìn)行歸約。1）要?dú)w約時，則根據(jù)某產(chǎn)生式U→XiXi+1…Xn進(jìn)行歸約：#X1X2…Xi-1UXn+1Xn+
