詞法分析(1)---詞法分析的有關概念以及轉換圖

詞法分析是編譯的第一個階段，前面簡介中也談到過詞法分析器的任務就是：
字符流------>詞法記號流

這里詞法分析和語法分析會交錯進行，也就是說，詞法分析器不會讀取所有的詞法記號再使用語法分析器來處理，通常情況下，每取一個詞法記號，就送入語法分析器進行分析，圖解：

詞法分析器是編譯器中與源程序直接接觸的部分，因此詞法分析器可以做諸如
1).去掉注釋，自動生成文檔(c#中的///注釋)
2).提供錯誤位置(可以通過記錄行號來提供)，當字符流變成詞法記號流以后，就沒有了行的概念
3).完成預處理，比如宏定義

1.詞法記號，詞法單元(lexeme)，模式
模式是一種規則
每個詞法單元都有一個特定記號

比如int a=3，這里int，a，＝，3都是詞法單元，每個詞法單元都屬于某個詞法記號，比如3就是"num"這個詞法記號的一個詞法單元，而模式規定了什么樣的字符串的詞法記號是什么樣的(模式是一種規則)

某一特定模式規定了某個詞法記號下的一類詞法單元，比如：
模式：用字母開頭的包含字母和數字的串
上面模式的詞法記號：id(所有符合上面模式的字符串的記號都是id)
詞法單元：a123或者aabc等

詞法記號舉例(簡稱為記號)：
1)每個的關鍵字都有屬于自己的一個記號，比如關鍵字for，它可以使用記號for；關鍵字int，可以使用記號int
2)所有的關系運算符只有一個記號，比如>=,<=都用記號relation
3)所有的標識符只有一個記號，比如a123,aab使用記號id
4)所有的常數只有一個記號，比如123,22,32.3,23E10使用記號num
5)所有的字符串只有一個記號，比如"123","ab1"使用記號literal
在實際的編譯器設計中，詞法記號，一般用一個整形數字表示

詞法記號的屬性：
我們喜歡用<詞法記號,屬性>這個二元組來描述一個詞法單元，比如，對于源代碼：position := initial + rate * 60
對于詞法單元+，我們可以使用<add_op, '+'>來表示。
有些情況，更加復雜一點，比如對于position，我們表示是這樣的，<id,指向符號表中的position元素的指針>，詳細來說應該是這樣的，假定屬性是一個字符串，那么id將指向這樣一個字符串"position\0"，我們把存放這個字符串的地方叫做符號表。有些時候，屬性是不必要的，比如:=，表示賦值，我們可以使用<assign_op,257>這樣的表示這個詞法單元，不過這個顯得有些多于，因為assign_op和詞法單元是一對一的，也就是assign_op只對應了:=，所以額外信息(屬性)就顯得多余的了

詞法錯誤：
詞法分析器是很難(有些錯誤還是可以檢測)檢測錯誤的，因為詞法分析器的目的是產生詞法記號流，它沒有能力去分析程序結構，因此無法檢測到和程序結構有關的錯誤，比如：
fi(a == b)
詞法分析器不會找到這個錯誤，它認為fi是一個標識符，而不是一個關鍵字，只有在后面的階段中，這個錯誤才會被發現，這是一個與程序結構有關的錯誤
詞法分析器，只能檢測到詞法單元上的問題，比如12.ab，作為一個詞法單元，卻不沒有對應的模式，那么就是產生一個錯誤。

2.正規式：
前面說過模式是一種規則，為了使用，我們需要一種規范的方式來表達模式，這就是正規式
1)串和語言
字符類(又叫字母表)：關于字符的有限集合
串：字符類上字符的有窮序列，串這個概念，具體來說是，某個字符類上的串
串的長度：串中字符的個數，比如串s = abc，那么串的長度為3，用|s|表示串的長度
空串：用ε表示
語言：某字符類上的串的集合，屬于語言的串，成為語言的句子或字

比如：{abc, a}這就是一個語言，abc和a就是句子。另外空集也是屬于語言

