《編譯原理簡(jiǎn)明教程》 第3章

《編譯原理簡(jiǎn)明教程》普通高等教育“十二五”規(guī)劃計(jì)算機(jī)教材---太原理工大學(xué)---計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院---馮秀芳、崔冬華、段富等第一章引言第二章形式語(yǔ)言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語(yǔ)法分析—自頂向下分析方法第六章語(yǔ)法分析—自底向上分析方法第七章語(yǔ)義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表第十一章目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織與分配第十二章出錯(cuò)處理第十三章編譯程序自動(dòng)生成工具簡(jiǎn)介第十四章面向?qū)ο笳Z(yǔ)言的編譯第十五章并行編譯技術(shù)目錄第3章自動(dòng)機(jī)理論

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

本章主要介紹有窮自動(dòng)機(jī)的理論及借助有窮自動(dòng)機(jī)實(shí)現(xiàn)詞法分析程序的方法。著重需要掌握以下內(nèi)容:

確定的有窮自動(dòng)機(jī)DFA

非確定的有窮自動(dòng)機(jī)NFA

NFA到DFA的轉(zhuǎn)換DFA的最小化正規(guī)表達(dá)式到DFA的轉(zhuǎn)換目錄3.1有限自動(dòng)機(jī)的基本概念3.2確定有限自動(dòng)機(jī)DFA的化簡(jiǎn)3.3正則表達(dá)式形式定義3.4下推自動(dòng)機(jī)PDA

文法：是從語(yǔ)言生成的角度定義了語(yǔ)言。

自動(dòng)機(jī)：是從識(shí)別語(yǔ)言出發(fā)，定義了語(yǔ)言。

自動(dòng)機(jī)---是具有離散輸入/出系統(tǒng)的一種數(shù)學(xué)模型。

自動(dòng)機(jī)理論：是編譯程序詞法分析的理論基礎(chǔ)。

3.1有限自動(dòng)機(jī)的基本概念3.1.1有限自動(dòng)機(jī)的定義和表示法

1.狀態(tài)轉(zhuǎn)換圖的引進(jìn)和構(gòu)造

定義1：轉(zhuǎn)換圖（TG）是定義在∑上的有向圖，滿(mǎn)足以下條件a.至少存在一個(gè)初始結(jié)點(diǎn)b.存在一些終止結(jié)點(diǎn)（也可為空）c.每條邊上標(biāo)有∑上的符號(hào)（也可為ε）

例：TG接收（or識(shí)別）的符號(hào)串：從某一初始結(jié)點(diǎn)到某一終止結(jié)點(diǎn)的序列。TG所接收的符號(hào)串集合：

L（TG）L（TG）={ab，bab，babbb，abbb，……}狀態(tài)轉(zhuǎn)換圖：結(jié)點(diǎn)-----狀態(tài)------文法的非終結(jié)符初始結(jié)點(diǎn)-----初始結(jié)點(diǎn)終止結(jié)點(diǎn)-----終止結(jié)點(diǎn)-----開(kāi)始符號(hào)邊------轉(zhuǎn)換關(guān)系------終結(jié)符號(hào)∑={a，b}1.狀態(tài)轉(zhuǎn)換圖構(gòu)造算法:②以每個(gè)非終結(jié)符號(hào)做其它狀態(tài)③對(duì)于形如Q→q的規(guī)則,

對(duì)于形如Q→Rq的規(guī)則,④以文法開(kāi)始符號(hào)為終止?fàn)顟B(tài)例3-1：文法G[Z]：Z→Za|Aa|BbA→Ba|aB→Ab|b①以S做初始狀態(tài)(S∨)2.應(yīng)用狀態(tài)轉(zhuǎn)換圖識(shí)別句子識(shí)別句子：從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)經(jīng)過(guò)的邊上的符號(hào)序列。識(shí)別句子的步驟：①?gòu)拈_(kāi)始狀態(tài)出發(fā)，以欲識(shí)別符號(hào)串的最左字符開(kāi)始，尋找標(biāo)有該字符的邊，狀態(tài)變化。②掃描下一個(gè)字符，從當(dāng)前狀態(tài)出發(fā)尋找標(biāo)有該字符的邊，當(dāng)前狀態(tài)變化。③重復(fù)第②步，直到掃描完所有字符為止，且當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。定理1

