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

1、指導(dǎo)教師:楊建國(guó)二零零七年十一月編 譯 原 理第6章自底向上優(yōu)先分析語(yǔ)法分析推導(dǎo)自上而下的語(yǔ)法分析過(guò)程預(yù)測(cè)分析程序，遞歸下降分析法（最左推導(dǎo)）注：要求文法是LL(1)文法歸約自下而上的語(yǔ)法分析過(guò)程簡(jiǎn)單優(yōu)先分析法，算符優(yōu)先分析法，LR分析法1.自底向上優(yōu)先分析概述2.簡(jiǎn)單優(yōu)先分析（優(yōu)先關(guān)系的理解）3.算符優(yōu)先分析確定句型的短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)、最左素短語(yǔ)算符優(yōu)先關(guān)系矩陣的構(gòu)造及輸入串的過(guò)程分析學(xué)習(xí)目標(biāo)第一節(jié) 自底向上優(yōu)先分析概述第二節(jié) 簡(jiǎn)單優(yōu)先分析法第三節(jié) 算符優(yōu)先分析法第四節(jié) 典型例題及解答教學(xué)內(nèi)容知識(shí)結(jié)構(gòu)從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法開(kāi)始符號(hào)；或者說(shuō)，從語(yǔ)法樹(shù)的末端開(kāi)

2、始，步步向上“歸約”，直到根結(jié)點(diǎn)。引言 1.基本思想自下而上的語(yǔ)法分析過(guò)程是一個(gè)最左歸約的過(guò)程，從輸入串開(kāi)始，朝著文法的開(kāi)始符號(hào)進(jìn)行歸約，直到到達(dá)文法的開(kāi)始符號(hào)為止的過(guò)程。從語(yǔ)法樹(shù)角度看，是以輸入符號(hào)串作為語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串，自底向上地構(gòu)造語(yǔ)法樹(shù)，使文法開(kāi)始符號(hào)正好是該語(yǔ)法樹(shù)的根。如果最終根結(jié)點(diǎn)是開(kāi)始符號(hào)，則輸入符號(hào)串是語(yǔ)言的一個(gè)句子，否則不是。自底向上分析過(guò)程實(shí)際上是一個(gè)不斷進(jìn)行直接歸約的過(guò)程。注意：輸入串在這里是指從詞法分析器送來(lái)的單詞符號(hào)組成的二元式的有限序列。 分析過(guò)程是重復(fù)以下步驟：1、找出當(dāng)前句型的句柄 x （或句柄的變形）2、找出以x為右部的規(guī)則Xx 3、把x規(guī)約為X，產(chǎn)生語(yǔ)

3、法樹(shù)的一枝關(guān)鍵：找出當(dāng)前句型的句柄x(或其變形），這不是很容易。2.實(shí)現(xiàn)方式-“移進(jìn)歸約”方式 語(yǔ)法分析程序 語(yǔ)法表 a+b#輸出帶# 自左至右把輸入串的符號(hào)逐個(gè)移進(jìn)?！咀ⅰ砍鯌B(tài)時(shí)棧內(nèi)僅有棧底符“”，讀頭指在最左邊的單詞符號(hào)上。 若棧頂形成某個(gè)句型的句柄，就將此句柄用相應(yīng)的產(chǎn)生式左部替換（歸約），若再形成句柄，就繼續(xù)替換，直到棧頂不再形成句柄為止。重復(fù)上面的過(guò)程直到棧頂只剩下#和文法的開(kāi)始符號(hào)，同時(shí)輸入串讀完為止，這樣就認(rèn)為識(shí)別了一個(gè)句子。3.語(yǔ)法分析程序執(zhí)行的動(dòng)作移進(jìn) 讀入下一個(gè)輸入符號(hào)并壓入棧內(nèi)，讀頭后移；歸約 檢查棧頂若干個(gè)符號(hào)能否進(jìn)行歸約，若能，就以產(chǎn)生式左部替代該符號(hào)串，同時(shí)輸出產(chǎn)生

4、式；接受 移進(jìn)歸約的結(jié)局是棧內(nèi)只剩下棧底符號(hào)和文法開(kāi)始符號(hào)，讀頭也指向語(yǔ)句的結(jié)束符； 報(bào)錯(cuò) 當(dāng)識(shí)別程序察覺(jué)一個(gè)錯(cuò)誤，因此輸入符號(hào)串不是句子而無(wú)法繼續(xù)識(shí)別工作時(shí)，調(diào)用一個(gè)出錯(cuò)處理子程序進(jìn)行處理或停止。例1：文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dabbcde步驟符號(hào)棧輸入符號(hào)串動(dòng)作 1） # abbcde# 移進(jìn) 2） #a bbcde# 移進(jìn)A 3） #ab bcde# 歸約(Ab) 4） #aA bcde# 移進(jìn)A 5） #aAb cde# 歸約(AAb) 6） #aA cde# 移進(jìn) 7） #aAc de# 移進(jìn)B 8） #aAcd e# 歸約(Bd)

5、9） #aAcB e# 移進(jìn)11） #S # 接受S10） #aAcBe # 歸約(S aAcBe)符號(hào)串a(chǎn)bbcde是否是GS的句子對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-歸約分析過(guò)程SaAcBeaAcdeaAbcdeabbcde順序掃描輸入符號(hào)并依次移進(jìn)棧棧頂部的符號(hào)串是否構(gòu)成一句柄？YN進(jìn)行一次歸約輸入串掃描完否？noY棧中僅有開(kāi)始符號(hào)？noerror輸入串合法，報(bào)告分析報(bào)告出口移進(jìn)-歸約過(guò)程Y（1）例子的分析過(guò)程是一步步地歸約當(dāng)前句型的句柄該句子的唯一語(yǔ)法樹(shù)為:aAcBeAbbdS注意兩點(diǎn)：（a）棧內(nèi)符號(hào)串+ 未處理輸入符號(hào)串 = 當(dāng)前句型（b）句柄都在棧頂實(shí)際上，以上分析過(guò)程并未真正解決句柄的

6、識(shí)別問(wèn)題說(shuō)明:（2）未真正解決句柄的識(shí)別 *上述分析過(guò)程是怎樣識(shí)別句柄的，主要看棧頂符號(hào)串 是否形成規(guī)則的右部。這種做法形式上是正確的，但在實(shí)際上不一定正確。 舉例的分析過(guò)程可以說(shuō)是一種巧合。 因?yàn)椴荒苷J(rèn)為:對(duì)句型 xuy 而言，若有Uu，即Uu 就斷定u是簡(jiǎn)單短語(yǔ)，u就是句柄，而是要同時(shí)滿(mǎn)足 Z xUy一.優(yōu)先分析法的類(lèi)別6.1自底向上優(yōu)先分析概述1.優(yōu)先分析器（Precedence Parser）簡(jiǎn)單優(yōu)先分析法算符優(yōu)先分析法2.LR分析器二.簡(jiǎn)單優(yōu)先分析法基本思想：按一定原則定義文法中所有符號(hào)（終結(jié)符和非終結(jié)符）之間的優(yōu)先關(guān)系，按照這種關(guān)系確定歸約過(guò)程中的句柄并實(shí)行歸約。是一種規(guī)范歸約。簡(jiǎn)

