詞法分析算法教程文件

詞法分析算法構(gòu)造識(shí)別主算符為選擇的正規(guī)式的NFAfi開始識(shí)別正規(guī)式s|t的NFAN(s)N(t)構(gòu)造識(shí)別主算符為連接的正規(guī)式的NFA

iN(s)f開始識(shí)別正規(guī)式st的NFAN(t)構(gòu)造識(shí)別主算符為閉包的正規(guī)式的NFA

N(s)f開始識(shí)別正規(guī)式s*的NFAi對(duì)于加括號(hào)的正規(guī)式(s)，使用N(s)本身作為它的NFA。所用數(shù)據(jù)結(jié)構(gòu)提示用字符串存儲(chǔ)正規(guī)式;用結(jié)構(gòu)體數(shù)組或鏈表存放狀態(tài)轉(zhuǎn)換圖

structNFA{intfrom;intto;char*varch;}表示經(jīng)過字符串varch,from到to狀態(tài)。中間過程可借助棧完成。

算法提示利用算符優(yōu)先的思想來處理正規(guī)式中所涉及的各種算符（*，|，（，），·）所對(duì)應(yīng)的操作。根據(jù)各運(yùn)算符間的優(yōu)先關(guān)系，構(gòu)造相應(yīng)的算符優(yōu)先關(guān)系表。如右表。用字符串存儲(chǔ)輸入的正規(guī)式，利用算符優(yōu)先分析過程，來分析輸入的字符串?！()*#·>><><>|<><><>(<<<=<E)>>E>>>*>>E>>>#<<<E<=程序流程‘#’入符號(hào)棧；輸入串+‘#’(將輸入串中的連接用‘·’代替)；While(輸入字符！=‘#’||符號(hào)棧頂元素！=‘#’){ if(輸入字符是小寫字母或數(shù)字) {構(gòu)造識(shí)別正規(guī)式a的NFA；NFA的弧入隊(duì)列；起始節(jié)點(diǎn)入狀態(tài)棧；讀取下一個(gè)字符。} else{比較符號(hào)棧頂元素和輸入字符的優(yōu)先關(guān)系（查表）

{case’<’:{當(dāng)前輸入符號(hào)進(jìn)符號(hào)棧；讀取下一個(gè)字符；}case‘=’:{符號(hào)棧棧頂元素出棧；讀取下一個(gè)字符；}程序流程case‘>’:{符號(hào)棧棧頂元素出棧；

if（符號(hào)棧頂元素==‘|’）

{狀態(tài)棧2個(gè)棧頂元素出棧，分別為s,t；構(gòu)造識(shí)別正規(guī)式s|t的NFA；NFA的弧入隊(duì)列；起始節(jié)點(diǎn)入狀態(tài)棧；}elseif（符號(hào)棧頂元素==‘·’）

{狀態(tài)棧2個(gè)棧頂元素出棧，分別為s,t；構(gòu)造識(shí)別正規(guī)式s·t的NFA；NFA的弧入隊(duì)列；起始節(jié)點(diǎn)入狀態(tài)棧；}elseif(輸入字符==‘*’){狀態(tài)棧1棧頂元素s出棧；構(gòu)造識(shí)別正規(guī)式s*的NFA；NFA的弧入隊(duì)列；起始節(jié)點(diǎn)入狀態(tài)棧；讀取下一個(gè)字符。}elseerror!}}}}把狀態(tài)棧頂元素出棧，該元素的弧的起始節(jié)點(diǎn)為整個(gè)NFA的起始節(jié)點(diǎn)，該弧的終止節(jié)點(diǎn)為整個(gè)NFA的終止節(jié)點(diǎn)。2、從NFA到DFA實(shí)驗(yàn)?zāi)康模赫莆兆蛹?，即將NFA轉(zhuǎn)換為與之等價(jià)的DFA的算法。實(shí)驗(yàn)要求：輸入：任意一個(gè)NFAN；輸出：一個(gè)接受同樣語言的DFA