連接：x是串，y是串，x和y連接，結果就是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中，所有的句子(串)以任意數目任意順序組成的句子的集合，包括ε，例如：
{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中，所有的句子(串)以任意數目任意順序組成的句子的集合，但是不包括ε
L+中的句子和L*中的句子相比少一個ε

那么，我們通過上面的知識就可以表示一個標識符了，我們知道一般語言規定標識符是由字母開頭，后接若干個字母或數字，我們可以這樣來表示：L={a-z A-Z} N={0-9}，那么標識符就是L(L U N)*

2)正規式
正規式又叫正規表達式，正規式是模式得一種規范的表達形式，正規式描述了一個集合，這個集合是由串組成的，其實這個集合就是我們前面說過的語言，不過這里大家喜歡使用正規集這個術語。正規式r表示正規集L(r)

正規式的運算：

1.閉包運算，運算優先級最高，(r)*表示(L(r))*

2.連接運算，運算優先集合低于閉包，(r)(s)表示(L(r))(L(s))

3.或運算，運算優先集合最低，(r) | (s)表示(L(r)) U (L(s))

例如：

a | b表示集合(語言，正規集) {a,b}

(a | b)(a | b)表示集合(語言，正規集) {aa,ab,ba,bb}

a*表示由一切a字符組成的集合(語言，正規集)，包括ε

(a | b)表示由a,b組成的集合(語言，正規集)，包括ε

等價的正規式：(a | b) = (b | a)

正規式的代數性質：

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.正規定義

我們可以使用 名字->正規式這種表示，來說明一個等價的代替，比如：

dight -> 0|1|2|3|4|5|6|7|8|9

這里，我們就可以使用名字digit來代替后面的正規表達式

我們可以對某個串集進行正規定義，比如我們對標識符集合進行正規定義：

letter -> A|B|...|Z|a|b|...|z

dight -> 0|1|2|3|4|5|6|7|8|9

id -> letter(letter|dight)*

請通過上面的例子理解正規定義。

在我們表達正規表達式的時候，可以使用一些符號使得表達簡化

1) +，表示一個或者多個實力，比如，a+表示{a,aa,aaa,aaaa,...}。區別一下*,他們的關系是這里r+ = r* | ε

2)字符組，[abc]表示a|b|c，還可以這樣表示[a-zA-Z]表示字母表中的字符

4.狀態轉換圖

狀態轉換圖是對詞法分析器進行分析過程的描述，我們看一個判斷關系運算的狀態轉化圖：

1)圖中圓圈表示狀態

2)箭頭叫做邊。X狀態的邊，一般指的是由X狀態出發，指向其他狀態的邊

3)邊上的符號叫做標記

如何來使用這個圖？假定輸入字符串是<=，那么識別開始時，發現<和狀態0與狀態1間的邊上的標記一樣，那么就進入1狀態，下一個輸入字符為=，將進入2狀態，識別結束，返回二元組<relop,LE>

上圖中2，3，4，5，7，8狀態，他們表示識別了一個關系運算符，這個狀態叫做接受狀態

狀態4上面有一個*，表示說，輸入指針需要回移。所謂的輸入指針，就是指向輸入字符串中現在被讀入的字符的位置，4狀態會多讀取一個字符，所以需要回移，也就是要注意的是，識別完成之后，輸入指針指向的是被識別對象的最后一個字符，而不是待識別對象的第一個字符，這樣的規定在實現詞法分析器時，是有一定的意義，舉例說明：

輸入字符串為：a>b

識別的時候，從>開始，讀入下一個字符b時，進入4狀態，這個時候，輸入指針指向b，這時候需要回移

我們在需要回移的狀態上加一個*

每個狀態后面有一個return(relop,XX)這個是狀態的行為，這里具體來說就是返回一個二元組的行為，詞法分析器分析的結果就是得到二元組(詞法記號和屬性的二元組)，這個二元組可以表示一個特定的字符串。其實上面的*，也是表示行為，也就是輸入指針回移的行為，我們可以看見，只有在接受狀態才會有行為出現

對一門典型的語言來說狀態可能有幾百個

5.如何編寫一個詞法分析器

1)根據需要寫出正規定義

2)根據正規定義畫出轉換圖

