第六章自底向上優先分析法

?自底向上優先分析思想概述

?簡單優先分析法

?優先關系的含義

?簡單優先文法的定義及操作步驟

?算符優先分析法

?算符優先分析法的定義

?算符優先關系表的構造

?優先函數

學習目標

?算符優先分析法是自下而上（自底向上）語法分析的一種，尤其

適應于表達式的語法分析，由于它的算法簡單直觀易于理解，因

此，也是學習其它自下而上語法分析的基礎。通過本章學習應掌

握：

?對給定的文法能夠判斷該文法是否是算符文法

?對給定的算符文法能夠判斷該文法是否是算符優先文法

?對給定的算符文法能構造算符優先關系表，并能利用算符優先關

系表判斷該文法是否是算符優先文法。

?能應用算符優先分析算法對給定的輸入串進行移進■歸約分析，

在分析的每一步能確定當前應移進還是歸約，并能判斷所給的輸

入串是否是該文法的句子。

?了解算符優先分析法的優缺點和實際應用中的局限性。

知識點

?算符優先分析法的算法簡單、直觀、易于理解，所以通常作為學

習其它自下而上語法分析的基礎。

?需復習有關語法分析的知識有：什么是語言、文法、句子、句型、

短語、簡單短語、句柄、最右推導、規范歸約基本概念。

?本章重難點

?算符文法的形式。

?對一個給定的算符文法能構造算符優先關系分析表，并能判別所

給文法是否為算符優先文法。

?分清規范句型的句柄和最左素短語的區別，進而分清算符優先歸

約和規范歸約的區別。（在分析過程中如何尋找可歸約串）

?對一個給定的輸入串能應用算符優先關系分析表給出分析（歸約）

步驟，并最終判斷所給輸入串是否為該文法的句子。

語法分析

?推導——自頂向下的語法分析過程

?預測分析程序，遞歸下降分析法(最左推導)

?要求文法是LL(1)文法

?歸約——自底向上的語法分析過程

?簡單優先分析法，算符優先分析法

?LR分析法

自底向上的語法分析過程思想::

?自底向上語法分析過程是一個最左歸約的過程

（規范推導的逆過程，亦稱規范歸約），從輸入

串開始，朝著文法的開始符號進行歸約，直到

到達文法的開始符號為止的過程。

?輸入串在這里依然是指從詞法分析器送來的單詞符

號組成的二元式的有限序列。

?自底向上的下推自動機PDA

?工作方式：“移進-歸約”方式

?對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后

進先出棧中，在移進過程中不斷查看棧頂符號串，一旦串形成

某個句型的句柄時（該句柄對應某產生式的右部），就用該產生

式的左部非終結符代替相應右部的文法符號串（歸約）。重復這

一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，

也就確認輸入串是文法的句子。

?棧頂符號串是指：該符號串包含棧頂符號在內，并由棧中某個

符號為該符號串的頭，棧頂符號為該符號串的尾，也可以只包

含一個符號。

?幾點說明：

?初態時，棧內僅有棧底符號“毋，讀頭指在最左以

的單詞符號上。

即初態為：棧輸入

#W#

語法分析執行的動作：

?移進讀入一個單詞并壓入棧內，讀頭后移；

?歸約檢查棧頂若干符號能否進行歸約，若能，就以產

生式左部替代該符號串，同時輸出產生式編號；

?識別成功移進-歸約的結局是棧內只剩下棧底符號和文

法開始符號，讀頭也指向語句的結束符；

即:直至最終形成如下格局：

標輸入

#S#

?識別失敗

例6.1文法G[S]產生式如下：

