編譯原理-總復(fù)習(xí)

1編譯程序是將一種語言（源語言,通常是高級語言）翻譯為另一種語言（目標(biāo)語言，通常用匯編語言或機器語言表示）的計算機程序。目標(biāo)程序翻譯源程序一個編譯程序涉及到三個方面的語言，即源語言、目標(biāo)語言和編譯程序的書寫語言。為了描述方便通常用T型圖來表示這三個方面的語言。T型圖的左上角表示源語言，右上角表示目標(biāo)語言，底部表示書寫語言(實現(xiàn)語言)STI■第一章2詞法分析源程序目標(biāo)程序語法分析語義分析目標(biāo)代碼生成文字表、符號表處理錯誤處理中間代碼優(yōu)化中間代碼生成前端后端1.2編譯過程和編譯程序的基本結(jié)構(gòu)3第二章2.2.1字母表和符號串字母表是元素的非空有窮集合。例如：

={a，b，c}

字母表中至少包含一個元素。字母表中的元素可以是字母、數(shù)字或其他符號。符號（字符）字母表中的元素稱為符號，或稱為字符。43.字符串（字）

符號的有窮序列稱為符號串。例如有字母表

={a，b，c}，則有字符串a(chǎn),b,ab,ba,……

符號串總是建立在某個特定字母表上的，且只能由字母表上的有窮多個符號組成。符號串中符號的順序很重要，例如ab和ba就是兩個不同的符號串。不包含任何符號的符號串，稱為空符號串，用ε表示?？辗柎?個符號組成，其長度

|ε|＝05注意：

ε是符號串，而不是集合

{ε}表示由空符號串ε所組成的集合，但這樣的集合不是空集合Φ＝{}6符號串的長度：符號串中所包含的符號的個數(shù)例s=string,|s|=6,|ε|＝0符號串的連接：設(shè)α、β是兩個符號串，則αβ稱為α與β的連接例α=some,β=thing,αβ=something εα=αε=α符號串的乘積：設(shè)A、B是兩個符號串的集合，AB表示A與B的乘積。

2.2.2符號串的運算7例：A={ab,cd},B={ef,gh}AB={abef,abgh,cdef,cdgh}

特別地，{ε}A=A{ε}=A符號串集合的正則閉包A+A+＝AA2A3…An，即A+為集合A上所有符號串的集合符號串集合的閉包記為A*定義A*={ε}

A+=A+

{ε}顯然，A+=AA*=A*A8符號串的冪運算設(shè)x是符號串，則x的冪運算定義為

x0=ε x1= x x2= xx ……

xn

= xx…x=xxn-1(n>0)例如，設(shè)x=abc

9集合的冪運算設(shè)A是符號串的集合，則集合A的冪運算定義為

A0={ε} A1= A A2= AA …… An= AA…A=AAn-1(n>0)例如，設(shè)A={a,b},則A2=?A+?A*?102.文法文法是產(chǎn)生式的非空有窮集合，通常表示成四元組G=(VN,VT,P,S)。其中:VN是產(chǎn)生式中非終結(jié)符的集合。VT是產(chǎn)生式中終結(jié)符的集合。VN∩VT＝?P是文法規(guī)則的集合。S是一個非終結(jié)符，稱為文法的開始符號，它至少要在一條規(guī)則的左部出現(xiàn)。由它開始，識別出我們所定義的語言。11復(fù)雜的產(chǎn)生式往往用一些基本的產(chǎn)生式組合而成。①基本式：Aα，這里α是終結(jié)符組成的串，這個語法所定義的語言只有一個符號串。例：A0②嵌套式:AαBβ，α、β是終結(jié)符串，B是一個非終結(jié)符串，A所定義的終結(jié)符串是每個B定義的語句（可推出的終結(jié)符串）前邊加α串并且后邊加β串。例：

AiBchina

Blove一些基本的產(chǎn)生式重點掌握給定的文法，能夠?qū)懗鑫姆ㄋ硎镜恼Z言。12③遞歸式：有兩個常用的產(chǎn)生式都能表示遞歸式。

AAα|α,A

αA|α

它們定義的串集合為：{α，αα，α…ααα}α…ααα可寫成αn，所以L(A)={αn|n≥1}例：(i)D

bD|ε(ii)AaA|d④成對符號遞歸：可用下述產(chǎn)生式表示成對符號遞歸：

AαAβ|αβA定義的語言可記為L(A)={αnβn|n≥1}例：AabAcd|abcd一些基本的產(chǎn)生式13

推導(dǎo)從開始符號開始，經(jīng)過有限次的推導(dǎo)后得到一個終結(jié)符串（句子）。從開始符到句子間，每步推導(dǎo)所得到的含有非終結(jié)符的符號串是一個句型，一個文法G經(jīng)過推導(dǎo)所能獲得的全部句子的集合就是這個文法語言L(G). =>*表示經(jīng)過0步或若干步推導(dǎo)

=>+表示經(jīng)過1步或若干步推導(dǎo)14■語言的形式定義4、句型和句子G=(VT,VN,P,S)，S=>*a，a∈(VTVN)*

稱a為句型。a∈VT*，稱a為句子。句型與句子區(qū)別：句型由終結(jié)符和非終結(jié)符構(gòu)成，句子只由終結(jié)符構(gòu)成。聯(lián)系：僅含終結(jié)符的句型是一個句子。即：句子必定是句型，但句型不一定是句子。例：設(shè)有文法G[S]:S01|0S1請分別判斷：01，000S111，0SS0，0011，0S1是該文法的句子還是句型？15■句型與句子舉例例：設(shè)有文法G[E]: EE+E|E*E|(E)|i試證明符號串

i+i*i(i*i+i)是文法G[E]的句子。16例2.5設(shè)有文法G[S]: S01|0S1有

S=>*01 S=>*0S1 S=>*00S11 S=>*000111問:哪些字符串是文法G的句子?哪些是文法的句型?如何由規(guī)則推導(dǎo)句子？推導(dǎo)方法：從一個要識別的符號開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進行推導(dǎo)。直到所有的非終結(jié)符號都由終結(jié)符號替代為止。17由此可見，從已知文法確定語言的中心思想是：從文法的開始符號出發(fā)，反復(fù)連續(xù)地使用規(guī)則（產(chǎn)生式），對非終結(jié)符施行替換和展開，找出句子的規(guī)律，用式子或自然語言描述出來。注意：（1）給定一個文法，就能唯一地確定其語言，即