3)根據轉換圖寫出詞法分析器

這里詳細討論面向過程的語言來實現一個詞法分析器(比如c語言)，并且主要討論的是第3步

1)我們需要一個nextchar()函數，取得緩存中下一個等待分析的字符，這個函數完成年2個任務

1.讓輸入指針向前移動一位

2.返回輸入指針指向的字符

2)定義一個變量token_beginning，在每個狀態轉換圖開始的時候，記錄輸入指針的位置，定義forward變量作為輸入指針

3)狀態轉換圖被實現成為代碼之后，每個狀態都有屬于自己的一塊代碼，這些代碼按順序完成以下工作：

1.讀取一個字符，通過nextchar()函數

2.讀取的字符(標志)，如果它和當前狀態的邊上的標記相同，那么狀態將轉換到邊所指向的狀態，具體實現只需要一個語句就是state = xxx(xxx為目標狀態)；如果當前狀態的所有邊的標記和這個讀取字符不一樣，那么表示沒有找到token(詞法記號)，這時候需要調用fail()函數

3.fail()函數完成這樣的功能：a.指針回移，完成forward＝token_beginning的操作b.找到適當的開始狀態(也就是尋找另外一個轉換圖的開始狀態)。假定所有的轉換圖都被嘗試過，并且無法匹配，這時候會調用一個發現錯誤的小程序，來報告錯誤

4.請不要隨意添加行為到各個狀態所持有的代碼中，應該以轉換圖中表示的行為為準

4)定義一個全局變量lexical_value，用于保存一個指針，這個指針由install_id()和install_num()兩個函數中的一個返回

5)定義兩個整形變量start,state，分別表示一個轉換圖的開始狀態和當前的狀態

6) nexttoken()，這是詞法分析器的主程序，可以說，我們通過調用nexttoken()就完成了詞法分析，這個函數一定是這樣的格式：
while(1){
switch(state){
case xx:
...
case yy:
...
default:
...
}
}

關于詳細的設計這里就不說了，舉例說明一個轉換圖如何轉換成為程序：

這是一個識別浮點數的例子，看下面的代碼：
#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個以上的可能狀態，那么這個finite automaton就是不確定的，反之就是確定的。例如：

這就是一個不確定的無限自動機，在symbol a輸入的時候，無法確定狀態應該轉向0，還是1

不論是確定的finite automaton還是非確定的finite automaton，它們都可以精確的描述正規集(regular sets)
我們可以很方便的把正規表達式(regular expressions)轉換成為不確定finite automaton

2. NFA(Nondeterministic Finite Automaton)
非確定的無限自動機，我們用NFA這個術語表示，它是一個數學模型(model)：

1.一個關于狀態的集合S

2.一個關于輸入符號(input symbols)的集合Σ

3.函數move : (狀態,符號) -> P(S)

4.一個開始狀態s0，是一個唯一的狀態

5.一個結束(接受)狀態集合F

注意，P(S)，表示S的冪集。在NFA中，input symbol可以為ε
轉換函數(transition function)的含義就是，一個確定的狀態已經從這個狀態出發的一條邊的標簽(符號symbol)，可以確定它的下一個狀態組成的集合，比如上圖(這個轉換圖就是NFA的一種表示方式)，0狀態，a符號，確定了一個狀態的集合{0,1}

3.轉換圖(transition graph)的表示
我們知道，計算機是無法直接表示一個圖，我們應該如何來表示一個轉換圖？使用表格就是一個最簡單的方法，每行表示一個狀態，每列表示一個input symbol，這種表格被叫做transtion table(轉換表)

可以說使用表格是最簡單的表示方式，但是我們可以注意到在這個圖中狀態1和input symbol a，是沒有下一個狀態的(空集合)，也就是，對于一個大的狀態圖，我們可能花費大量的空間，而其中空集合會消耗不少空間，但是這種消耗又不是必須的，所以，作為最簡單的一種實現方式，卻不是最優的

語言(language)被NFA定義成為一個input string的集合，而這個集合中的元素則是被NFA受接受的所有的字符串(那些可以從開始狀態到某接受狀態的input string)

