編譯原理簡(jiǎn)明教程（第3版）-課件 第6章 語(yǔ)法分析-自底向上

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

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

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

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

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

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

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

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

步驟分析棧句柄輸入符號(hào)串動(dòng)作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分析符號(hào)串#accbdd#分析過(guò)程見(jiàn)表6.1,共用了12步,其中”移進(jìn)7步”,歸約5步。規(guī)范歸約序列:accbddaAcbddaAbddaAbdBaAbBS

構(gòu)造語(yǔ)法樹過(guò)程見(jiàn)圖

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

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

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

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

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

句柄。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)先分析方法:簡(jiǎn)單優(yōu)先分析方法算符優(yōu)先分析方法6.2.1簡(jiǎn)單優(yōu)先分析方法131.簡(jiǎn)單優(yōu)先關(guān)系

文法中兩個(gè)符號(hào)之間的三種優(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中任意兩個(gè)符號(hào)15++2、簡(jiǎn)單優(yōu)先文法

定義6.1：文法G中①任意符號(hào)之間至多存在一種優(yōu)先關(guān)系。②任意產(chǎn)生式右部均不相同，則稱G為簡(jiǎn)單優(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)系也可用語(yǔ)法樹結(jié)構(gòu)表示SSSSbAbbAbbAbbAb

（Ba（B（BAa）Aa）

（BaAa）

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

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

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

說(shuō)明:

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

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

例6.2已知文法G[A]：

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

.

Aabcde#A

=

a=<

<

<b

>

>c

=d

>

>e

>

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

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

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

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

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

輸入符號(hào)串

句柄

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

1、簡(jiǎn)單表達(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.逆波蘭式

無(wú)括號(hào)，形式簡(jiǎn)單

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

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

（，）→↑→*，/→+，-由此可得到一個(gè)運(yùn)算符優(yōu)先關(guān)系矩陣（見(jiàn)下頁(yè)）。逆波蘭表達(dá)式生成算法見(jiàn)圖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)換過(guò)程如表6.528運(yùn)算符優(yōu)先關(guān)系矩陣29關(guān)系右左

+-*/

↑（

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

（<<<<<<=

）>>>>>>30表達(dá)式(a+b）*c/d→ab+c*d/31步驟輸入串當(dāng)前符號(hào)運(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中不會(huì)有形如“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(不是一個(gè)算符優(yōu)先文法)E→E+EE→E*EEE*EEE+E+<*+>*定義6.4：算符優(yōu)先文法-文法G是一個(gè)不含有空產(chǎn)生式的算符文法，且G中的兩個(gè)終結(jié)符之間，至多只有一種優(yōu)先關(guān)系。4.算符優(yōu)先關(guān)系矩陣的構(gòu)造方法⑴首先對(duì)文法G的每個(gè)非終結(jié)符A構(gòu)造兩個(gè)集合。FIRSTVT(A)={a|Aa…或ABa…，其中a∈,B∈}LASTVT(A)={a|A…a或A…aB，其中a∈,B∈}⑵確定終結(jié)符對(duì)之間的優(yōu)先關(guān)系。++++35＝關(guān)系，逐個(gè)查看產(chǎn)生式，由A→…ab…或A→…aBb…，找到a＝b。1<關(guān)系，查找文法中形“P→…aA…”的產(chǎn)生式，則對(duì)任何b∈FIRSTVT(A)，有a<b。2>關(guān)系，查找文法中形如“P→…Ab…”的產(chǎn)生式，則對(duì)任何a∈LASTVT(A)，有a>b。336例:G[E]E→E+T|TT→T*F|FF→(E)|i計(jì)算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ī)范歸約，即歸約時(shí)不一定是句柄。

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

最左素短語(yǔ)——句型最左邊的素短語(yǔ)。E

E+T

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

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

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

最左素短語(yǔ)：T*F40

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

最左素短語(yǔ)

…

滿足：

<

=,=,…,=>

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

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

步驟

當(dāng)前句型

優(yōu)先關(guān)系最左素短語(yǔ)歸約符號(hào)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的分析過(guò)程設(shè)：…最左素短語(yǔ)中包含，非終結(jié)符。

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

NN+NN+NiN*N

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

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

44步驟符號(hào)棧S[i]優(yōu)先關(guān)系輸入符號(hào)(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)文法符號(hào)或終結(jié)符較多時(shí)會(huì)變得很大。解決方法：壓縮矩陣，去掉空元素。

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

已知文法G，由算符優(yōu)先關(guān)系矩陣，若文法的每個(gè)終結(jié)符x、y滿足：1）當(dāng)x>y時(shí)，f(x)>g(y)2）當(dāng)x<y時(shí)，f(x)<g(y)3）當(dāng)x=y時(shí)，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個(gè)符號(hào)來(lái)決定是否移進(jìn)或歸約。48知識(shí)回顧自底向上語(yǔ)法分析思想和分析難點(diǎn)簡(jiǎn)單優(yōu)先和算符優(yōu)先分析方法6.3LR(K)分析方法

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

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

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

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

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

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

→輸入串

#…

…#

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

2.

LR分析表組成

兩部分：ACTION—分析動(dòng)作表

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

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

符，~為文法符號(hào)

ACTION表：

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

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

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

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

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

ACTIONGOTOS0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S426S6r156對(duì)符號(hào)串＃a，b＃的分析過(guò)程

步驟狀態(tài)棧符號(hào)棧余留符號(hào)產(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說(shuō)明無(wú)須向前查看符號(hào).LR(0)是其它LR分析法的基礎(chǔ).

例6.1

在分析的第5步棧中符號(hào)為#aAc時(shí),

用A→Ac歸約而沒(méi)有A→c.

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

步驟分析棧句柄輸入符號(hào)串動(dòng)作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分析符號(hào)串#accbdd#分析過(guò)程見(jiàn)表6.1,共用了12步,其中”移進(jìn)7步”,歸約5步。規(guī)范歸約序列:accbddaAcbddaAbddaAbdBaAbBS

構(gòu)造語(yǔ)法樹過(guò)程見(jiàn)圖

?????問(wèn)題

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

αβ,β∈

則稱α為規(guī)范前綴,又稱活前綴.(規(guī)范前綴中不含句柄之后的符號(hào))若α是句柄的活前綴,且句柄處在α的最右端,則稱α是可歸前綴.分析棧中的文法符號(hào)+余留輸入串規(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識(shí)別規(guī)范前綴的有限自動(dòng)機(jī)構(gòu)造一個(gè)識(shí)別規(guī)范前綴的有限自動(dòng)機(jī)

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

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

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

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

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

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

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

分句柄,期待其余

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

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

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

E→△E+TE→E△+TE→E+△T②后繼符號(hào)為空

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

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

x∈VT分析時(shí)x移入符號(hào)棧.(E→E△+T)②待約項(xiàng)目

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

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

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

A→α△,α∈V*

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

④接受項(xiàng)目

若為開始符號(hào)→α△,α∈V*

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

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

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

→△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)項(xiàng)目對(duì)應(yīng)的NFA:①LR(0)的一個(gè)項(xiàng)目對(duì)應(yīng)NFA的一個(gè)狀態(tài).②第一個(gè)項(xiàng)目(→△S)作為初始狀態(tài).③歸約項(xiàng)目均作為終止?fàn)顟B(tài).④對(duì)于同一個(gè)產(chǎn)生式,A→αxβ項(xiàng)目A→α△xβ變?yōu)轫?xiàng)目A→αx△β對(duì)應(yīng)Si→Sj⑤若項(xiàng)目中“△”后的符號(hào)是一個(gè)非終結(jié)符(如A)則畫Si→所有A→△γ的狀態(tài).上例中18個(gè)LR(0)項(xiàng)目作為NFA的18個(gè)狀態(tài).初始狀態(tài)→△S,終止?fàn)顟B(tài)有7個(gè).

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

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

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

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

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

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

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

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

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