7、單優(yōu)先分析法準(zhǔn)確、規(guī)范，但效率低，不實(shí)用，不流行。三.算符優(yōu)先分析法基本思想：只定義文法中終結(jié)符之間的優(yōu)先關(guān)系（不考慮非終結(jié)符），并由這種關(guān)系指導(dǎo)分析過(guò)程不是規(guī)范歸約算符優(yōu)先分析法分析速度快，特別適用于表達(dá)式的分析。缺點(diǎn)是不規(guī)范，常常要采用適當(dāng)措施克服其缺點(diǎn)。 6.2簡(jiǎn)單優(yōu)先分析法一.優(yōu)先關(guān)系的符號(hào)表示6.2.1 優(yōu)先關(guān)系.+*.+（1） XY當(dāng)且僅當(dāng)G中存在產(chǎn)生式規(guī)則 AXY（2） XY當(dāng)且僅當(dāng)G中存在產(chǎn)生式規(guī)則 A XB，且BY（3） XY當(dāng)且僅當(dāng)G中存在產(chǎn)生式規(guī)則 ABD,且B X和D Y三.從語(yǔ)法樹(shù)判別優(yōu)先性設(shè)G是已化簡(jiǎn)的文法,s,tV,若G中存在規(guī)范句型 =st, 則s,t與的句柄之

8、間的關(guān)系必有下述情況之一:1.s在句柄中,而t不在句柄中2.s與t均在句柄中3.s不在句柄中,而t在句柄中對(duì)于上述情況,我們規(guī)定：情況1:st;情況2:s=t;情況3:stA s t .A s t .A s t . 另外,還有一種情況,就是s和t均不在句柄中,那么一定存在某句型使得它們進(jìn)入上述三種情況之一。 若s和t在任何句型中都不可能相鄰出現(xiàn),則我們規(guī)定二者無(wú)關(guān)系。 注意,這種優(yōu)先關(guān)系是不對(duì)稱(chēng)的!在句型中，句柄內(nèi)各相鄰符號(hào)之間具有相同的優(yōu)先級(jí)。結(jié)論由于句柄要先歸約，所以規(guī)定句柄兩端符號(hào)的優(yōu)先級(jí) 要比位于句柄之外的相鄰符號(hào)的優(yōu)先級(jí)高。 句型中NiNj是句柄，則 N1Ni-1 Ni Nj Nj+

9、1Nn .【注】?jī)?yōu)先分析法基本思想也可以表述為： 若句型中NiNj是句柄，語(yǔ)法分析程序可以 通過(guò)尋找Ni-1 Ni和Nj Nj+1 這兩個(gè)關(guān)系來(lái)確定句 柄的頭尾，從而確定句柄進(jìn)行歸約。 .我們可以通過(guò)兩個(gè)相鄰符號(hào)SiSi+1之間的關(guān)系來(lái)找到句柄：SiSi+1在句柄內(nèi)：必然有規(guī)則USiSi+1Si在句柄內(nèi)部，但是Si+1在句柄之后，必然有規(guī)則USi，且存在規(guī)范句型USi+1。如果Si+1在句柄內(nèi)，而Si在句柄外，那么必然存在規(guī)范句型SiU，且有USi+1。如何確定優(yōu)先關(guān)系？例2文法GS：(1) S bAb(2) A (B|a(3) B Aa)1.求=關(guān)系：由(1)：b=A A=b由(2)：(=B

10、由(3)：A=a a=)注意：行列與左右，空4.#3.求關(guān)系：由(1)：Bb ab )b由(3)：Ba aa )a2.求關(guān)系：由(1)(2)：b ba由(2)(3)：(A ( (.第二步：找句柄頭trjkiSk-1 Skkk-1=SkSk+1Si是句柄，用它查產(chǎn)生式表與一產(chǎn)生式右部相同Si=#且trj=#結(jié)束ik，Si UU是該產(chǎn)生式左部符號(hào)errorii+1Si trjjj+1YNNYYNYYNerrorN文法GS：(1) S bAb(2) A (B|a(3) B Aa)步驟符號(hào)棧輸入符號(hào)串動(dòng)作 1） # b(aa)b# 2） #b (aa)b# 3） #b( aa)b# 4） #b(a a

