計算機課件計算機之編譯原理cpl之自底向上優(yōu)先分析算法

第六章自底向上優(yōu)先分析法

?自底向上優(yōu)先分析思想概述

?簡單優(yōu)先分析法

?優(yōu)先關(guān)系的含義

?簡單優(yōu)先文法的定義及操作步驟

?算符優(yōu)先分析法

?算符優(yōu)先分析法的定義

?算符優(yōu)先關(guān)系表的構(gòu)造

?優(yōu)先函數(shù)

學習目標

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

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

此，也是學習其它自下而上語法分析的基礎(chǔ)。通過本章學習應(yīng)掌

握：

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

?對給定的算符文法能夠判斷該文法是否是算符優(yōu)先文法

?對給定的算符文法能構(gòu)造算符優(yōu)先關(guān)系表，并能利用算符優(yōu)先關(guān)

系表判斷該文法是否是算符優(yōu)先文法。

?能應(yīng)用算符優(yōu)先分析算法對給定的輸入串進行移進■歸約分析，

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

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

?了解算符優(yōu)先分析法的優(yōu)缺點和實際應(yīng)用中的局限性。

知識點

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

習其它自下而上語法分析的基礎(chǔ)。

?需復(fù)習有關(guān)語法分析的知識有：什么是語言、文法、句子、句型、

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

?本章重難點

?算符文法的形式。

?對一個給定的算符文法能構(gòu)造算符優(yōu)先關(guān)系分析表，并能判別所

給文法是否為算符優(yōu)先文法。

?分清規(guī)范句型的句柄和最左素短語的區(qū)別，進而分清算符優(yōu)先歸

約和規(guī)范歸約的區(qū)別。（在分析過程中如何尋找可歸約串）

?對一個給定的輸入串能應(yīng)用算符優(yōu)先關(guān)系分析表給出分析（歸約）

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

語法分析

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

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

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

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

?簡單優(yōu)先分析法，算符優(yōu)先分析法

?LR分析法

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

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

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

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

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

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

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

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

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

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

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

某個句型的句柄時（該句柄對應(yīng)某產(chǎn)生式的右部），就用該產(chǎn)生

式的左部非終結(jié)符代替相應(yīng)右部的文法符號串（歸約）。重復(fù)這

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

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

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

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

含一個符號。

?幾點說明：

?初態(tài)時，棧內(nèi)僅有棧底符號“毋，讀頭指在最左以

的單詞符號上。

即初態(tài)為：棧輸入

#W#

語法分析執(zhí)行的動作：

?移進讀入一個單詞并壓入棧內(nèi)，讀頭后移；

?歸約檢查棧頂若干符號能否進行歸約，若能，就以產(chǎn)

生式左部替代該符號串，同時輸出產(chǎn)生式編號；

?識別成功移進-歸約的結(jié)局是棧內(nèi)只剩下棧底符號和文

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

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

標輸入

#S#

?識別失敗

例6.1文法G[S]產(chǎn)生式如下：

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

B->d

輸入串a(chǎn)bbcde是不是文法的句子？

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.優(yōu)先分析器：簡單優(yōu)先分析法；算符優(yōu)先分析

法。

2.LR分析器

6.1自底向上優(yōu)先分析思想

優(yōu)先分析法可分為簡單優(yōu)先分析法和算符優(yōu)先分析法。

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

（V集）之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過程中的句柄，

實際上，是一種規(guī)范歸約。

?算符優(yōu)先分析法的基本思想只考慮算符之間的優(yōu)先關(guān)系，在歸

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

因此，算符優(yōu)先歸約不是規(guī)范歸約。

優(yōu)先分析法基本思想

1.相鄰文法符號之間的優(yōu)先關(guān)系

在句型中，句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級。相同優(yōu)先級

用'工”表示。

由于句柄要先歸約，所以規(guī)定句柄兩端符號的優(yōu)先級要比位于句柄

之外的相鄰符號的優(yōu)先級高。優(yōu)先級低于表示為：優(yōu)先級高