當(dāng)識(shí)別一個(gè)符號(hào)串?時(shí)，如果能從轉(zhuǎn)換圖的開(kāi)始狀態(tài)出發(fā)行進(jìn)達(dá)到的右端，那么，?為句子的充要條件是最后的當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。例：判斷ababaaa及bababbb是否句子

當(dāng)前狀態(tài)輸入串的其余部分語(yǔ)法樹(shù)SababaaaZAbabaaaZaBabaaaAaAbaaaBaBaaaAbAaaBaZaAbZaa推導(dǎo)：ZZaAaaBaaaAbaaaBabaaaAbabaaaababaaa3.應(yīng)用狀態(tài)轉(zhuǎn)換圖為正則語(yǔ)言構(gòu)造正則文法

正則語(yǔ)言→狀態(tài)轉(zhuǎn)換圖→正則文法

ε

a

ab

a|b

b例3-3正則語(yǔ)言{|n≥0}正則文法：Z→CbC→b|BbB→AbA→a|Ba3.1.2有限自動(dòng)機(jī)(FA)FA可看作一個(gè)機(jī)器模型，由一個(gè)帶讀頭的有限控制器和一條字符輸入帶組成。工作原理：讀頭從左到右掃描輸入帶，讀到一個(gè)字符，狀態(tài)改變，同時(shí)讀頭右移一個(gè)字符，…，直到讀頭讀到

“#”，狀態(tài)進(jìn)入終止?fàn)顟B(tài)?？刂破髦邪ㄓ邢迋€(gè)狀態(tài)，讀入一個(gè)字符形成狀態(tài)轉(zhuǎn)換。

控制器輸入帶ababa…#

后繼狀態(tài)為自身狀態(tài)轉(zhuǎn)換后繼狀態(tài)為一個(gè)DFA

后繼狀態(tài)為多個(gè)NFA3.1.3確定有限自動(dòng)機(jī)(DFA)

定義：DFA是一個(gè)五元組=(Κ,Σ,,?,F)

其中：Κ

是狀態(tài)的非空有限集

Σ有窮的輸入字母表

是從ΚXΣ到Κ的映射，且為單值，

即有轉(zhuǎn)換函數(shù)

(,a)=,、∈Κ

表示當(dāng)前狀態(tài)為，輸入符號(hào)為a時(shí)，轉(zhuǎn)換到

?初始狀態(tài)?∈ΚF非空的終止?fàn)顟B(tài)集FΚ

例：由例3-1的狀態(tài)轉(zhuǎn)換圖構(gòu)造DFA如下

=({S,Z,A,B},{a,b},,S,{Z})其中：

(S,a)=A,

(S,b)=B

(A,a)=Z,

(A,b)=B

(B,a)=A,

(B,b)=Z

(Z,a)=Z例:=({,,,},{a,b,c},,,{,})

(,a)=,

(,a)=(,b)=,

(,c)=(,a)=,

(,b)=(,a)=,(,b)=定義:

所接收的語(yǔ)言（正則集）L()={β|S,∈F},

見(jiàn)書(shū)定義4.5L(D)={ab,ac,aaab,abaa…,acb…,…}β1、狀態(tài)轉(zhuǎn)換矩陣?yán)?-1

或或

注：空白或0表示空狀態(tài)（無(wú)后繼狀態(tài)）3.1.4DFA在計(jì)算機(jī)內(nèi)的表示0ABZZZAB0

輸入

狀態(tài)abSABAZBBAZZZ上例：

輸入

狀態(tài)abc2.表結(jié)構(gòu)表示（見(jiàn)表3.2）S2aAbBA2aZbB狀態(tài)名射出邊數(shù)邊上的標(biāo)記轉(zhuǎn)換后的狀態(tài)3.1.5不確定有限自動(dòng)機(jī)(NFA)定義：NFA是一個(gè)五元組，=(Κ,Σ,,?,F)

其中：Κ是狀態(tài)的非空有限集

Σ有窮的輸入字母表

是從ΚXΣ到Κ的子集的映射

?開(kāi)始狀態(tài)?

ΚF終止?fàn)顟B(tài)FΚ

