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

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

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

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

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

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

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

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

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

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

學(xué)習(xí)目標(biāo)

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

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

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

握：

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

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

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

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

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

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

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

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

知識(shí)點(diǎn)

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

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

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

短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、最右推導(dǎo)、規(guī)范歸約基本概念。

?本章重難點(diǎn)

?算符文法的形式。

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

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

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

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

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

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

語(yǔ)法分析

?推導(dǎo)——自頂向下的語(yǔ)法分析過(guò)程

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

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

?歸約——自底向上的語(yǔ)法分析過(guò)程

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

?LR分析法

自底向上的語(yǔ)法分析過(guò)程思想::

?自底向上語(yǔ)法分析過(guò)程是一個(gè)最左歸約的過(guò)程

（規(guī)范推導(dǎo)的逆過(guò)程，亦稱(chēng)規(guī)范歸約），從輸入

串開(kāi)始，朝著文法的開(kāi)始符號(hào)進(jìn)行歸約，直到

到達(dá)文法的開(kāi)始符號(hào)為止的過(guò)程。

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

號(hào)組成的二元式的有限序列。

?自底向上的下推自動(dòng)機(jī)PDA

?工作方式：“移進(jìn)-歸約”方式

?對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后

進(jìn)先出棧中，在移進(jìn)過(guò)程中不斷查看棧頂符號(hào)串，一旦串形成

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

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

一過(guò)程直到歸約到棧中只剩文法的開(kāi)始符號(hào)時(shí)則為分析成功，

也就確認(rèn)輸入串是文法的句子。

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

符號(hào)為該符號(hào)串的頭，棧頂符號(hào)為該符號(hào)串的尾，也可以只包

含一個(gè)符號(hào)。

?幾點(diǎn)說(shuō)明：

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

的單詞符號(hào)上。

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

#W#

語(yǔ)法分析執(zhí)行的動(dòng)作：

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

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

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

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

法開(kāi)始符號(hào)，讀頭也指向語(yǔ)句的結(jié)束符；

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

標(biāo)輸入

#S#

?識(shí)別失敗

例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

步驟棧輸入動(dòng)作輸出帶

(1)#abbcde#移進(jìn)

(2)#abbcde#移進(jìn)

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

(4)粕Abcde#移進(jìn)

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

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

(7)#aAcde#移進(jìn)

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

(9)粕AcBe#移進(jìn)

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

(11)#S*接受

沒(méi)有語(yǔ)法樹(shù)的提示，如何分析，如何歸約？

1.優(yōu)先分析器：簡(jiǎn)單優(yōu)先分析法；算符優(yōu)先分析

法。

2.LR分析器

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

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

?簡(jiǎn)單優(yōu)先分析法是對(duì)一個(gè)文法按一定原則求出該文法所有符號(hào)

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

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

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

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

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

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

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

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

用'工”表示。

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

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

于表示為：

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

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

2.句型中Nj……Nj是句柄，語(yǔ)法分析程序可以通過(guò)尋找

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

而確定句柄進(jìn)行歸約。

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

abce#bee#

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

?定義

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

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

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

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

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

?XY當(dāng)且僅當(dāng)G中含有形如P一…XY…

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

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

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

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

A—(B|a：：

B—Aa)

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

文法符號(hào)之間的優(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)于"#”的說(shuō)明：

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

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

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

始符號(hào)#..........#束符號(hào)

?對(duì)任何x,若文法開(kāi)始符號(hào)S與x…,貝I」#v?x,若有

S當(dāng)■???x,則x>#

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

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

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

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

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

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

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

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

高于或等于讀入符號(hào)，則找句柄進(jìn)行歸約，找不到句柄就繼

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

止，此時(shí)識(shí)別正確。

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

?優(yōu)點(diǎn)：技術(shù)簡(jiǎn)單

?缺點(diǎn)：適用范圍?。环治霰沓叽邕^(guò)大。

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

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

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

種語(yǔ)法分析過(guò)程.

?特點(diǎn)

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

的歸約過(guò)程，但可歸約串不一定是規(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的運(yùn)算

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

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

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

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

力口、減運(yùn)算符；同級(jí)運(yùn)算符服從左結(jié)合原則；有括號(hào)時(shí)，先括號(hào)

內(nèi)后括號(hào)外。

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

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

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

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

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

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

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

⑺E-E*(E+E)先算括號(hào)內(nèi)，在算括號(hào)外

(8)E—E*(E)

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

(10)E-E

(11)E

1.這個(gè)歸約過(guò)程是唯一的，運(yùn)算結(jié)果亦是唯一的。

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

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

進(jìn)行歸約。

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

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

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

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

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

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

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

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

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

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

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

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

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

+?*/id)#

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

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

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

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

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

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

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

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

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

說(shuō)明：

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

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

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

或以此保證語(yǔ)句先歸約。

?(二)表示括號(hào)是成對(duì)歸約的。

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

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

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

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

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

(b)對(duì)于一個(gè)無(wú)二義性文法，有機(jī)械方法。

?直觀算符分析法對(duì)下推自動(dòng)機(jī)的改進(jìn)

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

一個(gè)用于放操作符（包括執(zhí)括號(hào)）。

?算法概要

初始化（OPND='，QPTR=#，讀頭指向輸入串第一個(gè)符號(hào)）

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

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

當(dāng)OPTR棧頂符號(hào)9二'（'andsym='）',6彈出，讀頭下移；