GL(G)（2）給定一種語言，能確定其文法，但這個文法不一定是唯一的。文法和語言的關(guān)系■規(guī)范推導(dǎo)和規(guī)范歸約最左（右）推導(dǎo)：指對于一個推導(dǎo)序列中的每一步直接推導(dǎo)α=>β,都是對α中的最左(右)非終結(jié)符進行替換規(guī)范推導(dǎo):指最右推導(dǎo)規(guī)范句型:用規(guī)范推導(dǎo)推導(dǎo)出的句型稱為規(guī)范句型規(guī)范歸約(最左歸約):規(guī)范推導(dǎo)的逆過程例：設(shè)有文法G[S]:SAB AA0|1B B0|S1請給出句子1000的最左、最右推導(dǎo)。練習(xí)：給出句子101001的最左推導(dǎo)。19◆例2.12考慮文法G[N1]：

N1N NND|D D0|1|2該文法是左遞歸的，它所描述的語言是無窮集合。當(dāng)一個語言是無窮集合時，則定義該語言的文法一定是遞歸的。{0,1,2}+202.5.1推導(dǎo)和語法樹對句型的推導(dǎo)過程給出一種圖形表示，這種表示稱為語法樹，也稱推導(dǎo)樹。2.5語法樹與文法的二義性與推導(dǎo)相對應(yīng)的語法樹是一個作了標(biāo)記的樹，其中內(nèi)部的節(jié)點由非終結(jié)符標(biāo)出，樹葉節(jié)點由終結(jié)符標(biāo)出，每個內(nèi)部節(jié)點都表示推導(dǎo)的一個步驟中的相關(guān)非終結(jié)符的替換。樹根結(jié)點是文法的開始符號。21語法樹的特點：如果句子中有括號的話，括號在文法中表示了操作的優(yōu)先次序，這個次序在語法樹中已經(jīng)被樹的層次體現(xiàn)出來了?？拷Y(jié)點的計算總是較遲處理，靠近葉子的結(jié)點被優(yōu)先處理。22短語、簡單短語G=(T,N,P,S)，w=xuy

∈(T

N)*

為文法的句型,若S=>xUy,且U=>+u,則u是句型w相對于U的短語；若S=>xUy,

且

U=>u,則u是句型w相對于U的簡單短語;其中U∈N，u∈(T

N)+,x,y∈(T

N)*

句柄任一句型的最左簡單短語稱為該句型的句柄。

短語、簡單短語是相對于句型而言，一個句型可能有多個短語、簡單短語，句柄只能有一個。Note23子樹：由某一結(jié)點連同所有分支組成的部分。簡單子樹：指只有單層分支的子樹。短語/直接短語/句柄在語法樹中的直觀解釋：短語----子樹的末端結(jié)點形成的符號串是相對于子樹根的短語直接短語----簡單子樹的末端結(jié)點形成的符號串是相對于簡單子樹根的短語句柄----最左簡單子樹的末端結(jié)點形成的符號串是句柄24例：有文法G[E]：

ET|E+T|E-T

TF|T*F|T/F

Fi|(E)請判斷(E+T)*i+F是G的一句型嗎？如果是，請畫出它的推導(dǎo)的分析樹，并寫出該樹的短語、簡單短語、句柄。解：∵E=>*(E+T)*i+F

∴(E+T)*i+F是G的一句型E+ETTF+ET)E(F*TiF25簡單短語(每棵簡單子樹的葉組成簡單短語):E+T是句型(E+T)*i+F相對于E的簡單短語；i是句型(E+T)*i+F相對于F的簡單短語；F是句型(E+T)*i+F相對于T的簡單短語。E+ETTF+ET)E(F*TiF短語(每棵子樹的葉組成短語):(E+T)*i+F是句型(E+T)*i+F相對于E的短語；(E+T)*i是句型(E+T)*i+F相對于E、T的短語；(E+T)是句型(E+T)*i+F相對于T、F的短語；E+T是句型(E+T)*i+F相對于E的短語；i是句型(E+T)*i+F相對于F的短語；F是句型(E+T)*i+F相對于T的短語。句柄(最左簡單子樹的葉組成句柄):E+T是句型(E+T)*i+F相對于E的最左簡單短語。26◆例2.13.設(shè)有文法G[S]=({S,A,B},{a，b},P,S)其中，P為

SAB

AAa|bB

Ba|Sb請判斷baSb是G的一句型嗎？如果是，請畫出它的推導(dǎo)的分析樹，并寫出該樹的短語、簡單短語、句柄?！鑫姆ǖ亩x性引例：已知簡單整型算術(shù)表達式文法：

exp

expopexp|(exp)|iop

+|-|*

請畫出串i

-i

*i

的語法樹!解：1)推導(dǎo)

2)根據(jù)推導(dǎo)畫語法樹同一個句子若可生成兩棵不同的語法樹，則定義該句子的文法叫二義性文法。注意理解：若一個文法中存在某個句子，它有兩個不同的最左（最右）推導(dǎo)，這個文法是二義性文法?！鑫姆ǘx性的消除◆不修改文法，指定正確的語法樹；◆修改文法(考慮優(yōu)先級、結(jié)合性等)注意：文法的二義性和語言的二義性是兩個不同的概念。只要某文法定義的語言中，有一個句子有2棵以上的語法樹，該文法就是二義性的；而二義性語言是指，對它不存在無二義性的文法，這樣的語言稱為先天二義性的語言。文法G[E]：

E→T|E+T|E-T T→F|T*F|T/F

F→(E)|i文法G[E]:EE+E|E*E|(E)|i29注意：文法的二義性和語言的二義性是兩個不同的概念。通常我們只說文法的二義性，而不說語言的二義性，這是因為可能有兩個不同的文法G和G’，一個是二義性的，一個不是二義性的，但他們所描述的語言卻是一樣的，即L(G)=L(G’).

將一個語言說是二義性的，是指對它不存在無二義性的文法，這樣的語言稱為先天二義性的語言。人們已經(jīng)證明，不存在一個算法，它能在有限步驟內(nèi)確切地判定任給的一個上下文無關(guān)文法是否是二義性文法。30