例：=(Κ,Σ,,?,F)其中Κ={,,}Σ={a,b}?={,}F={}(,a)={}(,b)={,}(,a)=Φ(,b)={}(,a)=Φ(,b)={}得出：

輸入

狀態(tài)ab

例3-7由正則文法構(gòu)造NFAG[Z]:Z→Za|Aa|BbA→Ba|Za|aB→Ab|Ba|b識(shí)別符號(hào)串babbabb的過(guò)程:步驟當(dāng)前狀態(tài)輸入串余留部分可能的后繼狀態(tài)選擇狀態(tài)1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ8.

由此可見(jiàn)，在NFA中由于某些狀態(tài)的轉(zhuǎn)換需從

若干個(gè)可能的后繼狀態(tài)中進(jìn)行選擇，這種不確定

性給識(shí)別過(guò)程帶來(lái)反復(fù)，影響了工作效率。3.1.6NFA到DFA的等價(jià)轉(zhuǎn)換定理3：設(shè)L是一個(gè)為NFA某所接受的符號(hào)串集合，則存在一個(gè)

接受L的DFA，即L(D)=L(N)。算法：NFA=(Κ,Σ,,?,F)DFA=(,,,,)

1、若NFA中全部初始狀態(tài)為,,…,

則令DFA的初始狀態(tài)=[,,…,][]表示若干狀態(tài)構(gòu)成某一狀態(tài)

2、設(shè)Q=[,,…,]是DFA的一個(gè)狀態(tài)

在NFA中，({,,…,},a)={,,…,}

則令([,,…,],a)=[,,…,]。3、重復(fù)第2步，直到不出現(xiàn)新的狀態(tài)為止。4、上面得到DFA的狀態(tài)集，映射,Σ

不變。5、在DFA中，含有NFA終止?fàn)顟B(tài)的狀態(tài)均為DFA的終止?fàn)顟B(tài)。例=(Κ,Σ,,?,F)其中S={,}K={,,}

Σ={a,b}F={}轉(zhuǎn)換：①=[,]②({,},a)={}({,},b)={,}∴([,],a)=[]([,],b)=[,]③({},a)=Φ({},b)={}({,},a)={}({,},b)={,,}∴([],b)=[]

([,],a)=[]([,],b)=[,,]({},b)={}([],b)=[]({,,},a)={}([,,],a)=[]({,,},b)={,,}

([,,],b)=[,,]∴={[,],[],[,],[],[,,]}=[,]={[],[,],[,,]}

見(jiàn)書(shū)例3-9NFA有4個(gè)狀態(tài)，考慮狀態(tài)集合的一切子集。DFA中有2-1=15個(gè)狀態(tài)，其中有7個(gè)無(wú)關(guān)狀態(tài)，可刪去。

輸入

狀態(tài)ab

[][][,][][][,][][,,][][][,,][][,,]43.2DFA的化簡(jiǎn)

化簡(jiǎn)：對(duì)于一個(gè)DFA，構(gòu)造另一DFA，使L()=L()且的狀態(tài)個(gè)數(shù)不多。3.2.1等價(jià)狀態(tài)和無(wú)關(guān)狀態(tài)定義：等價(jià)狀態(tài),分別為一個(gè)狀態(tài)，L()是從出發(fā)導(dǎo)出的所有符號(hào)串，若L()=L()，則稱(chēng)，是等價(jià)狀態(tài)。定義：無(wú)關(guān)狀態(tài)無(wú)用狀態(tài)：從開(kāi)始狀態(tài)不能到達(dá)的狀態(tài)。死狀態(tài)：不能到達(dá)終止?fàn)顟B(tài)的狀態(tài)。例：L()=L()={a},是等價(jià)狀態(tài)

死狀態(tài)

無(wú)用狀態(tài)

3.2.2自動(dòng)機(jī)的化簡(jiǎn)

——求自動(dòng)機(jī)狀態(tài)最少化問(wèn)題

1、不等價(jià)狀態(tài)的區(qū)別

對(duì)于狀態(tài)，有(,a)=,(,a)=

若與等價(jià)，則稱(chēng),等價(jià)，否則,不等價(jià)。(,a)=，(,b)=，、等價(jià)嗎？上例合并等價(jià)狀態(tài)