11、)b# 5） #b(A a)b# 6） #b(Aa )b# 7） #b(Aa) b# 8） #b(B b# 9） #bA b#10） #bAb #11） #S #對(duì)輸入串b(aa)b#的簡(jiǎn)單優(yōu)先分析過(guò)程簡(jiǎn)單優(yōu)先關(guān)系矩陣注意：何時(shí)移進(jìn)，何時(shí)歸約？歸約中如何確定句柄？#b(a#b,移進(jìn)b(,移進(jìn)(a,用Aa歸約A=a,移進(jìn)a=),移進(jìn)#b(Aa)b,用BAa)歸約#b(BBb,用A(B歸約A=b,移進(jìn)#bAbb#,用SbAb歸約接受6.2.4 簡(jiǎn)單優(yōu)先分析法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：技術(shù)簡(jiǎn)單 缺點(diǎn)：適用范圍小，分析表尺寸太大。 6.2.5 簡(jiǎn)單優(yōu)先分析法的局限性簡(jiǎn)單優(yōu)先分析法是有局限性的，它只適應(yīng)于簡(jiǎn)單優(yōu)先文

12、法，但是程序設(shè)計(jì)語(yǔ)言的文法一般都不是簡(jiǎn)單優(yōu)先文法，即使是關(guān)于表達(dá)式的文法也不是簡(jiǎn)單優(yōu)先文法。如果要使用簡(jiǎn)單優(yōu)先文法，就必須修改相應(yīng)語(yǔ)言的文法，使之成為簡(jiǎn)單優(yōu)先文法。例3 設(shè)文法G：EE+T|T TT*F|F E（E）|i【解】因?yàn)橛蠩E+T，所以有+=T，但由于T T*F，所以有+.+( = )注意：是三種有序關(guān)系，與數(shù)學(xué)中的不同，所以a=b不意味b=a，ab不意味b +，在(E+T)中得 + )a1 a2 a3 ai an# 優(yōu)先關(guān)系表總控程序X1Xn-1Xn#分析器的邏輯結(jié)構(gòu)：優(yōu)先關(guān)系表、分析棧、總控程序文法符號(hào)二.分析器結(jié)構(gòu)例7 GE：EE+E|E-E|E*E|E/E|EE|(E)|i

13、這是一個(gè)二義文法，要用算符優(yōu)先法分析由該文法所確定的語(yǔ)言句子。如：i+i*i 二義性文法的句子往往有不同的規(guī)范推導(dǎo)，句子i+i*i的兩種不同的規(guī)范歸約過(guò)程如下：第一個(gè)規(guī)范歸約過(guò)程(1) i+i*i(2) E+i*i(3) E+E*i(4) E+E*E(5) E+E(6) E第二個(gè)規(guī)范歸約過(guò)程(1) i+i*i(2) E+i*i(3) E+E*i(4) E*i(5) E*E(6) Ei是句柄E+E是句柄按傳統(tǒng)的習(xí)慣規(guī)定優(yōu)先級(jí)從高到低為:（0）i的優(yōu)先級(jí)最高（1）優(yōu)先級(jí)次于i，右結(jié)合（2）*和/優(yōu)先級(jí)次之，左結(jié)合（3）+和-優(yōu)先級(jí)最低，左結(jié)合（4）括號(hào)(,)的優(yōu)先級(jí)大于括號(hào)外的運(yùn)算符，小于括號(hào)內(nèi)的

14、運(yùn)算符，內(nèi)括號(hào)的優(yōu)先性大于外括號(hào)（5）#優(yōu)先性低于與其相鄰的算符算符優(yōu)先關(guān)系表 但是采用關(guān)于算符優(yōu)先順序和結(jié)合規(guī)則的規(guī)定，并按這種規(guī)定歸約，那么歸約過(guò)程就是唯一的。 矩陣元素空白處表示這兩個(gè)終結(jié)符不能相鄰,故沒(méi)有優(yōu)先關(guān)系分析過(guò)程 i+i*i步驟符號(hào)棧輸入串優(yōu)先關(guān)系 動(dòng)作1234567891011#i#E#E+#E+i#E+E#E+E*#E+E*i#E+E*E#E+E#E#i#*i#*i#i*i#+i*i#+i*i#i+i*i#+#+*+*#*#+#移進(jìn)移進(jìn)移進(jìn)移進(jìn)移進(jìn)規(guī)約規(guī)約規(guī)約規(guī)約規(guī)約接受算法: 當(dāng)棧頂項(xiàng)(或次棧頂項(xiàng))終結(jié)符的優(yōu)先級(jí)大于棧外的終結(jié)符的優(yōu)先級(jí)則進(jìn)行規(guī)約，否則移進(jìn)。分析過(guò)程是從符