文法和語言分類：0型、1型、2型、3型（喬姆斯基層次）

0型文法稱為短語結(jié)構(gòu)文法（非限制）。產(chǎn)生式的左部和右部都可以是符號串，一個短語可以產(chǎn)生另一個短語?！?型：P：u

v

其中u∈(T

N)+

，v∈(T

N)*

■喬姆斯基層次2.6文法和語言的分類31

1型文法稱為上下文敏感或上下文有關(guān)文法。也即只有在x,y這樣的上下文中才能把U改寫為u●1型：P：xUy

xuy

其中U∈N，x,y,u∈(T

N)*例：1型（上下文有關(guān)）文法文法G[S]： S→CD

C→aCA

C→ε

C→bCB

D→ε

AD→aD

BD→bD

Aa→bD322型文法稱為上下文無關(guān)文法。也即把U推導(dǎo)為v時，不必考慮上下文。●2型：P：U

v

其中U∈N

，v∈(T

N)*

文法G[S]：

S→AB A→BS|0 B→SA|12型文法即上下文無關(guān)文法及相應(yīng)的語言是我們主要研究的對象。33例：G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|03型文法稱為正則文法，它是對2型文法進行進一步限制3型文法不能把非終結(jié)符嵌在終結(jié)符串里。如：S

aSb|ab不是3型文法，3型文法不能描述anbn這樣的符號串?！?型：(左線性)P：U

t

或

U

Wt

其中

U、W∈Nt∈T(右線性)P：U

t

或

U

tW

其中

U、W∈Nt∈T34●0型、1型、2型、3型比較產(chǎn)生式左部范圍右部范圍|左部||右部|0型u

v(T

N)+(T

N)*>=1>=01型xUy

xuy(T

N)+(T

N)*>=1>=02型U

vN(T

N)*=1>=03型U

tU

WtNT

N=1<=2●3型：P：U

t或

U

Wt其中

U、W∈Nt∈T●2型：P：U

v

其中U∈N

，v∈(T

N)*

●0型：P：u

v

其中u∈(T

N)+

，v∈(T

N)*

●1型：P：xUy

xuy

其中U∈N，x,y,u∈(T

N)*L3

L2

L1

L0353.1詞法分析程序的功能所謂詞法，即構(gòu)成詞的規(guī)則。詞法分析的任務(wù)是對字符串表示的源程序從左到右進行掃描和分解，根據(jù)語言的詞法規(guī)則識別出一個一個具有獨立意義的單詞符號。詞法分析是編譯過程中的一個階段，在語法分析前進行，可以作為單獨的一遍，將源程序轉(zhuǎn)換成單詞符號序列供下一遍使用。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序獲得當(dāng)前記號，供語法分析使用。363.2單詞符號及輸出單詞的形式源程序詞法分析程序單詞符號單詞符號是語言中具有獨立意義的最小單位，包括保留字、標(biāo)識符、常量、運算符和界符等。詞法分析程序輸出的單詞符號通常表示成如下的二元式：（單詞種別，單詞自身的值）37■正規(guī)式與正規(guī)集3.3語言單詞符號的兩種定義方式多數(shù)程序設(shè)計語言的單詞符號都能用正規(guī)文法或正規(guī)式來定義。設(shè)有字母表

={a1，a2，…，an}，在字母表上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則定義：（1）Φ是上的正規(guī)式，它所表示的正規(guī)集是Φ，即空集{}（2）ε是上的正規(guī)式，它所表示的正規(guī)集是{ε}（3）ai是上的正規(guī)式，它所表示的正規(guī)集由單個符號ai組成，即{ai}38■正規(guī)式與正規(guī)集（4）如果e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，則e1|e2是上的一個正規(guī)式，它所表示的正規(guī)集為L(e1|e2)=

L(e1)∪L(e2)e1e2是上的一個正規(guī)式，它所表示的正規(guī)集為L(e1e2)=L(e1)L(e2)(e1)*是上的一個正規(guī)式，它所表示的正規(guī)集為L((e1)*)=L((e1))*正規(guī)式描述了單詞符號的構(gòu)成規(guī)則，正規(guī)集是正規(guī)式能描述的所有的單詞的集合。39設(shè)有字母表

={a,b},根據(jù)正規(guī)式和正規(guī)集的定義有：■例3.1（1）a和b是正規(guī)式，相應(yīng)正規(guī)集為L(a)={a}（2）a|b是正規(guī)式，相應(yīng)正規(guī)集為L(a|b)={a,b}（3）ab是正規(guī)式，相應(yīng)正規(guī)集為L(ab)={ab}（4）(a|b)*是正規(guī)式，相應(yīng)正規(guī)集為L((a|b)*)={a,b}*={ε,a,b,ab,ba,…}（5）ba*是正規(guī)式，相應(yīng)正規(guī)集為L(ba*)={b,ba,baa,baaa,…}（6）(a|b)*(aa|bb)(a|b)*是正規(guī)式，相應(yīng)正規(guī)集為L={a,b}*{aa,bb}{a,b}*練習(xí)：若S=a|bb，則L((a|bb)*)=？40■正規(guī)式中運算的優(yōu)先級括號優(yōu)先，*次之，?（連接）再次之，|最后例：a|bc*≌a|(b(c*))

ab|c*d≌(ab)|((c*)d)

L(a|bc*)=L(a)∪L(bc*) =L(a)∪L(b)L(c*) =L(a)∪L(b)(L(c))* ={a}∪{ε,c,cc,ccc……} ={a,b,bc,bcc,bccc,……}■正規(guī)式與正規(guī)集舉例思考：L(ab|c*d)=？413.4正規(guī)式與有窮自動機有窮自動機是詞法的識別工具，它的功能是：尋找（匹配）符合正規(guī)式要求的字符串，根據(jù)正規(guī)式確定正規(guī)集。有窮自動機是描述特定類型算法的數(shù)學(xué)模型，可分為確定性有窮自動機(DFA)和非確定性有窮自動機(NFA)。42■確定有窮自動機（DFA）數(shù)學(xué)定義（五元組形式）：嚴(yán)密；狀態(tài)轉(zhuǎn)換表：面向編程。狀態(tài)轉(zhuǎn)移圖：直觀；DFA有三種表示形式43結(jié)點代表狀態(tài)(state)，用圓圈○表示。狀態(tài)之間用箭頭→(transition)連結(jié)，代表一個狀態(tài)向另一個狀態(tài)的轉(zhuǎn)換。一個有窮自動機只包含有限個狀態(tài)(即有限個結(jié)點)，其中只有一個為初態(tài)(startstate)（一個有開始狀態(tài)的箭頭指向），至少一個為終態(tài)(接受狀態(tài)acceptingstate)(雙圈表示)。例：標(biāo)識符的有窮自動機?！鲇懈F自動機的狀態(tài)轉(zhuǎn)移圖表示方法44■確定有窮自動機（DFA）◆∑輸入字母表◆Q有窮狀態(tài)集◆f:Q×∑→Q(狀態(tài)轉(zhuǎn)換函數(shù))◆S∈Q唯一的初始狀態(tài)◆Z

