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