編譯原理簡明教程（第3版）-課件 第3章 自動機原理

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

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

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

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

軟件構(gòu)造23自動機理論基礎(chǔ)本章主要介紹狀態(tài)轉(zhuǎn)換圖定義、有限自動機的理論及下推自動機的的理論。著重需要掌握以下內(nèi)容：確定的有限自動機DFA非確定的有限自動機NFANFA到DFA的轉(zhuǎn)換DFA的最小化下推自動機PDA3學(xué)習(xí)目標(biāo)

目錄3.1有限自動機的基本概念3.2確定有限自動機DFA的化簡3.3正則表達(dá)式形式定義3.4下推自動機PDA3.5本章小結(jié)43.1有限自動機的基礎(chǔ)5定義3.1：有限自動機定義為一個五元組：D=(K,Σ,δ,S,F)。K是有窮的非空狀態(tài)集合；Σ是有窮的輸入字母表；δ是從K×Σ到K的映射，表示狀態(tài)的轉(zhuǎn)換（狀態(tài)轉(zhuǎn)換函數(shù)）；S是初始狀態(tài)；F是終止?fàn)顟B(tài)。確定有限自動機

(DFA)：每次轉(zhuǎn)換的后繼狀態(tài)都是唯一的不確定有限自動機(NFA)：轉(zhuǎn)換的后繼狀態(tài)不是唯一的3.1.1有限自動機的定義和表達(dá)式1.狀態(tài)轉(zhuǎn)換圖的引進和構(gòu)造定義3.2：狀態(tài)轉(zhuǎn)換圖是定義在字母表上的有向圖，滿足以下三個條件：

至少存在一個初始結(jié)點

存在一些終止?fàn)顟B(tài)結(jié)點（也可為空）

每條邊上標(biāo)有字母表∑上的符號（也可為空串ε）6例：TG接收（or識別）的符號串：從某一初始結(jié)點到某一終止結(jié)

點的序列。TG所接收的符號串集合：L（TG）={ab，bab，abbb，……}狀態(tài)轉(zhuǎn)換圖：結(jié)點------狀態(tài)------文法的非終結(jié)符

初始結(jié)點--初始狀態(tài)

終止結(jié)點--終止?fàn)顟B(tài)--開始符號

邊--------轉(zhuǎn)換關(guān)系--終結(jié)符號∑={a，b}70S1S2Sbbbba算法3.1

正則文法構(gòu)造狀態(tài)轉(zhuǎn)換圖算法

將S設(shè)為初始狀態(tài)（假定文法的字母表中不含符號S）以每一個非終結(jié)符號作為其它狀態(tài)對于形如A→b

的每個規(guī)則，引一條從初始狀態(tài)S到狀態(tài)A的邊，其標(biāo)記為b；

而對于形如A→Bc

的規(guī)則，引一條從狀態(tài)B到A的邊，其標(biāo)

記為c（其中A、B為非終結(jié)符號，b、c為終結(jié)符號）。④以文法開始符號作為終止?fàn)顟B(tài)。

特別地，一個狀態(tài)轉(zhuǎn)換圖可以不止一個初始狀態(tài)，也可以有不止一個終止?fàn)顟B(tài)。8

例3.1：文法G[Z]，其中，VN=｛Z,A,B｝，VT=｛a,b｝。Z→Za|Aa|BbA→Ba|aB→Ab|b92.應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子識別句子：從開始狀態(tài)到終止?fàn)顟B(tài)經(jīng)過的邊上的符號序列。識別句子（α）的步驟：10定理3.1當(dāng)識別一個符號串α?xí)r，如果能從轉(zhuǎn)換圖的初始狀態(tài)出發(fā)行進達(dá)到α的右端，那么，α為句子的充要條件是：最后的當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。用狀態(tài)轉(zhuǎn)換圖識別句子的過程，稱為運行狀態(tài)轉(zhuǎn)換圖。111從開始狀態(tài)出發(fā)，以它作為當(dāng)前狀態(tài)，并從α的最左字符開始，重復(fù)第二步到達(dá)α的最右端為止2掃描α的下一個字符（當(dāng)前字符），在當(dāng)前狀態(tài)射出的各條邊中找出標(biāo)有該字符的邊并沿此邊前進，以所達(dá)到的狀態(tài)作為下一個當(dāng)前狀態(tài)。例3.2：對句子ababaaa進行分析并生成語法樹

當(dāng)前狀態(tài)輸入串的其余部分語法樹SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZ

123.應(yīng)用狀態(tài)轉(zhuǎn)換圖為正則語言構(gòu)造正則文法狀態(tài)轉(zhuǎn)換正則文法正則語言

ε

a

ab

a|b

13b14正則文法：

A→CbC→Bb|bB→AbA→Ba|a例3.3正則語言{|n≥0}153.1.2有限自動機的機器模型