D。注：DFA的表現(xiàn)形式不限。子集法回顧初始時(shí)，ε_(tái)closure(s0)是Dstates中唯一的狀態(tài)且未被記；WhileDstates中存在一個(gè)未標(biāo)記的狀態(tài)Tdobegin

標(biāo)記T；

For每個(gè)輸入符號(hào)adobeginU:=ε_(tái)closure(s0)(move(T,a));IfU沒在Dstates中then

將U作為一個(gè)未標(biāo)記的狀態(tài)添加到Dstates中；

endend實(shí)現(xiàn)思路1、構(gòu)造數(shù)據(jù)結(jié)構(gòu)：圖的數(shù)據(jù)結(jié)構(gòu)；轉(zhuǎn)換關(guān)系的數(shù)據(jù)結(jié)構(gòu)。2、求圖的開始節(jié)點(diǎn)的ε-closure，作為子集鏈表的頭節(jié)點(diǎn)。然后對(duì)其ε-closure中的每個(gè)節(jié)點(diǎn)，根據(jù)轉(zhuǎn)換關(guān)系，求出新的子集，將新求出的子集插入到子集鏈表的尾部。實(shí)現(xiàn)方法構(gòu)造主要的數(shù)據(jù)結(jié)構(gòu)：structdiagram{ intsnum;//節(jié)點(diǎn)編號(hào)

move*transfer;//轉(zhuǎn)換關(guān)系

diagram*next;};//圖的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法構(gòu)造主要的數(shù)據(jù)結(jié)構(gòu)：structsubset{ intsnum;//節(jié)點(diǎn)編號(hào)，

charclosure[MAX];//該節(jié)點(diǎn)中包含原來的哪些節(jié)點(diǎn)，也就是其ε_(tái)closure move*transfer;//來源關(guān)系

subset*next;};//子集的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)方法構(gòu)造主要的數(shù)據(jù)結(jié)構(gòu)：structmove{ intpoint;//來自或轉(zhuǎn)向哪一個(gè)節(jié)點(diǎn)

charinput;//轉(zhuǎn)向條件

move*next;};//存儲(chǔ)來源關(guān)系程序流程（1）讀取文件中的數(shù)據(jù)，組成圖的初始鏈表。（2）將圖的開始節(jié)點(diǎn)加入到其子集節(jié)點(diǎn)的closure數(shù)組中，調(diào)用求ε-closure的子函數(shù)求出圖開始節(jié)點(diǎn)的ε-closure存儲(chǔ)在該子集節(jié)點(diǎn)的closure數(shù)組中。將該子集作為作為子集鏈表的頭節(jié)點(diǎn)。（3）遍歷子集鏈表，對(duì)子集節(jié)點(diǎn)中closure數(shù)組中的每個(gè)元素，對(duì)其轉(zhuǎn)換輸入中的非ε元素，構(gòu)造一個(gè)新的子集節(jié)點(diǎn)，將該輸入之后所到達(dá)的節(jié)點(diǎn)插入新構(gòu)造的子集節(jié)點(diǎn)的closure數(shù)組中，調(diào)用求ε-closure的子函數(shù)求該子集節(jié)點(diǎn)的ε-closure，存儲(chǔ)在該子集節(jié)點(diǎn)的closure數(shù)組中。同時(shí)構(gòu)造構(gòu)造轉(zhuǎn)換關(guān)系節(jié)點(diǎn)，將該輸入字母和來源節(jié)點(diǎn)編號(hào)填入該轉(zhuǎn)換節(jié)點(diǎn)中，將該轉(zhuǎn)換節(jié)點(diǎn)掛在剛才新構(gòu)造的子集節(jié)點(diǎn)上。（4）將新構(gòu)造的子集節(jié)點(diǎn)插入子集鏈表中。關(guān)鍵算法實(shí)現(xiàn)思路求ε-closure：遍歷closure數(shù)組中的每個(gè)元素，如果該元素節(jié)點(diǎn)的轉(zhuǎn)換輸入（圖數(shù)據(jù)結(jié)構(gòu)）中存在ε，則把輸入ε之后能到達(dá)的那個(gè)節(jié)點(diǎn)插入closure數(shù)組（尾插法）。注意事項(xiàng)（1）所有的插入操作，在插入的時(shí)候都需要比較即將插入的元素是否已經(jīng)存在于插入對(duì)象中，如果已經(jīng)存在，則不插入。（2）對(duì)于子集的插入，采用尾插法，插入的時(shí)候給新的子集編號(hào)。比較兩個(gè)子集是否相同，是比較子集數(shù)據(jù)結(jié)構(gòu)中的closure數(shù)組中的元素是否相同。如個(gè)有相同的子集，則只把轉(zhuǎn)換關(guān)系節(jié)點(diǎn)加入到已有的子集節(jié)點(diǎn)的轉(zhuǎn)換關(guān)系鏈表中，不插入該子集節(jié)點(diǎn)。（3）由于新的子集是在插入時(shí)才獲得編號(hào)，所以，子集節(jié)點(diǎn)中轉(zhuǎn)換關(guān)系鏈表和圖中的轉(zhuǎn)換鏈表有含義有所差別。圖中的是目的節(jié)點(diǎn)，輸入字符；子集中是來源節(jié)點(diǎn)，輸入字符。（4）為了便于比較closure數(shù)組，在每次求完ε-closure之后，有必要對(duì)closure數(shù)組中的元素進(jìn)行排序。3、DFA的最小化實(shí)驗(yàn)?zāi)康模赫莆兆钚』疍FA的算法。實(shí)驗(yàn)要求：輸入：任意一個(gè)DFAD；輸出：一個(gè)接受同樣語言的DFA

