鄂州網(wǎng)站開(kāi)發(fā)微信朋友圈推廣
一、詞法分析程序的設(shè)計(jì)
1、詞法分析程序的輸出
在識(shí)別出下一個(gè)單詞同時(shí)驗(yàn)證其詞法正確性之后，詞法分析程序?qū)⒔Y(jié)果以單詞符號(hào)的形式發(fā)送至語(yǔ)法分析程序以回應(yīng)其請(qǐng)求。
單詞符號(hào)一般分下列5類(lèi)：
- 關(guān)鍵字：如：begin、end、if、while和var。
- 標(biāo)識(shí)符：如：常量名、變量名和過(guò)程名
- 常數(shù)：各種類(lèi)型的常數(shù)，如：25、TRUE和"ABC"等。
- 運(yùn)算符：如+、*、<、=等。
- 界符：如：逗號(hào)、分號(hào)、括號(hào)等、
2、詞法分析程序中如何識(shí)別單詞
常見(jiàn)的可以用于詞法規(guī)則描述的工具有狀態(tài)轉(zhuǎn)換圖、擴(kuò)展巴克斯范式（EBNF）、有限狀態(tài)自動(dòng)機(jī)、正規(guī)表達(dá)式以及正規(guī)文法等。
二、單詞的形式化描述工具
1、正規(guī)文法
正規(guī)文法也稱(chēng)3型文法G={VN，VT，S，P}，其P中的每一條規(guī)則都有下述形式：A→aB或A→a，其中A,BVN，a
。正規(guī)文法描述的是VT上的正規(guī)集。
2、正規(guī)式
設(shè)字母表Σ={，
，|，.，*，（，）}。
????1）ε和?都是Σ上的一個(gè)正規(guī)式，它們所表示的正規(guī)集為{ε}和?。
????2）任何a∈Σ，a是Σ上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}。
????3）假設(shè)e1和e2是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，則
? ? ? ? ·e1|e2是Σ上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1|e2)= L(e1)∪L(e2)。
? ? ? ? ·e1e2是Σ上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1e2)= L(e1)L(e2)。
? ? ? ? ·(e1)*是Σ上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)((e1)*)= L(e1)*。
? ? 4）僅由有限次上述3個(gè)步驟而定義的表達(dá)式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的符號(hào)串的集合才是Σ上的正規(guī)集。
?例子：令Σ={a，b}，則有：
? ? ? ? 1）正規(guī)式a表示的正規(guī)集為{a}。
????????2）正規(guī)式a|b表示的正規(guī)集為{a，b}。? ? ? ? 3）正規(guī)式ab表示的正規(guī)集為{ab}。
? ? ? ? 4）正規(guī)式(a|b)(a|b)表示的正規(guī)集為{aa，ab，ba，bb}。
? ? ? ? 5）正規(guī)式a*表示的正規(guī)集為{ε，a，aa，aaa，…}。
? ? ? ? 6）正規(guī)式(a|b)*表示的正規(guī)集為{ε，a，b，aa，ab，ba，bb，aaa，…}。
? ? ? ? 7）正規(guī)式a|a*b表示的正規(guī)集為包含字符串a(chǎn)和包含0個(gè)或多個(gè)a后跟隨一個(gè)b的所有的符號(hào)串。
若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同，則說(shuō)e1和e2等價(jià)，寫(xiě)作e1=e2。
設(shè)r，s，t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律如下：
? ? ? ?1）r|s=s|r
? ? ? ?2）r|(s|r)=(r|s)|t
? ? ? ?3）(rs)t=r(st)
? ? ? ?4）r(s|t)=rs|rt，(s|t)r=sr|tr
? ? ? ?5）r=r，r
=r
? ? ? ?6）r|r=r
3、正規(guī)式轉(zhuǎn)正規(guī)文法
字母表Σ上的正規(guī)式r到正規(guī)文法G-=(VN，VT，S，P)的轉(zhuǎn)換方法為：
????1）選擇一個(gè)非終結(jié)符S生成類(lèi)似產(chǎn)生式的形式：Sr，并將S定為G放識(shí)別符號(hào)。為表述方便，將S
r稱(chēng)作正規(guī)式產(chǎn)生式，因?yàn)樵?img referrerpolicy="no-referrer" alt="\rightarrow" class="mathcode" src="https://latex.csdn.net/eq?%5Crightarrow" />右部中含有“.”，“*”或“|”等正規(guī)式符號(hào)，不是V中的符號(hào)。
????2）若x和y都是正規(guī)式，對(duì)形如Axy的正規(guī)式產(chǎn)生式，重寫(xiě)成A
xB，B
y兩個(gè)產(chǎn)生式，其中B是新選擇的非終結(jié)符。
例：對(duì)于r=a(a|d)*
? ? ? ? 首先形成S
a(a|d)*，然后形成S
? ? ? ? S
? ? ? ? A
? ? B
? ? ? ? B
4、正規(guī)文法轉(zhuǎn)正規(guī)式
| 文法產(chǎn)生式 | 正規(guī)式 | |
| 規(guī)則1 | A | A=xy |
| 規(guī)則2 | A | A=x*y |
| 規(guī)則3 | A | A=x|y |
例如：文法G[S]如下：
S
解：首先有
? ? ? S=aA|a
? ? ? A=(aA|dA)|(a|d)
? ? ? ?再將A的正規(guī)式變換成A=(a|d)A|(a|d)，又變換為A=(a|d)*(a|d)，再代入S得：
? ? ? S=a(a|d)*(a|d)|a
? ? ? 再利用正規(guī)式的代數(shù)變換可依此得到
? ? ? ?S=a(a|d)*(a|d)|
? ? ? ?S=a(a|d)*?
三、有窮自動(dòng)機(jī)
1、確定的有窮自動(dòng)機(jī)
1.定義：一個(gè)確定的有限自動(dòng)機(jī)(DFA) M是一個(gè)五元組：M=(K，Σ，f，S，Z)，其中：
????1）K是一個(gè)有限集，它的每一個(gè)元素稱(chēng)為一個(gè)狀態(tài)。
????2）Σ是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。
????3）f是一個(gè)轉(zhuǎn)換函數(shù)，是KΣ
K上的映像。
????4）S∈K，是唯一的初態(tài)。
????5）Z?S，F是一個(gè)終態(tài)集，可以為空。?
2.DFA的狀態(tài)轉(zhuǎn)移矩陣
????????DFA可用一個(gè)二維矩陣表示，矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示δ(s，a)的值。
3.DFA是狀態(tài)轉(zhuǎn)換圖
????????若設(shè)DFA M含有m個(gè)狀態(tài)和n個(gè)輸入字符，則這個(gè)圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有n條箭弧射出與其它的狀態(tài)結(jié)點(diǎn)相連接，每個(gè)箭弧用Σ中的一個(gè)不同輸入字符作為標(biāo)記。整張圖含有唯一的初態(tài)結(jié)點(diǎn)和若干終態(tài)結(jié)點(diǎn)。
例子：設(shè)DFA M=({0,1,2,3}，{a,b}，δ，{3})，其中，δ定義為：
????????δ(0，a)=1，δ(0，b)=2，δ(1，a)=3，δ(1，b)=2，δ(2，a)=1，δ(2，b)=3，δ(3，a)=3，δ(3，b)=3。
4.DFA的識(shí)別字符串
????????1）對(duì)Σ上的任何符號(hào)串w∈Σ*，若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且該通路上所有弧的標(biāo)記符連接成的字符串等于w，則稱(chēng)w可被DFA M所識(shí)別。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字符串ε被M所識(shí)別。
?????????2）DFA與語(yǔ)言的關(guān)系：DFA M所能識(shí)別的符號(hào)串的全體記為L(zhǎng)(M)。
2、不確定的有窮自動(dòng)機(jī)
1.定義：一個(gè)不確定有限自動(dòng)機(jī)(NFA) M是一個(gè)五元組：M=(S，Σ，δ，S0，F)，其中：
????1）S是一個(gè)有限集，它的每一個(gè)元素稱(chēng)為一個(gè)狀態(tài)。
????2）Σ是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。
????3）δ是一個(gè)從S×Σ到S的子集的映射，即δ：S×Σ*→2S
????4）S0?S，S0是一個(gè)非空初態(tài)集。
????5）F ?S，F是一個(gè)終態(tài)集，可以為空。
2.NFA的狀態(tài)轉(zhuǎn)換圖
????若設(shè)NFA M含有n個(gè)狀態(tài)和m個(gè)輸入符號(hào)，則這個(gè)圖含有n個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可射出若干箭弧與其它的狀態(tài)結(jié)點(diǎn)相連接。對(duì)于w∈{ε}∪Σ，若δ(q0，a)={q1，q2，…，qk}(k≥0)，則從q0出發(fā)，分別到q1，q2，…，qk的k條弧，弧上均標(biāo)記為a。整張圖含有唯一的初態(tài)結(jié)點(diǎn)和若干終態(tài)結(jié)點(diǎn)。
3.NFA識(shí)別字符串
????1）對(duì)Σ*上的任何符號(hào)串，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且該通路上所有弧的標(biāo)記符號(hào)依次連接成的字符串等于w，則稱(chēng)w可被NFA M所識(shí)別。若M的某些結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字符串ε被M所識(shí)別。
????2）NFA與語(yǔ)言的關(guān)系：Σ*中所有可被NFA M所識(shí)別的符號(hào)串的集合記為L(zhǎng)(M)。
4.DFA和NFA的關(guān)系
????1）DFA是NFA的特例，NFA是DFA概念的推廣。
????2）NFA能識(shí)別的語(yǔ)言都能被一個(gè)DFA識(shí)別。
????3）DFA相對(duì)NFA的識(shí)別程序更容易實(shí)現(xiàn)。
3、NFA轉(zhuǎn)換為等價(jià)的DFA
1.NFA的確定化：對(duì)任給的NFA M。都能相應(yīng)地構(gòu)造一個(gè)DFA M‘，使得L(M’)=L(M)。
2.NFA的子集法：DFA的每一個(gè)狀態(tài)代表NFA狀態(tài)集合的某個(gè)子集，構(gòu)造的DFA使用它的狀態(tài)去記錄NFA讀入輸入符號(hào)之后可能到達(dá)的所有狀態(tài)的集合。
3.狀態(tài)集合I的a弧轉(zhuǎn)換，表示為ε-Closure(I)，定義為一個(gè)狀態(tài)集，是狀態(tài)集I中的一組任何狀態(tài)S經(jīng)任意條ε弧而能夠到達(dá)的狀態(tài)的集合。
4.狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I，a)，定義為狀態(tài)集合J，其中J是所有那些可以從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。
4、確定有限自動(dòng)機(jī)的化簡(jiǎn)
1.化簡(jiǎn)的目的：去除多余或等價(jià)的狀態(tài)，降低存儲(chǔ)代價(jià)，提高句子識(shí)別的效率。
2.有限自動(dòng)機(jī)的多余狀態(tài)：從初態(tài)出發(fā)，任何可識(shí)別的輸入串也不能到達(dá)的狀態(tài)。
3.狀態(tài)等價(jià)：在兩個(gè)狀態(tài)s和t等價(jià)的條件是以下兩個(gè)：
? ? ? ? 一致性條件--狀態(tài)s和t必須同時(shí)為可接受狀態(tài)或不可接受狀態(tài)。
? ? ? ? 蔓延性條件--對(duì)于所有輸入符號(hào)，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。
4.DFA的化簡(jiǎn)（分割法）：
?????????i）將DFA M的狀態(tài)集S劃分為兩個(gè)子集；終態(tài)集F和非終態(tài)集F ?，形成初始劃分Π。
????????ii）對(duì)Π建立新的劃分Πnew。對(duì)Π中的每個(gè)狀態(tài)子集G進(jìn)行如下變換：
????????????a）把G劃分成新的子集，使G的兩個(gè)狀態(tài)s和t屬于同一個(gè)子集，當(dāng)且僅當(dāng)對(duì)任何輸入符號(hào)a，狀態(tài)s和t轉(zhuǎn)換到的狀態(tài)都屬于Π的同一子集。
????????????b）用G劃分出的所有新子集替換G，形成新的劃分Πnew。
????????iii）若Πnew和Π相等，則執(zhí)行第iv）步，否則，令Π=Πnew，重復(fù)第ii）步。
????????iv）劃分結(jié)束后，對(duì)劃分中的每個(gè)狀態(tài)子集，選出一個(gè)狀態(tài)作為代表，刪去其它一切等價(jià)的狀態(tài)，并把射向其它狀態(tài)的箭弧改為射向這個(gè)代表的狀態(tài)。