15、號(hào)串開(kāi)始,根據(jù)相鄰終結(jié)符之間的優(yōu)先 關(guān)系確定句型的“句柄”,并進(jìn)行規(guī)約,直到識(shí)別符號(hào)E,最 后分析成功: i+i*iL（GE）出錯(cuò)情況: 1.相鄰終結(jié)符之間無(wú)優(yōu)先關(guān)系 2.對(duì)雙目運(yùn)行符進(jìn)行規(guī)約時(shí),符號(hào)棧中無(wú)足夠項(xiàng) 3.非正常結(jié)束狀態(tài) 6.3.2 算符優(yōu)先文法定義一.算符文法的定義定義6.1 對(duì)上下文無(wú)關(guān)文法G，若它所有的產(chǎn)生式的右部均不含相連的非終結(jié)符，則該文法為算符文法。顯然算符文法中沒(méi)有下列形式的產(chǎn)生式 P-QR 例GE: EEE|E*E |(E) |i GE: EEAE|(E)|i A|*注：算符文法保證了兩個(gè)運(yùn)算符之間只有一個(gè)操作數(shù)。 證明：用歸納法設(shè)是句子，S，即S01.n-1n推導(dǎo)

16、長(zhǎng)度是n，歸納起點(diǎn)n1時(shí)，S=0 1，即S，必存在一個(gè)規(guī)則S，而由算符文法的定義，文法的規(guī)則中無(wú)相鄰的非終結(jié)符，滿(mǎn)足性質(zhì)1。 假設(shè)n1，n-1滿(mǎn)足性質(zhì)1。若n-1A，A為非終結(jié)符。由假設(shè)的的尾符號(hào)和的首符號(hào)都不是非終結(jié)符，否則與假設(shè)矛盾。又若A是文法的規(guī)則，則有n-1n=而A是文法的規(guī)則，它不含兩個(gè)相鄰非終結(jié)符，所以 也不含兩個(gè)相鄰的非終結(jié)符，滿(mǎn)足性質(zhì)1。*性質(zhì)1：在算符文法中，任意句型都不含兩個(gè)相鄰的非終結(jié)符。性質(zhì)2：若Ab或bA出現(xiàn)在算符文法的句型中，其中AVN ,bVT,則中任何含b的短語(yǔ)必包含A。 證明：用反證法。由算符文法的性質(zhì)1可知。SbA若存在Bb，（b是僅含b但不含A的短語(yǔ)）這

17、時(shí)b和A不同時(shí)歸約，分屬于不同的短語(yǔ)，則必有SBA，這樣在句型BA中，存在相鄰的非終結(jié)符，所以與性質(zhì)1矛盾。故：中任何含b的短語(yǔ)必包含A，證畢。*注意：含b的短語(yǔ)必含A，含A的短語(yǔ)不一定含b。二.算符優(yōu)先文法的定義優(yōu)先關(guān)系的定義定義6.2 設(shè)G是一個(gè)不含產(chǎn)生式的算符文法，A、B、C是非終結(jié)符，a、b是終結(jié)符，則算符優(yōu)先關(guān)系定義為：1)a=b iff文法中有形如 Aab或A aBb2)ab iff文法中有形如 A Bb, 其中B a或B aV +1)當(dāng)棧頂為a，預(yù)掃描的下一字符為b，應(yīng)該執(zhí)行移進(jìn)操作，因?yàn)閍和b在同一個(gè)產(chǎn)生式A中。2)當(dāng)棧頂為a，預(yù)掃描的下一字符為b，應(yīng)該執(zhí)行移進(jìn)操作，期望先規(guī)約

18、出B，然后再試圖規(guī)約出A。3)當(dāng)棧頂為a，預(yù)掃描的下一字符為b，應(yīng)該先執(zhí)行規(guī)約操作，規(guī)約出B，然后再移入b。以上三種關(guān)系存在語(yǔ)法子樹(shù)如下圖：算符優(yōu)先文法的定義定義6.3 設(shè)有一OG文法,如果在任意兩個(gè)終結(jié)符之間,至多只有上述關(guān)系中的一種成立,則稱(chēng)該文法為算符優(yōu)先文法，也叫OPG（operator precedence grammar）文法。結(jié)論:算符優(yōu)先文法是無(wú)二義的。例GE: EEE|E*E |(E) |i EE+T| E-T|T TT*F| T/F|F F(E)|i例8 文法GE：EE+E|E*E|(E)|i所有規(guī)則中都沒(méi)有相鄰的非終結(jié)符，所以它是算符文法OG。由于EE+E 和EE*E，所

19、以有+*運(yùn)算符+和*之間存在兩種不同的優(yōu)先關(guān)系，所以該文法不是算符優(yōu)先文法OPG。+三.算符文法和算符優(yōu)先文法定義的意義 這兩個(gè)定義相當(dāng)于對(duì)文法的句型和可歸約的短語(yǔ)做了如下規(guī)定：設(shè)A1A2Ai-1AiAi+1An是文法G的一個(gè)句型， 1、若AiVN，則Ai-1、Ai+1 VT，即不許出現(xiàn)相繼兩個(gè)非終結(jié)符； 2、若B1B2Bm是當(dāng)前可歸約短語(yǔ)，并可歸約為Ai，則：a)B1B2Bm中不能有相繼兩個(gè)非終結(jié)符且相鄰的終結(jié)符優(yōu)先級(jí)別全相等；b)對(duì)于B1B2Bm中首終結(jié)符b有Ai-1 b；c)對(duì)于B1B2Bm中尾終結(jié)符b有b Ai+1。 注：實(shí)際上，可歸約短語(yǔ)是某產(chǎn)生式右部符號(hào)串，所以通過(guò)檢查G的每個(gè)產(chǎn)生