至于存儲的方式，可以試試鄰接表。注意，使用什么樣的數據結構來保存NFA按情況不同而不同，在一些特殊情況下，某些數據結構會變得很方便使用，而換入其他情況，則不可以使用了。

詞法分析(3)---DFA

1. DFA(Deterministic Finite automaton)
DFA就是確定的有限自動機，因為DFA和NFA關系密切，我們經常需要把他們拿到一起來講，NFA可以轉化成為一個DFA，DFA依然是一個數學model，它和NFA有以下區別

1.不存在ε-transition，也就是說，不存在ε為input symbol的邊

2.對于move函數，move : (state, symbol) -> S，具體來說就是，一個狀態和一個特定的input symbol，不會映射到2個不同的狀態。這樣的結果是，每個狀態，關于每個特定的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的轉化

1.子集構造(Subset Construction)
這是一個轉換NFA到DFA的算法。我們知道NFA和DFA的區別最主要的就是一個狀態和一個input symbol是否能夠確定一個狀態的問題，對于NFA，它將確定一個組狀態，而DFA將確定一個狀態，因此，我們有一個很好的辦法就是把NFA的狀態集對應每個DFA的狀態，這就是subset construction的思想，不過這只是大概泛泛而論，我們需要更加明確的認識

1) NFA在任何一個input symbol下，映射的狀態集(通過move函數，這個集合通常用T字母表示)應該被知道
2)必須保證1)中狀態集都對應了DFA中的一個狀態

具體算法：
Input :一個NFA N
Output :接受相同語言的DFA D
Method :為D構架一個transition table(轉換表) Dtran，每個DFA的狀態是一個NFA的狀態集合(這里一定要注意前面說過的1)2)兩點)。我們定義一些操作：

s表示NFA的狀態，T表示NFA的狀態集合，a表示一個input symbol
ε-transition(ε轉換)就是說input symbol為ε時的transition(轉換)

操作(operation)	描述(description)
ε-closure(s)	從NFA的狀態s出發，只通過ε-transition到達的NFA的狀態集合
ε-closure(T)	NFA的集合T中的狀態p，只通過ε-transition到達的NFA的狀態集合，再求這些集合的交集。用數學表達就是{p|p屬于ε-closure(t) , t屬于T}
move(T,a)	NFA的集合，這個集合在input symbol為a，狀態為T中任意狀態情況下，通過一個轉換得到的集合

注意一下，所有的操作都是針對NFA的狀態或者狀態集合，得到的時NFA的狀態集合，或者說是DFA看為一個狀態

Subset Construction
初始Dstates，它僅僅含有狀態(D的狀態)ε-closure(s0)，并且狀態未被標記，s0表示開始狀態，注意，Dstates放的是D的狀態
while ( Dstates有未標記的狀態T ) { // T是D中的一個狀態，也是N中一個狀態集
標記T;
for ( input symbol a ){ //遍歷所有的input symbol
U = ε-closure(move(T, a)); // move為NFA的move函數
if ( U不在Dstates中)
把U作為尚未標記的狀態加入Dstates;
Dtran[T, a] = U
}
}

注意，狀態s，ε-closure(s)一定包含s
我們先來熟悉上面的操作operation，再來看上面的算法

ε-closure(0) = {0, 1, 2, 4, 7} //從0狀態出發的，input symbol為ε的所有狀態的集合
ε-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}

現在可以回去理解一下算法了。

這里再說說求ε-closure(T)的算法：

把T的所有狀態壓入stack(棧);
ε-closure(T)的初始值為T中的所有元素; //也就是一定包含他們本身
while(棧非空) {
彈出棧頂元素t ;
for(每個屬于move(t, ε)的狀態u ){
if( u不在ε-closure(T)中){
u加入ε-closure(T);
把u入棧;
}
}
}

下面對上圖如何使用Set Construction算法來構建DFA做一個詳細的描述：
1.初始化Dstates把集合ε-closure(s0) = {0, 1, 2, 4, 7}作為第一個狀態，設此狀態為A
2.現在轉化，input symbol {a, b}，因此，求：
ε-closure(move(A, a));
ε-closure(move(A, b));
這里會得到2個狀態
ε-closure(move(A, a)) = {1, 2, 3, 4, 6, 7, 8},設其為B
ε-closure(move(A, b)) = {1, 2, 4, 5, 6, 7},設其為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轉化成為DFA：