D`，且狀態(tài)數(shù)最少。注：DFA的表現(xiàn)形式不限。算法回顧所有狀態(tài)分成兩個(gè)子集－終態(tài)集和非終態(tài)集；運(yùn)用判定狀態(tài)可區(qū)別原則分別對(duì)兩個(gè)子集的狀態(tài)進(jìn)行分析和劃分，把互相等價(jià)的狀態(tài)構(gòu)成一個(gè)子集，若發(fā)現(xiàn)不等價(jià)，繼續(xù)劃分；當(dāng)無法運(yùn)用可區(qū)別原則時(shí)，則看Ia是否全包含在現(xiàn)行劃分中，是則不可區(qū)分，不是則繼續(xù)劃分從每個(gè)子集中選出一個(gè)狀態(tài)做代表，即可構(gòu)成簡(jiǎn)化的DFA；含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。主要數(shù)據(jù)結(jié)構(gòu)用鏈表實(shí)現(xiàn)DFA的構(gòu)造，由節(jié)點(diǎn)鏈表和轉(zhuǎn)換弧鏈表組成：

structnode//節(jié)點(diǎn)的定義

{ intpos;//節(jié)點(diǎn)在哪個(gè)組中

intnum;//節(jié)點(diǎn)的序號(hào)

intaccept;//節(jié)點(diǎn)是否為接受狀態(tài)

structnode*next; }NODE; 主要數(shù)據(jù)結(jié)構(gòu)structarc//弧的定義

{intstart;//開始的頂點(diǎn)位置

charinput; //弧上所接受的輸入字符

intend;//結(jié)束的頂點(diǎn)位置

structarc*next;}ARC；主要數(shù)據(jù)結(jié)構(gòu)NODE*fenzu[MAX];//劃分（組）的定義structgroups//分組后各節(jié)點(diǎn)所在組位置

{intn;//屬于哪個(gè)組

inti;//在組中的位置

}GROUPS;GROUPSGROUP[MAX]程序流程“尾插法”構(gòu)建各鏈表；從文件中讀入DFA；進(jìn)行初次劃分debided1()形成∏0，將accept為0的所有結(jié)點(diǎn)構(gòu)建鏈表fenzu[0]，其pos為0，將accept為1的所有結(jié)點(diǎn)構(gòu)建鏈表fenzu[MAX-1]，其pos為MAX-1，并形成GROUP[0]和GROUP[MA