20、式的每個(gè)候選式，可以查找出任意優(yōu)先級(jí)相同的終結(jié)符序偶。要找出所有滿(mǎn)足關(guān)系 和 的終結(jié)符序偶，就要找出各非終結(jié)符B的首終結(jié)符集和尾終結(jié)符集。6.3.3 算符優(yōu)先關(guān)系表的構(gòu)造由定義直接構(gòu)造由算法構(gòu)造由關(guān)系圖形構(gòu)造一.由定義直接構(gòu)造算符優(yōu)先關(guān)系表1.求各個(gè)非終結(jié)符的首終結(jié)符集和尾終結(jié)符集 定義 （1）首終結(jié)符集FIRSTVT(B)=b|B b或B Cb.直觀(guān)含義：對(duì)于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的最左邊的終結(jié)符集合（允許其左邊有一非終結(jié)符集）思考：ABaBeFIRST（A）？FIRSTVT（A）？FIRST（B）？FIRSTVT（B）？（2）尾終結(jié)符集LASTVT(B)=a|B a或B . aC

21、直觀(guān)含義：對(duì)于非終結(jié)符B，其往下推導(dǎo)所可能出現(xiàn)的最右邊的終結(jié)符集合（允許其右邊有一非終結(jié)符集）思考：ABaBeFollow（A）？LASTVT（A）？Follow（B）？LASTVT（B）？（1）=關(guān)系直接看產(chǎn)生式的右部，若出現(xiàn)了Aab或AaBb,則a=b（2）關(guān)系求出每個(gè)非終結(jié)符B的FIRSTVT(B)若AaB,則bFIRSTVT(B),a關(guān)系求出每個(gè)非終結(jié)符B的LASTVT(B)若ABb,則aLASTVT(B),ab2.三種優(yōu)先關(guān)系的計(jì)算例9文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) PiFIRSTVT(E)=

22、#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)= ,),iLASTVT(P)= ),i2)=關(guān)系 逐條掃描產(chǎn)生式,由產(chǎn)生式(0)和(6),得#=#，（=）4)關(guān)系找：ABb的產(chǎn)生式E# ,則 LASTVT(E)#E+ ,則 LASTVT(E)+ T* ,則 LASTVT(T)* P ,則 LASTVT(P) E) ,則 LASTVT(E)3）關(guān)系找：AaB產(chǎn)生式#E：則#FIRSTVT(E)+T: 則+FIRS

23、TVT(T) *F: 則*FIRSTVT(F)F: 則FIRSTVT(F)(E: 則(FIRSTVT(E)注意技巧！1)求每個(gè)非終結(jié)符的FIRSTVT和LASTVT表達(dá)式文法算符優(yōu)先關(guān)系表：+*i()#+*i()#.二.由算法構(gòu)造算符優(yōu)先關(guān)系表1.構(gòu)造FIRSTVT集的兩條規(guī)則若有產(chǎn)生式Aa或ABa,則aFIRSTVT(A)若aFIRSTVT(B)，且有產(chǎn)生式AB,則aFIRSTVT(A)2.構(gòu)造FIRSTVT集的算法（1）前期工作建立一個(gè)布爾數(shù)組Fm，n(m為非終結(jié)符個(gè)數(shù)，n為終結(jié)符個(gè)數(shù))和一個(gè)后進(jìn)先出棧STACK將所有的非終結(jié)符排序，用iA表示非終結(jié)符A的序號(hào)，再將所有的終結(jié)符排序，用ja

24、表示終結(jié)符a的序號(hào)（2）算法目的要使數(shù)組每一個(gè)元素最終取值滿(mǎn)足：當(dāng)且僅當(dāng)aFIRSTVT(A)， FiA，ja的值為真（3）步驟【1】首先按第一條規(guī)則對(duì)數(shù)組元素賦初值為假，再經(jīng)分析讓所有初值為真的符號(hào)對(duì)(A, a)進(jìn)棧STACK。【2】若棧不空，則逐項(xiàng)出棧記為(B, a)，對(duì)每個(gè)形如AB的產(chǎn)生式，若FiA，ja為假，則變?yōu)檎媲?A, a)入棧；反復(fù)操作，直至棧空。（4）程序描述PROCEDURE INSERT(A,a); IFNOT FiA，ja THEN BEGIN FiA，ja:=TRUE PUSH(A，a） ONTOSTACK END INSERT過(guò)程說(shuō)明：當(dāng)aFIRSTVT(A)時(shí)置F

25、iA，ja為真，并將符號(hào)對(duì)（A,a）下推到棧中主程序BEGIN（MAIN）FORi從1到m，j從1到n DO FiA，ja :=FALSE; */賦值符*/ FOR 每個(gè)形如Aa或ABa的產(chǎn)生式 DOINSERT（A,a) WHILE STACK 非空DO BEGIN 把STACK的頂項(xiàng)記為（B,a）彈出去 FOR每個(gè)形如AB的產(chǎn)生式DOINSERT（A,a) ENDEND（MAIN）例10文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi 第一次掃描產(chǎn)生式后，棧STACK的初值為：（6） （P，i )（5） （P，