Q終止（接受）狀態(tài)集合這里的字母表是問題固有的；狀態(tài)集合是編寫DFA時定義的，是用戶所做的命名。DFAM是一個五元組（Q,∑,f,S,Z

）確定性有窮自動機(DFA)：下一狀態(tài)由當(dāng)前狀態(tài)和當(dāng)前輸入字符唯一給出的自動機。（取決于f）“確定”即狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)——數(shù)學(xué)定義45■非確定有窮自動機（NFA）由M接受的語言L(M)

L(M)＝{c1c2c3….cn

|ci∈∑U{ε},s1=T(s0,c1),s2=T(s1,c2),…,sn=T(sn-1,cn),sn∈A.}“非確定”即狀態(tài)轉(zhuǎn)移函數(shù)是多值函數(shù)◆∑:輸入字母表◆Q:有窮狀態(tài)集◆f:Sx(

U{ε})?(S)(狀態(tài)轉(zhuǎn)換函數(shù))◆S

Q初始狀態(tài)集◆Z

Q終止?fàn)顟B(tài)集NFAM也是一個五元組（Q,∑,f,S,Z

）46轉(zhuǎn)換函數(shù)T初態(tài)NFAM(S,∑,T,S0,F)S×(

U{ε})

→S的子集多值映射S0

S非空初態(tài)集DFAM(S,∑,T,s0,F)S×∑→S的元素單值映射s0∈S唯一的初態(tài)●NFA與DFA的區(qū)別：47■由正規(guī)表達式R構(gòu)造NFA

(a)對于正規(guī)式φ,所構(gòu)造NFA:xy

(b)對于正規(guī)式ε,所構(gòu)造NFA:xyε

(c)對于正規(guī)式a,a∈Σ,則NFA:xya1.基本正規(guī)表達式48■由正規(guī)表達式R構(gòu)造NFA2、若r,s為正規(guī)式：123rssr13rsr|sr*例：構(gòu)造與正規(guī)表達式R=ab*a(a|b)*等價的NFA。1r32εε49定義1：狀態(tài)集合I的ε-閉包：令I(lǐng)是一個狀態(tài)集的子集，定義ε-closure（I）為：1）若s∈I，則s∈ε-closure（I）；2）若s∈I，則從s出發(fā)經(jīng)過任意條ε弧能夠到達的任何狀態(tài)都屬于ε-closure（I）。狀態(tài)集ε-closure（I）稱為I的ε-閉包為了使得NFA確定化，給出兩個定義：56432aεaaε1例：如圖所示的狀態(tài)圖：令I(lǐng)={1}，求ε-closure（I）=？解：根據(jù)定義：ε-closure（I）={1，3}例：若I1={1,2}，則ε-closure（I1）={1,2,3,6}DFA的確定化50——J是從狀態(tài)子集I中的每個狀態(tài)出發(fā)，經(jīng)過標(biāo)記為a的弧而達到的狀態(tài)集合。——

