《編譯原理簡明教程》 第3章

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

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

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

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

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

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

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

自動機(jī)：是從識別語言出發(fā)，定義了語言。

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

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

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

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

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

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

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

對于形如Q→Rq的規(guī)則,④以文法開始符號為終止?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)換圖識別句子識別句子：從開始狀態(tài)到終止?fàn)顟B(tài)經(jīng)過的邊上的符號序列。識別句子的步驟：①從開始狀態(tài)出發(fā)，以欲識別符號串的最左字符開始，尋找標(biāo)有該字符的邊，狀態(tài)變化。②掃描下一個字符，從當(dāng)前狀態(tài)出發(fā)尋找標(biāo)有該字符的邊，當(dāng)前狀態(tài)變化。③重復(fù)第②步，直到掃描完所有字符為止，且當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。定理1

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

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

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

ε

a

ab

a|b

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

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

控制器輸入帶ababa…#

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

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

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

其中：Κ

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

Σ有窮的輸入字母表

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

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

(,a)=,、∈Κ

表示當(dāng)前狀態(tài)為，輸入符號為a時，轉(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)=定義:

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

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

或或

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

輸入

狀態(tài)abSABAZBBAZZZ上例：

輸入

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

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

Σ有窮的輸入字母表

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

?開始狀態(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識別符號串babbabb的過程:步驟當(dāng)前狀態(tài)輸入串余留部分可能的后繼狀態(tài)選擇狀態(tài)1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ8.

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

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

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

接受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的一個狀態(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)=[,,]∴={[,],[],[,],[],[,,]}=[,]={[],[,],[,,]}

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

輸入

狀態(tài)ab

[][][,][][][,][][,,][][][,,][][,,]43.2DFA的化簡

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

死狀態(tài)

無用狀態(tài)

3.2.2自動機(jī)的化簡

——求自動機(jī)狀態(tài)最少化問題

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

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

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

刪除無關(guān)狀態(tài)2.自動機(jī)的簡化算法：

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

進(jìn)一步劃分,

對于(,a)=,(,a)=

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

合，否則分兩個集合。

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

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

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

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

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

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

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

”也可用“|”

例：Σ={a,b}見書P48

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

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

…}L()={ε,aa,ab,aab,…}L()={a,aab,aabab,…}正則集：對于標(biāo)識符的描述類似于擴(kuò)充的BNF表示法<標(biāo)識符>∷=<字母>{<字母>|<數(shù)字>}又如可含有正負(fù)號的整數(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下推自動機(jī)(PDA)例：文法G[Z]:Z→Z(Z)|ε語言：ε,(),(()),((())),()(),…成對括號自動機(jī)：下推自動機(jī)可解決上述自動機(jī)的缺陷3.4.1下推自動機(jī)的機(jī)器模型由一條輸入帶，一個有限控制器和一個下推棧組成abaa…#控制器輸入帶┆棧頂下推棧3.4.2PDA的形式定義定義：PDA是一個七元組=(K,∑,,δ,S,,F)其中：K是狀態(tài)集合∑字母表

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

的映射

棧中初始符號∈

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

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

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

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