于表示為：

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

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

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

岫.產(chǎn)?岫和這兩個關(guān)系來確定句柄的頭尾，從

而確定句柄進行歸約。

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

abce#bee#

6.2簡單優(yōu)先分析法：：

?定義

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

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

X,Y￡V或者沒有關(guān)系，或者存在優(yōu)先級相同或低于、

高于等關(guān)系之一，則這是一個簡單優(yōu)先文法。

?優(yōu)先級的定義

?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)

解析根據(jù)優(yōu)先級的定義，由文法產(chǎn)生式可求得

文法符號之間的優(yōu)先關(guān)系如下：

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

2,求v?關(guān)系：b<-(,b<-a,(<-A...

3.求:關(guān)系：)->b,a->b,),>a,a>a,B->a...

?關(guān)于"#”的說明：

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

志了句子的開始和結(jié)束。

■母子的開工*4旬子的結(jié)

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

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

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

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

?為句子的開始符號、終結(jié)符號和句中符號添加優(yōu)先

關(guān)系，使句子易于被識別處理。

?簡單優(yōu)先分析的思想

?簡單優(yōu)先矩陣：根據(jù)優(yōu)先關(guān)系的定義，將文法中各文法符號

之間的這種關(guān)系用一矩陣表示，稱作簡單優(yōu)先矩陣。

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

棧頂符號優(yōu)先級低于該單詞，繼續(xù)讀入；若棧頂符號優(yōu)先級

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

續(xù)讀入。直到最后棧內(nèi)只剩下開始符號，輸入串讀到“#"為

止，此時識別正確。

?簡單優(yōu)先分析法的優(yōu)缺點

?優(yōu)點：技術(shù)簡單

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

6.3算符優(yōu)先分析法

?算符優(yōu)先分析的基本思想

?所謂算符優(yōu)先分析法是仿效四則運算的計算過程而構(gòu)造的一

種語法分析過程.

?特點

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

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

符優(yōu)先歸約不是規(guī)范歸約。

?關(guān)鍵

?分析表只規(guī)定算符（廣義為終結(jié)符）之間的優(yōu)先關(guān)系，也就是

只考慮終結(jié)符之間的優(yōu)先關(guān)系及結(jié)合性質(zhì)，不考慮非終結(jié)符

之間的優(yōu)先關(guān)系。

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

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

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

歸約，實際運算會得到不同結(jié)果，但按傳統(tǒng)的習慣規(guī)定優(yōu)先級和

結(jié)合律進行歸約，優(yōu)先級從高到低為：乘幕運算符，乘、除運算符

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

內(nèi)后括號外。

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

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

(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)先算括號內(nèi)，在算括號外

(8)E—E*(E)

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

(10)E-E

(11)E

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

2.上述歸約過程中起決定作用的是相鄰兩個終結(jié)符號之間的優(yōu)先關(guān)系

一旦確定了這種優(yōu)先關(guān)系，就可以借助這種關(guān)系去尋找可歸約串并

進行歸約。

?因此，算符優(yōu)先分析法的關(guān)鍵是比較兩個相繼出現(xiàn)的終結(jié)

符的優(yōu)先級而決定應(yīng)采取的動作。

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

現(xiàn)的運算符的優(yōu)先級并表示為矩陣的形式，使得能夠在分析

中通過查詢矩陣元素而得到算符之間的優(yōu)先關(guān)系。

?對于任何兩個可能相繼出現(xiàn)的終結(jié)符號a與b,若具有以下

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

之間的關(guān)系為：

?a<-b表示a的優(yōu)先級低于b

?a=b表示a的優(yōu)先級等于b

?a->b表示a的優(yōu)先級大于b

?若a,b在任何情況下不可能相繼出現(xiàn)，貝Ua,b無關(guān)系

表6.2優(yōu)先關(guān)系表

+?*/id)#

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

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

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

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

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

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

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

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

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

說明：

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

id的優(yōu)先級高于算符。