26、( )（4） （F，)（3） （T，* )（2） （E，+ )（1） （E，#)由產(chǎn)生式FP，TF，ET棧頂（6）的內(nèi)容逐次改變?yōu)椋海‵,i)，（T,i)，（E,i)再無(wú)右部以E開(kāi)始的產(chǎn)生式所以（E,i)彈出后無(wú)進(jìn)棧項(xiàng)， 這時(shí)棧頂（5）為（P，()，同樣由產(chǎn)生式： FP，TF，ET當(dāng)前棧頂（5）的變化依次為： （F,( )， （T,( ) ，（E,( ) （E,( )彈出后無(wú)進(jìn)棧項(xiàng),此時(shí)當(dāng)前棧頂（4）為（F，），由產(chǎn)生式TF，ET當(dāng)前棧頂（4）的變化依次為： （T, )， （E,) （E, )彈出后無(wú)進(jìn)棧項(xiàng)當(dāng)前棧頂（3）為（T,*），由產(chǎn)生式ET，棧頂（3）變?yōu)椋‥，*），以下逐次彈出棧頂元素

27、后，都再無(wú)進(jìn)棧項(xiàng)，直至棧空由算法可知，凡在棧中出現(xiàn)過(guò)的非終結(jié)符和終結(jié)符對(duì)，在相應(yīng)數(shù)組元素的布爾值為真，在下表的數(shù)組中用“1”表示+*i()#EETFP布爾數(shù)組的值111111111111111由上表，我們得出FIRSTVT（A）集合為：FIRSTVT（E）FIRSTVT（E） +，*，(，iFIRSTVT（T） *，(，iFIRSTVT（F） ，(，i FIRSTVT（P） (，i與直接由定義計(jì)算結(jié)果相同。3.構(gòu)造LASTVT集的兩條規(guī)則若產(chǎn)生式Aa，或AaB，則aLASTVT(A)若有產(chǎn)生式AB，且aLASTVT(B)，則aLASTVT(A)4.構(gòu)造LASTVT集的算法設(shè)一個(gè)棧ST,和一個(gè)布

28、爾數(shù)組H PROCEDURE INSERT(A,a) IF NOT HA,a THEN BEGIN HA,a:=TRUE;把(A,a)推進(jìn)ST棧; END;BEGIN FOR 每個(gè)非終結(jié)符號(hào)A和終結(jié)符號(hào)a DO HA,a:=FALSE; FOR 每個(gè)形如Aa或AaB的產(chǎn)生式 DO INSERT (A,a); WHILE ST棧非空 DO BEGIN 把ST棧的棧頂彈出,記為(B,a); FOR 每條形如AB的規(guī)則 DO INSERT(A,a); END OF WHILE; END;三.由關(guān)系圖形構(gòu)造算符優(yōu)先關(guān)系表圖中的結(jié)點(diǎn)為某個(gè)非終結(jié)符的FIRSTVT集或終結(jié)符對(duì)每一個(gè)形如Aa和ABa的產(chǎn)生式

29、，則構(gòu)造由FIRSTVT（A）結(jié)點(diǎn)到終點(diǎn)符結(jié)點(diǎn)用箭弧連接的圖形對(duì)每一形如AB的產(chǎn)生式，則對(duì)應(yīng)圖中由FIRSTVT（A）結(jié)點(diǎn)到FIRSTVT（B）結(jié)點(diǎn)用箭弧連接若某一非終結(jié)符A的FIRSTVT（A）經(jīng)箭弧有路徑能到達(dá)某終結(jié)符結(jié)點(diǎn)a，則有aFIRSTVT（A）FIRSTVT(E)FIRSTVT(E)FIRSTVT(T)FIRSTVT(F)FIRSTVT(P)#+* ( i練習(xí)：用關(guān)系圖求每個(gè)非終結(jié)符的LASTVT(A)的集合四.優(yōu)先關(guān)系表的構(gòu)造算法for 每條產(chǎn)生式BX1X2Xn for(i=1;in;i+) if ( Xi和Xi+1都是終結(jié)符) XiXi+1; if (i= n-2 且 Xi和X

30、i+2為終結(jié)符， Xi+1為非終結(jié)符) Xi =Xi+2; if (Xi為終結(jié)符而Xi+1為非終結(jié)符) for FIRSTVT(Xi+1)中的每個(gè)元素b XiXi+1; 例11 試構(gòu)造例10中文法GE的優(yōu)先關(guān)系表。 可根據(jù)優(yōu)先關(guān)系表判斷該文法是否為算符優(yōu)先文法如果表中元素不存在沖突，即文法的任何終結(jié)符至多只存在一種優(yōu)先關(guān)系，則該文法是一個(gè)算符優(yōu)先文法一.算符優(yōu)先分析句型的性質(zhì)算符文法的任一句型有如下形式（不允許Ni相連）：#N1a1N2a2.NnanNn+1#,若Niai.NjajNj+1為句 柄，則有ai-1 ai+1根據(jù)算符優(yōu)先文法的定義可知算符優(yōu)先分析句型有如下性質(zhì)： 如果aNb（或ab