詞法分析(5)---從正規式到NFA

在說到這個問題前，先告訴大家，我們可以直接從Regular expression到DFA，不過這里我們先不討論這個問題

關于RE到DFA的算法有很多，這里學習一個最簡單的

Algorithm Thompson's construction：
Input :一個字母表(Σ)上的Regular Experssion r
Output :一個接受L(r)的NFA N
Method :把r解析成為子表達式(subexpressions)，然后使用下面的1),2)規則，為r中的基本符號(basic symbols,基本符號就是ε和Σ中的字符)構建NFA，基本符號符合1),2)關于正規式的定義，注意，假如symbol a出現多次，那么它每次出現都要構建一個NFA。之后，我們需要通過r的語法結構，通過規則3)組合前面構建的NFA，直到得到整個NFA為止。對于中間產生的NFA，它只有一個終態，沒有進入開始裝狀態的邊，也沒有離開接受狀態的邊。
1)對于ε構造如下NFA

注意，每次構建時，i,f的值都不一樣，因此可見構造一個識別ε的NFA，會產生2個新的狀態

2)對于Σ中的每個字符a

同樣，對于aaa，第一個a構造的NFA中的i,f不會和第2個a構造的i,f一樣，因此可見構造一個識別Σ中的每個字符a的NFA，會產生2個新的狀態

3)先假定N(t) N(s)分別是t s的NFA，則：
a)對于表達式s|t構建NFA N(s|t)

這里一樣會產生2個新的狀態i,j，我們看其中一個N(s)，左邊的圓圈，表示N(s)的開始狀態，右邊的圓圈表示N(s)的接受狀態，N(t)同理
b)對于表達式st ,構建N(st)

這個時候，不產生新的狀態，N(s)的開始狀態變為N(st)的開始狀態，N(t)的接受狀態變成N(st)的接受狀態，N(s)的接受狀態和N(t)開始狀態成為一個狀態。這里提醒一下，寫程序的時候，這里千萬要注意，因為沒有新的狀態產生，必須考慮狀態的部分復制，如果不小心就會出錯。
c)對于正規式s*，構造N(s*)

這里一樣需要產生2個新的狀態i,f，注意，產生了一條N(s)接受狀態到N(s)開始狀態的邊，邊上的symbol為ε
d)對于(s)，使用N(s)本身作為它的NFA，也就是不用構造新的NFA

注意一下，以上產生的NFA，有以下性質：
1)只有一個接受狀態和一個開始狀態
2)每個狀態最多含有2個指向其他狀態的邊，詳細的來說，如果狀態只有一條指向其他狀態的邊，那么邊上的symbol為Σ中的任意字符或者ε，如果狀態有兩條指向其他狀態的邊，那么邊上的symbol一定為2個ε

由以上性質，我們可以很好的選擇數據結構來表示NFA

詞法分析(6)---DFA的化簡

通過NFA轉化而成的DFA不一定是最簡的，也就是說，有多余的狀態可以被刪除，對于每一個正規定義，我們一定可以得到一個唯一的最簡的DFA

我們回顧一下Move函數，DFA的move函數：

move : (state, symbol) -> S

注意，這里(state, symbol)表示的是一個集合，這里規范的數學表達應該是：

move : { (state, symbol) |所有屬于DFA的state和symbol } -> S或者

move : S × Σ -> S

假如一個DFA的move函數不是全函數，那么必須引入死狀態。假如某個DFA的move函數是全函數，那么每個狀態在所有input symbol下都有出邊，比如：

這個DFA每個狀態都可以接受所有的input symbol，這里是a，b。而下面的DFA：

先不要看紅色部分，那么這個DFA的狀態c，d，它們無法通過input symbol b進入下一個狀態，我們可以加上紅色的部分，把這個move函數，轉化成為一個全函數，并且，經過轉化操作之后，新的DFA與原DFA等價。這個紅色部分標識的狀態，被叫做死狀態

