自底向上優(yōu)先分析法.ppt

1、第五章 自底向上優(yōu)先分析法,5.1 概述,原理:在采用自左向右掃描，自底向上分析的前提下，該類 分析方法是從輸入符號串入手，通過反復(fù)查找當(dāng)前句 型的句柄（最左簡單短語），并使用文法的產(chǎn)生式把 句柄歸約成相應(yīng)的非終極符來一步步地進行分析的。 最終把輸入串歸約成文法的開始符號，表明分析成功。,所以，任何自底向上分析方法的關(guān)鍵就是要找出當(dāng)前句型的句柄（或是他的變型），然后根據(jù)產(chǎn)生式判別將它歸約成什么樣的非終極符號。,下面，我們結(jié)合具體的實現(xiàn)方法，介紹在分析過程中如何來識別句柄的。我們首先介紹自底向上分析的一般過程，再介紹兩種常用的分析技術(shù)：簡單優(yōu)先分析法和LR分析方法。,一、自底向上分析的一般過程：

2、,先設(shè)置一個寄存符號的棧，稱為分析棧。其作用是用來記錄分析的歷史和指示分析的下一步動作。分析進行時，把輸入符號一個一個地按掃描順序移進棧中，當(dāng)棧頂符號形成一個句柄（即為某產(chǎn)生式的右部）時，就進行一次歸約，把棧頂構(gòu)成句柄的那個符號串用相應(yīng)的產(chǎn)生式左部符號來替換。,接著再檢查在棧頂是否又出現(xiàn)了新的句柄，則再進行歸約，直至整個輸入符號串處理完。最終如果棧頂為文法的開始符號，則所分析的輸入符號串為合法的符號串，報告分析成功,否則，是不合格的符號串，報告錯誤。,例：考慮文法G(E)：EE +T |T TT*F | F Fi| (E) 并假定輸入串為（i+i)*i，考察自底向上的分析過程。,例：考慮文法G

3、(E)：EE +T |T TT*F | F Fi| (E)并假定輸入串為（i+i)*i，考察自底向上的分析過程。,分析過程圖表：,為了具體實現(xiàn)上的方便，我們?nèi)越y(tǒng)一約定以“#”作為輸入串的左右分界符（開始和結(jié)束標志）。作為初始狀態(tài)，先將符號串的開始標志“#”壓入分析棧中，作為棧底符號，則分析過程為：,步驟 分析棧 輸入串 動作 # (i+i)*i# 移進 #( i+i)*i# 移進 #(i +i)*i# 歸約 #(F +i)*i# 歸約 #(T +i)*i# 歸約 #(E +i)*i# 移進 #(E+ i)*i# 移進 #(E+i )*i# 歸約 #(E+F )*i# 歸約,步驟 分析棧 輸入串

4、 動作 10 #(E+T )*i# 歸約 11 #(E )*i# 移進 12 #(E) *i# 歸約 13 #F *i# 歸約 14 #T *i# 移進 15 #T* i# 移進 16 #T*i # 歸約 17 #T*F # 歸約 18 #T # 歸約 19 #E # 接受,分析過程圖表：,步驟 分析棧 輸入串 動作 # (i+i)*i# 移進 #( i+i)*i# 移進 #(i +i)*i# 歸約 #(F +i)*i# 歸約 #(T +i)*i# 歸約 #(E +i)*i# 移進 #(E+ i)*i# 移進 #(E+i )*i# 歸約 #(E+F )*i# 歸約,步驟 分析棧 輸入串 動作

5、10 #(E+T )*i# 歸約 11 #(E )*i# 移進 12 #(E) *i# 歸約 13 #F *i# 歸約 14 #T *i# 移進 15 #T* i# 移進 16 #T*i # 歸約 17 #T*F # 歸約 18 #T # 歸約 19 #E # 接受,需要說明的是分析棧上的候選式不一定是句柄。例如，在第14步對棧頂為T，它是E的一候選式，但它不是句柄，不能歸約成E。判定候選式是極為簡單的事情，但判定句柄就不那么容易。而不同的自底向上方法給出不同的判定方法。,從上述例子可知，自底向上方法主要包括以下四個動作：,移進：把輸入流的頭符讀到分析棧中。,歸約：把分析棧頂?shù)木浔鷼w約為一非終