31、）出現(xiàn)在句型r中，則a和b之間有且只有一種優(yōu)先關(guān)系即若ab則在r中必含有b而不含a的短語(yǔ)存在若ab則在r中必含有a而不含b的短語(yǔ)存在若ab則在r中必含有a必含b的短語(yǔ)存在，反之亦然.6.3.4 算符優(yōu)先分析算法說(shuō)明： 算符優(yōu)先分析法的歸約過(guò)程與規(guī)范歸約不同規(guī)范歸約 嚴(yán)格按照句柄進(jìn)行歸約，終結(jié)符和非終結(jié)符一起考慮，只要棧頂形成句柄，不管句柄內(nèi)是否包含終結(jié)符都要進(jìn)行歸約。 算符優(yōu)先分析法的歸約過(guò)程 在算符優(yōu)先分析中，僅研究終結(jié)符之間的優(yōu)先關(guān)系，而不考慮非終結(jié)符之間的優(yōu)先關(guān)系，但句柄是由終結(jié)符和非終結(jié)符一起構(gòu)成的，所以算符優(yōu)先分析相對(duì)來(lái)說(shuō)是非規(guī)范的分析。 例12 考慮非二義的表達(dá)式文法G(E)： E

32、E+T|T TT*F|F F(E)| i 識(shí)別語(yǔ)句 i+i*i的過(guò)程（1）規(guī)范歸約i+i*i#1.F+i*i# 6. E+T*F# 2.T+i*i# 7. E+T#3.E+i*i# 8. E# 4.E+F*i# 5.E+T*i#（2）算符優(yōu)先分析法的歸約過(guò)程-i+i*i#1.E+i*i# 4. E+T#2.E+T*i# 5. E# 3.E+T*F#兩種分析的語(yǔ)法樹(shù)對(duì)比EE TT T * FF F i i iEE T i T * F i i【注】當(dāng)單個(gè)非終結(jié)符是句柄時(shí)，算符優(yōu)先法無(wú)法確定該非終結(jié)符為句柄因?yàn)槲磳?duì)非終結(jié)符定義算符優(yōu)先關(guān)系，所以不能使用簡(jiǎn)單優(yōu)先關(guān)系查找單個(gè)非終結(jié)符組成的句柄。因此，為

33、了實(shí)現(xiàn)算符優(yōu)先方法進(jìn)行歸約，我們不能像在規(guī)范分析中那樣簡(jiǎn)單地使用“句柄”這個(gè)概念，即這種分析仍然是自底向上的，但不是嚴(yán)格的從左到右。因此，引進(jìn)素短語(yǔ)的概念。素短語(yǔ)是算符優(yōu)先分析中要涉及的一個(gè)十分重要的概念。二.素短語(yǔ) 所謂素短語(yǔ)是指這樣的一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且除它自身之外不再含有任何更小的素短語(yǔ)。 最左素短語(yǔ)是指處于句型最左邊的那個(gè)素短語(yǔ)。最左素短語(yǔ)是算符優(yōu)先分析算法的可歸約串。素短語(yǔ)是滿(mǎn)足下面條件的短語(yǔ)：（1）至少包含一個(gè)終結(jié)符號(hào)。（2）該短語(yǔ)不再包含滿(mǎn)足第一個(gè)條件的更小的短語(yǔ)。1.素短語(yǔ)和最左素短語(yǔ)定義例13文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(

34、5) FPF|P(6) P(E)(7) Pi句型#T+T*F+i#其短語(yǔ)有：最左素短語(yǔ)：T*F素短語(yǔ)：T*F， i*EET+ETFFTTi句型T+T*F+i的語(yǔ)法樹(shù)T+T*F+iT+T*FTT*Fi規(guī)范歸約每次歸約當(dāng)前句型中的句柄，上面句型的句柄是T算符優(yōu)先分析每次歸約當(dāng)前句型的最左素短語(yǔ)，T*F，去掉了單非終結(jié)符的歸約，因?yàn)槿糁挥幸粋€(gè)非終結(jié)符時(shí)，無(wú)法與句型中該非終結(jié)符的左部和右部的串比較優(yōu)先關(guān)系，也就無(wú)法確定該非終結(jié)符為句柄。2. 最左素短語(yǔ)的判斷定理:一個(gè)OPG句型的最左素短語(yǔ)是描述下列條件的最左子串:NiaiNjajNj+1 ai-1aj+1尋找最左素短語(yǔ)的方法: 從左到右掃描符號(hào)串w

35、,找到第一個(gè)ajaj+1時(shí),記下aj,再回掃, 找到第一個(gè)ai-1ai,此時(shí), NiaiNi+1ai+1NjajNj+1就是應(yīng)被子歸約的最左素短語(yǔ)。 注意:出現(xiàn)在aj左端和ai右端的非終結(jié)符號(hào)一定屬于 這個(gè)素短語(yǔ),因?yàn)槲覀兊倪\(yùn)算是中綴形式給出 的(OPG文法的特點(diǎn))NaNaNaN NaWaN例: 文法GE E:=E+T|T T:=T*F|F F:=(E)|i分析文法的句型T+T*F+i步驟句型關(guān)系最左子串規(guī)約符號(hào)1234#T+T*F+i#T+T+i#E+i#E+F#+#+#+#T*FT+TiE+FTEEF例14文法GE EE+T|T TT*F|F F(E)|i三.算符優(yōu)先分析規(guī)約過(guò)程算法基本思