死狀態：

假如出現DFA的move函數不是全函數，我們可以引入一個死狀態S(僅僅引入一個方可)，這個狀態包括所有input symbol對自身的轉換，所有的其他狀態假如不接受某個input symbol a，那么，我們建立這個狀態到S且input symbol為a的邊。

狀態的區別：

假如一個狀態s，通過input string w，可以轉換到某個狀態，而某個狀態t，通過w，轉化到了一個與s通過w轉化到的狀態不同的狀態，那么我們就可以通過w來區別狀態s，t，如果這樣的w不存在，那么s，t這2個狀態是無法區別的。

每個接受狀態都可以通過ε和非接受狀態進行區別。

化簡算法，極小化DFA的思想：

極小化DFA算法，它把狀態分成一些不相交的子集，每一個子集中的所有狀態都是不可區別的，而不同子集中的每個狀態兩兩都是可區別的，最后我們把每個子集中的所有狀態合成一個狀態。

1)劃分狀態集

首先把所有狀態劃分成為2個集合，一個集合是接受狀態的集合，一個集合是非接受狀態的集合，他們通過ε來區別。然后看每個集合中的狀態時候還可以區別，例如一個集合通過input symbol a，轉換后得到的狀態落入當前劃分的不同集合，那么說明通過input symbol a，是可以區別這個集合中的狀態的(這里要強調的是，對于一個而不是多個input symbol，假如轉換到的狀態落入不同的劃分中那么這些狀態就是可以區別的)。我們假定有一個狀態集合{s1,s2},s1通過a到達狀態集合t1，s2通過a到達狀態集合t2，t1,t2分別是當前劃分的狀態集合，那么，集合{s1,s2}就可以分成2個集合{s1},{s2}

2)構造最簡的DFA

我們可以重復1)的步驟，最后得到一些子集合，我們從每個子集合中取一個狀態，通過它們可以得到最簡的DFA，但具體需要按一定規則去構建

極小化DFA狀態數的算法：

Input :一個DFA M，它的狀態集是S，輸入符號集合Σ，move : S × Σ -> S，開始狀態為s0，接受狀態的集合為F

Output :一個DFA N，它和DFA M等價，并為最簡

Method :

1)初始化:假如move函數不是全函數，那么加入死狀態，構造劃分X：把S分成2個子集合，包括接受狀態集合F和非接受狀態集合S-F(F集合的補集)

2) Xnew是一個劃分

for( X中的每個集合G ){

G中狀態每次通過Σ中的symbol轉化到的狀態如果屬于X的不同子集，那么把集合G分成子集，每個symbol都可能劃分G，劃分之后，使用下一個symbol進行操作，一直到遍歷完所有的input symbol

更新Xnew，用G的劃分代替G

}

3)如果Xnew == X，那么定義Xfinal = X，執行4)，否則進行賦值操作X = Xnew，進行2)

4) Xfinal中每個子集合中選擇一個狀態來代表這個狀態集合，包含s0的狀態集合，就是表示開始狀態的集合。通過DFA M來構造DFA N，規則是這樣的：假如某狀態p通過某input symbol a，通過DFA M的move函數轉到另外一個狀態q，我們就用q所在的集合的代表狀態來表示q，并把這個轉換過程的邊，input symbol，集合的代表狀態，加入DFA N中。我們需要遍歷DFA M，然后按規則構建DFA N。化簡的DFA中，可能有多個接受狀態。

5)如果N中有死狀態(終態不是死狀態)，去掉它，有開始狀態無法到達的狀態，也去掉它。注意，在DFA N中有可能出現死狀態，也就是通過所有的input symbol都回到自己的狀態，前面說過，添加一個死狀態得到的新的DFA與原DFA等價，那么我們這里也自然可以刪除它。

在真正的實現上面算法的時候，是靈活的，因為出于時間復雜度的考慮，可能并不需要完全照搬上面的算法，把握主要的思想是很重要的。

1)每個input symbol都可能劃分一次集合

2)每個集合都中的狀態被看成是不可區別的，即使在計算過程中某些集合中的狀態是可以區別的

