編譯原理簡(jiǎn)明教程（第3版）-課件 第3章 自動(dòng)機(jī)原理

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

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

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

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

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

目錄3.1有限自動(dòng)機(jī)的基本概念3.2確定有限自動(dòng)機(jī)DFA的化簡(jiǎn)3.3正則表達(dá)式形式定義3.4下推自動(dòng)機(jī)PDA3.5本章小結(jié)43.1有限自動(dòng)機(jī)的基礎(chǔ)5定義3.1：有限自動(dòng)機(jī)定義為一個(gè)五元組：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)。確定有限自動(dòng)機(jī)

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

至少存在一個(gè)初始結(jié)點(diǎn)

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

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

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

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

終止結(jié)點(diǎn)--終止?fàn)顟B(tài)--開(kāi)始符號(hào)

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

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

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

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

而對(duì)于形如A→Bc

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

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

特別地，一個(gè)狀態(tài)轉(zhuǎn)換圖可以不止一個(gè)初始狀態(tài)，也可以有不止一個(gè)終止?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)換圖識(shí)別句子識(shí)別句子：從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)經(jīng)過(guò)的邊上的符號(hào)序列。識(shí)別句子（α）的步驟：10定理3.1當(dāng)識(shí)別一個(gè)符號(hào)串α?xí)r，如果能從轉(zhuǎn)換圖的初始狀態(tài)出發(fā)行進(jìn)達(dá)到α的右端，那么，α為句子的充要條件是：最后的當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。用狀態(tài)轉(zhuǎn)換圖識(shí)別句子的過(guò)程，稱為運(yùn)行狀態(tài)轉(zhuǎn)換圖。111從開(kāi)始狀態(tài)出發(fā)，以它作為當(dāng)前狀態(tài)，并從α的最左字符開(kāi)始，重復(fù)第二步到達(dá)α的最右端為止2掃描α的下一個(gè)字符（當(dāng)前字符），在當(dāng)前狀態(tài)射出的各條邊中找出標(biāo)有該字符的邊并沿此邊前進(jìn)，以所達(dá)到的狀態(tài)作為下一個(gè)當(dāng)前狀態(tài)。例3.2：對(duì)句子ababaaa進(jìn)行分析并生成語(yǔ)法樹(shù)

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

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

ε

a

ab

a|b

13b14正則文法：

A→CbC→Bb|bB→AbA→Ba|a例3.3正則語(yǔ)言{|n≥0}153.1.2有限自動(dòng)機(jī)的機(jī)器模型

有限自動(dòng)機(jī)（FA，F(xiàn)initeAutomata）可看作一個(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)換。

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

輸入帶ababa…#控制器163.1.3

確定有限自動(dòng)機(jī)（DFA）

定義3.3：DFA是一個(gè)五元組

D=(Κ,Σ,,?,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Κ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)造確定有限自動(dòng)機(jī)如下：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

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

1、矩陣表示

例3.6

或

或

注：

S0表示初始狀態(tài)，0表示無(wú)后繼狀態(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不確定有限自動(dòng)機(jī)（NFA）定義3.6

NFA是一個(gè)五元組，=(Κ,Σ,,?,F)其中：Κ是狀態(tài)的非空有限集Σ有窮的輸入字母表是從ΚXΣ到Κ的子集的映射?開(kāi)始狀態(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對(duì)于輸入符號(hào)串babbabb運(yùn)行過(guò)程:28

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

解決這一問(wèn)題的一個(gè)方法就是下面將介紹的使NFA轉(zhuǎn)換成等價(jià)的DFA。293.1.6NFA到DFA的等價(jià)轉(zhuǎn)換定理3.3：設(shè)L是一個(gè)為某NFA所接受的符號(hào)串集合，則存在一個(gè)接受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的一個(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)。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確定有限自動(dòng)機(jī)DFA的化簡(jiǎn)

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

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

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

死狀態(tài)

無(wú)用狀態(tài)403.2.2自動(dòng)機(jī)的化簡(jiǎn)上例合并等價(jià)狀態(tài)刪除無(wú)關(guān)狀態(tài)

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

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

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

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

2、進(jìn)一步劃分,

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

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

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

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

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

例：解:10

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

∴{,

,

}={

,}{

}又∵(,b)=∴{

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

,}

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

用正則運(yùn)算符來(lái)構(gòu)造描述語(yǔ)言的表達(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項(xiàng)都是正則表達(dá)式。例：Σ={a,b}正則表達(dá)式：

ε,Φ,a,b,ab，

,

,…

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

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

對(duì)于標(biāo)識(shí)符的描述

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

正則表達(dá)式

<字母>

正則集

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

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

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

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

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

用正則表達(dá)式β

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

49自動(dòng)機(jī)：下推自動(dòng)機(jī)可解決上述自動(dòng)機(jī)的缺陷

語(yǔ)言：

ε,(),(()),((())),()(),…成對(duì)括號(hào)3.4.1下推自動(dòng)機(jī)的機(jī)器模型

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

P=(K,∑,,δ,S,,F)其中：K是狀態(tài)集合∑是輸入字母表下推字母表（棧符號(hào)的有限集）δ從Kx(∑∪{ε})x→Kx的映射下推棧中的初始下推符號(hào)號(hào)∈ S初始狀態(tài)集SKF終止?fàn)顟B(tài)集FK51轉(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)換。52【例3.11】

Z→Z(Z)|

ε

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

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

輸入符號(hào)A(()(()))A(()(()))A(()(()))A((()))A((()))A((()))A(())A(