①S—aAcBe②A—b③A—Ab(4

B->d

輸入串abbcde是不是文法的句子？

SnaABenaAdenaAbcdenabbcde

S

naAcBe

naAcde

naAbcde

nabbcde

b

G[s]：①S—aAcBe②A—b③A->Ab④B—d

步驟棧輸入動作輸出帶

(1)#abbcde#移進

(2)#abbcde#移進

(3)#abbcde#歸約，A-b2

(4)粕Abcde#移進

(5)粕Ab[A—b?cde#歸約，A-Ab2,3

(6)#aAIA>/\b?cde#移進

(7)#aAcde#移進

(8)粕Acde#歸約，B-d2,3,4

(9)粕AcBe#移進

(10)#aAcBe#歸約，SfaAcBe2,3,4,1

(11)#S*接受

沒有語法樹的提示，如何分析，如何歸約？

1.優先分析器：簡單優先分析法；算符優先分析

法。

2.LR分析器

6.1自底向上優先分析思想

優先分析法可分為簡單優先分析法和算符優先分析法。

?簡單優先分析法是對一個文法按一定原則求出該文法所有符號

（V集）之間的優先關系，按照這種關系確定歸約過程中的句柄，

實際上，是一種規范歸約。

?算符優先分析法的基本思想只考慮算符之間的優先關系，在歸

約過程中，只要找到可歸約串就歸約，不考慮其是否為句柄，

因此，算符優先歸約不是規范歸約。

優先分析法基本思想

1.相鄰文法符號之間的優先關系

在句型中，句柄內各相鄰符號之間具有相同的優先級。相同優先級

用'工”表示。

由于句柄要先歸約，所以規定句柄兩端符號的優先級要比位于句柄

之外的相鄰符號的優先級高。優先級低于表示為：優先級高

于表示為：

某句型中：M…NgV,Nj工...丁Nj…4

N^..Nj.^-Nj......Nj->Nj+1...Nn

2.句型中Nj……Nj是句柄，語法分析程序可以通過尋找

岫.產?岫和這兩個關系來確定句柄的頭尾，從

而確定句柄進行歸約。

型吟"G[S]：S—>aBeB—>bc

abce#bee#

6.2簡單優先分析法：：

?定義

?一個文法G,如果它不含￡產生式,也不含任何右部

相同的不同產生式,并且它的任何符號對(X,Y),

X,Y￡V或者沒有關系，或者存在優先級相同或低于、

高于等關系之一，則這是一個簡單優先文法。

?優先級的定義

?XY當且僅當G中含有形如P一…XY…

?X=Y當且僅當G中含有形如P—…XQ…，且Q+Y-

?X->Y當且僅當G中含有形如P—…QR…，且=>

Q-X,RY-(YeFIRST(R)),YeVTo

例6.2有文法G：S—bAb：：

A—(B|a：：

B—Aa)

解析根據優先級的定義，由文法產生式可求得

文法符號之間的優先關系如下：

1,求工關系：b=A,A=b,(三B,A=a,a=)

2,求v?關系：b<-(,b<-a,(<-A...

3.求:關系：)->b,a->b,),>a,a>a,B->a...

?關于"#”的說明：

?通常把讀頭下待分析的句子放在一對#的中間，小

志了句子的開始和結束。

■母子的開工*4旬子的結

始符號#..........#束符號

?對任何x,若文法開始符號S與x…,貝I」#v?x,若有

S當■???x,則x>#

#<■X..............X>>#

?為句子的開始符號、終結符號和句中符號添加優先

關系，使句子易于被識別處理。

?簡單優先分析的思想

?簡單優先矩陣：根據優先關系的定義，將文法中各文法符號

之間的這種關系用一矩陣表示，稱作簡單優先矩陣。

?PDA讀入一個單詞后，比較棧頂符號和該單詞的優先級，若

棧頂符號優先級低于該單詞，繼續讀入；若棧頂符號優先級

高于或等于讀入符號，則找句柄進行歸約，找不到句柄就繼

續讀入。直到最后棧內只剩下開始符號，輸入串讀到“#"為

止，此時識別正確。

?簡單優先分析法的優缺點

?優點：技術簡單

?缺點：適用范圍小；分析表尺寸過大。

6.3算符優先分析法

?算符優先分析的基本思想

?所謂算符優先分析法是仿效四則運算的計算過程而構造的一

種語法分析過程.

?特點

?簡單直觀，特別適用于表達式分析,易于手工實現，是自底向上

的歸約過程，但可歸約串不一定是規范句型的句柄，所以算

符優先歸約不是規范歸約。

?關鍵

?分析表只規定算符（廣義為終結符）之間的優先關系，也就是

只考慮終結符之間的優先關系及結合性質，不考慮非終結符

之間的優先關系。

?例如，30*40-10+20的運算

G[E]:E^E+E|E-E|E*E|E/E|ETE|(E)|-E|id

?由于該文法是一個二義文法，它的句子往往有不同的規范推導和

歸約，實際運算會得到不同結果，但按傳統的習慣規定優先級和

結合律進行歸約，優先級從高到低為：乘幕運算符，乘、除運算符

力口、減運算符；同級運算符服從左結合原則；有括號時，先括號

內后括號外。

?則文法的句子id+id—id*(id+id)的歸約過程為：

(1)id+id-id*(id+id)設算數級別最高，最先歸約

(2)E+id-id*(id+id)

(3)E+E-id*(id+id)十,■同級，先歸約左邊十號

(4)E-id*(id+id)

(5)E-E*(id+id)?，*不同級，先歸約右邊的*

(6)E-E*(E+id)

⑺E-E*(E+E)先算括號內，在算括號外

(8)E—E*(E)

(9)E-E*E先歸約*,在歸約十

(10)E-E

(11)E

1.這個歸約過程是唯一的，運算結果亦是唯一的。

2.上述歸約過程中起決定作用的是相鄰兩個終結符號之間的優先關系

一旦確定了這種優先關系，就可以借助這種關系去尋找可歸約串并

進行歸約。

?因此，算符優先分析法的關鍵是比較兩個相繼出現的終結

符的優先級而決定應采取的動作。

?需完成運算符間優先級的比較，可以先定義各種可能相繼出

現的運算符的優先級并表示為矩陣的形式，使得能夠在分析

中通過查詢矩陣元素而得到算符之間的優先關系。

?對于任何兩個可能相繼出現的終結符號a與b,若具有以下

形式”…ab…”或“…aQb…”，其中Q為某非終結符，則a,b

之間的關系為：

?a<-b表示a的優先級低于b

?a=b表示a的優先級等于b

?a->b表示a的優先級大于b

?若a,b在任何情況下不可能相繼出現，貝Ua,b無關系

表6.2優先關系表

+?*/id)#

+?>?><?<?<?<?<??>?>

??>?><?<?<?<?<??>?>

*?>?>?>?><?<?<??>?>

/?>?>?>?><?<?<??>?>

?>?>?>?><?<-<??>?>

id?>?>?>?>?>?>?>

1r<?<?<?<?<?<?<?—

)?>?>?>?>?>?>?>