當(dāng)遇到可歸約串時(shí)（即OPTR棧頂符號(hào)串與讀頭下符號(hào)形成了一對(duì)＜?????＞）,

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

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

分析完畢。

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

+i)*i#

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

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

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

(

OPND#+

E

OPTR把

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

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

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

a+b*c#

OPTR棧只剩一個(gè)#,

讀頭亦只剩一個(gè)#,

分析結(jié)束，

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

Tl=b*cT2=a+Tl

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

?優(yōu)點(diǎn)

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

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

時(shí)把計(jì)算口力取值改成相應(yīng)指令（&3,叫，?。┘纯伞?/p>

?缺點(diǎn)

算法采用兩個(gè)下推棧，有時(shí)會(huì)將錯(cuò)誤句子識(shí)別成合法句子，并且，

無(wú)法指出輸入串中出錯(cuò)位置。

對(duì)于含有單目運(yùn)算符的算術(shù)表達(dá)式不便處理

■比如負(fù)號(hào)，由于負(fù)號(hào)的優(yōu)先級(jí)高于加減法，低于乘除法，但負(fù)號(hào)的形式

與減號(hào)相同，不容易識(shí)別。

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

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

2"Tl=i+ii

T3=i4+T22

1+-

#

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

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

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

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

注質(zhì)。

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

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

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

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

Grammar：也稱(chēng)0G文法。

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

生式。

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

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

法。

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

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

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

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

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

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

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

的產(chǎn)生式

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

B與b...或B當(dāng)Cb...

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

...a或...aC

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

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

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

(OperatorPrecedenceGrammar),即OPG文法。

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

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

①amb則存在語(yǔ)法子樹(shù)如圖（a）

其中b為E或?yàn)锽,這樣a,b在同一句柄中同時(shí)歸約所以?xún)?yōu)先級(jí)相同。

②avb則存在語(yǔ)法子樹(shù)如圖（b）

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

③a>b則存在語(yǔ)法子樹(shù)如圖（c）。

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

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

??

?0G和OPG定義的意義

?這兩個(gè)定義相當(dāng)于對(duì)文法的句型和可歸約的短語(yǔ)做了如下

規(guī)定：

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

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

結(jié)符；

?若B〔B2…Bm是當(dāng)前可歸約短語(yǔ)，并可歸約為Aj,則

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

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

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

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

?實(shí)際上，可歸約短語(yǔ)是某產(chǎn)生式右部符號(hào)串，所以通過(guò)檢

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

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

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

構(gòu)造過(guò)程::

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

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

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

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

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

?三關(guān)系

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

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

?v?關(guān)系

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

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

?＞關(guān)系

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

A—…Bb…中，對(duì)每一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)計(jì)算每個(gè)非終結(jié)符的左

FIRSTVT與LASTVT；a

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

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

解析FIRSTVT(S)={a}c

FIRSTVT(A)=

FIRSTVT(B)=83wz8rod

LASTVT(S)={e}e

LASTVT(A)=

LASTVT(B)=xeknt7n

構(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)生式中

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

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

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

當(dāng)且僅當(dāng)a￡FIRSTVT(A)。

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

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

?算法如下：

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

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

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

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

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

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

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

■重復(fù)3,直到?？諡橹?。

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

集。

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

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

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

算法過(guò)程：

對(duì)每條產(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)中的每個(gè)ado

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

ifX,￡VN而Xj+i^VTthen

{forLASTVT(X)中的每個(gè)ado

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

})

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

如果文法G按此算法構(gòu)造出的優(yōu)先分析表沒(méi)有重定義項(xiàng)，則文法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é)符集。為考慮語(yǔ)句

的開(kāi)始和結(jié)束符號(hào)“#“，對(duì)文法拓廣，加一個(gè)產(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）填寫(xiě)算符優(yōu)先表

■

右+*

左ifthenelse1b#

if

then

else

+

*

■

1

b

#

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

■

右+*

左ifthenelse1b#

if=<■

then=<■<■<■

else<-<■<■■>

+■>■><-<■■>

*->■>■><■■>

■

1■>■>■>■>

b■>

#<■

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

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

begin/*移進(jìn)*/

把b推入棧中；

使ip前進(jìn)到下一個(gè)符號(hào)；

end

ifa->bthen/*歸約*/

repeat

從棧中彈出符號(hào)

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

elseerror

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

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

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

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

多重定義項(xiàng)。

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

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

句子id+id*id有二個(gè)不同的最右推導(dǎo)：

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ī)范歸約：嚴(yán)格按照句柄進(jìn)行歸約，終結(jié)符和非終結(jié)符

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

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

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

E—E+T|TT-T*F|FF->(E)|i,識(shí)別語(yǔ)句i+i*i的過(guò)程

?規(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)先分析

相對(duì)來(lái)說(shuō)是非規(guī)范的分析過(guò)程。

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

i+i*i#

E+i*i#

E+T*i#

E+T*F#

E+T*F#

E+T#

E#

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

左素短語(yǔ)。素短語(yǔ)是指這樣一個(gè)短語(yǔ)，至少含有一個(gè)終

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

符號(hào)的短語(yǔ)。

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

句型的最左素短語(yǔ)是唯一的。

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

寫(xiě)出句型#丁+丁*F+i#的素短語(yǔ)。

由定義可知，

短語(yǔ)有：T,T*F,i,T+T*F+i

素短語(yǔ)有：T*F,i

左素短語(yǔ)有：T*F