編譯原理簡明教程（第3版）-課件 第6章 語法分析-自底向上

新工科建設(shè)·計算機(jī)類系列教材

免費(fèi)提供編譯原理16目錄第一章引言第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造2自下而上語法分析的基本思想自下而上語法分析面臨的問題及解決方法簡單優(yōu)先分析法算符優(yōu)先分析法LR(K)四種語法分析方法36語法分析

----自底向上分析方法學(xué)習(xí)目標(biāo)

目錄6.1自底向上語法分析技術(shù)6.2自底向上優(yōu)先分析方法6.3LR(K)分析方法6.4本章小結(jié)46.1自底向上語法分析技術(shù)6.1.1自底向上語法分析思想從輸入串開始，逐步進(jìn)行“歸約”,直到歸約到文法的開始符號。又稱為“移進(jìn)-歸約”分析法。

分析過程：采用一個先進(jìn)后出的分析棧，分析開始后，將輸入串自左向右逐個移進(jìn)分析棧，邊移入邊分析，一旦棧頂形成某個句型的句柄時，就進(jìn)行歸約，歸約后的非終結(jié)符入棧，繼續(xù)分析,直到輸入串處理完畢，同時棧中只有文法的開始符號。5例6.1G[S]：S→aAbBA→c|AcB→d|dB分析符號串a(chǎn)ccbdd6表6.1自底向上分析法對輸入串a(chǎn)ccbdd的分析過程

步驟分析棧句柄輸入符號串動作1#accbdd#移進(jìn)2#a

ccbdd#移進(jìn)3#ac

cbdd#移進(jìn)4#aAc

cbdd#歸約（A→c）5#aAc

bdd#移進(jìn)6#aAAc

bdd#歸約（A→Ac）7#aAb

dd#移進(jìn)8#aAbd

d#移進(jìn)9#aAbdd#移進(jìn)10#aAbdBd#歸約（B→d）11#aAbBdB#歸約（B→dB）12#S

aAbB#歸約（S→aAbB）7分析符號串#accbdd#分析過程見表6.1,共用了12步,其中”移進(jìn)7步”,歸約5步。規(guī)范歸約序列:accbddaAcbddaAbddaAbdBaAbBS

構(gòu)造語法樹過程見圖

?????1.如何確定句柄例：表6.1中第5步棧內(nèi)符號aAc

棧頂c或Ac可選規(guī)則A→c或A→Ac，選擇了A→Ac，

同樣，在第8步棧頂是d，可用B→d歸約但沒用，而

是在第9步用A→d歸約?！叩?步c不是句柄，第8步d也不是句柄?！?/p>

但不可能依靠事先給出句子的最右推導(dǎo)或語法樹來尋找

句柄。6.1.2自底向上分析難點(diǎn)9

2.文法中出現(xiàn)兩條以上規(guī)則右部相同的規(guī)則例：A→eB→eC→e

如何確定選擇哪條規(guī)則？例：G[S]：S→AB|cA→bA|aB→aSb|c

分析bbaacb

S→cB→cSABbAaSbbAca10

步驟

分析棧

規(guī)則

句柄

余留輸入串

1

#bbaacb#

2

#bbaacb#

3

#bbaacb#

4

#bbaacb#

5

#bbAAaaacb#

6

#bAAbAbAacb#

7

#AAbAbAacb#

8

#Aacb#

9

#Aacb#

10

#AaSSccb#

11

#AaSb#

12

#ABBaSbaSb#

13

#SSABAB#11

在第8步，a出現(xiàn)在棧頂，能否用A→a歸約？

在第9步，c出現(xiàn)在棧頂，能否用B→c歸約？126.2自底向上優(yōu)先分析方法優(yōu)先分析方法:簡單優(yōu)先分析方法算符優(yōu)先分析方法6.2.1簡單優(yōu)先分析方法131.簡單優(yōu)先關(guān)系

文法中兩個符號之間的三種優(yōu)先關(guān)系:"=，>，<"。

注：“=、<、>”不同于數(shù)學(xué)中的“=、>、<”，A>B并不一定意味著B<A，A=B也并不代表B=A。14A=B表示A和B優(yōu)先關(guān)系相等A>B表示A的優(yōu)先性高于BA<B表示A的優(yōu)先性低于B三種優(yōu)先關(guān)系的定義：

設(shè)A、B是文法G中任意兩個符號15++2、簡單優(yōu)先文法

定義6.1：文法G中①任意符號之間至多存在一種優(yōu)先關(guān)系。②任意產(chǎn)生式右部均不相同，則稱G為簡單優(yōu)先文法。

例：文法G[S]：S→bAb

A→(B|a

B→Aa)1617（1）求=關(guān)系由S→bAb,A→(B,B→Aa)