有限自動機（FA，F(xiàn)initeAutomata）可看作一個機器模型，由一個帶讀頭的有限控制器和一條字符輸入帶組成。工作原理：讀頭從左到右掃描輸入帶，讀到一個字符，狀態(tài)改變，同時讀頭右移一個字符，…，直到讀頭讀到“#”，狀態(tài)進入終止?fàn)顟B(tài)?？刂破髦邪ㄓ邢迋€狀態(tài)，讀入一個字符形成狀態(tài)轉(zhuǎn)換。

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

輸入帶ababa…#控制器163.1.3

確定有限自動機（DFA）

定義3.3：DFA是一個五元組

D=(Κ,Σ,,?,F)

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

Σ有窮的輸入字母表

是從ΚXΣ到Κ的映射，且為單值，即如果有轉(zhuǎn)換函數(shù)(,a)=,、∈Κ表示當(dāng)前狀態(tài)為，輸入符號為a時，轉(zhuǎn)換到

?初始狀態(tài)?∈Κ

F非空的終止?fàn)顟B(tài)集FΚDFA----DeterministicFiniteAotomaton17例3.4：由例3.1的狀態(tài)轉(zhuǎn)換圖構(gòu)造DFA如下

D1=

({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

同理，由例3.3中的狀態(tài)轉(zhuǎn)換圖構(gòu)造確定有限自動機如下：D2=({S,A,B

,C,Z},{a,b},,S,{Z})

18(S,a)=A

(S,a)=C(A,b)=

(B,a)=

(B,b)=C(C,b)=

19定義3.5

由有限自動機接受的符號串集合稱為正則集，記為L（D）。20定義3.4對于某個DFAD=(K,Σ,δ,S,F)，如果δ(S,α)=P，P∈F，則稱字符串α可被該DFAD所接受(識別)。3.1.4有限自動機在計算機內(nèi)的表示

1、矩陣表示

例3.6

或

或

注：

S0表示初始狀態(tài)，0表示無后繼狀態(tài)

輸入狀態(tài)abS0=SAB

S1=AZB

S2=BAZ

S3=ZZ0ABZZZAB021上例：

輸入狀態(tài)abc222.表結(jié)構(gòu)表示狀態(tài)名射出邊數(shù)標(biāo)記1指向下一狀態(tài)……標(biāo)記k指向下一狀態(tài)k233.1.5不確定有限自動機（NFA）定義3.6

NFA是一個五元組，=(Κ,Σ,,?,F)其中：Κ是狀態(tài)的非空有限集Σ有窮的輸入字母表是從ΚXΣ到Κ的子集的映射?開始狀態(tài)?ΚF終止?fàn)顟B(tài)FΚ24例：=(Κ,Σ,,?,F)其中

Κ={,,

}Σ={a,b}?={,}F={}(,a)={}(,b)={,}(,a)=Φ(,b)={}(,a)=Φ(,b)={}25

得出：

輸入狀態(tài)ab

26例3.7由正則文法G[Z]=(VN,VT,S,P)構(gòu)造NFA其中VN={Z,A,B}VT={a,b}P集為Z→Za|Aa|BbA→Ba|Za|aB→Ab|Ba|b27步驟當(dāng)前狀態(tài)輸入串余留部分可能的后繼狀態(tài)選擇狀態(tài)

1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ8.

例3.8對于輸入符號串babbabb運行過程:28

由此可見，在NFA中由于某些狀態(tài)的轉(zhuǎn)換需從若干個可能的后繼狀態(tài)中進行選擇，這種不確定性給識別過程帶來反復(fù)，影響了工作效率。

解決這一問題的一個方法就是下面將介紹的使NFA轉(zhuǎn)換成等價的DFA。293.1.6NFA到DFA的等價轉(zhuǎn)換定理3.3：設(shè)L是一個為某NFA所接受的符號串集合，則存在一個接受L的DFA，即L(D)=L(N)。

算法3.2:NFAN=

(Κ,Σ,,?,F)DFAN’=(,,,,)

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

則令DFA的初始狀態(tài)=[,,…,]

[]表示由若干狀態(tài)構(gòu)成的某一狀態(tài)302、設(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)。31例3.9=(Κ,Σ,,?,F)其中S={,}K={,,}Σ={a,b}F={}32

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

33

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

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

輸入狀態(tài)ab

[][][,][][]

[,][][,,][]

[][,,][][,,]363.2確定有限自動機DFA的化簡

化簡：對于一個DFA，構(gòu)造另一DFA，使L()=L()且的狀態(tài)個數(shù)不多于

的狀態(tài)個數(shù)。定義3.7：設(shè)A1與A2是兩個有限自動機，如果L(A1)=L(A2),即接受相同的語言，則稱這兩個有限自動機A1與A2等價。373.2.1等價狀態(tài)和無關(guān)狀態(tài)定義3.8從Si出發(fā)能導(dǎo)出的所有符號串集合記為L(Si)，設(shè)有兩個狀態(tài)Si和Sj，若有L(Si)=L(Sj)則稱Si和Sj是等價狀態(tài)。定義3.9無關(guān)狀態(tài)包括無用狀態(tài)和死狀態(tài)。對于狀態(tài)Si

，若從初始狀態(tài)不可能到達(dá)該狀態(tài)，則稱Si為無用狀態(tài)。對于狀態(tài)Si，若從該狀態(tài)出發(fā)不能到達(dá)終止?fàn)顟B(tài)，則稱Si為死狀態(tài)。38L()=L(),是等價狀態(tài)例(如圖3.9)：39AbabbSBZABAB