#<?<-<?<?<-<?<-

說明：

?上述表滿足通常數學上的習慣約定，且附加一條約定：運算量

id的優先級高于算符。

?語句開始符號和結束符號“鏟與終結符相繼出現時，應該有

或以此保證語句先歸約。

?(二)表示括號是成對歸約的。

?算術關系二”和“〉”與優先關系具有十分不同的性質。例

如，并不一定意味著b>a,例如：+<-(,(<-+o終結

符所處的左右位置很重要。

?決定優先關系方法：

(a)直觀方法：代數規則；

(b)對于一個無二義性文法，有機械方法。

?直觀算符分析法對下推自動機的改進

?添加了一個下推棧：一個用于放操作數和運算結果；

一個用于放操作符（包括執括號）。

?算法概要

初始化（OPND='，QPTR=#，讀頭指向輸入串第一個符號）

讀入符號到sym,若sym是運算數，則入OPND棧，讀頭下移，若sym是符

號則查表比較OPTR棧頂6與sym的優先級：

當OPTR棧頂符號9二'（'andsym='）',6彈出，讀頭下移；

當遇到可歸約串時（即OPTR棧頂符號串與讀頭下符號形成了一對＜?????＞）,

OPND彈出棧頂兩個元素g、TT2,OPTR彈出棧頂元素&將口華改的結果入

OPND棧，繼續讀下一個符號，直到OPTR棧底的‘#’遇到讀頭下的

分析完畢。

a+b……#添加一個下推棧的原因：

+i)*i#

推"----------直觀算符優先控制

棧0------------------------------

"優先表（=,＜）E

(

OPND#+

E

OPTR把

例如，改進的PDA,句子a+b*c#的直觀算符優先分析過程。

a+b*c#a+b*c#a+b*c#

initial#<?++<?*+<***?>#

a+b*c#

OPTR棧只剩一個#,

讀頭亦只剩一個#,

分析結束，

T2即是運算結果。

Tl=b*cT2=a+Tl

?直觀算符分析法的優缺點

?優點

簡單明了，易于手工實現，適于分析各種算術表達式

使用此算法可以很方便的把表達式翻譯成目標指令，只要在歸約

時把計算口力取值改成相應指令（&3,叫，丁）即可。

?缺點

算法采用兩個下推棧，有時會將錯誤句子識別成合法句子，并且，

無法指出輸入串中出錯位置。

對于含有單目運算符的算術表達式不便處理

■比如負號，由于負號的優先級高于加減法，低于乘除法，但負號的形式

與減號相同，不容易識別。

分析句子：i[i2+i3*+i4分析句子:甲2+++++

回3*乜#用2+++++#

2"Tl=i+ii

T3=i4+T22

1+-

#

?以上介紹的是直觀算符優先分析法，僅僅是為了易于理解算符

優先分析法的概念。

?直觀算符優先分析法的關鍵是對一個給定文法G,人為地規定

其算符的優先順序，即給出優先級別和同一個級別中的結合

注質。

?仍需要討論的問題是：任意給定的一個文法如何按形式算法

的規則計算算符之間的優先關系。

定義6.1設有一文法G,如果G中沒有形如A->g或形如A-...BC…的產

生式，其中B和C為非終結符，則稱G為算符文法(Operater

Grammar：也稱0G文法。

>理解：即算符文法G中沒有右部為￡或右部具有相鄰非終結符號的產

生式。

>例如：表達式文法E-E+E|E*E|(E)|i,其中任何一個產生式

中都不包含兩個非終結符相鄰的情況，因此該文法是算符文

法。

>又例：E->EAE|(E)|-E|idA—+|—1*|/|T不是算符文法，

因右部EAE具有相鄰的非終結符號。

>算符文法保證了兩個運算符之間只有一個操作數。

定義6.2設G是一個不含8產生式的算符文法，a和b

是任意兩個終結符，A、B、C是非終結符，算符優

先關系三、?>、v?定義如下：

?az：b當且僅當G中含有形如A一…ab…或A—>…aBb…

的產生式

?av?b當且僅當G中含有形如A一…aB…的產生式，且

B與b...或B當Cb...

?a?>b當且僅當G中含有形如A一…Bb…的產生式，且

...a或...aC

定義6.3設有一不含w產生式的算符文法G,如果對

任意兩個終結符對(a,b)之間至多只有IZ?和v?三種

關系中的?種成立，則稱G是一個算符優先文法

(OperatorPrecedenceGrammar),即OPG文法。

?算符優先文法是無二義性的。

(a)a^zb(b)a<-b(c)a?〉b

①amb則存在語法子樹如圖（a）

其中b為E或為B,這樣a,b在同一句柄中同時歸約所以優先級相同。

②avb則存在語法子樹如圖（b）

其中b為z或為C。a,b不在同一句柄中，b先歸約，所以a的優先級低于b。

③a>b則存在語法子樹如圖（c）。

其中6為￡或為C,a、b不在同一句柄中，a先歸約，所以a的優先性大于b。

算符優先關系表的構造r

??

?0G和OPG定義的意義

?這兩個定義相當于對文法的句型和可歸約的短語做了如下

規定：

?設A〔A?…AgAA+1…An是文法G的一個句型，

?若A]￡VN，則Ag,Ai+1eVT,即不允許出現相繼兩個非終

結符；

?若B〔B2…Bm是當前可歸約短語，并可歸約為Aj,則

B1B2…Bm中不能相繼出現兩個非終結符，且相鄰的終結符

優先級全相等；

對于B1B2…Bm中首終結符b有AgV?b

對于以B2…Bm中的尾終結符b有b>Aj+i

?實際上，可歸約短語是某產生式右部符號串，所以通過檢

查G的每個產生式的候選式可以查找出任意優先級相同的終

結符序偶對；要找出滿足v?關系和》關系的終結符序偶，就

要找出各非終結符Ai的首終結符集和尾終結符集。

構造過程::

?求各非終結符的首終結符集和尾終結符集：??

?FIRSTVT(B尸{b|B多b…或B與Cb…}

?LASTVT(B尸但舊二…a或Bm…aC}

?則算符文法中任何兩個終結符對(a,b)之間的優先關系,

其算法依據如下：

?三關系

?可直接查看產生式的右部，對如下形式的產生式

A一…ab…，Af..aBb…，有a=b成立。

?v?關系

?求出每個非終結符B的FIRSTVT(B),在如下形式的產生式

A一…aB…中，對每一b￡FIRSTVT(B),有b成立。

?＞關系

?計算每個非終結符B的LASTVT(B),在如下形式的產生式

A—…Bb…中，對每一a￡LASTVT(B),有a〉b成立。

由定義6.2可有如下推論：

a)若有產生式A-a..,或A->Ba.?.，則a^FIRSTVT(A),其中A、B

為非終結符，a為終結符。

b)若a￡FIRSTVT(B)且有產生式ATB…，則有a￡FIRSTVT(A)。

例設文法G的產生式為：

S->aAcBeA->.Bb

右

A—bB—dabcde

(1)計算每個非終結符的左

FIRSTVT與LASTVT；a

(2)計算所有終結符之間的關系

(優先關系表)。b

解析FIRSTVT(S)={a}c

FIRSTVT(A)={b}

FIRSTVT(B)=scgxv1td

LASTVT(S)={e}e

LASTVT(A)={b}

LASTVT(B)=mak41og

構造算法

1.構造集合FIRSTVT(P)的算法

?依據：定義和推論

1)若有產生式A-a??,或A—Ba.?.，則a@FIRSTVT(A),其中A、

BeVN,aeVT

2)若a￡FIRSTVT(B)且有產生式A—B…，則有