Ia是狀態(tài)子集,其元素為J中的狀態(tài)，加上從J中每一個狀態(tài)出發(fā)通過ε弧到達的狀態(tài)。定義2:狀態(tài)子集的構(gòu)造：s∈I例：令I(lǐng)={1}，求Ia=?Ia=ε-closure(J)=ε-closure(T(1，a)）

=ε-closure({2，4}）

={2，4，6}56432aεaaε1令I(lǐng)是NFAM’的狀態(tài)集的一個子集,a∈Σ定義:Ia=ε-closure(J)其中J=∪T(s,a)51例：有NFAM，求DFAM’。a1234startabaccε

IIa

Ib

Ic

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}初態(tài)I=ε-closure({1})={1,4}Ia=ε-closure(T(1,a)∪T(4,a))=ε-closure({2,3}∪φ）

=ε-closure({2,3})={2,3}Ib=ε-closure(T(1,b)∪T(4,b))=ε-closure(φ）

=φIc=ε-closure(T(1,c)∪T(4,c))=φI={2,3},Ia={2},Ib={4},Ic={3,4}……DFA的狀態(tài)52

符號狀態(tài)abc02341221________3344●DFAM’狀態(tài)表將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號start01423{1,4}{2,3}{4}{2}acabbc{3,4}

IIa

Ib

Ic

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}包含NFA終態(tài)的狀態(tài)子集全都是DFA的終態(tài)53例:將該DFA最小化5724361srartaaaaaaabbbbbbb狀態(tài)集的劃分將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個子集G1,G2;分別從兩個子集G1,G2中尋找不等價狀態(tài)進行分割?！胺指罘ā保喊岩粋€DFA(不含多余狀態(tài))的狀態(tài)分割成一些不相關(guān)的子集，使得任何不同的兩個子集狀態(tài)都是可區(qū)別的，而同一個子集中的任何狀態(tài)都是等價的.54解:(一)區(qū)分終態(tài)與非終態(tài)123456637315467374142ab567374142ab123463731546231區(qū)號5724361srartaaaaaaabbbbbbb將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個子集區(qū)號12123456637315467374142ab5512431243123456637315467374142ab5123456637315467374142ab區(qū)號區(qū)號12345ab5214355231155243aaaaabbbbb567374142ab123463731546123區(qū)號將區(qū)號代替狀態(tài)號得:56正規(guī)文法正規(guī)式NFADFA最小化ABtA

tB(2)對終態(tài)Z增加Z

ε(1)右線性文法增加終態(tài)；左線性文法增加初態(tài)解方程組，若x=αx+β，則x=α*β;Aab

轉(zhuǎn)換成AaB和BbAa*b轉(zhuǎn)換成AaA|b;57為R=(a|b)*(aa|bb)(a|b)*構(gòu)造最小化的DFA,使得L(N)=L(R)■課堂練習(xí)例：構(gòu)造與正則表達式R=ba(a|b)*等價的狀態(tài)最少的DFA，并寫出該DFA的五元組形式。58語法分析程序的功能是以詞法分析器生成的單詞符號序列作為輸入，根據(jù)語言的語法規(guī)則（文法），識別出各種語法成分，并在分析過程中進行語法檢查，檢查所給單詞符號序列是否是該語言的文法的一個句子。若是，則以該句子的某種形式的語法樹作為輸出；若不是，則表明有錯誤，并指出錯誤的性質(zhì)和位置。4.1語法分析程序的功能語法分析程序的輸入是單詞符號序列；輸出是語法樹。59遞歸下降法LL(1)分析法回溯分析方法（不確定的分析法）預(yù)測分析方法(確定的分析法)LR(0)parsingSLR(1)parsingLR(1)parsingLALR(1)parsing自頂向下分析方法從根結(jié)點出發(fā)構(gòu)造語法樹

自底向上分析方法從葉結(jié)點出發(fā)構(gòu)造語法樹

語法分析方法L:由左向右的處理輸入L:為輸入串構(gòu)造最左推導(dǎo)

60■文法左遞歸的消除4.2自上而下分析法左遞歸導(dǎo)致無限遞歸循環(huán)；解決無限遞歸循環(huán)的方法：消除左遞歸。（1）左遞歸改成右遞歸——簡單直接左遞歸的消除

A→Aα|βA→βA’A’→αA’|ε解：exp→termexp’

exp’→addoptermexp’|ε例：將文法G：exp→exp

addopterm|term

消除左遞歸。左遞歸的消除不改變語言，但是改變了文法和分析樹。確定的自上而下分析法對文法要求：(1)無左遞歸；(2)無回溯61將文法G：A→αβ|αγ提取左因子。解：A→αA’

A’→β|γ■提取左因子規(guī)則例：將文法G提取左因子。

stmt-sequence→stmt;stmt-sequence|stmt

stmt→s

提取左因子的結(jié)果：stmt-sequence→stmtstmt-seq’stmt-seq’→;stmt-sequence|εstmt→s注意：不可以這樣提?。篈a(β|γ)文法中括號的含義與正規(guī)式中括號的含義不同。62First集合和Follow集合■First集合定義：FIRST(α)={a|α=>*aβ，a

T,α,β

(T

N)*

}

若α=>*ε，則規(guī)定ε

FIRST(α)該集合稱為α的頭符號集合631.若X

,則FIRST(X)={X}2.若X

N,且有產(chǎn)生式X

a…，則把a加入到FIRST(X)中;若X

也是一條產(chǎn)生式,則把

也加到FIRST(X)中.3.若X

Y…是一個產(chǎn)生式且Y

N,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X

Y1Y2…YK

是一個產(chǎn)生式,Y1,Y2,…,Y(i-1)都是非終結(jié)符,而且,對于任何j,1≤j≤i-1,FIRST(Yj)都含有

(即Y1..Y(i-1)

=>*

),則把FIRST(Yi)中的所有非

元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj,j=1,2,…,K)均含有

,則把

加到FRIST(X)中.■First集合算法P69令X為一個文法符號或

，則集合First(X)由終結(jié)符組成，此外還可能有

，定義如下：64■求First集合舉例2求文法G的FIRST集合G:(1)M→TB (2)T→Ba|ε (3)B→Db|eT|ε (4)D→d|ε注意：有ε產(chǎn)生式時求First集，別漏元素！！First(M)={e,a,d,b,ε}

First(T)={e,a,d,b,ε}

First(B)=

{e,d,b,ε}

First(D)=

{d,ε}注意：除了求非終結(jié)符的First集外，還可求符號串的First集。例：求First(BaB)65定義：FOLLOW(A)={a|S=>*

…Aa…，a∈T}A∈N,S開始符號特殊地：若S=>*...A，則$∈FOLLOW(A)■Follow集合1.對于文法的開始符號S,置$于FOLLOW(S)

中;2.若Ａ

αBβ是一個產(chǎn)生式,則把FIRST(β)－{}加至FOLLOW(B)中;3.若Ａ

αB是一個產(chǎn)生式,或Ａ

αBβ是一個產(chǎn)生式而

FIRST(β)，則把FOLLOW（A）加至FOLLOW（B）中。算法：66練習(xí)4)求文法G的FOLLOW集合

E→TE’

E’→+TE’|ε

T→FT’T’→*FT’|ε

F→(E)|iFIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)={(，i}FIRST(E’)={+,ε}FIRST(E)={(，i}FOLLOW(E)={$,)}FOLLOW(E’)={$,)}FOLLOW(T)={+,),$}FOLLOW(T’)={+,),$}FOLLOW(F)={*,+,),$}解：67■Select集合Select集合是針對規(guī)則（產(chǎn)生式）的。設(shè)A

α是文法的任一條規(guī)則，則定義：Select(A

α)=First(α) 若α=>*

First(α)-{}

∪Follow(A)

若α=>*

例：求下列文法的每個規(guī)則的Select集合：

AaB|d

BbBA|

68一個上下文無關(guān)文法G是LL(1)文法，當(dāng)且僅當(dāng)對G中每個非終結(jié)符A的任何兩個不同的規(guī)則A

α

β滿足：Select(A

α)∩Select(A

β)=