死狀態(tài)

無用狀態(tài)403.2.2自動機的化簡上例合并等價狀態(tài)刪除無關(guān)狀態(tài)

1、不等價狀態(tài)的區(qū)別對于狀態(tài)，有(,a)=,(,a)=若與等價，則稱,等價，否則,不等價。(,a)=，(,b)=，、等價嗎？41

2.自動機的化簡

算法3.3自動機的化簡

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

2、進一步劃分,

直到不產(chǎn)生新的劃分。

對于(,a)=,(,a)=若,屬同一狀態(tài)集合，則,將放在同一集合，否則分兩個集合。

3、重復(fù)步驟2，直到每個集合不能再劃分為止，此時每個狀態(tài)集合中的狀態(tài)均是等價的。

4、合并等價狀態(tài)，即在等價狀態(tài)集合中取任一狀態(tài)作為代表，刪去其他一切等價狀態(tài)。

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

例：解:10

{,,}{,}(,a)=,(,a)=,(,a)=(,b)=,(,b)=,(,b)=43

∴{,

,

}={

,}{

}又∵(,b)=∴{

,}={}{}{}{}{}{

,}

合并，得：443.3正則表達(dá)式形式定義

用正則運算符來構(gòu)造描述語言的表達(dá)式，稱作正則表達(dá)式。

1.α;α∈∑;2.ε;3.Φ;4.(R1∪R2),這里R1和R2是正則表達(dá)式；5.(R1·R2),這里R1和R2是正則表達(dá)式；6.(R1*),這里R1是正則表達(dá)式。45定義3.10正則表達(dá)式的形式定義：

如果R1和R2是正則表達(dá)式，則以下1~6項都是正則表達(dá)式。例：Σ={a,b}正則表達(dá)式：

ε,Φ,a,b,ab，

,

,…

L(ε)={ε},L(Φ)=Φ,L(a)={a}L()={ε,a,aa,aaa,…}L()={ε,aa,ab,aab,…}L()={a,aab,aabab,…}正則集：見書P53

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

對于標(biāo)識符的描述

Σ={<字母>，<數(shù)字>}

正則表達(dá)式

<字母>

正則集

L(R)={<字母>,<字母><字母>,

<字母><數(shù)字>,…}

類似于擴充的BNF表示法<標(biāo)識符>∷=<字母>{<字母>|<數(shù)字>}

47例：G=({A},{α,β},A,P)

P:A→αA|βL(G[A])={β,αβ,ααβ,…}={β|n≥0}

用正則表達(dá)式β

正則集L(β)={β,αβ,ααβ,…}483.4下推自動機（PDA）例：文法G[Z]:Z→Z(Z)|ε

49自動機：下推自動機可解決上述自動機的缺陷

語言：

ε,(),(()),((())),()(),…成對括號3.4.1下推自動機的機器模型

由一條輸入帶，一個有限控制器和一個下推棧組成abaa…#控制器輸入帶┆棧頂下推棧503.4.2PDA的形式定義定義3.12PDA定義為一個七元組

P=(K,∑,,δ,S,,F)其中：K是狀態(tài)集合∑是輸入字母表下推字母表（棧符號的有限集）δ從Kx(∑∪{ε})x→Kx的映射下推棧中的初始下推符號號∈ S初始狀態(tài)集SKF終止?fàn)顟B(tài)集FK51轉(zhuǎn)換函數(shù)

δ(,a,)=(,β)表示：在狀態(tài)，輸入a，棧頂符號為時，進入狀態(tài)，由符號串β代替，同時讀頭右移一格。

(β的最左符號放在棧頂，即β的逆串放入下推棧)特別：當(dāng)β=ε時，表示被彈出，讀頭右移;當(dāng)a=ε時，表示讀頭不動，狀態(tài)仍轉(zhuǎn)換。52【例3.11】

Z→Z(Z)|

ε

其中K={},∑={(,)},={A,(}S={},=A,F={}δ(,(,A)=(,(A)δ(,(,()=(,(()δ(,),()=(,ε)δ(,ε,A)=(,ε)=(K,∑,,δ,S,,F)53

當(dāng)前狀態(tài)下推棧

輸入符號A(()(()))A(()(()))A(()(()))A((()))A((()))A((()))A(())A(