3)一定要確保每個集合都無法在分

關于正則表達式、正則文法、NFA、LR(1)

昨天和Sumtec談到自動機和語法分析，一下子腦子有點混亂，把一些概念搞混了，看了半天清華的編譯書也沒有整明白...今天早上起來看了《離散數學及其應用》里的自動機一部分，才厘清了頭緒。還是外國人的書講得清楚一點。

昨天主要是把NFA和語法分析中的LL(1) LR(1)搞混了。事實上LL(1)分析也好LR(1)分析也好，使用的是一個基于下推自動機的計算模型，而不是有限自動機。下推自動機的計算能力要比有限自動機強。

其次就是NFA和DFA的計算能力確實是等價的，也就是對于任意一個NFA都可以找到一個與之等價的DFA(可以使用子集法來構造這樣一個DFA)。

為了說明有限自動機與LL(1) LR(1)等分析法的關系，先概述一下文法的分類

文法分為四類：

(1)短語文法(0型文法)

(2)上下文相關文法(1型文法)

(3)上下文無關文法(2型文法)

(4)正規(則)文法(3型文法)

上面四種文法有包含的關系，1型文法是0型文法的一個子集，2型文法是1型文法的一個子集，,3型文法是2型文法的一個子集。

我們主要研究2型和3型方法。

3型文法(正則文法)與正則表達式(Regular Expression)是等價的，任意一個正則文法總是可以轉化成一個等價的正則表達式。同時正則表達式與有限自動機是等價的。一個能由有限自動機識別的語言，必然可以用正則表達式來表示，而一個用正則表達式表示的語言一定可以用一個有限自動機來識別。

但是正則文法不足以描述程序設計語言(比如，不能用正則表達式定義帶有括號的數學表達式)，現在流行的程序設計語言如C#, java等都是用2型文法，也就是上下文無關文法來定義的。因此有限自動機沒有能力來識別程序設計語言(最后我會舉個例子)。因此提出來下推自動機的模型。下推自動機具有限自動機的所有部件，如狀態、狀態轉移表等，同時它比有限自動機多一個堆棧，常稱為計算棧。下推自動機可以根據情況將終結符或者非終結符壓入棧，或者彈出棧。

而LL(1)，LR(1)等分析法就是用來分析上下文無關文法的，基于下推自動機的模型。這也是為什么介紹語法分析時，所有的書都會說一個基于LR(1)分析法的預測分析器，都會有三部分組成：狀態轉移表、控制器和計算棧。而所謂的移進與歸約就是入棧與出棧的問題。

最后，舉一個例子(好象大家都睡著了-_-b)

先給出一個文法：

S->0S1 | 01

其中0、1是終結符。

這樣一個文法描述的語言其實就是n個0加上相等數量的n個1，這里n是某個整數。

這個文法是一個上下文無關文法，但不是一個正則文法。所以說我們沒辦法寫出一個正則表達式來描述這樣一個語言。等于一個能識別這個文法中的任意句子的NFA，我們總能找到這樣一個句子，它不是由該文法所定義的，卻能被這個NFA接受。換句話說，任意NFA都不能用來判斷某個句子是不是由以上這個文法所定義。說得實際一點，如果要求寫一個著色程序，輸入的文件是一串0、1組成的序列，要求把其中n個0加n個1的序列用紅色著色，而其它用黑色的話，我們就不能光用正則表達式匹配來完成這一任務了。

如果上面這個例子還比較抽象的話，那么對于“帶有括號的數學表達式”這樣一個語言，也是沒有辦法用正則表達式來進行匹配的。因為描述“帶有括號的數學表達式”的文法，也不是一個正則文法，因為其中帶有類似：

F->(E)

這樣的部分。

而正則文法要求所有的產生式都必須是A->aB或者A->a這樣的形式的(其中A、B是非終結符，a是終結符)

?如果你喜歡本文, 請長按二維碼，關注公眾號 分布式編程.

作者：分布式編程

出處：https://zthinker.com/

本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。

總結

以上是生活随笔為你收集整理的词法分析(NFA与DFA)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。