?語句開始符號和結(jié)束符號“鏟與終結(jié)符相繼出現(xiàn)時，應(yīng)該有

或以此保證語句先歸約。

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

?算術(shù)關(guān)系二”和“〉”與優(yōu)先關(guān)系具有十分不同的性質(zhì)。例

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

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

?決定優(yōu)先關(guān)系方法：

(a)直觀方法：代數(shù)規(guī)則；

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

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

?添加了一個下推棧：一個用于放操作數(shù)和運算結(jié)果；

一個用于放操作符（包括執(zhí)括號）。

?算法概要

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

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

號則查表比較OPTR棧頂6與sym的優(yōu)先級：

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

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

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

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

分析完畢。

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

+i)*i#

推"----------直觀算符優(yōu)先控制

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

"優(yōu)先表（=,＜）E

(

OPND#+

E

OPTR把

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

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

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

a+b*c#

OPTR棧只剩一個#,

讀頭亦只剩一個#,

分析結(jié)束，

T2即是運算結(jié)果。

Tl=b*cT2=a+Tl

?直觀算符分析法的優(yōu)缺點

?優(yōu)點

簡單明了，易于手工實現(xiàn)，適于分析各種算術(shù)表達式

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

時把計算口力取值改成相應(yīng)指令（&3,叫，?。┘纯?。

?缺點

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

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

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

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

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

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

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

2"Tl=i+ii

T3=i4+T22

1+-

#

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

優(yōu)先分析法的概念。

?直觀算符優(yōu)先分析法的關(guān)鍵是對一個給定文法G,人為地規(guī)定

其算符的優(yōu)先順序，即給出優(yōu)先級別和同一個級別中的結(jié)合

注質(zhì)。

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

的規(guī)則計算算符之間的優(yōu)先關(guān)系。

定義6.1設(shè)有一文法G,如果G中沒有形如A->g或形如A-...BC…的產(chǎn)

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

Grammar：也稱0G文法。

>理解：即算符文法G中沒有右部為￡或右部具有相鄰非終結(jié)符號的產(chǎn)

生式。

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

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

法。

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

因右部EAE具有相鄰的非終結(jié)符號。

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

定義6.2設(shè)G是一個不含8產(chǎn)生式的算符文法，a和b

是任意兩個終結(jié)符，A、B、C是非終結(jié)符，算符優(yōu)

先關(guān)系三、?>、v?定義如下：

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

的產(chǎn)生式

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

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

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

...a或...aC

定義6.3設(shè)有一不含w產(chǎn)生式的算符文法G,如果對

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

關(guān)系中的?種成立，則稱G是一個算符優(yōu)先文法

(OperatorPrecedenceGrammar),即OPG文法。

?算符優(yōu)先文法是無二義性的。

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

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

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

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

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

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

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

算符優(yōu)先關(guān)系表的構(gòu)造r

??

?0G和OPG定義的意義

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

規(guī)定：

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

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

結(jié)符；

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

B1B2…Bm中不能相繼出現(xiàn)兩個非終結(jié)符，且相鄰的終結(jié)符

優(yōu)先級全相等；

對于B1B2…Bm中首終結(jié)符b有AgV?b

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

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

查G的每個產(chǎn)生式的候選式可以查找出任意優(yōu)先級相同的終

結(jié)符序偶對；要找出滿足v?關(guān)系和》關(guān)系的終結(jié)符序偶，就

要找出各非終結(jié)符Ai的首終結(jié)符集和尾終結(jié)符集。

構(gòu)造過程::

?求各非終結(jié)符的首終結(jié)符集和尾終結(jié)符集：??

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

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

?則算符文法中任何兩個終結(jié)符對(a,b)之間的優(yōu)先關(guān)系,

其算法依據(jù)如下：

?三關(guān)系

?可直接查看產(chǎn)生式的右部，對如下形式的產(chǎn)生式

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

?v?關(guān)系

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

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

?＞關(guān)系

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

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

由定義6.2可有如下推論：

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

為非終結(jié)符，a為終結(jié)符。

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

例設(shè)文法G的產(chǎn)生式為：

S->aAcBeA->.Bb

右

A—bB—dabcde

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

FIRSTVT與LASTVT；a

(2)計算所有終結(jié)符之間的關(guān)系

(優(yōu)先關(guān)系表)。b

解析FIRSTVT(S)={a}c

FIRSTVT(A)=

FIRSTVT(B)=kg7aihpd

LASTVT(S)={e}e

LASTVT(A)=

LASTVT(B)=hcpl4um

構(gòu)造算法

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

?依據(jù)：定義和推論

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

BeVN,aeVT

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

aeFIRSTVT(A).

?注：規(guī)則1是求A的首終結(jié)符a的關(guān)系；規(guī)則2是求A與產(chǎn)生式中

開頭的非終結(jié)符B之間的關(guān)系。

?兩個數(shù)據(jù)結(jié)構(gòu)

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

當且僅當a￡FIRSTVT(A)。

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

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

?算法如下：

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

按規(guī)則1,查看產(chǎn)生式，對于形如A-a…或A-Ba…的

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

?按規(guī)則2,對棧施加如下操作：

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

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

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

■重復(fù)3,直到?？諡橹埂?/p>

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

集。

2.構(gòu)造集合LASTVT(P)

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

3.構(gòu)造算符優(yōu)先表算法

算法過程：

對每條產(chǎn)生式P—X1X2…Xndo

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

{ifX和X.均為終結(jié)符then優(yōu)先表表中置*尸為+1；

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

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

{優(yōu)先表表中置Xj〈?a}}

ifX,￡VN而Xj+i^VTthen

{forLASTVT(X)中的每個ado

{優(yōu)先表表中置a>X+i}}

})

