詞法分析(1)---詞法分析的有關(guān)概念以及轉(zhuǎn)換圖
詞法分析是編譯的第一個(gè)階段，前面簡(jiǎn)介中也談到過詞法分析器的任務(wù)就是：
字符流------>詞法記號(hào)流
這里詞法分析和語法分析會(huì)交錯(cuò)進(jìn)行，也就是說，詞法分析器不會(huì)讀取所有的詞法記號(hào)再使用語法分析器來處理，通常情況下，每取一個(gè)詞法記號(hào)，就送入語法分析器進(jìn)行分析，圖解：
詞法分析器是編譯器中與源程序直接接觸的部分，因此詞法分析器可以做諸如
1). 去掉注釋，自動(dòng)生成文檔(c#中的///注釋)
2). 提供錯(cuò)誤位置(可以通過記錄行號(hào)來提供)，當(dāng)字符流變成詞法記號(hào)流以后，就沒有了行的概念
3). 完成預(yù)處理，比如宏定義
1. 詞法記號(hào)，詞法單元(lexeme)，模式
模式是一種規(guī)則
每個(gè)詞法單元都有一個(gè)特定記號(hào)
比如 int a=3，這里 int，a，＝，3都是詞法單元，每個(gè)詞法單元都屬于某個(gè)詞法記號(hào)，比如3就是"num"這個(gè)詞法記號(hào)的一個(gè)詞法單元，而模式規(guī)定了什么樣的字符串的詞法記號(hào)是什么樣的(模式是一種規(guī)則)
某一特定模式規(guī)定了某個(gè)詞法記號(hào)下的一類詞法單元，比如：
模式：用字母開頭的包含字母和數(shù)字的串
上面模式的詞法記號(hào)：id(所有符合上面模式的字符串的記號(hào)都是id)
詞法單元：a123 或者 aabc 等
詞法記號(hào)舉例(簡(jiǎn)稱為記號(hào))：
1) 每個(gè)的關(guān)鍵字都有屬于自己的一個(gè)記號(hào)，比如關(guān)鍵字for，它可以使用記號(hào)for；關(guān)鍵字int，可以使用記號(hào)int
2) 所有的關(guān)系運(yùn)算符只有一個(gè)記號(hào)，比如 >=,<=都用記號(hào)relation
3) 所有的標(biāo)識(shí)符只有一個(gè)記號(hào)，比如a123,aab使用記號(hào)id
4) 所有的常數(shù)只有一個(gè)記號(hào)，比如123,22,32.3,23E10使用記號(hào)num
5) 所有的字符串只有一個(gè)記號(hào)，比如"123","ab1"使用記號(hào)literal
在實(shí)際的編譯器設(shè)計(jì)中，詞法記號(hào)，一般用一個(gè)整形數(shù)字表示
詞法記號(hào)的屬性：
我們喜歡用<詞法記號(hào), 屬性>這個(gè)二元組來描述一個(gè)詞法單元，比如，對(duì)于源代碼：position := initial + rate * 60
對(duì)于詞法單元 +，我們可以使用 <add_op, '+'> 來表示。
有些情況，更加復(fù)雜一點(diǎn)，比如對(duì)于 position，我們表示是這樣的，<id, 指向符號(hào)表中的position元素的指針>，詳細(xì)來說應(yīng)該是這樣的，假定屬性是一個(gè)字符串，那么id將指向這樣一個(gè)字符串"position\0"，我們把存放這個(gè)字符串的地方叫做符號(hào)表。有些時(shí)候，屬性是不必要的，比如 := ，表示賦值，我們可以使用 <assign_op,257> 這樣的表示這個(gè)詞法單元，不過這個(gè)顯得有些多于，因?yàn)?span lang="EN-US">assign_op和詞法單元是一對(duì)一的，也就是assign_op只對(duì)應(yīng)了:=，所以額外信息(屬性)就顯得多余的了
詞法錯(cuò)誤：
詞法分析器是很難(有些錯(cuò)誤還是可以檢測(cè))檢測(cè)錯(cuò)誤的，因?yàn)樵~法分析器的目的是產(chǎn)生詞法記號(hào)流，它沒有能力去分析程序結(jié)構(gòu)，因此無法檢測(cè)到和程序結(jié)構(gòu)有關(guān)的錯(cuò)誤，比如：
fi(a == b)
詞法分析器不會(huì)找到這個(gè)錯(cuò)誤，它認(rèn)為 fi 是一個(gè)標(biāo)識(shí)符，而不是一個(gè)關(guān)鍵字，只有在后面的階段中，這個(gè)錯(cuò)誤才會(huì)被發(fā)現(xiàn)，這是一個(gè)與程序結(jié)構(gòu)有關(guān)的錯(cuò)誤
詞法分析器，只能檢測(cè)到詞法單元上的問題，比如 12.ab ，作為一個(gè)詞法單元，卻不沒有對(duì)應(yīng)的模式，那么就是產(chǎn)生一個(gè)錯(cuò)誤。
2. 正規(guī)式：
前面說過模式是一種規(guī)則，為了使用，我們需要一種規(guī)范的方式來表達(dá)模式，這就是正規(guī)式
1) 串和語言
字符類(又叫字母表)：關(guān)于字符的有限集合
串：字符類上字符的有窮序列，串這個(gè)概念，具體來說是，某個(gè)字符類上的串
串的長度：串中字符的個(gè)數(shù)，比如串 s = abc ，那么串的長度為3，用|s|表示串的長度
空串：用 ε 表示
語言：某字符類上的串的集合，屬于語言的串，成為語言的句子或字
比如：{abc, a}這就是一個(gè)語言，abc和a就是句子。另外空集也是屬于語言
連接：x是串，y是串，x和y連接，結(jié)果就是 xy 這個(gè)串。假如 x 是串，x^3為 xxx。對(duì)于 x^n (n>=0),x^0 = ε
語言的運(yùn)算(假定L和M是語言)：
1. L U M = {s|s屬于L或者M}，例如：
L={1,2} M={3,4} 那么 L U M = {1,2,3,4}
2. LM = {st|s屬于L且t屬于M}，例如：
L={a,b} M={1,2} 那么 LM = {a1,a2,b1,b2} ML={1a,1b,2a,2b}
3. L^n = LLL...LLL (n個(gè)L)，例如：
L={a,b} 那么 L^3 = {aaa,aab,aba,abb,baa,bab,bbb,bba}
注意 n 可以為0，L^0 = {ε}
4. L* = L^0 U L^1 U L^2 U L^3 U ...
L*表示，語言L中，所有的句子(串)以任意數(shù)目任意順序組成的句子的集合，包括 ε，例如：
{a,b}* = {ε,a,b,ab,ba,aab,aba,baa,bba,bab,abb,aaa,bbb...}
L*叫做L的閉包
5. L+ = L^1 U L^2 U L^3 U...
L+表示，語言L中，所有的句子(串)以任意數(shù)目任意順序組成的句子的集合，但是不包括 ε
L+中的句子和 L*中的句子相比少一個(gè) ε
那么，我們通過上面的知識(shí)就可以表示一個(gè)標(biāo)識(shí)符了，我們知道一般語言規(guī)定標(biāo)識(shí)符是由字母開頭，后接若干個(gè)字母或數(shù)字，我們可以這樣來表示： L={a-z A-Z} N={0-9}，那么標(biāo)識(shí)符就是 L(L U N)*
2) 正規(guī)式
正規(guī)式又叫正規(guī)表達(dá)式，正規(guī)式是模式得一種規(guī)范的表達(dá)形式，正規(guī)式描述了一個(gè)集合，這個(gè)集合是由串組成的，其實(shí)這個(gè)集合就是我們前面說過的語言，不過這里大家喜歡使用正規(guī)集這個(gè)術(shù)語。正規(guī)式 r 表示正規(guī)集L(r)
正規(guī)式的運(yùn)算：
1. 閉包運(yùn)算，運(yùn)算優(yōu)先級(jí)最高，(r)* 表示 (L(r))*
2. 連接運(yùn)算，運(yùn)算優(yōu)先集合低于閉包，(r)(s) 表示 (L(r))(L(s))
3. 或運(yùn)算，運(yùn)算優(yōu)先集合最低，(r) | (s) 表示 (L(r)) U (L(s))
例如：
a | b 表示集合(語言，正規(guī)集) {a,b}
(a | b)(a | b) 表示集合(語言，正規(guī)集) {aa,ab,ba,bb}
a* 表示由一切a字符組成的集合(語言，正規(guī)集)，包括 ε
(a | b) 表示由a,b組成的集合(語言，正規(guī)集)，包括 ε
等價(jià)的正規(guī)式：(a | b) = (b | a)
正規(guī)式的代數(shù)性質(zhì)：
1. r|s = s|r
2. r|(s|t) = (r|s)|t
3. (rs)t = r(st)
4. r(s|t) = rs|rt
5. εr = r
6. r** = r*
7. r* = (r|ε)*
注意，rs != sr 因?yàn)檫B接運(yùn)算是有順序的，記住并理解2個(gè)最基本的運(yùn)算：a|b表示{a,b}，ab表示{ab}
3. 正規(guī)定義
我們可以使用 名字 -> 正規(guī)式這種表示，來說明一個(gè)等價(jià)的代替，比如：
dight -> 0|1|2|3|4|5|6|7|8|9
這里，我們就可以使用名字 digit 來代替后面的正規(guī)表達(dá)式
我們可以對(duì)某個(gè)串集進(jìn)行正規(guī)定義，比如我們對(duì)標(biāo)識(shí)符集合進(jìn)行正規(guī)定義：
letter -> A|B|...|Z|a|b|...|z
dight -> 0|1|2|3|4|5|6|7|8|9
id -> letter(letter|dight)*
請(qǐng)通過上面的例子理解正規(guī)定義。
在我們表達(dá)正規(guī)表達(dá)式的時(shí)候，可以使用一些符號(hào)使得表達(dá)簡(jiǎn)化
1) + ，表示一個(gè)或者多個(gè)實(shí)力，比如，a+ 表示 {a,aa,aaa,aaaa,...}。區(qū)別一下*,他們的關(guān)系是這里 r+ = r* | ε
2) 字符組，[abc]表示a|b|c，還可以這樣表示[a-zA-Z]表示字母表中的字符
4. 狀態(tài)轉(zhuǎn)換圖
狀態(tài)轉(zhuǎn)換圖是對(duì)詞法分析器進(jìn)行分析過程的描述，我們看一個(gè)判斷關(guān)系運(yùn)算的狀態(tài)轉(zhuǎn)化圖：
1) 圖中圓圈表示狀態(tài)
2) 箭頭叫做邊。X狀態(tài)的邊，一般指的是由X狀態(tài)出發(fā)，指向其他狀態(tài)的邊
3) 邊上的符號(hào)叫做標(biāo)記
如何來使用這個(gè)圖？假定輸入字符串是 <= ，那么識(shí)別開始時(shí)，發(fā)現(xiàn) < 和狀態(tài)0與狀態(tài)1間的邊上的標(biāo)記一樣，那么就進(jìn)入1狀態(tài)，下一個(gè)輸入字符為=，將進(jìn)入2狀態(tài)，識(shí)別結(jié)束，返回二元組<relop,LE>
上圖中2，3，4，5，7，8狀態(tài)，他們表示識(shí)別了一個(gè)關(guān)系運(yùn)算符，這個(gè)狀態(tài)叫做接受狀態(tài)
狀態(tài)4上面有一個(gè)*，表示說，輸入指針需要回移。所謂的輸入指針，就是指向輸入字符串中現(xiàn)在被讀入的字符的位置，4狀態(tài)會(huì)多讀取一個(gè)字符，所以需要回移，也就是要注意的是，識(shí)別完成之后，輸入指針指向的是被識(shí)別對(duì)象的最后一個(gè)字符，而不是待識(shí)別對(duì)象的第一個(gè)字符，這樣的規(guī)定在實(shí)現(xiàn)詞法分析器時(shí)，是有一定的意義，舉例說明：
輸入字符串為： a>b
識(shí)別的時(shí)候，從>開始，讀入下一個(gè)字符b時(shí)，進(jìn)入4狀態(tài)，這個(gè)時(shí)候，輸入指針指向b，這時(shí)候需要回移
我們?cè)谛枰匾频臓顟B(tài)上加一個(gè)*
每個(gè)狀態(tài)后面有一個(gè)return(relop,XX)這個(gè)是狀態(tài)的行為，這里具體來說就是返回一個(gè)二元組的行為，詞法分析器分析的結(jié)果就是得到二元組(詞法記號(hào)和屬性的二元組)，這個(gè)二元組可以表示一個(gè)特定的字符串。其實(shí)上面的*，也是表示行為，也就是輸入指針回移的行為，我們可以看見，只有在接受狀態(tài)才會(huì)有行為出現(xiàn)
對(duì)一門典型的語言來說狀態(tài)可能有幾百個(gè)
5. 如何編寫一個(gè)詞法分析器
1) 根據(jù)需要寫出正規(guī)定義
2) 根據(jù)正規(guī)定義畫出轉(zhuǎn)換圖
3) 根據(jù)轉(zhuǎn)換圖寫出詞法分析器
這里詳細(xì)討論面向過程的語言來實(shí)現(xiàn)一個(gè)詞法分析器(比如c語言)，并且主要討論的是第3步
1) 我們需要一個(gè) nextchar() 函數(shù)，取得緩存中下一個(gè)等待分析的字符，這個(gè)函數(shù)完成年2個(gè)任務(wù)
1. 讓輸入指針向前移動(dòng)一位
2. 返回輸入指針指向的字符
2) 定義一個(gè)變量 token_beginning，在每個(gè)狀態(tài)轉(zhuǎn)換圖開始的時(shí)候，記錄輸入指針的位置，定義forward變量作為輸入指針
3) 狀態(tài)轉(zhuǎn)換圖被實(shí)現(xiàn)成為代碼之后，每個(gè)狀態(tài)都有屬于自己的一塊代碼，這些代碼按順序完成以下工作：
1. 讀取一個(gè)字符，通過nextchar()函數(shù)
2. 讀取的字符(標(biāo)志)，如果它和當(dāng)前狀態(tài)的邊上的標(biāo)記相同，那么狀態(tài)將轉(zhuǎn)換到邊所指向的狀態(tài)，具體實(shí)現(xiàn)只需要一個(gè)語句就是 state = xxx(xxx為目標(biāo)狀態(tài))；如果當(dāng)前狀態(tài)的所有邊的標(biāo)記和這個(gè)讀取字符不一樣，那么表示沒有找到token(詞法記號(hào))，這時(shí)候需要調(diào)用 fail() 函數(shù)
3. fail() 函數(shù)完成這樣的功能：a.指針回移，完成 forward ＝ token_beginning 的操作 b.找到適當(dāng)?shù)拈_始狀態(tài)(也就是尋找另外一個(gè)轉(zhuǎn)換圖的開始狀態(tài))。假定所有的轉(zhuǎn)換圖都被嘗試過，并且無法匹配，這時(shí)候會(huì)調(diào)用一個(gè)發(fā)現(xiàn)錯(cuò)誤的小程序，來報(bào)告錯(cuò)誤
4. 請(qǐng)不要隨意添加行為到各個(gè)狀態(tài)所持有的代碼中，應(yīng)該以轉(zhuǎn)換圖中表示的行為為準(zhǔn)
4) 定義一個(gè)全局變量 lexical_value，用于保存一個(gè)指針，這個(gè)指針由 install_id() 和 install_num() 兩個(gè)函數(shù)中的一個(gè)返回
5) 定義兩個(gè)整形變量 start,state，分別表示一個(gè)轉(zhuǎn)換圖的開始狀態(tài)和當(dāng)前的狀態(tài)
6) nexttoken()，這是詞法分析器的主程序，可以說，我們通過調(diào)用nexttoken()就完成了詞法分析，這個(gè)函數(shù)一定是這樣的格式：
while(1){
switch(state){
case xx:
...
case yy:
...
default:
...
}
}
關(guān)于詳細(xì)的設(shè)計(jì)這里就不說了，舉例說明一個(gè)轉(zhuǎn)換圖如何轉(zhuǎn)換成為程序：
這是一個(gè)識(shí)別浮點(diǎn)數(shù)的例子，看下面的代碼：
#include <stdio.h>
#include <ctype.h>
#include <string.h>
char *nexttoken();
char nextchar();
void next();
void back();
char* gettoken();
char cbuf[]="12.3*********klj12.2e2jj778";
int forward = -1;
int main(){
while(1){
printf("%s\n",nexttoken());
if(forward >= strlen(cbuf)-1){
getchar();
return 0;
}
}
}
int state;
int start;
char* nexttoken(){
char c;
state = 12;
while(1){
switch(state){
case 12:
c = nextchar();
start = forward;
if(isdigit(c)){
state = 13;
}else{
next();
}
break;
case 13:
c = nextchar();
if(isdigit(c))
state = 13;
else if(c == 'e'||c == 'E')
state = 16;
else if(c == '.')
state = 14;
else
state = 19;
break;
case 14:
c = nextchar();
if(isdigit(c))
state = 15;
break;
case 15:
c = nextchar();
if(isdigit(c))
state = 15;
else if(c == 'e'|| c == 'E')
state = 16;
else
state = 19;
break;
case 16:
c = nextchar();
if(isdigit(c))
state = 18;
else if(c == '+' || c == '-')
state = 17;
break;
case 17:
c = nextchar();
if(isdigit(c))
state = 18;
break;
case 18:
c = nextchar();
if(isdigit(c))
state = 18;
else
state = 19;
break;
case 19:
back();
return gettoken();
}
}
}
char nextchar(){
forward ++;
return cbuf[forward];
}
void back(){
forward --;
}
void next(){
forward ++;
}
char token_buf[128];
char* gettoken(){
int i,j=0;
for(i = start; i <= forward; i ++){
token_buf[j++] = cbuf[i];
}
token_buf[j] = '\0';
return token_buf;
}
詞法分析(2)---NFA
假定一個(gè)輸入符號(hào)(symbol)，可以得到2個(gè)或者2個(gè)以上的可能狀態(tài)，那么這個(gè)finite automaton就是不確定的，反之就是確定的。例如：
這就是一個(gè)不確定的無限自動(dòng)機(jī)，在symbol a輸入的時(shí)候，無法確定狀態(tài)應(yīng)該轉(zhuǎn)向0，還是1
不論是確定的finite automaton還是非確定的finite automaton，它們都可以精確的描述正規(guī)集(regular sets)
我們可以很方便的把正規(guī)表達(dá)式(regular expressions)轉(zhuǎn)換成為不確定 finite automaton
2. NFA(Nondeterministic Finite Automaton)
非確定的無限自動(dòng)機(jī)，我們用NFA這個(gè)術(shù)語表示，它是一個(gè)數(shù)學(xué)模型(model)：
1. 一個(gè)關(guān)于狀態(tài)的集合S
2. 一個(gè)關(guān)于輸入符號(hào)(input symbols)的集合Σ
3. 函數(shù) move : (狀態(tài), 符號(hào)) -> P(S)
4. 一個(gè)開始狀態(tài)s0，是一個(gè)唯一的狀態(tài)
5. 一個(gè)結(jié)束(接受)狀態(tài)集合F
注意，P(S)，表示S的冪集。在NFA中，input symbol可以為 ε
轉(zhuǎn)換函數(shù)(transition function)的含義就是，一個(gè)確定的狀態(tài)已經(jīng)從這個(gè)狀態(tài)出發(fā)的一條邊的標(biāo)簽(符號(hào)symbol)，可以確定它的下一個(gè)狀態(tài)組成的集合，比如上圖(這個(gè)轉(zhuǎn)換圖就是NFA的一種表示方式)，0狀態(tài)，a符號(hào)，確定了一個(gè)狀態(tài)的集合{0,1}
3. 轉(zhuǎn)換圖(transition graph)的表示
我們知道，計(jì)算機(jī)是無法直接表示一個(gè)圖，我們應(yīng)該如何來表示一個(gè)轉(zhuǎn)換圖？使用表格就是一個(gè)最簡(jiǎn)單的方法，每行表示一個(gè)狀態(tài)，每列表示一個(gè)input symbol，這種表格被叫做 transtion table(轉(zhuǎn)換表)
可以說使用表格是最簡(jiǎn)單的表示方式，但是我們可以注意到在這個(gè)圖中狀態(tài)1和input symbol a，是沒有下一個(gè)狀態(tài)的(空集合)，也就是，對(duì)于一個(gè)大的狀態(tài)圖，我們可能花費(fèi)大量的空間，而其中空集合會(huì)消耗不少空間，但是這種消耗又不是必須的，所以，作為最簡(jiǎn)單的一種實(shí)現(xiàn)方式，卻不是最優(yōu)的
語言(language)被NFA定義成為一個(gè)input string的集合，而這個(gè)集合中的元素則是被NFA受接受的所有的字符串(那些可以從開始狀態(tài)到某接受狀態(tài)的input string)
至于存儲(chǔ)的方式，可以試試鄰接表。注意，使用什么樣的數(shù)據(jù)結(jié)構(gòu)來保存NFA按情況不同而不同，在一些特殊情況下，某些數(shù)據(jù)結(jié)構(gòu)會(huì)變得很方便使用，而換入其他情況，則不可以使用了。
詞法分析(3)---DFA
1. DFA(Deterministic Finite automaton)
DFA就是確定的有限自動(dòng)機(jī)，因?yàn)?span lang="EN-US">DFA和NFA關(guān)系密切，我們經(jīng)常需要把他們拿到一起來講，NFA可以轉(zhuǎn)化成為一個(gè)DFA，DFA依然是一個(gè)數(shù)學(xué)model，它和NFA有以下區(qū)別
1. 不存在ε-transition，也就是說，不存在ε為input symbol的邊
2. 對(duì)于move函數(shù)，move : (state, symbol) -> S，具體來說就是，一個(gè)狀態(tài)和一個(gè)特定的input symbol，不會(huì)映射到2個(gè)不同的狀態(tài)。這樣的結(jié)果是，每個(gè)狀態(tài)，關(guān)于每個(gè)特定的input symbol，只有一條出邊
下圖就是一個(gè)DFA：
接受語言(a|b)*ab，注意一下，接受語言(a|b)*ab的DFA我們前面見過，就是這張圖：
2. DFA的行為
我們用一個(gè)算法來模擬DFA的行為
s = s0;
c = nextchar();
while(c != EOF){
s = move(s,c);
c = nextchar();
}
if(s屬于F)
return "yes"
else
return "no"
詞法分析(4)---NFA與DFA的轉(zhuǎn)化
1. 子集構(gòu)造(Subset Construction)
這是一個(gè)轉(zhuǎn)換NFA到DFA的算法。我們知道NFA和DFA的區(qū)別最主要的就是一個(gè)狀態(tài)和一個(gè)input symbol是否能夠確定一個(gè)狀態(tài)的問題，對(duì)于NFA，它將確定一個(gè)組狀態(tài)，而DFA將確定一個(gè)狀態(tài)，因此，我們有一個(gè)很好的辦法就是把NFA的狀態(tài)集對(duì)應(yīng)每個(gè)DFA的狀態(tài)，這就是subset construction的思想，不過這只是大概泛泛而論，我們需要更加明確的認(rèn)識(shí)
1) NFA在任何一個(gè)input symbol下，映射的狀態(tài)集(通過move函數(shù)，這個(gè)集合通常用T字母表示)應(yīng)該被知道
2) 必須保證1)中狀態(tài)集都對(duì)應(yīng)了DFA中的一個(gè)狀態(tài)
具體算法：
Input : 一個(gè)NFA N
Output : 接受相同語言的DFA D
Method : 為D構(gòu)架一個(gè)transition table(轉(zhuǎn)換表) Dtran，每個(gè)DFA的狀態(tài)是一個(gè)NFA的狀態(tài)集合(這里一定要注意前面說過的1)2)兩點(diǎn))。我們定義一些操作：
s 表示NFA的狀態(tài)，T 表示NFA的狀態(tài)集合，a表示一個(gè)input symbol
ε-transition(ε轉(zhuǎn)換)就是說input symbol為ε時(shí)的transition(轉(zhuǎn)換)
| 操作(operation) | 描述(description) |
| ε-closure(s) | 從NFA的狀態(tài)s出發(fā)，只通過ε-transition到達(dá)的NFA的狀態(tài)集合 |
| ε-closure(T) | NFA的集合T中的狀態(tài)p，只通過ε-transition到達(dá)的NFA的狀態(tài)集合，再求這些集合的交集。用數(shù)學(xué)表達(dá)就是 {p|p 屬于 ε-closure(t) , t屬于T} |
| move(T,a) | NFA的集合，這個(gè)集合在input symbol為a，狀態(tài)為T中任意狀態(tài)情況下，通過一個(gè)轉(zhuǎn)換得到的集合 |
注意一下，所有的操作都是針對(duì)NFA的狀態(tài)或者狀態(tài)集合，得到的時(shí)NFA的狀態(tài)集合，或者說是DFA看為一個(gè)狀態(tài)
Subset Construction
初始Dstates，它僅僅含有狀態(tài)(D的狀態(tài))ε-closure(s0)，并且狀態(tài)未被標(biāo)記，s0表示開始狀態(tài)，注意，Dstates放的是D的狀態(tài)
while ( Dstates 有未標(biāo)記的狀態(tài) T ) { // T是D中的一個(gè)狀態(tài)，也是N中一個(gè)狀態(tài)集
標(biāo)記 T;
for ( input symbol a ){ // 遍歷所有的input symbol
U = ε-closure(move(T, a)); // move為NFA的move函數(shù)
if ( U 不在 Dstates 中 )
把U作為尚未標(biāo)記的狀態(tài)加入Dstates;
Dtran[T, a] = U
}
}
注意，狀態(tài)s，ε-closure(s)一定包含s
我們先來熟悉上面的操作operation，再來看上面的算法
ε-closure(0) = {0, 1, 2, 4, 7} // 從0狀態(tài)出發(fā)的，input symbol為ε的所有狀態(tài)的集合
ε-closure(3) = {1, 2, 3, 4, 6, 7}
ε-closure(8) = {8}
ε-closure( {3, 8} ) = ε-closure(3) U ε-closure(8) = {1, 2, 3, 4, 6, 7, 8}
move(0,a) = 空
move(7,a) = {8}
move(8,b) = {9}
move( {0, 1, 2, 4, 7}, a) = move(0,a) U move(1,a) U move(2,a) U move(4,a) U move(7,a) = {3, 8}
現(xiàn)在可以回去理解一下算法了。
這里再說說求ε-closure(T)的算法：
把T的所有狀態(tài)壓入stack(棧);
ε-closure(T)的初始值為 T 中的所有元素 ; // 也就是一定包含他們本身
while( 棧非空 ) {
彈出棧頂元素 t ;
for( 每個(gè)屬于 move(t, ε) 的狀態(tài) u ){
if( u 不在 ε-closure(T) 中 ){
u 加入 ε-closure(T);
把 u 入棧;
}
}
}
下面對(duì)上圖如何使用Set Construction算法來構(gòu)建DFA做一個(gè)詳細(xì)的描述：
1. 初始化Dstates 把集合 ε-closure(s0) = {0, 1, 2, 4, 7}作為第一個(gè)狀態(tài)，設(shè)此狀態(tài)為 A
2. 現(xiàn)在轉(zhuǎn)化，input symbol {a, b}，因此，求：
ε-closure(move(A, a));
ε-closure(move(A, b));
這里會(huì)得到2個(gè)狀態(tài)
ε-closure(move(A, a)) = {1, 2, 3, 4, 6, 7, 8},設(shè)其為 B
ε-closure(move(A, b)) = {1, 2, 4, 5, 6, 7}, 設(shè)其為C
B，C放入Dstates
改寫 Dtrans
最終得到的 Dtrans 為：
A = {0, 1, 2, 4, 7}
B = {1, 2, 3, 4, 6, 7, 8}
C = {1, 2, 4, 5, 6, 7}
D = {1, 2, 4, 5, 6, 7, 9}
因此，NFA轉(zhuǎn)化成為DFA：
詞法分析(5)---從正規(guī)式到NFA
在說到這個(gè)問題前，先告訴大家，我們可以直接從 Regular expression 到 DFA，不過這里我們先不討論這個(gè)問題
關(guān)于RE到DFA的算法有很多，這里學(xué)習(xí)一個(gè)最簡(jiǎn)單的
Algorithm Thompson's construction：
Input : 一個(gè)字母表(Σ)上的 Regular Experssion r
Output : 一個(gè)接受 L(r) 的 NFA N
Method : 把 r 解析成為子表達(dá)式(subexpressions)，然后使用下面的1),2)規(guī)則，為 r 中的基本符號(hào)(basic symbols,基本符號(hào)就是ε和Σ中的字符)構(gòu)建NFA，基本符號(hào)符合1),2)關(guān)于正規(guī)式的定義，注意，假如symbol a 出現(xiàn)多次，那么它每次出現(xiàn)都要構(gòu)建一個(gè)NFA。之后，我們需要通過 r 的語法結(jié)構(gòu)，通過規(guī)則3)組合前面構(gòu)建的NFA，直到得到整個(gè)NFA為止。對(duì)于中間產(chǎn)生的NFA，它只有一個(gè)終態(tài)，沒有進(jìn)入開始裝狀態(tài)的邊，也沒有離開接受狀態(tài)的邊。
1) 對(duì)于 ε 構(gòu)造如下NFA
注意，每次構(gòu)建時(shí)，i,f的值都不一樣，因此可見構(gòu)造一個(gè)識(shí)別 ε 的NFA，會(huì)產(chǎn)生2個(gè)新的狀態(tài)
2) 對(duì)于Σ中的每個(gè)字符a
同樣，對(duì)于aaa，第一個(gè)a構(gòu)造的NFA中的i,f不會(huì)和第2個(gè)a構(gòu)造的i,f一樣，因此可見構(gòu)造一個(gè)識(shí)別Σ中的每個(gè)字符a 的NFA，會(huì)產(chǎn)生2個(gè)新的狀態(tài)
3) 先假定 N(t) N(s) 分別是 t s 的NFA，則：
a) 對(duì)于表達(dá)式 s|t 構(gòu)建 NFA N(s|t)
這里一樣會(huì)產(chǎn)生2個(gè)新的狀態(tài)i,j，我們看其中一個(gè)N(s)，左邊的圓圈，表示N(s)的開始狀態(tài)，右邊的圓圈表示N(s)的接受狀態(tài)，N(t)同理
b) 對(duì)于表達(dá)式 st ,構(gòu)建N(st)
這個(gè)時(shí)候，不產(chǎn)生新的狀態(tài)，N(s)的開始狀態(tài)變?yōu)?span lang="EN-US">N(st)的開始狀態(tài)，N(t)的接受狀態(tài)變成N(st)的接受狀態(tài)，N(s)的接受狀態(tài)和N(t)開始狀態(tài)成為一個(gè)狀態(tài)。這里提醒一下，寫程序的時(shí)候，這里千萬要注意，因?yàn)闆]有新的狀態(tài)產(chǎn)生，必須考慮狀態(tài)的部分復(fù)制，如果不小心就會(huì)出錯(cuò)。
c) 對(duì)于正規(guī)式 s*，構(gòu)造N(s*)
這里一樣需要產(chǎn)生2個(gè)新的狀態(tài)i,f，注意，產(chǎn)生了一條N(s)接受狀態(tài)到N(s)開始狀態(tài)的邊，邊上的symbol為 ε
d) 對(duì)于(s)，使用N(s)本身作為它的NFA，也就是不用構(gòu)造新的NFA
注意一下，以上產(chǎn)生的NFA，有以下性質(zhì)：
1) 只有一個(gè)接受狀態(tài)和一個(gè)開始狀態(tài)
2) 每個(gè)狀態(tài)最多含有2個(gè)指向其他狀態(tài)的邊，詳細(xì)的來說，如果狀態(tài)只有一條指向其他狀態(tài)的邊，那么邊上的symbol為Σ中的任意字符或者ε，如果狀態(tài)有兩條指向其他狀態(tài)的邊，那么邊上的symbol一定為2個(gè)ε
由以上性質(zhì)，我們可以很好的選擇數(shù)據(jù)結(jié)構(gòu)來表示NFA
詞法分析(6)---DFA的化簡(jiǎn)
通過NFA轉(zhuǎn)化而成的DFA不一定是最簡(jiǎn)的，也就是說，有多余的狀態(tài)可以被刪除，對(duì)于每一個(gè)正規(guī)定義，我們一定可以得到一個(gè)唯一的最簡(jiǎn)的DFA
我們回顧一下Move函數(shù)，DFA的move函數(shù)：
move : (state, symbol) -> S
注意，這里(state, symbol)表示的是一個(gè)集合，這里規(guī)范的數(shù)學(xué)表達(dá)應(yīng)該是：
move : { (state, symbol) | 所有屬于DFA的state和symbol } -> S 或者
move : S × Σ -> S
假如一個(gè)DFA的move函數(shù)不是全函數(shù)，那么必須引入死狀態(tài)。假如某個(gè)DFA的move函數(shù)是全函數(shù)，那么每個(gè)狀態(tài)在所有input symbol下都有出邊，比如：
這個(gè)DFA每個(gè)狀態(tài)都可以接受所有的input symbol，這里是a，b。而下面的DFA：
先不要看紅色部分，那么這個(gè)DFA的狀態(tài)c，d，它們無法通過input symbol b 進(jìn)入下一個(gè)狀態(tài)，我們可以加上紅色的部分，把這個(gè)move函數(shù)，轉(zhuǎn)化成為一個(gè)全函數(shù)，并且，經(jīng)過轉(zhuǎn)化操作之后，新的DFA與原DFA等價(jià)。這個(gè)紅色部分標(biāo)識(shí)的狀態(tài)，被叫做死狀態(tài)
死狀態(tài)：
假如出現(xiàn)DFA的move函數(shù)不是全函數(shù)，我們可以引入一個(gè)死狀態(tài)S(僅僅引入一個(gè)方可)，這個(gè)狀態(tài)包括所有input symbol對(duì)自身的轉(zhuǎn)換，所有的其他狀態(tài)假如不接受某個(gè)input symbol a，那么，我們建立這個(gè)狀態(tài)到S且input symbol為 a 的邊。
狀態(tài)的區(qū)別：
假如一個(gè)狀態(tài)s，通過input string w，可以轉(zhuǎn)換到某個(gè)狀態(tài)，而某個(gè)狀態(tài)t，通過w，轉(zhuǎn)化到了一個(gè)與s通過w轉(zhuǎn)化到的狀態(tài)不同的狀態(tài)，那么我們就可以通過w來區(qū)別狀態(tài)s，t，如果這樣的w不存在，那么s，t這2個(gè)狀態(tài)是無法區(qū)別的。
每個(gè)接受狀態(tài)都可以通過ε和非接受狀態(tài)進(jìn)行區(qū)別。
化簡(jiǎn)算法，極小化DFA的思想：
極小化DFA算法，它把狀態(tài)分成一些不相交的子集，每一個(gè)子集中的所有狀態(tài)都是不可區(qū)別的，而不同子集中的每個(gè)狀態(tài)兩兩都是可區(qū)別的，最后我們把每個(gè)子集中的所有狀態(tài)合成一個(gè)狀態(tài)。
1) 劃分狀態(tài)集
首先把所有狀態(tài)劃分成為2個(gè)集合，一個(gè)集合是接受狀態(tài)的集合，一個(gè)集合是非接受狀態(tài)的集合，他們通過ε來區(qū)別。然后看每個(gè)集合中的狀態(tài)時(shí)候還可以區(qū)別，例如一個(gè)集合通過input symbol a，轉(zhuǎn)換后得到的狀態(tài)落入當(dāng)前劃分的不同集合，那么說明通過input symbol a，是可以區(qū)別這個(gè)集合中的狀態(tài)的(這里要強(qiáng)調(diào)的是，對(duì)于一個(gè)而不是多個(gè)input symbol，假如轉(zhuǎn)換到的狀態(tài)落入不同的劃分中那么這些狀態(tài)就是可以區(qū)別的)。我們假定有一個(gè)狀態(tài)集合{s1,s2},s1通過a到達(dá)狀態(tài)集合t1，s2通過a到達(dá)狀態(tài)集合t2，t1,t2分別是當(dāng)前劃分的狀態(tài)集合，那么，集合{s1,s2}就可以分成2個(gè)集合{s1},{s2}
2) 構(gòu)造最簡(jiǎn)的DFA
我們可以重復(fù)1)的步驟，最后得到一些子集合，我們從每個(gè)子集合中取一個(gè)狀態(tài)，通過它們可以得到最簡(jiǎn)的DFA，但具體需要按一定規(guī)則去構(gòu)建
極小化DFA狀態(tài)數(shù)的算法：
Input : 一個(gè)DFA M，它的狀態(tài)集是S，輸入符號(hào)集合Σ，move : S × Σ -> S，開始狀態(tài)為s0，接受狀態(tài)的集合為F
Output : 一個(gè)DFA N，它和DFA M等價(jià)，并為最簡(jiǎn)
Method :
1) 初始化: 假如move函數(shù)不是全函數(shù)，那么加入死狀態(tài)，構(gòu)造劃分X：把S分成2個(gè)子集合，包括接受狀態(tài)集合F和非接受狀態(tài)集合S-F(F集合的補(bǔ)集)
2) Xnew是一個(gè)劃分
for( X 中的每個(gè)集合G ){
G中狀態(tài)每次通過Σ中的symbol轉(zhuǎn)化到的狀態(tài)如果屬于X的不同子集，那么把集合G分成子集，每個(gè)symbol都可能劃分G，劃分之后，使用下一個(gè)symbol進(jìn)行操作，一直到遍歷完所有的input symbol
更新Xnew，用G的劃分代替G
}
3) 如果Xnew == X，那么定義 Xfinal = X，執(zhí)行4)，否則進(jìn)行賦值操作 X = Xnew，進(jìn)行2)
4) Xfinal中每個(gè)子集合中選擇一個(gè)狀態(tài)來代表這個(gè)狀態(tài)集合，包含s0的狀態(tài)集合，就是表示開始狀態(tài)的集合。通過DFA M來構(gòu)造DFA N，規(guī)則是這樣的：假如某狀態(tài)p通過某input symbol a，通過DFA M的move函數(shù)轉(zhuǎn)到另外一個(gè)狀態(tài)q，我們就用q所在的集合的代表狀態(tài)來表示q，并把這個(gè)轉(zhuǎn)換過程的邊，input symbol，集合的代表狀態(tài)，加入DFA N中。我們需要遍歷DFA M，然后按規(guī)則構(gòu)建DFA N。化簡(jiǎn)的DFA中，可能有多個(gè)接受狀態(tài)。
5) 如果N中有死狀態(tài)(終態(tài)不是死狀態(tài))，去掉它，有開始狀態(tài)無法到達(dá)的狀態(tài)，也去掉它。注意，在DFA N中有可能出現(xiàn)死狀態(tài)，也就是通過所有的input symbol都回到自己的狀態(tài)，前面說過，添加一個(gè)死狀態(tài)得到的新的DFA與原DFA等價(jià)，那么我們這里也自然可以刪除它。
在真正的實(shí)現(xiàn)上面算法的時(shí)候，是靈活的，因?yàn)槌鲇跁r(shí)間復(fù)雜度的考慮，可能并不需要完全照搬上面的算法，把握主要的思想是很重要的。
1) 每個(gè)input symbol都可能劃分一次集合
2) 每個(gè)集合都中的狀態(tài)被看成是不可區(qū)別的，即使在計(jì)算過程中某些集合中的狀態(tài)是可以區(qū)別的
3) 一定要確保每個(gè)集合都無法在分