aeFIRSTVT(A).

?注：規則1是求A的首終結符a的關系；規則2是求A與產生式中

開頭的非終結符B之間的關系。

?兩個數據結構

?二維布爾矩陣F.行標為非終結符A,列標為終結符a；F[A,a]=true,

當且僅當a￡FIRSTVT(A)。

棧STACK棧中動態存放曾在F[A,a]中為真的序偶對(A,a)。

1.構造集合FIRSTVT(P)的算法

?算法如下：

?初始化，將布爾矩陣中各元素置為false,棧為空；

按規則1,查看產生式，對于形如A-a…或A-Ba…的

產生式，置相應的[A,a]為true,并將序偶對(A,a)入棧；

?按規則2,對棧施加如下操作：

■彈出棧頂序偶對并記為(B,a),查看所有產生式，看有無形如

A—B…的產生式，若有,且a不屬于FISRTVT(A)(即F[A,a]

為false),則將F[A,a]置為true,并把(A,a)入棧;

■重復3,直到棧空為止。

最后，在F[A,a]中，凡是true的元素即屬于A的首終結符

集。

2.構造集合LASTVT(P)

LASTVT集的求解方法和FIRSTVT相似，不再贅述。

3.構造算符優先表算法

算法過程：

對每條產生式P—X1X2…Xndo