■LL(1)文法的要求69■預(yù)測分析表的構(gòu)造算法（1）計算每一非終結(jié)符的First集和Follow集；（2）對于First(α)中的每個記號a，都將A→α添加到表項M[A,a]中；（3）若ε在First(α)中，則對于Follow(A)的每個元素a(記號或是$)，都將A→α添加到M[A,a]中;（4）把分析表中沒有填入內(nèi)容的空白格都標(biāo)上出錯標(biāo)志error。例：文法：Sa|^|(T) TT,S|S試判斷該文法是否是LL(1)文法，若不是請轉(zhuǎn)換，并求轉(zhuǎn)換后LL(1)文法的預(yù)測分析表。70●練習(xí)1Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number}Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number}Follow(factor)={$,+,-,*,)}(1)First集和Follow集First(exp)={(,number}First(exp’)={+,-,ε}First(addop)={+,-}First(term)={(,number}First(term’)={*,ε}First(mulop)={*}First(factor)={(,number}文法：exp→expaddop

term∣term

addop

→

+|- term→termmulop

factor∣factor

mulop

→* factor→(exp)

∣

number

注意：先消除左遞歸71Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number)Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number)Follow(factor)={$,+,-,*,)}(2)First集和Follow集First(exp)={(,number)First(exp’)={+,-,ε}First(addop)={+,-}First(term)={(,number)First(term’)={*,ε}First(mulop)={*}First(factor)={(,number)11109788886654223311factormulopterm’termaddopexp’exp$*-+)Number(M[N,T](3)LL(1)分析表解

(1)文法1exp→termexp’2exp’→addoptermexp’3exp’→ε4addop

→+5addop

→-6term→factorterm’7term’→

mulopfactorterm’8term’→ε9mulop

→*10factor→(exp)11factor→number（1）對于First(α)中的每個記號a，都將A→α添加到表項M[A,a]中；（2）若ε在First(α)中，則對于Follow(A)的每個元素a(記號或是$)，都將A→α添加到M[A,a]中。4.5LR分析

LR分析法是一種自上而下進行規(guī)范規(guī)約的語法分析方法。這里的L是指從左到右掃描輸入符號串，R是指構(gòu)造最右推導(dǎo)的逆過程。這種分析法比遞歸下降分析法、預(yù)測分析法和算府優(yōu)先分析法對文法的限制要少的多，也就是說，對大多數(shù)無二義性的上下文無關(guān)文法描述的語言都可以用LR分析法進行分析，而且分析速度快，并能準(zhǔn)確及時地指出輸入串的語法錯誤和出錯位置。缺點：構(gòu)造LR分析器的工作量大734.5LR分析法本節(jié)介紹四種LR分析法：LR(0)、SLR(1)、LR(1)、LALR，這四種方法的區(qū)別只有分析表不同。LR分析法是一種自下而上進行規(guī)范歸約的語法分析方法。這里L(fēng)是指從左向右掃描輸入符號串，R是只構(gòu)造最右推導(dǎo)的逆過程。優(yōu)點：對文法的限制少的多，分析速度快；缺點：構(gòu)造LR分析器的工作量大，實現(xiàn)困難。4.5.1LR分析器的工作原理和過程

LR分析法是一種規(guī)范規(guī)約分析方法，這種分析法的關(guān)鍵是在分析過程中如何確定分析棧棧頂?shù)姆柎欠窨尚纬删浔?/p>

LR分析法確定句柄的基本思想是在規(guī)范規(guī)約分析過程中，根據(jù)分析棧中記錄的已移進和規(guī)約出的整個字符串（歷史）和根據(jù)使用規(guī)則推測未來可能遇到的輸入符號（即展望），以及現(xiàn)讀到的輸入符號這3方面的信息來確定分析棧的棧頂?shù)姆柎欠駱?gòu)成句柄。75輸入

a1...ai...an$LR驅(qū)動程序分析表輸出棧smXmsm-1Xm-1...s0actiongoto

LR分析器的結(jié)構(gòu)和工作過程■LR分析器的工作原理和過程

LR分析表是LR分析器的核心部分。一張LR分析表由分析動作（ACTION）表和狀態(tài)轉(zhuǎn)換表（GOTO）兩部分組成，他們都是二維數(shù)組。狀態(tài)轉(zhuǎn)換表元素GOTO[Si，X]規(guī)定了當(dāng)狀態(tài)Si面臨文法符號X時，應(yīng)該轉(zhuǎn)移到的下一個狀態(tài)。分析動作表元素ACTION[Si,a]規(guī)定了當(dāng)狀態(tài)Si面臨輸入符號a時應(yīng)執(zhí)行的動作。有如下4種可能的動作：（1）移進：把狀態(tài)Sj＝GOTO[Si,a]和輸入符號a移入分析棧。（2）規(guī)約：當(dāng)棧頂符號串a(chǎn)形成句柄，且文法中有A

的規(guī)則，其中|α|=β，則規(guī)約動作是從分析棧棧頂去掉β個文法符號和β個狀態(tài)，并把規(guī)約符A和GOTO[Si-β,A]=Sj移入分析棧中（3）接受（acc)：表示分析成功。此時，分析棧中只剩文法開始符號S‘和當(dāng)前讀到的輸入符號$，即輸入的符號串已經(jīng)結(jié)束。（4）報錯：表示輸入串有錯誤，此時出現(xiàn)棧頂?shù)哪骋粻顟B(tài)遇到了不該遇到的輸入符號。78在文法產(chǎn)生式右部某個位置標(biāo)有‘.’的產(chǎn)生式，稱為文法的一個LR(0)項目。形如A.的項目稱為初始項目；形如A.的項目稱為歸約項目；形如A.B（B∈N）的項目稱為待約項目；形如A.a（a∈T）的項目稱為移進項目；形如S’S.的項目稱為接受項目，其中S’為文法的唯一的開始符號■項目分類79設(shè)I是文法G的一個LR(0)項目集合，I的項目閉包closure(I)定義為：(1)Iclosure(I)。

(2)若項目A.Bclosure(I)，且B是G的產(chǎn)生式，則項目B.closure(I)。

(3)closure(I)僅包含上述兩條規(guī)則確定的LR(0)項目。項目閉包：轉(zhuǎn)移函數(shù)：若I是文法G的一個LR(0)項目集，X是G中的文法符號。go(I,X)=closure(J)其中J={AX.|A.XI}稱函數(shù)go(I,X)為轉(zhuǎn)移函數(shù)。項目AX.稱為項目A.X后繼?！鰳?gòu)造識別文法所有規(guī)范句型活前綴DFA的方法80■LR(0)分析表的構(gòu)造若對于一個文法G的拓廣文法G’的LR(0)項目集規(guī)范族中的每個項目集，不存在移進項目和歸約項目同時并存或多個歸約項目同時并存，則稱G為LR(0)文法。即LR(0)文法中不能存在移進－歸約沖突或者歸約－歸約沖突。E'→·EE→·E+nE→·nE→n·E'→E·E→E·+nE→E+n·En+n012E→E+·n34根據(jù)右圖某文法識別活前綴的DFA判斷該文法是否為LR(0)文法81■LR(0)分析表的構(gòu)造LR(0)分析表包含兩個子表：ACTION表和GOTO表假定項目集規(guī)范族C={I0,I1,…,In}，令每個項目集Ik的下標(biāo)k作為分析器的狀態(tài)，兩個子表的構(gòu)造過程如下：（1）若項目A.a