【例6.5】:G[S]:S→A|BA→aAb|cB→d把G[S']第一個(gè)項(xiàng)目S'→▲S作為初始狀態(tài)項(xiàng)目集的核，通過(guò)求核的閉包，求得初始狀態(tài)的項(xiàng)目集，然后求初始狀態(tài)的后繼狀態(tài)，再求得各后繼狀態(tài)的項(xiàng)目集閉包，...，依次類推，直到不出現(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)的項(xiàng)目集中,若不同項(xiàng)目其后繼符號(hào)相同時(shí),

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

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

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

狀態(tài)

項(xiàng)目集

后繼符號(hào)

后繼狀態(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例如:項(xiàng)目集{A→α△aβ,B→γ△}移進(jìn)—?dú)w約沖突

項(xiàng)目集{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)項(xiàng)目集規(guī)范族中不存在“移進(jìn)一歸約”沖突或“歸約一歸約”沖突。81相容的項(xiàng)目集需滿足以下條件:①無(wú)移進(jìn)項(xiàng)目與歸約項(xiàng)目并存.②無(wú)歸約項(xiàng)目與歸約項(xiàng)目并存.5.LR(0)分析表的構(gòu)造

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

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

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

則對(duì)所有的a∈VT,均置ACTION[Si,a]=γj.④對(duì)于→S△∈Si,則置ACTION[Si,#]=acc.⑤其他情況均置出錯(cuò).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)分析表對(duì)輸入串進(jìn)行分析過(guò)程①若ACTION[Si,a]=Sj,a∈VT,則a入符號(hào)棧,Sj入狀態(tài)棧.②若ACTION[Si,a]=γj,a∈VT∪’#’,則按第j個(gè)產(chǎn)生式歸約,符號(hào)棧和狀態(tài)棧相應(yīng)元素退棧,歸約后的文法符號(hào)進(jìn)符號(hào)棧.③若ACTION[Si,a]=acc,a=’#’,則分析成功.④若GOTO[Si,x]=j,X∈VN,則Sj入狀態(tài)棧.(前一個(gè)動(dòng)作是歸約,歸約后的非終結(jié)符是X)⑤若ACTION[Si,a]=空白,則轉(zhuǎn)向出錯(cuò)處理.對(duì)輸入串“#aacbb#”的分析過(guò)程見(jiàn)表6.1685利用分析表對(duì)輸入串#aacbb#分析如下:步驟

狀態(tài)棧符號(hào)棧

輸入串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)文法要求項(xiàng)目集中不含沖突項(xiàng)目,大多數(shù)文法不能滿足.

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

因?yàn)橹粚?duì)有沖突的狀態(tài)才向前看一個(gè)符號(hào),所以是簡(jiǎn)單的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)造項(xiàng)目集的規(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沖突項(xiàng)目集:S1

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

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

解決沖突的辦法:

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

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

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

若a∈Follow(A),則置ACTION[Si,a]=γj.④對(duì)于→S△∈Si,則置ACTION[Si,#]=acc.⑤其他情況均置出錯(cuò).定義：SLR(1)文法，按SLR(1)分析表構(gòu)造算法的分析表中不含有沖突動(dòng)作。92表達(dá)式文法的項(xiàng)目集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á)式文法的項(xiàng)目集構(gòu)造SLR(1)分析表如表6.20所示.對(duì)符號(hào)串#i*(i+i)#的分析過(guò)程如表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)棧符號(hào)棧產(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符號(hào)串#i*(i+i)#的分析過(guò)程步驟狀態(tài)棧符號(hào)棧產(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

例：符號(hào)串

i*i

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

SLR(1)算法簡(jiǎn)單,是一種較為實(shí)用的方法,但仍有一些程序設(shè)計(jì)語(yǔ)言的文法不是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[]項(xiàng)目集的規(guī)范族如下:

狀態(tài)

項(xiàng)目集

后繼符號(hào)

后繼狀態(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·項(xiàng)目集S6={B→a△,C→a△}，存在“歸約-歸約”沖突?！ろ?xiàng)目集S8={S→CbBA△,