{for(i=1;i<=n-1;i++)

{ifX和X.均為終結符then優先表表中置*尸為+1；

ifi<n-2andXj^nXi+2^VTandXi+1eVNthen

{forFIRSTVT(X+i)中的每個ado

{優先表表中置Xj〈?a}}

ifX,￡VN而Xj+i^VTthen

{forLASTVT(X)中的每個ado

{優先表表中置a>X+i}}

})

算符優先文法的另一個定義：

如果文法G按此算法構造出的優先分析表沒有重定義項，則文法G是算符優先文法.

構造下面文法的算符優先表。

①S—ifEbthenEelseE②E-E+T|T

③T—T*F|F④F—i⑤E「＞b

解析

1）先求各非終結符的首終結符集和尾終結符集。為考慮語句

的開始和結束符號“#“，對文法拓廣，加一個產生式S，T#S#

FISRTVT(S)={if}LASTVT(S)={else,+,*,i}

FISRTVT(Eb)={b}LASTVT(Eb)={b}

FISRTVT(E)={+,*,i}LASTVT(E)={+,*,i}

FISRTVT(T)={*,i}LASTVT(T)={*,i}

FISRTVT(F)={i}LASTVT(F)={i}

2）填寫算符優先表

■

右+*

左ifthenelse1b#

