編譯原理文法知識(shí)
?
??? 今天來(lái)學(xué)習(xí)一下編譯原理的文法相關(guān)知識(shí)。這是屬于計(jì)算機(jī)的基礎(chǔ)內(nèi)容，還是比較有用的一塊內(nèi)容，比較類似于數(shù)據(jù)結(jié)構(gòu)，但是針對(duì)計(jì)算機(jī)的低級(jí)語(yǔ)言。一般來(lái)講比較難以理解，暫時(shí)就只是了解一下吧。OK開始：
?
?
??? 文法是一個(gè)四元組：G = {VT,VN,S,P}
?
??? 其中VT是一個(gè)非空有限的符號(hào)集合，它的每個(gè)元素成為終結(jié)符號(hào)。VN也是一個(gè)非空有限的符號(hào)集合，它的每個(gè)元素稱為非終結(jié)符號(hào)，并且VT∩VN=Φ。S∈VN，稱為文法G的開始符號(hào)。P是一個(gè)非空有限集合，它的元素稱為產(chǎn)生式。所謂產(chǎn)生式，其形式為α→β，α稱為產(chǎn)生式的左部，β稱為產(chǎn)生式的右部，符號(hào)“→”表示“定義為”，并且α、β∈(VT∪VN)*，α≠ε，即α、β是由終結(jié)符和非終結(jié)符組成的符號(hào)串。開始符S必須至少在某一產(chǎn)生式的左部出現(xiàn)一次。另外可以對(duì)形式α→β，α→γ的產(chǎn)生式縮寫為α→β|γ，以方便書寫。
?
??? 注：一般以大寫字母表示非終結(jié)符，以小寫字母表示終結(jié)符。
?
??? 著名語(yǔ)言學(xué)家Noam Chomsky(喬姆斯基)根據(jù)對(duì)產(chǎn)生式所施加的限制的不同，把文法分成四種類型，即0型、1型、2型和3型。
?
0型文法
?
??? 設(shè)G={VT,VN,S,P}，如果它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu)：α∈(VT∪VN)* 且至少含有一個(gè)非終結(jié)符，而β∈(VT∪VN)*，則G是一個(gè)0型文法。0型文法也稱短語(yǔ)文法。一個(gè)非常重要的理論結(jié)果是：0型文法的能力相當(dāng)于圖靈機(jī)(Turing)。或者說(shuō)，任何0型文語(yǔ)言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個(gè)0型語(yǔ)言。0型文法是這幾類文法中限制最少的一個(gè)，所以一般見到的至少是0型文法。
?
1型文法
??? 1型文法也叫上下文有關(guān)文法，此文法對(duì)應(yīng)于線性有界自動(dòng)機(jī)。它是在0型文法的基礎(chǔ)上每一個(gè)α→β，都有|β|>=|α|。這里的|β|表示的是β的長(zhǎng)度。
??? 注意：雖然要求|β|>=|α|，但有一特例：α→ε也滿足1型文法。
??? 如有A->Ba則|β|=2,|α|=1符合1型文法要求。反之,如aA->a，則不符合1型文法。
?
2型文法
?
??? 2型文法也叫上下文無(wú)關(guān)文法，它對(duì)應(yīng)于下推自動(dòng)機(jī)。2型文法是在1型文法的基礎(chǔ)上，再滿足：每一個(gè)α→β都有α是非終結(jié)符。如A->Ba，符合2型文法要求。
??? 如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因?yàn)槠洇?Ab，而Ab不是一個(gè)非終結(jié)符。
?
3型文法
?
??? 3型文法也叫正規(guī)文法，它對(duì)應(yīng)于有限狀態(tài)自動(dòng)機(jī)。它是在2型文法的基礎(chǔ)上滿足：A→α|αB（右線性）或A→α|Bα（左線性）。
??? 如有：A->a,A->aB,B->a,B->cB，則符合3型文法的要求。但如果推導(dǎo)為:A->ab,A->aB,B->a,B->cB或推導(dǎo)為：A->a,A->Ba,B->a,B->cB則不符合3型方法的要求了。具體的說(shuō)，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定義,如果把后面的ab,改成“一個(gè)非終結(jié)符＋一個(gè)終結(jié)符”的形式(即為aB)就對(duì)了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改為B->Bc的形式就對(duì)了，因?yàn)锳→α|αB(右線性)和A→α|Bα(左線性)兩套規(guī)則不能同時(shí)出現(xiàn)在一個(gè)語(yǔ)法中，只能完全滿足其中的一個(gè)，才能算3型文法。
?
一些相關(guān)的定義：
?
??? 1、當(dāng)G為2型或3型文法時(shí)，命題“L(G)是空集、有限集或無(wú)限集”才是可判斷的。
??? 2、當(dāng)G1和G2都是3型文法時(shí)，命題“L(G1)=L(G2)”才是可判斷的。
??? 3、最左/右推導(dǎo)：推導(dǎo)的每一步都對(duì)最左/右的非終結(jié)符使用推導(dǎo)公式
??? 4、若S可以推出mAn，而A可以推出a，則稱a是非終結(jié)符號(hào)A的、句型mAn的短語(yǔ)。若存在A=>a，則為直接短語(yǔ)。
??? 5、一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄
??? 6、素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，并除自身外不包含其他的素短語(yǔ)。
?
*************************************************************************
注：此類問(wèn)題可以用語(yǔ)法樹來(lái)判定，規(guī)則如下
?
1.每個(gè)句型對(duì)應(yīng)一棵語(yǔ)法樹
2.每棵語(yǔ)法樹的所有葉子結(jié)點(diǎn)從左到右排列構(gòu)成一個(gè)句型
3.每棵語(yǔ)法樹的子樹的葉子結(jié)點(diǎn)從左到右排列構(gòu)成一個(gè)短語(yǔ)
4.每棵語(yǔ)法樹的簡(jiǎn)單子樹(只有父子兩層結(jié)點(diǎn))的葉子結(jié)點(diǎn)從左到右排列構(gòu)成一個(gè)簡(jiǎn)單(直接)短語(yǔ)
5.每棵語(yǔ)法樹的最左簡(jiǎn)單子樹(只有父子兩層結(jié)點(diǎn))的葉子結(jié)點(diǎn)從左到右排列構(gòu)成句柄
6.素短語(yǔ)是至少包含一個(gè)終結(jié)符的短語(yǔ)，但它不能包含其它素短語(yǔ)
7.最左推導(dǎo)：在每個(gè)推導(dǎo)過(guò)程中，總是首先考慮對(duì)當(dāng)前最左邊的非終結(jié)符號(hào)進(jìn)行推導(dǎo)??
8.最右推導(dǎo)：在每個(gè)推導(dǎo)過(guò)程中，總是首先考慮對(duì)當(dāng)前最右邊的非終結(jié)符號(hào)進(jìn)行推導(dǎo)
?
舉例如下：
?
Vt={a,b,d,(,)}.Vn={S,T},S是開始符
S -> a|b|(T)
T -> TdS|S
句型(Sd(T)db)是S的一個(gè)_____,其中___是句柄;____是最左素短語(yǔ);____是該句型的直接短語(yǔ),_____是短語(yǔ)。
?
?
語(yǔ)法樹如下：
????????????? S??
??????????? / | \??
?????????? (? T? )??
?????????? /? |? \??
????????? T?? d?? S??
??????? / | \???? |??
?????? T? d? S??? b??
?????? |??? /|\??
?????? S?? ( T )??
?
1.首先在T->S之后還有一個(gè)S-b的推導(dǎo)，所以該句型不是最左推導(dǎo)，只是一個(gè)簡(jiǎn)單的推導(dǎo)
2.再看直接短語(yǔ)，有S,(T),b這3個(gè)，其余子樹均大于或等于3層
3.句柄為最左直接短語(yǔ)，即S
4.素短語(yǔ)在短語(yǔ)中從左往右找，S不是排除，Sd(T)包含了(T)，排除，最后剩下
(T)為最左素短語(yǔ)
5.短語(yǔ)很多，直接從備選答案里找即可
?
*************************************************************************
?
?
?
-------------------------------------------------------------------------------
?
有限狀態(tài)自動(dòng)機(jī)
?
??? 注：說(shuō)明一點(diǎn)，只要是有限狀態(tài)自動(dòng)機(jī)，則必定符合3型文法，且可用正則表達(dá)。
?
??? 一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)M(記做DFA)是一個(gè)五元組：M=(∑,Q,q0,F,δ)
?
??? 其中：
??? (1) Q是一個(gè)有限狀態(tài)合集
??? (2) ∑是一個(gè)字母集，其中的每個(gè)元素稱為一個(gè)輸入符號(hào)
??? (3) q0∈Q，稱為初始狀態(tài)
??? (4) F∈Q，稱為終結(jié)狀態(tài)集合
??? (5) δ是一個(gè)從Q×∑(Q與∑的笛卡爾積)到Q的單值映射：
??????? δ(q,a)=q* (q,q*∈Q, a∈∑)
??????? 以上式子表示當(dāng)前狀態(tài)為q，輸入符號(hào)a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一個(gè)狀態(tài)q*，q*稱為q的一個(gè)后繼。
?
??????? 若Q={q1,q2,...,qn
},∑={a1,a2,...,an}，則(δ(qi,aj))n×m是一個(gè)n行m列矩陣，稱為DFA的狀態(tài)轉(zhuǎn)換矩陣，或稱轉(zhuǎn)換表。
?
?
??? 有限狀態(tài)自動(dòng)機(jī)可以形象地用狀態(tài)轉(zhuǎn)換圖表示，舉例如下：
?
??? DFA M=({S,A,B,C,f},{1,0},S,{f
},δ)
??? 其中：δ(S,0)=B, δ(S,1)=A, δ(A,0)=f, δ(A,1)=C, δ(B,0)=C, δ(B,1)=f, δ(C,0)=f
, δ(C,1)=f
??? 則對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如下所示：
?
???
??? 其中圈表示狀態(tài)結(jié)點(diǎn)，雙圈表示終結(jié)狀態(tài)結(jié)點(diǎn)，而邊表示狀態(tài)的轉(zhuǎn)換，代表映射。邊上的符號(hào)表示此轉(zhuǎn)換需要輸入的符號(hào)，代表映射的輸入。
?
??? 對(duì)于∑上的任何字符串w∈∑*，若存在一條從初始結(jié)點(diǎn)到終態(tài)結(jié)點(diǎn)的路徑，在這條路徑上的所有邊的符號(hào)連接稱的符號(hào)串恰好是w，則w被DFA所識(shí)別(或接受、讀出)。DFA所能識(shí)別的符號(hào)串的全體記為L(zhǎng)(M)，稱為DFA所識(shí)別的語(yǔ)言。
?
?
NFA介紹
?
??? 之前介紹的是確定的有限自動(dòng)機(jī)，即一個(gè)狀態(tài)對(duì)于待定的輸入字符有一個(gè)確定的后繼狀態(tài)。而當(dāng)一個(gè)狀態(tài)對(duì)于特定的輸入字符有一個(gè)以上的后繼狀態(tài)時(shí)，我們稱該有限自動(dòng)機(jī)為非確定有限自動(dòng)機(jī)(記做NFA)，其形式定義也是M=(∑,Q,q0,F,δ)，且前面的字符定義均和DFA相同，但是δ：Q×∑對(duì)應(yīng)所有Q的任意子集。
?
??? 在NFA中能夠識(shí)別的路徑與DFA中定義也相同。
?
??? 對(duì)任何一個(gè)NFA，都存在一個(gè)DFA*使L(M*)=L(M)，這時(shí)我們稱M*與M等價(jià)。構(gòu)造與M等價(jià)的M*的基本方法是讓M*的狀態(tài)對(duì)應(yīng)于M的狀態(tài)集合。即如果δ(q,a)={q1,q2,...,qn}，則把{q1,q2,...,qn}看作M*的一個(gè)狀態(tài)，即M*中的狀態(tài)集合Q*的一個(gè)元素。
?
正則表達(dá)式的轉(zhuǎn)換
?
??? DFA和NFA和正則式的轉(zhuǎn)換比較模式化，看一個(gè)例子就明白了，具體的方法可以看下面這篇博客：
?
****************************************************************************************
?
版權(quán)聲明：可以任意轉(zhuǎn)載，但轉(zhuǎn)載時(shí)必須標(biāo)明原作者charlee、原始鏈接
http://tech.idv2.com/2006/05/08/parse-regex-with-dfa/
以及本聲明。
程序編譯的第一個(gè)階段是詞法分析，即把字節(jié)流識(shí)別為記號(hào)（token）流，提供給下一步的語(yǔ)法分析過(guò)程。而識(shí)別記號(hào)的方法就是正則表達(dá)式的分析。本文介紹利用有限自動(dòng)機(jī)分析表達(dá)式的方法。
概念
-
記號(hào)
-
有字母表中的符號(hào)組成的有限長(zhǎng)度的序列。記號(hào)s的長(zhǎng)度記為|s|。長(zhǎng)度為0的記號(hào)稱為空記號(hào)，記為ε。
-
有限自動(dòng)機(jī)(Finite State Automaton)
-
為研究某種計(jì)算過(guò)程而抽象出的計(jì)算模型。擁有有限個(gè)狀態(tài)，根據(jù)不同的輸入每個(gè)狀態(tài)可以遷移到其他的狀態(tài)。
-
非確定有限自動(dòng)機(jī)(Nondeterministic Finite Automaton)
-
簡(jiǎn)稱NFA，由以下元素組成：
-
1. 有限狀態(tài)集合S；
-
2. 有限輸入符號(hào)的字母表Σ；
-
3. 狀態(tài)轉(zhuǎn)移函數(shù)move；
-
4. 開始狀態(tài) sSUB{0}；
-
5. 結(jié)束狀態(tài)集合F，F ∈ S。
-
自動(dòng)機(jī)初始狀態(tài)為sSUB{0}，逐一讀入輸入字符串中的每一個(gè)字母，根據(jù)當(dāng)前狀態(tài)、讀入的字母，由狀態(tài)轉(zhuǎn)移函數(shù)move控制進(jìn)入下一個(gè)狀態(tài)。如果輸入字符串讀入結(jié)束時(shí)自動(dòng)機(jī)的狀態(tài)屬于結(jié)束狀態(tài)集合F，則說(shuō)明該自動(dòng)機(jī)接受該字符串，否則為不接受。
-
確定有限自動(dòng)機(jī)(Deterministic Finite Automaton)
-
簡(jiǎn)稱DFA，是NFA的一種特例，有以下兩條限制：
-
1. 對(duì)于空輸入ε，狀態(tài)不發(fā)生遷移；
-
2. 某個(gè)狀態(tài)對(duì)于每一種輸入最多只有一種狀態(tài)轉(zhuǎn)移。
將正則表達(dá)式轉(zhuǎn)換為NFA(Thompson構(gòu)造法)
算法
算法1 將正則表達(dá)式轉(zhuǎn)換為NFA(Thompson構(gòu)造法)
輸入 字母表Σ上的正則表達(dá)式r
輸出 能夠接受L(r)的NFA N
方法 首先將構(gòu)成r的各個(gè)元素分解，對(duì)于每一個(gè)元素，按照下述規(guī)則1和規(guī)則2生成NFA。 注意：如果r中記號(hào)a出現(xiàn)了多次，那么對(duì)于a的每次出現(xiàn)都需要生成一個(gè)單獨(dú)的NFA。
之后依照正則表達(dá)式r的文法規(guī)則，將生成的NFA按照下述規(guī)則3組合在一起。
規(guī)則1 對(duì)于空記號(hào)ε，生成下面的NFA。
規(guī)則2 對(duì)于Σ的字母表中的元素a，生成下面的NFA。
規(guī)則3 令正則表達(dá)式s和t的NFA分別為N(s)和N(t)。
a) 對(duì)于s|t，按照以下的方式生成NFA N(s|t)。
b) 對(duì)于st，按照以下的方式生成NFA N(st)。
c) 對(duì)于s*，按照以下的方式生成NFA N(s*)。
d) 對(duì)于(s)，使用s本身的NFA N(s)。
性質(zhì)
算法1生成的NFA能夠正確地識(shí)別正則表達(dá)式，并且具有如下的性質(zhì)：
-
N(r)的狀態(tài)數(shù)最多為r中出現(xiàn)的記號(hào)和運(yùn)算符的個(gè)數(shù)的2倍。
-
N(r)的開始狀態(tài)和結(jié)束狀態(tài)有且只有一個(gè)。
-
N(r)的各個(gè)狀態(tài)對(duì)于Σ中的一個(gè)符號(hào)，或者擁有一個(gè)狀態(tài)遷移，或者擁有最多兩個(gè)ε遷移。
示例
利用算法1，根據(jù)正則表達(dá)式 r=(a|b)*abb 可以生成以下的NFA。
將NFA轉(zhuǎn)化為DFA
算法
使用以下的算法可以將NFA轉(zhuǎn)換成等價(jià)的DFA。
算法2 將NFA轉(zhuǎn)化為DFA
輸入 NFA N
輸出 能夠接受與N相同語(yǔ)言的DFA D
方法 本算法生成D對(duì)應(yīng)的狀態(tài)遷移表Dtran。DFA的各個(gè)狀態(tài)為NFA的狀態(tài)集合，對(duì)于每一個(gè)輸入符號(hào)，D模擬N中可能的狀態(tài)遷移。
定義以下的操作。
|
操作
|
說(shuō)明
|
|
ε-closure(s)
|
從NFA的狀態(tài)s出發(fā)，僅通過(guò)ε遷移能夠到達(dá)的NFA的狀態(tài)集合
|
|
ε-closure(T)
|
從T中包含的某個(gè)NFA的狀態(tài)s出發(fā)，僅通過(guò)ε遷移能夠到達(dá)的NFA的狀態(tài)集合
|
|
move(T, a)
|
從T中包含的某個(gè)NFA的狀態(tài)s出發(fā)，通過(guò)輸入符號(hào)a遷移能夠到達(dá)的NFA的狀態(tài)集合
|
令 Dstates 中僅包含ε-closure(s), 并設(shè)置狀態(tài)為未標(biāo)記;
while Dstates中包含未標(biāo)記的狀態(tài)T do
begin
? 標(biāo)記T;
? for 各輸入記號(hào)a do
? begin
??? U := ε-closure(move(T, a));
??? if U不在Dstates中 then
????? 將 U 追加到 Dstates 中，設(shè)置狀態(tài)為未標(biāo)記;
??? Dtrans[T, a] := U;
? end
end
ε-closure(T)的計(jì)算方法如下：
將T中的所有狀態(tài)入棧;
設(shè)置ε-closure(T)的初始值為T;
while 棧非空 do
begin
? 從棧頂取出元素t;
? for 從t出發(fā)以ε為邊能夠到達(dá)的各個(gè)狀態(tài)u do
??? if u不在ε-closure(T)中 then
??? begin
????? 將u追加到ε-closure(T)中;
????? 將u入棧;
??? end
end
示例
將上面生成的NFA轉(zhuǎn)化為DFA。
最初，Dstates內(nèi)僅有ε-closure(0) = A = {0, 1, 2, 4, 7}。然后對(duì)于狀態(tài)A，對(duì)于輸入記號(hào)a，計(jì)算 ε-closure(move(A, a)) = ε-closure(move({0, 1, 2, 4, 7}, a)) = ε-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8}，即 B={1, 2, 3, 4, 6, 7, 8}, Dtran[A, a]=B。對(duì)于狀態(tài)A，由輸入記號(hào)b能夠到達(dá)的僅有4->5，因此 C = ε-closure({5}) = {1, 2, 4, 5, 6, 7}，即 Dtran[A, b] = C。
以此類推，可得到以下的狀態(tài)和Dtran。
A = {0, 1, 2, 4, 7}????????? D = {1, 2, 4, 5, 6, 7, 9}
B = {1, 2, 3, 4, 6, 7, 8}??? E = {1, 2, 4, 5, 6, 7, 10}
C = {1, 2, 4, 5, 6, 7}
|
狀態(tài)
|
輸入符號(hào)
|
|
a
|
b
|
|
A
|
B
|
C
|
|
B
|
B
|
D
|
|
C
|
B
|
C
|
|
D
|
B
|
E
|
|
E
|
B
|
C
|
由此得出DFA如下圖所示。
NFA和DFA的效率
給定正則表達(dá)式r和輸入記號(hào)序列x，判斷r是否能夠接受x。
使用NFA的情況下，由正則表達(dá)式生成NFA的時(shí)間復(fù)雜度為O(|r|)，另外由于NFA的狀態(tài)數(shù)最多為r的2倍，因此空間復(fù)雜度為O(|r|)。由NFA判斷是否接受x時(shí)，時(shí)間復(fù)雜度為O(|r|×|x|)。因此，總體上處理時(shí)間與 r、x的長(zhǎng)度之積成比例。這種處理方法在x不是很長(zhǎng)時(shí)十分有效。
如果使用DFA，由于利用DFA判斷是否接受x與狀態(tài)數(shù)無(wú)關(guān)，因此時(shí)間復(fù)雜度為O(|x|)。但是DFA的狀態(tài)數(shù)與正則表達(dá)式的長(zhǎng)度呈指數(shù)關(guān)系。例如，正則表達(dá)式 (a|b)*a(a|b)(a|b)...(a|b)，尾部有 n-1 個(gè) (a-b)的話， DFA最小狀態(tài)數(shù)也會(huì)超過(guò) 2SUP{n}。
?
?
?
?