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