6、極符。,接受：分析成功。,報錯：處理錯誤。,5.2 簡單優(yōu)先方法,一、概述,簡單優(yōu)先方法是一種簡單直觀，廣為使用的自底向上的分析方法它是經(jīng)由算符優(yōu)先方法變化而來的。這種方法特別有利于分析表達式。,大家知道，在做算術(shù)式的四則運算時，為了保證計算過程和結(jié)果的唯一性，人們作了統(tǒng)一的四則運算規(guī)則的規(guī)定。這個法則的主要方面就是規(guī)定運算符之間的優(yōu)先順序。即先乘除后加減，同優(yōu)先級的運算符先左后右（左結(jié)合律）。還有先括號內(nèi)后括號外的規(guī)定。,而簡單優(yōu)先方法就是根據(jù)上述算術(shù)運算的計算過程而設(shè)計的一種語法分析方法。,這種方法的基本思想為：,首先規(guī)定文法符號之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后在利用這種關(guān)系，通過比較兩個相

7、鄰的符號之間的優(yōu)先順序來確定句型的“句柄”并進行歸約。,二、相鄰關(guān)系：,設(shè)Si和Sj是文法G的任意兩個符號，那么它們在句型中可相鄰出現(xiàn)的充要條件是必須滿足下列條件之一：,1、有形如 U SiSj的產(chǎn)生式,1、有形如 U SiSj的產(chǎn)生式,三、優(yōu)先關(guān)系：,為了把上述條件加以形式化，引進三種優(yōu)先關(guān)系。其定義如下：,當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式U SiSj ,當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式USiW的生產(chǎn)式，,當(dāng)且僅當(dāng)存在形如下面的產(chǎn)生式UVW的生產(chǎn)式,在實際使用這些優(yōu)先關(guān)系去識別句子時，我們希望采用同一種簡潔的方法去表示這些關(guān)系，優(yōu)先關(guān)系矩陣是一種常用的方式。,其定義為：,例：設(shè)有文法Gz：Z bMb

8、 Ma( L LMa),則可根據(jù)定義求出其優(yōu)先矩陣來（如下）,優(yōu)先關(guān)系矩陣：,Z bMb Ma( L LMa),構(gòu)造優(yōu)先矩陣的一種簡便方法：,STEP 1 對每個非終極符W求下面兩種集合：,STEP 2 對每個符號對Si,Sj填寫優(yōu)先關(guān)系矩陣元素(其中W,VVN):,四、簡單優(yōu)先文法的分析方法：,1、簡單優(yōu)先文法的定義：,定義：滿足下面兩個條件的文法稱為簡單優(yōu)先文法：,(1)任意兩個符號至多成立一種優(yōu)先關(guān)系。,(2)任意兩個產(chǎn)生式具有不同右部。,為了處理方便，引進特殊符號#，并定義 # S，S # (SVNUVT),2、簡單優(yōu)先文法的句柄,定理：設(shè)S1S2Sn是簡單優(yōu)先文法的規(guī)范句型，其子串S

9、iSi+1Sj 是滿足下列條件的最左子串：,則SiSi+1Sj定是S1S2Sn的句柄。 證明：略。,這個定理給我們提供確定句柄的一種方法。,簡單優(yōu)先文法分析算法的主要思想是找出句柄并歸納之。,而給定一個句型X，尋找它的句柄是這樣進行的：從左向右進行掃描，每次只查看兩個相鄰的文法符號，并由此得知什么時候查到句柄的尾Sj，然后再返過頭來向句型左端進行加工，仍然只查看相鄰的兩個運算符，找出句柄的頭Si。此時就可以進行歸約了。,3、分析算法的要點：,STEP 3: 用SiSi+1Sj去查產(chǎn)生式表的右部，并用相應(yīng)的左 部符號代替(歸約)句柄SiSj，若查不到，則為出錯。,STEP 4：重復(fù)上述過程，直至歸約完為止。,則從棧中退掉子串Sj1,Sj1+1,Si，并把U進棧；然后轉(zhuǎn)(2)。 若查不到轉(zhuǎn)出錯處理。,(5) 若T(j)=#,并且S棧的內(nèi)容為# Z(Z為文法開始符號)則正確停機。否則，出錯停機。,4、語法分析程序：,(1) 置初始狀態(tài)： S(1):=#, i:=1, j:=1,