刪除無(wú)關(guān)狀態(tài)2.自動(dòng)機(jī)的簡(jiǎn)化算法：

劃分狀態(tài)K=(終止?fàn)顟B(tài)集,非終止?fàn)顟B(tài)集)

進(jìn)一步劃分,

對(duì)于(,a)=,(,a)=

若,屬同一狀態(tài)集合，則,將放在同一集

合，否則分兩個(gè)集合。

重復(fù)，直到每個(gè)集合不能再劃分。

同一集合中的狀態(tài)為等價(jià)狀態(tài)，進(jìn)行合并。

若有無(wú)關(guān)狀態(tài)，則將其刪除。

例：解：{,,,}{}(,a)=,(,a)=,(,a)=,(,a)=(,b)=,(,b)=,(,b)=,(,b)=∴{,,,}={,,}{}又∵(,b)=∴{,,}={,}{}{,}{}{}{}

合并，得：3.3正則表達(dá)式（正則式）定義：

①ε，Φ是Σ上正則表達(dá)式。{ε}，Φ②任意a∈Σ是正則表達(dá)式。{a}③若,是正則表達(dá)式{},{}則,?,,也是正則表達(dá)式。正則式所描述的語(yǔ)言又稱(chēng)為正則集，記L(R)。|

用正則運(yùn)算符（閉包，連接，并）來(lái)構(gòu)造描述語(yǔ)言的表達(dá)式。例：b,0110(01|10)“

”也可用“|”

例：Σ={a,b}見(jiàn)書(shū)P48

正則表達(dá)式也是描述單詞的重要工具。正則表達(dá)式：

ε,Φ,a,b,ab,,…L(ε)={ε},L(Φ)=Φ,L(a)={a}L()={ε,a,aa,aaa,

…}L()={ε,aa,ab,aab,…}L()={a,aab,aabab,…}正則集：對(duì)于標(biāo)識(shí)符的描述類(lèi)似于擴(kuò)充的BNF表示法<標(biāo)識(shí)符>∷=<字母>{<字母>|<數(shù)字>}又如可含有正負(fù)號(hào)的整數(shù)和小數(shù)可表示為：

(D={0,1,2,…,9})

R={+,-,

ε}(..)Σ={<字母>，<數(shù)字>}正則表達(dá)式<字母>正則集L(R)={<字母>,<字母><字母>,<字母><數(shù)字>,…}例：G=({A},{α,β},A,P)性質(zhì)：Rф=RR??=R

R

?≠RR??≠

фRф=фR=фR?=?R=R=()==()=()P:A→αA|βL(G[A])={β,αβ,ααβ,…}={β|

n≥0}

用正則表達(dá)式

β

正則集L(β)={β,αβ,ααβ,…}3.4下推自動(dòng)機(jī)(PDA)例：文法G[Z]:Z→Z(Z)|ε語(yǔ)言：ε,(),(()),((())),()(),…成對(duì)括號(hào)自動(dòng)機(jī)：下推自動(dòng)機(jī)可解決上述自動(dòng)機(jī)的缺陷3.4.1下推自動(dòng)機(jī)的機(jī)器模型由一條輸入帶，一個(gè)有限控制器和一個(gè)下推棧組成abaa…#控制器輸入帶┆棧頂下推棧3.4.2PDA的形式定義定義：PDA是一個(gè)七元組=(K,∑,,δ,S,,F)其中：K是狀態(tài)集合∑字母表

下推字母表（棧符號(hào)的有限集）δ從Kx(∑∪{ε})x→Kx

的映射

棧中初始符號(hào)∈

S初始狀態(tài)集SKF終止?fàn)顟B(tài)集FK轉(zhuǎn)換函數(shù)δ(,a,)=(,β)表示：在狀態(tài)，輸入a，棧頂符號(hào)為時(shí)，進(jìn)

入狀態(tài)，由符號(hào)串β代替，同時(shí)讀頭

右移一格。(β的最左符號(hào)放在棧頂，即β的逆串放入下推棧)特別：當(dāng)β=ε時(shí)，表示被彈出，讀頭右移;

當(dāng)a=ε時(shí)，表示讀頭不動(dòng)，狀態(tài)仍轉(zhuǎn)換。例：Z→Z(Z)|ε