if

then

else

+

*

■

1

b

#

2）填寫算符優先表（參考）

■

右+*

左ifthenelse1b#

if=<■

then=<■<■<■

else<-<■<■■>

+■>■><-<■■>

*->■>■><■■>

■

1■>■>■>■>

b■>

#<■

算符優先分析法流程

if(a<-b)or(a=b)then

begin/*移進*/

把b推入棧中；

使ip前進到下一個符號；

end

ifa->bthen/*歸約*/

repeat

從棧中彈出符號

until棧頂終結符號〈?最近彈出的終結符號

elseerror

算符優先文法的若干問題

1.優先表構造算法討論

?構造優先表的算法僅僅反映文法符號間關系，并不反映

附加條件，對二義性文法構造算符優先表，可能會出現

多重定義項。

?二義性文法存在規范歸約不唯一的句子。例如，

文法G[E]:E-E+E|E*E|(E)|id

句子id+id*id有二個不同的最右推導：

E=E+EE=>E*E

nE+E*E=>E*id

nE+E*id3=>E+E*id

nE+id2*id3=>E+id*id

nid1+id2*id3=>id1+id2*id3

句型E+E*id3中，句柄不唯一o

2.非規范分析

?規范歸約：嚴格按照句柄進行歸約，終結符和非終結符

一起考慮，只要棧頂形成句柄，不管句柄內是否包含終

結符都要進行歸約。

例如，考慮非二義的表達式文法G[E]:

E—E+T|TT-T*F|FF->(E)|i,識別語句i+i*i的過程

?規范歸約：

i+i*i#

F+i*i#

T+i*i#

E+i*i#

E+F*i#

E+T*i#

E+T*F#

E+T#

E#

算符優先分析：算符優先分析中，僅研究終結符之間的

優先關系，而不考慮非終結符之間的優先關系，但句柄

是由終結符和非終結符一起構成的，所以算符優先分析

相對來說是非規范的分析過程。

對上例的算符優先分析過程：

i+i*i#

E+i*i#

E+T*i#

E+T*F#

E+T*F#

E+T#

E#

在優先分析中，可歸約的短語不再稱為句柄，而稱為最

左素短語。素短語是指這樣一個短語，至少含有一個終

結符號，并且除自身之外不再含有任何更小的帶有終結

符號的短語。

注：最左素短語是指處于句型最左邊的那個素短語；算符優先文法

句型的最左素短語是唯一的。

文法G[E]:E-E+T|TT-T*F|FF一(E)|i,

寫出句型#丁+丁*F+i#的素短語。

由定義可知，

短語有：T,T*F,i,T+T*F+i

素短語有：T*F,i

左素短語有：T*F