36、想：先利用關(guān)系找到最左素短語(yǔ)的尾，再利用關(guān)系aj+1為止；2）最左素短語(yǔ)尾已在符號(hào)棧S的棧頂，由棧頂向下找最左素短語(yǔ)的頭符號(hào)，即找到第一個(gè)關(guān)系：ai-1ai；向棧中移進(jìn)符號(hào)，以形成最左素短語(yǔ)尋找滿(mǎn)足的sj a 的sj+1 ，即最左素短語(yǔ)的頭S：符號(hào)棧K：棧頂a:輸入符號(hào)j:指向素短語(yǔ)的前一個(gè)位置Q：Sj1k=1,sk=# ;/s為符號(hào)棧，#壓入棧，sk為棧頂項(xiàng)do a=getsym( );/讀入下一個(gè)符號(hào)給a if(skVT ) j=k; else j=k-1; while(sj a) do/在棧中尋找滿(mǎn)足的sj a 的sj+1 ， 即最左素短語(yǔ)的頭 Q= sj ; if(sj-1 VT )

37、j=j-1; else j=j-2; while(sj =Q) sj+1 sk N; /歸約最左素短語(yǔ) k=j+1; sk=N;/end of while if(sj a| sj = a)k=k+1;sk=a; /移進(jìn) else error while(a!=# | 符號(hào)棧中不是#S) 若出現(xiàn)j減1后的值小于等于0時(shí)，說(shuō)明輸入串有錯(cuò)，算法成功時(shí)，S中應(yīng)為#N#。算法并沒(méi)有指出應(yīng)把所找到的最左素短語(yǔ)歸約到哪一個(gè)非終結(jié)符號(hào)“N”。N是指這樣一個(gè)產(chǎn)生式的左部符號(hào)，此產(chǎn)生式的右部和Sj+1Sk構(gòu)成如下一一對(duì)應(yīng)關(guān)系：自左至右，終結(jié)符對(duì)終結(jié)符，非終結(jié)符對(duì)非終結(jié)符，而且對(duì)應(yīng)的終結(jié)符相同。由于非終結(jié)符對(duì)歸約沒(méi)

38、有影響，因此，非終結(jié)符根本可以不進(jìn)棧。算法說(shuō)明：1.算法中每次都取終結(jié)符進(jìn)行比較，當(dāng)棧頂符號(hào)不是終結(jié)符時(shí)，便取其下面符號(hào)（這時(shí)一定是終結(jié)符）2.歸約時(shí)檢查是否有與最左素短語(yǔ)對(duì)應(yīng)的產(chǎn)生式，查看產(chǎn)生式的右部：符號(hào)個(gè)數(shù)與該素短語(yǔ)的符號(hào)個(gè)數(shù)相等非終結(jié)符位置對(duì)應(yīng)，不管其符號(hào)名是什么終結(jié)符名字和位置都對(duì)應(yīng)相等；若有滿(mǎn)足以上條件的產(chǎn)生式才歸約，否則出錯(cuò)構(gòu)造方法非常簡(jiǎn)單分析速度也比較快診查錯(cuò)誤的能力較弱適用的范圍小算符優(yōu)先分析法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)缺點(diǎn)關(guān)于算符優(yōu)先分析的若干結(jié)論按算符優(yōu)先分析所確定的歸約子串恰好是當(dāng)前句型的最左素短語(yǔ)(證明略);算符優(yōu)先分析是自底向上的,但并不是規(guī)范歸約,因此,每步所得句型不是規(guī)范句型

39、;由于分析過(guò)程中只考慮兩個(gè)相鄰VT之間的關(guān)系,VN無(wú)關(guān)緊要,所以歸約所得的VN可任意命名;分析所得的語(yǔ)法樹(shù)不是真正意義上的語(yǔ)法樹(shù),而是其分枝構(gòu)架,它省略了單產(chǎn)生式的歸約過(guò)程;分析算法可容易地形式化:引入一分析棧,先將#壓入棧,分析時(shí)總是用棧頂符與當(dāng)前掃描符進(jìn)行比較,遇時(shí)回頭查找最左素短語(yǔ),歸約之;若兩個(gè)符號(hào)無(wú)關(guān)系,則報(bào)錯(cuò).若棧頂為開(kāi)始符S,掃描符為#,成功。6.3.5 優(yōu)先函數(shù)在算符優(yōu)先分析法中，文法終結(jié)符之間的優(yōu)先關(guān)系是用矩陣表示的，這樣需要大量的內(nèi)存空間。當(dāng)文法有n個(gè)終結(jié)符時(shí)，就需要(n+1)2個(gè)內(nèi)存單元(包括#)。實(shí)際實(shí)現(xiàn)中使用優(yōu)先函數(shù)來(lái)代替優(yōu)先矩陣表示優(yōu)先關(guān)系，對(duì)具有n個(gè)終結(jié)符的文法，它只需2(n+1)個(gè)內(nèi)存單元存放優(yōu)先函數(shù)，可以節(jié)省大量存儲(chǔ)空間。優(yōu)先關(guān)系表 (n+1)2 個(gè)單元優(yōu)先函數(shù)表 2(n+1) 個(gè)單元i+#i+#=i