算符優(yōu)先文法的另一個定義：

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

構(gòu)造下面文法的算符優(yōu)先表。

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

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

解析

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

的開始和結(jié)束符號“#“，對文法拓廣，加一個產(chǎn)生式S，T#S#

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

FISRTVT(Eb)=LASTVT(Eb)=

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

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

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

2）填寫算符優(yōu)先表

■

右+*

左ifthenelse1b#

if

then

else

+

*

■

1

b

#

2）填寫算符優(yōu)先表（參考）

■

右+*

左ifthenelse1b#

if=<■

then=<■<■<■

else<-<■<■■>

+■>■><-<■■>

*->■>■><■■>

■

1■>■>■>■>

b■>

#<■

算符優(yōu)先分析法流程

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

begin/*移進*/

把b推入棧中；

使ip前進到下一個符號；

end

ifa->bthen/*歸約*/

repeat

從棧中彈出符號

until棧頂終結(jié)符號〈?最近彈出的終結(jié)符號

elseerror

算符優(yōu)先文法的若干問題

1.優(yōu)先表構(gòu)造算法討論

?構(gòu)造優(yōu)先表的算法僅僅反映文法符號間關(guān)系，并不反映

附加條件，對二義性文法構(gòu)造算符優(yōu)先表，可能會出現(xiàn)

多重定義項。

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

文法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.非規(guī)范分析

?規(guī)范歸約：嚴格按照句柄進行歸約，終結(jié)符和非終結(jié)符

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

結(jié)符都要進行歸約。

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

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

?規(guī)范歸約：

i+i*i#

F+i*i#

T+i*i#

E+i*i#

E+F*i#

E+T*i#

E+T*F#

E+T#

E#

算符優(yōu)先分析：算符優(yōu)先分析中，僅研究終結(jié)符之間的

優(yōu)先關(guān)系，而不考慮非終結(jié)符之間的優(yōu)先關(guān)系，但句柄

是由終結(jié)符和非終結(jié)符一起構(gòu)成的，所以算符優(yōu)先分析

相對來說是非規(guī)范的分析過程。

對上例的算符優(yōu)先分析過程：

i+i*i#

E+i*i#

E+T*i#

E+T*F#

E+T*F#

E+T#

E#

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

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

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

符號的短語。

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

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

文法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