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

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

學習目標

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

確定的有窮自動機DFA

非確定的有窮自動機NFA

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

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

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

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

自動機理論：是編譯程序詞法分析的理論基礎。

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

1.狀態(tài)轉換圖的引進和構造

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

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

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

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

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

當前狀態(tài)輸入串的其余部分語法樹SababaaaZAbabaaaZaBabaaaAaAbaaaBaBaaaAbAaaBaZaAbZaa推導：ZZaAaaBaaaAbaaaBabaaaAbabaaaababaaa3.應用狀態(tài)轉換圖為正則語言構造正則文法

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

ε

a

ab

a|b

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

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

控制器輸入帶ababa…#

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

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

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

其中：Κ

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

Σ有窮的輸入字母表

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

即有轉換函數(shù)

(,a)=,、∈Κ

表示當前狀態(tài)為，輸入符號為a時，轉換到

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

例：由例3-1的狀態(tài)轉換圖構造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)轉換矩陣例3-1

或或

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

輸入

狀態(tài)abSABAZBBAZZZ上例：

輸入

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

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

Σ有窮的輸入字母表

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

?開始狀態(tài)?

ΚF終止狀態(tài)FΚ

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

輸入

狀態(tài)ab

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

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

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

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

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

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

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

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

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

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

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

Σ={a,b}F={}轉換：①=[,]②({,},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個無關狀態(tài)，可刪去。

輸入

狀態(tài)ab

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

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

死狀態(tài)

無用狀態(tài)

3.2.2自動機的化簡

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

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

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

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

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

劃分狀態(tài)K=(終止狀態(tài)集,非終止狀態(tài)集)

進一步劃分,

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

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

合，否則分兩個集合。

重復，直到每個集合不能再劃分。

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

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

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

合并，得：3.3正則表達式（正則式）定義：

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

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

”也可用“|”

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

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

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

…}L()={ε,aa,ab,aab,…}L()={a,aab,aabab,…}正則集：對于標識符的描述類似于擴充的BNF表示法<標識符>∷=<字母>{<字母>|<數(shù)字>}又如可含有正負號的整數(shù)和小數(shù)可表示為：

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

R={+,-,

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

R

?≠RR??≠

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

n≥0}

用正則表達式

β

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

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

的映射

棧中初始符號∈

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

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

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

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