屬于Ik且GO(Ik,a)=Ij，a為終結(jié)符，則置ACTION[k,a]為”sj”；（2）若項目A.

屬于Ik，則對任何終結(jié)符a（包括終結(jié)符$），置ACTION[k,a]為”rj”（注：j是產(chǎn)生式A的編號，而不是狀態(tài)集的狀態(tài)號）；（3）若項目S’→S·屬于Ik(S·表示整個句子已輸入并歸約結(jié)束)，則置ACTION[k,$]為“acc”，表示接受。（4）若GO[Ik,A]=Ij，A為非終結(jié)符，則置GOTO[k,A]=j;（5）分析表凡不能用規(guī)則(1)-(4)填入的空白格均置為“error”。例：S(S)|a狀態(tài)序號ACTIONGOTO終結(jié)符和$非終結(jié)符0……n分析表格式82例x：已知文法G[S]，求其LR(0)的分析表。

SaA|bB

AcA|d

BcB|dS

b.BB

.cBB

.d解:(1)識別文法活前綴的DFAA

d.A

c.AA

.cAA

.dS

a.AA

.cAA

.dB

c.BB

.cBB

.dS

.SS

.aAS

.bBstartS

S.A

cA.S

aA.AddAcabSS

bB.B

cB.B

d.BddBccc0123456789101183狀態(tài)actiongotoabcd$SAB01234567891011s2s3accs5s6s8s9r1r1

r1

r1

r1s5s6r4r4

r4

r4

r4r2r2

r2

r2

r2s8s9r6r6

r6

r6

r6r3r3

r3

r3

r3r5r5

r5

r5

r51

4710

11(2)LR(0)分析表(1)識別文法活前綴的DFAA

d.A

c.AA

.cAA

.dS

a.AA

.cAA

.dS

b.BB

.cBB

.dB

c.BB

.cBB

.dS

.SS

.aAS

.bBstartS

S.A

cA.S

aA.AddAcabSS

bB.B

cB.B

d.BddBccc012367891011450SS1SaA2SbB

3AcA4Ad

5BcB6Bd84例：已知文法G[E]，分析i*i+i∈L(G[E])?EE+T|TTT*F|FF(E)|i出現(xiàn)問題：由該文法識別活前綴的DFA看的出來，有的有效項目集中存在著移進－歸約沖突，不能用LR(0)分析方法進行分析。解決方法：對含有沖突的項目集向前查看一個輸入符號，這種分析方法稱為SLR(1)分析方法。復(fù)習(xí)：LR(0)文法中不能存在移進－歸約沖突或者歸約－歸約沖突。■引例85解：(1)拓廣文法G的拓廣文法G[E]：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fi(3)TT*F

(2)識別文法的活前綴的DFA(3)SLR(1)分析表

