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

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

2、,先設置一個寄存符號的棧，稱為分析棧。其作用是用來記錄分析的歷史和指示分析的下一步動作。分析進行時，把輸入符號一個一個地按掃描順序移進棧中，當棧頂符號形成一個句柄（即為某產生式的右部）時，就進行一次歸約，把棧頂構成句柄的那個符號串用相應的產生式左部符號來替換。,接著再檢查在棧頂是否又出現(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)上的方便，我們仍統(tǒng)一約定以“#”作為輸入串的左右分界符（開始和結束標志）。作為初始狀態(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)先方法是一種簡單直觀，廣為使用的自底向上的分析方法它是經由算符優(yōu)先方法變化而來的。這種方法特別有利于分析表達式。,大家知道，在做算術式的四則運算時，為了保證計算過程和結果的唯一性，人們作了統(tǒng)一的四則運算規(guī)則的規(guī)定。這個法則的主要方面就是規(guī)定運算符之間的優(yōu)先順序。即先乘除后加減，同優(yōu)先級的運算符先左后右（左結合律）。還有先括號內后括號外的規(guī)定。,而簡單優(yōu)先方法就是根據上述算術運算的計算過程而設計的一種語法分析方法。,這種方法的基本思想為：,首先規(guī)定文法符號之間的優(yōu)先關系和結合性質，然后在利用這種關系，通過比較兩個相

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

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

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