可得b=A,A=b,(=B,A=a,a=)（2）求<關(guān)系由S→bAb,且A(B,Aa得b<(,b<a

由A→(B，且B(B…,Ba…,BA…

得(<(,(<a,(<A（3）求>關(guān)系,由S→bAb,且A…),A…B,A…a

得)>b，B>b，a>b

由B→Aa）且A…),Aa,A…B

得)>a,a>a,B>a+++++++++++

上述關(guān)系也可用語法樹結(jié)構(gòu)表示SSSSbAbbAbbAbbAb

（Ba（B（BAa）Aa）

（BaAa）

B>ba>b)>a,B>a,a>ab<(b<ab<(,(<(,(<A（<a18把文法符號之間的關(guān)系用矩陣表示

——優(yōu)先關(guān)系矩陣SbA（Ba

）#S>b=<<>A==(<<=<B>>a>>=)>>#<<=1920

說明:

①文法符號相互之間的優(yōu)先關(guān)系是唯一的。共有四種情況“=、<、>、空”，其中“空”表示兩符號之間無相鄰關(guān)系。

②“#”定界符，“#”<所有符號，所有符號>“#”，當(dāng)然僅對與“#”有相鄰關(guān)系的文法符號而言。#S##bAb#.21

例6.2已知文法G[A]：

A→aAb|cd|e試判斷該文法是否是簡單優(yōu)先文法。首先，求=、<、>關(guān)系.22

.

Aabcde#A

=

a=<

<

<b

>

>c

=d

>

>e

>

>#<<<=例6.2文法的優(yōu)先關(guān)系矩陣3、簡單優(yōu)先分析算法①根據(jù)文法構(gòu)造優(yōu)先關(guān)系矩陣。②設(shè)有符號棧S，將輸入符號串“#…#”依次壓入S棧，同時檢查相鄰符號與的優(yōu)先關(guān)系，一旦>

出現(xiàn)時，停止入棧。③當(dāng)前棧頂符號為，從開始向左在棧中查找符號，直到找到<

為止。23④符號串…即為當(dāng)前句型的句柄，查找規(guī)則右部…

的產(chǎn)生式，若找到則將…

歸約為左部，若找不到則為出錯。⑤重復(fù)②~④步，直到分析完所有輸入符號，棧中只剩文法的開始符號，則分析成功，否則分析失敗。243、簡單優(yōu)先分析算法例：分析#aeb#步驟S棧優(yōu)先關(guān)系

輸入符號串

句柄

1#<aeb#2#a<eb#3#aeb#4#aAb#e5#aAb=#6#A分析成功#>aAb25>6.2.2算符優(yōu)先分析法

1、簡單表達(dá)式表示法中綴表示法a+b(a+b)*ca+b/c

前綴表示法+ab*+abc+a/bc（波蘭式）

后綴表示法ab+ab+c*abc/+（逆波蘭式）基本思想：算符優(yōu)先分析法是按照終結(jié)符的優(yōu)先關(guān)系確定“句柄”并進(jìn)行歸約。算符優(yōu)先分析法：一種分析速度快，使用較多的自底向上分析方法。事實(shí)上，不是一種規(guī)范歸約，適用于表達(dá)式的分析。261.逆波蘭式

無括號，形式簡單

運(yùn)算符次序與運(yùn)算次序完全相同

逆波蘭式：27波蘭邏輯學(xué)家1929年發(fā)明，在編譯程序出現(xiàn)之前，已用于算術(shù)表達(dá)式。逆波蘭式易于計算機(jī)處理（僅需一個棧，自左向右掃描逆波蘭式，遇運(yùn)算量壓棧，遇運(yùn)算符從棧頂取一個或兩個運(yùn)算量進(jìn)行運(yùn)算，運(yùn)算結(jié)果壓棧，繼續(xù)掃描…，直到整個表達(dá)式處理完畢）。在編譯程序中逆波蘭式可作為一種中間語言代碼。2.逆波蘭式的生成算術(shù)運(yùn)算遵守一定的運(yùn)算規(guī)則：

（，）→↑→*，/→+，-由此可得到一個運(yùn)算符優(yōu)先關(guān)系矩陣（見下頁）。逆波蘭表達(dá)式生成算法見圖6.3關(guān)鍵:比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先關(guān)系.當(dāng)

前的高,當(dāng)前進(jìn)棧,棧頂?shù)母?棧頂退棧。例：表達(dá)式(a+b）*c/d→ab+c*d/

轉(zhuǎn)換過程如表6.528運(yùn)算符優(yōu)先關(guān)系矩陣29關(guān)系右左

+-*/

↑（

）+>><<<<>->><<<<>*>>>><<>/>>>><<>↑>>>>><>

（<<<<<<=

）>>>>>>30表達(dá)式(a+b）*c/d→ab+c*d/31步驟輸入串當(dāng)前符號運(yùn)算符棧輸出串1(a+b)*c/d((

2a+b)*c/da(a3+b)*c/d+(+a4b)*c/db(+ab5)*c/d)(ab+6*c/d)

ab+7*c/d**ab+8c/dc*ab+c9/d//ab+c*10dd/ab+c*d11

ab+c*d/3.算符優(yōu)先文法定義6.3:算符優(yōu)先關(guān)系=、<、>a、b∈VT，A、B、C∈VN

①a=b，當(dāng)且僅當(dāng)文法中含有形如“A→…ab…”或“A→…aBb…”的產(chǎn)生式。定義6.2：算符文法-文法G中，A、B∈VN,若G中不會有形如“V→…AB…”的產(chǎn)生式。32例：G[E]：E→E+E|E*E|(E)|i算符文法②a<b，當(dāng)且僅當(dāng)文法中含有形如“A→…aB…”的產(chǎn)生式，其中Bb…或BCb…。③a>b，當(dāng)且僅當(dāng)文法中含有形如“A→…Bb…”的產(chǎn)生式，其中B…a或B…aC。++++3334定義算符優(yōu)先文法例G[E]:E→E+E|E*E|(E)|i(不是一個算符優(yōu)先文法)E→E+EE→E*EEE*EEE+E+<*+>*定義6.4：算符優(yōu)先文法-文法G是一個不含有空產(chǎn)生式的算符文法，且G中的兩個終結(jié)符之間，至多只有一種優(yōu)先關(guān)系。4.算符優(yōu)先關(guān)系矩陣的構(gòu)造方法⑴首先對文法G的每個非終結(jié)符A構(gòu)造兩個集合。FIRSTVT(A)={a|Aa…或ABa…，其中a∈,B∈}LASTVT(A)={a|A…a或A…aB，其中a∈,B∈}⑵確定終結(jié)符對之間的優(yōu)先關(guān)系。++++35＝關(guān)系，逐個查看產(chǎn)生式，由A→…ab…或A→…aBb…，找到a＝b。1<關(guān)系，查找文法中形“P→…aA…”的產(chǎn)生式，則對任何b∈FIRSTVT(A)，有a<b。2>關(guān)系，查找文法中形如“P→…Ab…”的產(chǎn)生式，則對任何a∈LASTVT(A)，有a>b。336例:G[E]E→E+T|TT→T*F|FF→(E)|i計算FIRSTVT、LASTVT集FIRSTVT(E)={(,i,+,*}FIRSTVT(T)={(,i,*}FIRSTVT(F)={(,i}LASTVT(E)={+,*,),i}LASTVT(T)={*,),i}LASTVT(F)={),i}=關(guān)系

由F→(E)得(=)3712<關(guān)系由E→E+T+<FIRSTVT(T)即+<{*,(,i}由T→T*F*<FIRSTVT(F)即*<{(,i}由F→(E)(<FIRSTVT(E)即(<{+,*,(,i}3>關(guān)系由E→E+TLASTVT(E)>+即{+,*,),i}>+由T→T*FLASTVT(T)>*即{*,),i}>*由F→(E)LASTVT(E)>)即{+,*,),i}>)438G[E]的算符優(yōu)先關(guān)系矩陣

+*()i#+><<><>*>><><>(<<<=<)>>>>i>>>>#<<<<=395.算符優(yōu)先分析算法

算符優(yōu)先分析法是一種自底向上的方法，但不是規(guī)范歸約，即歸約時不一定是句柄。

定義：素短語——至少包含一個終結(jié)符，且除自身不含其它素短語的短語。

最左素短語——句型最左邊的素短語。E

E+T

E+TFTT*Fi例：句型：T+T*F+i

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

素短語：T*F,i

最左素短語：T*F40

#---定界符，終結(jié)符，可有可無的非終結(jié)符

最左素短語

…

滿足：

<

=,=,…,=>

算符優(yōu)先分析類似于簡單優(yōu)先分析法，只是歸

約的不是句柄，而是最左素短語。##…41句型的一般形式

步驟

當(dāng)前句型

優(yōu)先關(guān)系最左素短語歸約符號12345.#T+T*F+i# #<+,+<*,*>+T*F T#T+T+i# #<+,+>+ T+T E#E+i# #<+,+<i,i># i F#E+F# #<+,+># E+F E#E#42表6.7T+T*F+i的分析過程設(shè)：…最左素短語中包含，非終結(jié)符。

這種分析方法起主導(dǎo)作用的是終結(jié)符之間的優(yōu)先關(guān)系，非終結(jié)符的名字無所謂，且單個非終結(jié)符也不是素短語。所以，歸約過程得到一個語法樹的樹架。

NN+NN+NiN*N

算符優(yōu)先分析法的流程圖見下圖（圖6.6）

43表6.8句子(i+i)*i的分析過程

44步驟符號棧S[i]優(yōu)先關(guān)系輸入符號(a)待分析串1#<(i+i)*i#2#(<i+i)*i#3#(i>+i)*i#4#(N<+i)*i#5#(N+<i)*i#6#(N+i>)*i#7#(N+N>)*i#8#(N=)*i#9#(N)>*i#10#N<*i#11#N*<i#12#N*i>#

13#N*N>#

14#N分析成功456.優(yōu)先函數(shù)

優(yōu)先關(guān)系矩陣，當(dāng)文法符號或終結(jié)符較多時會變得很大。解決方法：壓縮矩陣，去掉空元素。

構(gòu)造優(yōu)先函數(shù)。定義6.6：優(yōu)先函數(shù)f、g

已知文法G，由算符優(yōu)先關(guān)系矩陣，若文法的每個終結(jié)符x、y滿足：1）當(dāng)x>y時，f(x)>g(y)2）當(dāng)x<y時，f(x)<g(y)3）當(dāng)x=y時，f(x)=g(y)f—內(nèi)優(yōu)先函數(shù)（入棧優(yōu)先函數(shù)）g—外優(yōu)先函數(shù)（比較優(yōu)先函數(shù)）466.優(yōu)先函數(shù)

表6.9G(E

)的優(yōu)先函數(shù)終結(jié)符優(yōu)先函數(shù)+*()i#f351551g2461616.3LR(K)分析方法

LR(K)根據(jù)分析棧的當(dāng)前內(nèi)容以及向前查看k個符號來決定是否移進(jìn)或歸約。48知識回顧自底向上語法分析思想和分析難點(diǎn)簡單優(yōu)先和算符優(yōu)先分析方法6.3LR(K)分析方法

LR(K)是一種有效的自底向上語法分析方法。它的適應(yīng)范圍廣，分析速度快，且能準(zhǔn)確及時地發(fā)現(xiàn)語法錯誤，所以是當(dāng)前最一般的語法分析方法。

LR(K):根據(jù)分析棧的當(dāng)前內(nèi)容以及向前查看k個符號來決定是否移進(jìn)或歸約。49

LR(0)是基礎(chǔ)，但分析能力低，局限性大

SLR(1)“簡單LR”實(shí)現(xiàn)容易，能力較強(qiáng)，不適合有些文法

LR(1)分析能力最強(qiáng)，適用于大多數(shù)文法，但工作量大

LALR(1)能力介于SLR(1)與LR(1)之間，空間節(jié)省6.3LR(K)分析方法501234LR語法分析方法類型6.3.1LR分析思想及邏輯結(jié)構(gòu)1、LR分析思想及邏輯結(jié)構(gòu)基本思想：掃描輸入串，進(jìn)行自底向上分析，在分析每一步記住當(dāng)前已移進(jìn)和歸約的文法符號，同時向前查看k個輸入符號，由此確定棧頂是否出現(xiàn)句柄，從而進(jìn)行歸約或移進(jìn)，直至分析完畢。51

→輸入串

#…

…#

分析表總控程序控制機(jī)構(gòu)……#下推分析棧52LR分析法的邏輯結(jié)構(gòu)

2.

LR分析表組成

兩部分：ACTION—分析動作表

GOTO—狀態(tài)轉(zhuǎn)換表

~為分析器的狀態(tài)，~為文法終結(jié)符和定界

符，~為文法符號

ACTION表：

輸入符號狀態(tài)…ACTION[，]

………ACTION[，]…ACTION[，]53GOTO表:

分析動作表中，ACTION[，]規(guī)定棧頂狀態(tài)為，輸入符號為時，所執(zhí)行的動作，有以下四種：

文法符號狀態(tài)…GOTO[，]……GOTO[，]…GOTO[，]542.

LR分析表組成移進(jìn)（S），把（Si,aj）的下一個狀態(tài)移入狀態(tài)棧，輸入符號移入文法符號棧，繼續(xù)掃描下個符號。歸約（r），當(dāng)棧頂形成句柄時，按相應(yīng)的產(chǎn)生式進(jìn)行歸約，若產(chǎn)生式右端長度為n，則從狀態(tài)棧和文法符號棧的棧頂退n個符號，再將歸約后的文法符號移入符號棧，新的狀態(tài)進(jìn)入狀態(tài)棧。接受（acc），當(dāng)輸入串分析結(jié)束（只剩下“#”）時，文法符號棧中只剩下文法的開始符號時，分析成功，終止分析。報錯（error），當(dāng)狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，說明輸入串有錯，報告出錯信息。狀態(tài)轉(zhuǎn)換表中，GOTO[Si，xj]規(guī)定了當(dāng)棧頂狀態(tài)為Si，文法符號為Sj時,xj應(yīng)轉(zhuǎn)向的下一個狀態(tài)(用j表示）。55231413、LR分析過程例6.3G[A]：A→B，AA→BB→aB→bG[A]的LR分析表狀態(tài)ab,#AB

ACTIONGOTOS0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S426S6r156對符號串＃a，b＃的分析過程

步驟狀態(tài)棧符號棧余留符號產(chǎn)生式ACTION/GOTO12345678S0 # a,b# S3S0S3 #a ,b# γ32S0S2 #B ,b#B→a S5S0S2S5 #B, b# S4S0S2S5S4#B,b # γ42S0S2S5S2#B,B #B→b γ26S0S2S5S6#B,A #A→B γ11S0S1 #A #A→B,A acc576.3.2LR(0)的分析方法

LR(k)中k=0說明無須向前查看符號.LR(0)是其它LR分析法的基礎(chǔ).

例6.1

在分析的第5步棧中符號為#aAc時,

用A→Ac歸約而沒有A→c.

實(shí)際上與棧中符號串的前綴有關(guān).58表6.1自底向上分析法對輸入串a(chǎn)ccbdd的分析過程

步驟分析棧句柄輸入符號串動作1#accbdd#移進(jìn)2#a

ccbdd#移進(jìn)3#ac

cbdd#移進(jìn)4#aAc

cbdd#歸約（A→c）5#aAc

bdd#移進(jìn)6#aAAc

bdd#歸約（A→Ac）7#aAb

dd#移進(jìn)8#aAbd

d#移進(jìn)9#aAbdd#移進(jìn)10#aAbdBd#歸約（B→d）11#aAbBdB#歸約（B→dB）12#S

aAbB#歸約（S→aAbB）59分析符號串#accbdd#分析過程見表6.1,共用了12步,其中”移進(jìn)7步”,歸約5步。規(guī)范歸約序列:accbddaAcbddaAbddaAbdBaAbBS

構(gòu)造語法樹過程見圖

?????問題

61?LR分析過程中，需要確定當(dāng)前句型的句柄進(jìn)行歸約，如何在當(dāng)前句型中尋找句柄？解決：直接尋找句柄有困難，可以迂回尋找含有句柄的字符串總結(jié)與思考LR方法的分析思想與分析過程LR分析方法與優(yōu)先方法的區(qū)別延展學(xué)習(xí)：DonaldErvinKnuth生平以及對計算機(jī)所作出的貢獻(xiàn)基礎(chǔ)軟件領(lǐng)域中編譯技術(shù)發(fā)展現(xiàn)狀1.規(guī)范前綴和可歸前綴定義6.7:已知文法G[S],若有規(guī)范推導(dǎo)S

αβ,β∈

則稱α為規(guī)范前綴,又稱活前綴.(規(guī)范前綴中不含句柄之后的符號)若α是句柄的活前綴,且句柄處在α的最右端,則稱α是可歸前綴.分析棧中的文法符號+余留輸入串規(guī)范句型r*62例:文法G[S]:

S→aAbB

A→c|Ac

B→d|dBS

aAbBAcdBcdSaAbBaAbdBaAbddaAcbddaccbddrrrrr63規(guī)范前綴

規(guī)范句型

規(guī)范前綴

可歸前綴accbdda,acacaAcbddaA,aAcaAcaAbddaA,aAb,aAbd,aAbddaAbddaAbdBaAbdBaAbdBaAbBaAbBaAbB64規(guī)范前綴和可歸前綴

65識別規(guī)范前綴的有限自動機(jī)構(gòu)造一個識別規(guī)范前綴的有限自動機(jī)

①將終結(jié)符和非終結(jié)符都看作輸入符號.②每當(dāng)一個符號進(jìn)棧時,狀態(tài)發(fā)生變化.③當(dāng)識別完可歸前綴時,到達(dá)終態(tài).S0S1S2S3S4S5S0S7S8S9acAcddBBb

66規(guī)范前綴由狀態(tài)圖可以看出:

⑴從S0到任一狀態(tài)形成的符號串構(gòu)成某規(guī)范句型的規(guī)范前綴.

⑵從S0到任一終止?fàn)顟B(tài)形成的符號串構(gòu)成某規(guī)范句型的可歸前綴.2.LR(0)項目

規(guī)范前綴與句柄的關(guān)系:

規(guī)范前綴完全包含句柄----棧頂出現(xiàn)句柄可歸約

規(guī)范前綴只含句柄的一部分符號----棧頂有一部

分句柄,期待其余

規(guī)范前綴不含句柄的任何符號----棧頂未出現(xiàn)句

柄,移進(jìn)符號定義：文法G，產(chǎn)生式右部標(biāo)上特殊符號“△”“·”，這樣的產(chǎn)生式稱為文法LR(0)項目，簡稱項目。67例：E→E+T項目：E→△E+TE→·E+TE→E△+TE→E·+TE→E+△TE→E+·TE→E+T△E→E+T·項目中出現(xiàn)在“△”后面的符號稱為該項目的后繼符號。

①后繼符號為終結(jié)符或非終結(jié)符

E→△E+TE→E△+TE→E+△T②后繼符號為空

E→E+T△或68根據(jù)“△”所在位置和項目的后繼符號可分項目為四種：①移進(jìn)項目

如A→α△xβ,α,β∈V*,

x∈VT分析時x移入符號棧.(E→E△+T)②待約項目

A→α△xβ,α,β∈V*,

x∈VN期待讀入歸約到x的其它輸入符號.E→△E+T

E→E+△T69LR(0)項目③歸約項目

A→α△,α∈V*

如E→E+T△表示產(chǎn)生式右部已形成,可歸約

④接受項目

若為開始符號→α△,α∈V*

特殊的歸約項目,歸約后分析結(jié)束.四種項目代表LR分析器的四種不同狀態(tài).△xx△表示分析器從一種狀態(tài)另一種狀態(tài).70LR(0)項目3.構(gòu)造識別規(guī)范前綴的有限自動機(jī)例6.4:文法G[S]:S→aA|bA→bA|c

將文法G[S]拓廣為G[],增加→S

保證了接受項目的唯一性.71G[]的LR(0)項目:

→△S

→S△S→△aAS→a△AS→aA△S→△b

S→b△

A→△bA

A→b△AA→bA△A→△cA→c△72構(gòu)造LR(0)項目對應(yīng)的NFA:①LR(0)的一個項目對應(yīng)NFA的一個狀態(tài).②第一個項目(→△S)作為初始狀態(tài).③歸約項目均作為終止?fàn)顟B(tài).④對于同一個產(chǎn)生式,A→αxβ項目A→α△xβ變?yōu)轫椖緼→αx△β對應(yīng)Si→Sj⑤若項目中“△”后的符號是一個非終結(jié)符(如A)則畫Si→所有A→△γ的狀態(tài).上例中18個LR(0)項目作為NFA的18個狀態(tài).初始狀態(tài)→△S,終止?fàn)顟B(tài)有7個.

見圖6.11xε73構(gòu)造LR(0)項目對應(yīng)的NFA:74圖6.11識別規(guī)范前綴的NFA構(gòu)造LR(0)項目對應(yīng)的DFA:75圖6.12識別規(guī)范前綴的DFA

由此構(gòu)造的NFA能識別文法G的所有規(guī)范前綴.所以,又稱之為識別規(guī)范前綴的NFA.

使用第3章NFA→DFA轉(zhuǎn)化算法.可得到一個識別規(guī)范前綴的DFA,讀DFA的狀態(tài)是一個項目集.如圖6.12定義：構(gòu)造識別一個文法規(guī)范前綴的DFA的項目集（狀態(tài)）的全體，稱為LR（0）項目集規(guī)范族，（上例12個狀態(tài)對應(yīng)12個項目集）。764.LR(0)項目集規(guī)范族的構(gòu)造

基本項目集(BASIC)項目集的閉包(CLOSURE)對于文法G[S],首先進(jìn)行拓廣[]假定“I”是文法[]中的任一項目集。則：①

BASIC(I)={A→αB△β|A→α△Bβ∈J}

說明I是J關(guān)于符號B的后繼狀態(tài).②

CLOSURE(I)的計算a.BASIC(I)

CLOSURE(I)b.若A→α△Bβ∈CLOSURE(I),且B∈VN則B→△γ∈CLOSURE(I)c.重復(fù)b,直到CLOSURE(I)不再增加為止.一個狀態(tài)的項目集分為兩部分77

求文法的LR(0)項目集規(guī)范族:

【例6.5】:G[S]:S→A|BA→aAb|cB→d把G[S']第一個項目S'→▲S作為初始狀態(tài)項目集的核，通過求核的閉包，求得初始狀態(tài)的項目集，然后求初始狀態(tài)的后繼狀態(tài)，再求得各后繼狀態(tài)的項目集閉包，...，依次類推，直到不出現(xiàn)新的狀態(tài)為止。78拓廣文法G[]:

（0）→S⑴S→A⑵S→B⑶A→aAb⑷A→c⑸B→d若I={S→△A},則CLOSURE(I)={S→△A,A→△aAb,A→△c}規(guī)定:

①同一狀態(tài)的項目集中,若不同項目其后繼符號相同時,

后繼狀態(tài)也相同.

②不同狀態(tài)的項目集中,若出現(xiàn)對應(yīng)相同的項目時,則

后繼狀態(tài)也相同.79對于上例構(gòu)造G[]的LR(0)項目集規(guī)范族如下:

狀態(tài)

項目集

后繼符號

后繼狀態(tài)

S0B→△d}dS6

A→△ccS5A→△aAbaS4S→△BBS3S→△AAS2

{→△SSS1

S1 {→S△}#→SS9S2{S→A△} #S→A S9S3 {S→B△} #S→BS9

S4{A→a△AbAS7

A→△aAbaS4A→△c}cS5

80例如:項目集{A→α△aβ,B→γ△}移進(jìn)—?dú)w約沖突

項目集{A→α△,B→β△}歸約—?dú)w約沖突

S5{A→c△}#A→c S9S6{B→d△}#B→d S9S7{A→aA△b} b S8S8{A→aAb△}#A→aAb S9S9定義：LR(0)文法

文法的LR(0)項目集規(guī)范族中不存在“移進(jìn)一歸約”沖突或“歸約一歸約”沖突。81相容的項目集需滿足以下條件:①無移進(jìn)項目與歸約項目并存.②無歸約項目與歸約項目并存.5.LR(0)分析表的構(gòu)造

設(shè)GO是一個狀態(tài)轉(zhuǎn)換函數(shù)GO(Si,x)=Sj

即Sj={A→αx△β|A→α△xβ∈Si}Sj是Si關(guān)于文法符號x的后繼狀態(tài).82

設(shè)有文法G[]①對于A→α△Xβ∈Si,且GO[Si,X]=Sj,X∈VN,則置GOTO[Si,X]=j.②對于A→α△aβ∈Si,且GO[Si,a]=Sj,a∈VT,則置ACTION[Si,a]=Sj.③對于A→α△∈Si,且A→α是文法G[]的第j個產(chǎn)生式,

則對所有的a∈VT,均置ACTION[Si,a]=γj.④對于→S△∈Si,則置ACTION[Si,#]=acc.⑤其他情況均置出錯.83LR(0)分析表構(gòu)造算法：構(gòu)造上例中的LR(0)分析表：

狀態(tài)ACTIONabcd#GOTOSAB

S0 S4S5S6123S1 accS2γ1γ1γ1γ1γ1S3 γ2γ2γ2γ2γ2S4S4S5

7S5 γ4γ4γ4γ4γ4S6 γ5γ5γ5γ5γ5S7 S8S8 γ3γ3γ3γ3γ384利用LR(0)分析表對輸入串進(jìn)行分析過程①若ACTION[Si,a]=Sj,a∈VT,則a入符號棧,Sj入狀態(tài)棧.②若ACTION[Si,a]=γj,a∈VT∪’#’,則按第j個產(chǎn)生式歸約,符號棧和狀態(tài)棧相應(yīng)元素退棧,歸約后的文法符號進(jìn)符號棧.③若ACTION[Si,a]=acc,a=’#’,則分析成功.④若GOTO[Si,x]=j,X∈VN,則Sj入狀態(tài)棧.(前一個動作是歸約,歸約后的非終結(jié)符是X)⑤若ACTION[Si,a]=空白,則轉(zhuǎn)向出錯處理.對輸入串“#aacbb#”的分析過程見表6.1685利用分析表對輸入串#aacbb#分析如下:步驟

狀態(tài)棧符號棧

輸入串ACTIONGOTO

acc(A→c)(A→aAb)(A→aAb)(S→A)1S0 #

aacbb# S42S0S4 #a acbb# S43S0S4S4 #aa cbb# S54S0S4S4S5 #aac bb# γ47

5S0S4S4S7#aaA bb# S86S0S4S4S7S8#aaAb b# γ377S0S4S7 #aA b# S88S0S4S7S8 #aAb # γ329S0S2 #A # γ1110 S0S1 #S #866.3.3SLR(1)分析方法

LR(0)文法要求項目集中不含沖突項目,大多數(shù)文法不能滿足.

SLR(1)分析方法,利用向前看一個符號解決LR(0)項目集中的沖突.

因為只對有沖突的狀態(tài)才向前看一個符號,所以是簡單的LR(1)方法.87例:表達(dá)式文法G[]:(0)→E

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→(E)

(6)F→i88構(gòu)造項目集的規(guī)范族:S0:{→△E,E→△E+T,E→△T,T→△T*F,T→△F,F→△(E),F→△i}S1:{→E△,E→E△+T}S2:{E→T△,T→T△*F}S3:{T→F△}S4:{F→(△E),E→△E+T,E→△T,T→△T*F,T→△F,F→△(E),F→△i}S5:{F→i△}S6:{E→E+△T,T→△T*F,T→△F,F→△(E),F→△i}89S7:{T→T*△F,F→△(E),F→△i}S8:{F→△(E),E→E△+T}S9:{E→E+T△,T→T△*F}S10:{T→T*F△}S11:{F→(E)△}S12:{}90沖突項目集:S1

移進(jìn)—接受沖突

S2,S9移進(jìn)—?dú)w約沖突分析表如表6.19,出現(xiàn)多重定義的元素.

解決沖突的辦法:

對于一個狀態(tài)Si的項目集:Si={A→α△β,B→γ△,C→δ△}其中,

α,γ,δ∈V*First(β)∈VT存在“移進(jìn)—?dú)w約”“歸約—?dú)w約”沖突

若Follow(B)∩Follow(C)∩First(β)=ф則當(dāng)輸入符號為a時,(a∈VT∪’#’)⑴若a∈First(β),則移進(jìn)a.⑵若a∈Follow(B),則用B→γ進(jìn)行歸約.⑶若a∈Follow(C),則用C→δ進(jìn)行歸約.⑷其他報錯.91SLR(1)分析表構(gòu)造算法:①對于A→α△Xβ∈Si,且GO[Si,X]=Sj,X∈VN,則GOTO[Si,X]=j.②對于A→α△aβ∈Si,且GO[Si,a]=Sj,a∈VT,則置ACTION[Si,a]=Sj.③對于A→α△∈Si,,且A→α是文法G[]的第j個產(chǎn)生式,則對終結(jié)符a(包括’#’).

若a∈Follow(A),則置ACTION[Si,a]=γj.④對于→S△∈Si,則置ACTION[Si,#]=acc.⑤其他情況均置出錯.定義：SLR(1)文法，按SLR(1)分析表構(gòu)造算法的分析表中不含有沖突動作。92表達(dá)式文法的項目集S1={→E△,E→E△+T}Follow()={#}First(+T)={+}

{#}∩{+}=фS2={E→T△,T→T△*F}Follow(E)={+,),#}First(*F)={*}

{+,),#}∩{*}=ф93S9={E→E+T△,T→T△*F}Follow(E)={+,),#}First(*F)={*}

{+,),#}∩{*}=фS1,S2,S9中的沖突都可解決,所以G[E]是SLR(1)文法.94表達(dá)式文法的項目集構(gòu)造SLR(1)分析表如表6.20所示.對符號串#i*(i+i)#的分析過程如表6.21所示95狀態(tài)ACTIONGOTOi+*()#ETFS0S5

S4

123S1

S6

acc

S2

r2S7

r2r2

S3

r4r4

r4r4

S4S5

S4

823S5

r6r6

r6r6

S6S5

S4

93S7S5

S4

10S8

S6

S11

S9

r1S7

r1r1

S10

r3r3

r3r3

S11

r5r5

r5r5

表6.20算術(shù)表達(dá)式文法的SLR(1)分析表96步驟狀態(tài)棧符號棧產(chǎn)生式輸入串分析表1S0#

i*(i+i)#S52S0S5#i

*(i+i)#r6、33S0S3#FF→i*(i+i)#r4、24S0S2#TT→F*(i+i)#S75S0S2S7#T*

(i+i)#S46S0S2S7S4#T*(

i+i)#S57S0S2S7S4S5#T*(i

+i)#r6、38S0S2S7S4S3#T*(FF→i+i)#r4、29S0S2S7S4S2#T*(TT→F+i)#r2、810S0S2S7S4S8#T*(EE→T+i)#S611S0S2S7S4S8S6#T*(E+

i)#S512S0S2S7S4S8S6S5#T*(E+i

)#r6、313S0S2S7S4S8S6S3#T*(E+FF→i)#r4、914S0S2S7S4S8S6S9#T*(E+TT→F)#r1、815S0S2S7S4S8#T*(EE→E+T)#S1116S0S2S7S4S8S11#T*(E)F→(E)#r5、1017S0S2S7S10#T*F

#r3、218S0S2#TT→T*F#r2、119S0S1#EE→T#acc表6.21符號串#i*(i+i)#的分析過程步驟狀態(tài)棧符號棧產(chǎn)生式輸入串分析表1S0#

i*i#S52S0S5#i

*i#r6、33S0S3#FF→i*i#r4、24S0S2#TT→F*i#S75S0S2S7#T*

i#S56S0S2S7S5#T*i

#r6、107S0S2S7S10#T*F

F→i#r3、28S0S2#TT→T*F#r2、19S0S1#EE→T#acc

例：符號串

i*i

的SLR(1)分析過程6.3.4LR(1)分析方法

SLR(1)算法簡單,是一種較為實(shí)用的方法,但仍有一些程序設(shè)計語言的文法不是SLR(1)文法.

LR(1)是一種功能最強(qiáng)的LR方法.例:G[S]:S→L=R|RL→*R|iR→L

拓廣文法G[]:(0)→S(1)S→L=R(2)S→R(3)L→*R(4)L→i(5)R→L98G[]項目集的規(guī)范族如下:

狀態(tài)

項目集

后繼符號

后繼狀態(tài)

S3{S→R△} #S→RS9S2R→L△}#R→LS9{S→L△=R=S6

S1 {→S△} #→SS9

R→△L}LS2L→△i

iS5L→△*R*S4S→△RRS3

S→△L=RLS2

{→△SSS1

S099

S9S8 {S→L=R△} #S→L=RS9S7 {L→*R△} #L→*RS9S6L→△i}iS5L→△*R*S4

R→△LLS2

{S→L=△RRS8

S5 {L→i△} #L→iS9L→△i}iS5

L→△*R*S4R→△LLS2

{L→*△RRS7

S4100

S2={S→L△=R,R→L△}First(=R)={=}Follow(R)={#,=}

{=}∩{#,=}={=}≠ф

所以,該文法不是SLR(1)文法,不能用SLR(1)方法解決沖突。101【例6.6】已知文法G[S′]：(0)S′→S(1)S→CbBA(2)A→Aab(3)A→b(4)B→a(5)B→Ca(6)C→a·項目集S6={B→a△,C→a△}，存在“歸約-歸約”沖突?！ろ椖考疭8={S→CbBA△,