(4)分析過程例：已知文法G[E]，并用SLR(1)方法分析i*i+i∈L(G[E])?EE+T|TTT*F|FF(E)|iSLR(1)的分析過程與LR(0)的分析過程完全一樣，唯一不同的是分析表！E’EEE+TETTT*FTFF(E)FidEE’EEE+TTETTT*F(F(E)EE+TETTT*FTFF(E)FidI0I1I2I6FTFI3FididI5TI2FI3idI5(EE+TTT*FTFF(E)Fid+*TT*FF(E)FidI7F(E)EE+TEI8TEE+TTT*FI9FI3idI5(FTT*FI10idI4(I4*I7)F(E)+I6I11G

：(0)EE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fid

(2)識別文法的活前綴的DFA87若有效項目集中存在沖突動作:I={X.b,A.,B.}將b移進棧將

歸約為A將

歸約為B解決方法：設(shè)當(dāng)前輸入符號為x,1.若x=b,則移進;2.若xFollow(A),則用A進行歸約;3.若xFollow(B),則用B進行歸約;4.其余情況報錯.要求：移進項目的符號集FOLLOW(A)FOLLOW(B)=■SLR(1)分析法88對于表達式文法的例子，F(xiàn)OLLOW集如下：G

：(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*FI2:FOLLOW(E)∩{*}=ΦI9:FOLLOW(E)∩{*}=Φ∴可用SLR(1)方法實現(xiàn)FOLLOW集E’$E$，），+T$，），+，*F$，），+，*EE+TTT*FETTT*FI2:I9:89●SLR分析表的構(gòu)造算法輸入：一個拓廣文法G

輸出：對于G

的分析表的action子表和goto子表方法：1.構(gòu)造G

的LR(0)項目集規(guī)范族。2.對于狀態(tài)Ii的分析動作如下：

(a)若A.aBIi且go(Ii,a)=

Ij

action[i,a]=shiftj(b)若A.Ii,對于所有aFollow(A)

action[i,a]=reduceA,AS(c)若SS.Ii,action[i,$]=accept3.若go(Ii,A)=Ij,AVN,則goto[i,A]=j4.分析表其余位置為error90(3)SLR分析表Follow(E)={$,+,)}ACTIONGOTO+*()id$ETF0S4S51231S6ACC2R2S7R2R23R4R4R4R44S4S58235R6R6R6R66S4S5937S4S5108S6S119R1S7R1R110R3R3R3R311R5R5R5R591(4)id*id+id的LR分析過程分析棧輸入串動作(1)0(2)0id5(3)0F3(4)0T2(5)0T2*7(6)0T2*7id5(7)0T2*7F10(8)0T2(9)0E1(10)0E1+6(11)0E1+6id5(12)0E1+6F3(13)0E1+6T9(14)0E1id*id+id$*id+id$*id+id$*id+id$id+id$+id$+id$+id$+id$id$$$$$

shiftreducebyF

idreducebyTFshiftshiftreducebyFidreducebyTT*FreducebyETshiftshiftreducebyFidreducebyTFreducebyEE+Taccept92例：已知文法G[S]：S→(S)S|ε，求其SLR(1)的分析表，并判斷()()∈L(G)?(3)SLR(1)分析表(2)構(gòu)造識別文法活前綴的DFA，并判斷用何種方法進行分析解:(1)拓廣文法(4)分析過程注意：|ε|=0，所以用S→ε進行歸約時，不用出棧，直接將S入棧即可。LR(0)分析不了的，SLR(1)有可能能分析；LR(0)能分析的，SLR(1)都能分析！■課堂練習(xí)●example例：已知文法G[S]，求其SLR(1)的分析表，并判斷()()∈L(G)?

S→rD

DD,i|i(3)構(gòu)造分析表(2)識別文法活前綴的DFA解:(1)拓廣文法(4)分析過程94SLR(1)方法與LR(0)方法的區(qū)別僅在于有效項目集中有歸約項目時：在LR(0)方法中，若項目集Ik含有A

，則在狀態(tài)k時，無論面臨什么輸入符號都用“A

”進行歸約——即假定A

產(chǎn)生式編號為j，則在分析表ACTION部分，對應(yīng)狀態(tài)k行的所有欄目都填”rj”。在SLR(1)方法中，若項目集Ik含有A

，則在狀態(tài)k時，僅當(dāng)輸入符號為a∈FOLLOW(A)時，才用”

A

”進行歸約，這樣在分析表ACTION部分狀態(tài)k行，所有b不屬于FOLLOW(A)的欄目將空出來。若正好在b這一列有移進項目不會產(chǎn)生沖突。SLR(1)方法比LR(0)優(yōu)越，它可以解決更多的沖突。95例：已知文法G[S]，請判斷id:=id∈L(G)?S→id|V:=EV→idE→V|n■引例該文法的SLR[1]分析表中存在歸約－歸約沖突，該文法不能用SLR[1]分析方法進行分析。所以要采用另一種新的方法——LR[1]分析方法對該文法進行語法分析。4.5.4一般的LR(1)分析由于用SLR(1)方法解決動作沖突時，它僅孤立地考察對于規(guī)約項目Aα.，只要當(dāng)前面臨輸入符號a∈FOLLOW(A)時，就確定使用規(guī)則Aα進行規(guī)約，而沒有考察符號串α所在規(guī)范句型的環(huán)境。因為如果棧里的符號串為$δa，規(guī)約后變成$δA，當(dāng)前讀到的輸入符號是a，若文法中不存在以δAa為前綴的規(guī)范句型，那么，這種規(guī)約無效。

LR(1)分析法的思想是在分析過程中，當(dāng)試圖用某一規(guī)則Aα規(guī)約棧頂?shù)姆柎習(xí)r，不僅應(yīng)該查看棧中符號δα，還應(yīng)向前掃視一個輸入符號a，只有當(dāng)δAa的確構(gòu)成文法某一規(guī)范句型的前綴時，才能用此規(guī)則進行規(guī)約。為此，可以考慮在原來LR(0)項目集中增加更多的展望信息，這些展望信息有助于克服動作沖突和排除無效規(guī)約。一個LR(1)項目是一個二元組[Aα.β,a]，其中Aα.β是一個LR(0)項目，每個a是終結(jié)符，稱它為展望符或搜索符。當(dāng)β≠ε時，搜索符是無意義的；當(dāng)β＝ε時，搜索符a明確指出當(dāng)[Aα.,a]是棧頂狀態(tài)的一個LR(1)項目時，僅在輸入符號是a時才能用Aα規(guī)約，而不是對FOLLOW(A)中的所有符號用Aα規(guī)約。99

■LR(1)分析法LR(1)項：LR(1)項是由LR(0)項和一個先行記號組成的對，利用中括號將LR[1]項寫作：

[A

，a]其中A

是一個LR[0]項，稱為“心”；而a則是一個記號（先行），稱為“向前搜索符”。a∈FOLLOW(A)。100假設(shè)有LR[1]項目[AX，a]，其中X是任意符號（終結(jié)符或非終結(jié)符），那么X就有一個到項目[AX，a]的轉(zhuǎn)換。轉(zhuǎn)換函數(shù)（1）I的任何項目都屬于CLOSURE(I);（2）若項目[AB，a]屬于CLOSURE(I)，B

是文法中的一條規(guī)則，b屬于

First（a），則項目[B,b]屬于CLOSURE(I);（3）重復(fù)（2）直到CLOSURE(I)不再增大為止。項目集I的閉包函數(shù)■LR(1)分析法101■LR(1)分析表的構(gòu)造(1)若項目[Aa

，b]屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符，則置ACTION[k,a]為“sj”；(3)若項目[S’S，$]屬于Ik，則置ACTION[k,$]為“acc”;(4)若GO[Ik,A]=Ij,A為非終結(jié)符，則置GOTO（Ik,A）=j；(5)分析表中凡不能用規(guī)則(1)-(4)填入信息的空白欄均置為“error”。(2)若項目[A

，a]屬于Ik，則置ACTION[k,a]為“rj”，其中j是產(chǎn)生式的編號;102例：已知文法G[S]:S→id|V:=E V→id E→V|n求其LR(1)的分析表，并判斷id:=id∈L(G)?(3)LR(1)分析表(2)識別文法活前綴的DFA解:(1)拓廣文法(4)分析過程103解:(1)拓廣文法并對產(chǎn)生式進行編號0：S’→S1：S→id2：S→V:=E3：V→id4：E→V5：E→n(2)識別文法活前綴的DFA[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n,$][V→.id,$][Sid.,$][Vid.,:=][S’→.S,$][S→.id,$][S→.V:=E,$][V→.id,:=]start[S

S.,$][E→V.,$]V:=idVS[S→V:=E.,$][E→n.,$]nE01234567[V→id.,$]id8104(3)LR(1)分析表id := n $ S V E 012345678Action gotoS2 1 3 ACC R3 R1 S4 S8 S7 6 5 R2 R4 R5 R30S’→S1S→id2S→V:=E3V→id4E→V5E→n[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n,$][V→.id,$][Sid.,$][Vid.,:=][S’→.S,$][S→.id,$][S→.V:=E,$][V→.id,:=]start[S

S.,$][E→V.,$]V:=idVS[S→V:=E.,$][E→n.