編譯原理及實(shí)現(xiàn)技術(shù)：12-語法分析-自底向上的語法分析概述、簡單優(yōu)先方法

第三章：語法分析

自底向上語法分析概述

簡單優(yōu)先方法1.自底向上的語法分析例子：EE+TETTT

*FTFF(E)

Fi分析(a+t)*cETT*F(E)E+TTFtFcFa符號棧輸入流動(dòng)作#(a+t)*c#移入#(a+t)*c#移入#(a+t)*c#歸約#(E+t)*c#移入#(E+t)*c#歸約#(E+T)*c#歸約#(E)*c#移入#(E)*c#歸約.........#E#成功1.自底向上的語法分析語法分析的動(dòng)作：a.移入：把輸入流的頭符壓入分析棧b.歸約：把分析棧棧頂?shù)木浔?，用某一非終極符進(jìn)行替換c.成功d.失敗核心問題

如何確定句柄，不同的找句柄的方法構(gòu)成不同的語法分析程序2.簡單優(yōu)先方法1966年提出的，當(dāng)文法滿足某種條件時(shí)，可以用這種分析方法，但是條件比較茍刻，因此很難完整的用于整個(gè)編譯程序。但是方法本身很巧妙。優(yōu)先分析法的主要思想是，為每個(gè)符號對(X,Y)定義其在句型中的相鄰關(guān)系，并通過相鄰關(guān)系判定進(jìn)行何種分析動(dòng)作。符號相鄰：如存在形如"…XY…"的句型，則稱X和Y是可相鄰的。2.1符號相鄰定理假設(shè)X和Y是語法符號，則XY是可相鄰的當(dāng)且僅當(dāng)下面4個(gè)條件之一成立：【1】存在產(chǎn)生式形如A

…XY…【2】存在產(chǎn)生式形如A…XB…并有B?+Y……XY……XB…Y…2.1符號相鄰定理【3】存在產(chǎn)生式形如A…BY…并有B?+…X【4】存在產(chǎn)生式形如A…BC…并有B?+…X且C?+Y……BY……X…BC……XY…2.2優(yōu)先關(guān)系定義為了把符號相鄰概念更加形式化，引入、?、?三種優(yōu)先關(guān)系，其中對應(yīng)符號相鄰定理中第一條，?對應(yīng)第二條，?對應(yīng)三四條。XY：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式A…XY…X?Y：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式A…XB…并有B?+Y…X?Y：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式A…BC…并有B?+…X，C?*Y…特別假設(shè)對輸入流結(jié)束標(biāo)志'#'有：X?#；對符號棧棧底標(biāo)志'#'有：#?X；其中X為文法中任意符號2.3優(yōu)先文法若文法G滿足下面兩個(gè)條件，則稱文法G為簡單優(yōu)先文法：對于任意兩個(gè)語法符號X和Y，至多成立一種優(yōu)先關(guān)系；任意兩個(gè)產(chǎn)生式都具有不同的右部.2.4優(yōu)先文法結(jié)論優(yōu)先文法無二義性若有XY，則XY相鄰包含于句柄中若有X?Y，則有Y是句柄的頭若有X?Y，則Y是句柄的后繼符若X1…XiXi+1…Xj…Xn是一個(gè)句型，若有 Xi

?Xi+1

Xi+2

…Xj-1Xj

?Xj+1則Xi+1Xi+2…Xj-1Xj一定是該句型的簡單短語。2.5優(yōu)先關(guān)系矩陣優(yōu)先關(guān)系可以用一個(gè)矩陣來表示，稱之為優(yōu)先關(guān)系矩陣。其中:R[X,Y]=，當(dāng)XY時(shí)R[X,Y]=?，當(dāng)X?Y時(shí)R[X,Y]=?，當(dāng)X?Y時(shí)R[X,Y]=空，當(dāng)X和Y無任何關(guān)系時(shí)2.5.2優(yōu)先矩陣的構(gòu)造對每一個(gè)VN求兩個(gè)集合：FIRST(W)={S|W+S…，S(VNVT)}LAST(W)={S|W+…S，S(VNVT)}對語法符號填優(yōu)先關(guān)系若有U…SiSj…:則有Si

Sj;若有U…SiW…:則對任意SjFIRST(W),有Si?Sj若有U…VW…:則對任意SiLAST(V),Sj(FIRST(W){W})則有Si?Sj

2.5.3實(shí)例

ZbMbMaM(LLMa))a(bLMZ)a(bLMZ)a

L)bM(aa(bLMZFIRST

LAST???????????2.6語法分析算法找第一個(gè)使Sj?Sj+1的Sj從Sj開始往前(左)找第一個(gè)使Si-1?Si的Si用SiSi+1…Sj去查產(chǎn)生式的右部，并用相應(yīng)的左部符號代替句柄SiSi+1…Sj

(歸約)

。重復(fù)上述過程，直至輸入符結(jié)束。如果歸約出文法的開始符號則成功。否則失敗。2.7程序結(jié)構(gòu)StackInput#cba驅(qū)動(dòng)程序X1X2...Xn#優(yōu)先矩陣規(guī)則集例子分析b(aa)b符號棧關(guān)系輸入流

#?

b(aa)b##b?(aa)b##b(?aa)b##b(a?a)b##b(M

a)b##b(Ma)b##b(Ma)?b##b(L?b##bMb##bMb?