《形式語言的基礎知識.ppt》由會員分享，可在線閱讀，更多相關《形式語言的基礎知識.ppt（56頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第2章 形式語言的基礎知識,,內容提要,形式語言 文法和語言 分析樹,2.1 形式語言,符號和字符串 符號：抽象實體，不加以形式定義。就像幾何學中的“點”?；蛘呓性痈拍?，憑直覺去體會。 字母表：有限個符號的集合。字母表一般用記。例如,英語的字母表=a,b,,z,A,B,,Z；漢語的字母表由漢字構成。,,字符串：字母表中符號的有窮序列。 字符串的長度：組成該字符串的符號的個數(shù)。字符串的長度記作||。 例如字符串banana的長度為6。空字符串記作，由0個符號組成，故||=0。,,字符串的前綴：該字符串領頭的若干符號。 字符串的后綴：該字符串結尾的若干符號。 例如，字符串a(chǎn)bc具有前綴，a，ab

2、和abc；其后綴有，c，bc，abc。 若字符串的前綴（或后綴）不是字符串本身，則稱之為真前綴（或真后綴）。,,字符串的子串：去掉字符串的一個前綴和后綴后得到的字符串。例如，nan是banana的一個子串。 字符串的子序列：從字符串中刪除0個或多個符號后得到的串（這些被刪除的符號可以不相鄰）。例如，baaa是banana的子序列。,,字符串的運算 字符串的連接：如果x和y是字符串，那么x和y的連接xy是把y接到x后面所形成的字符串。 例如，如果x=dog，y=house，則xy=doghouse。由的定義，顯然有==。,,字符串的方冪：設x是字符串，把x自身連接n次得到字符串z，即z=xxxx

3、，稱為字符串x的n次方冪，記作z=xn。我們規(guī)定x0=。 例如，設x=AB，則x0=，x1=AB，x2=ABAB，x3=ABABAB。對于，n0，有xn=xxn-1=xn-1x。,,字符串集合的連接：兩個字符串集合A和B的連接AB=xy|xA，yB，即AB是滿足x屬于A，y屬于B的所有字符串xy所組成的集合。 例如，若A=a,b，B=c,d，則AB=ac,ad,bc,bd。另外，我們有A=A=A。 對任意字符串集合A，An=AAAA，即n個A相連。A0定義為。,,Kleene閉包：一個固定的字母表上所有的字符串的集合稱為集合的Kleene閉包，記作*。根據(jù)定義，我們有*=012n。 正閉包：+

4、=123n稱為的正閉包。顯然有 *=0+ +=*=*,,形式語言 語言：給定字母表上的任意一個字符串集合，即*的子集（*本身也是自己的子集，所以*也是語言）?？占陀煽兆址M成的集合都是語言。,2.2 文法和語言,文法是程序語言的生成系統(tǒng)，而自動機則是程序語言的識別系統(tǒng)。用文法可以精確地定義一個語言，并依據(jù)該文法構造出識別這個語言的自動機。因此，文法對程序語言和編譯程序的構造具有重要意義，如程序語言的詞法可用正規(guī)文法描述，語法可用上下文無關文法描述，而語義則要借助于上下文有關文法描述。,2.2.1 基本概念 定義 文法 文法表示成四元組G=(VT, VN, S, P)，其中： (1)VT為終

5、結符號(terminal)集，是一個非空有限集，它的每個元素稱為終結符號； (2)VN為非終結符(non-terminal)集，也是一個非空有限集，其每個元素稱為非終結符號。 要求VTVN=； (3)S為一文法開始符號，也稱作識別符號，是一個特殊的非終結符號，即SVN；,(4)P是產(chǎn)生式的非空有限集，其中每個產(chǎn)生式(或稱規(guī)則)是一序偶(, )，通常寫作 讀作“是”或“定義為”。在此，為產(chǎn)生式的左部，而為產(chǎn)生式的右部，、是由終結符和非終結符組成的符號串， (VTVN)+且至少有一個非終結符，而(VTVN)*。 終結符和非終結符的集合用符號V表示，即V=VTVN。,終結符代表了語法的最小元素。 非

6、終結符號也稱語法變量，它代表語法實體或語法范疇；非終結符代表一個一定的語法概念，因此，一個非終結符是一個類、一個集合。 例如，在程序語言中，可以把變量、常數(shù)、“+”、“*”等看作是終結符，而像“算術表達式”這個非終結符則代表著一定算術表達式組成的類，如i*(i+i)、i+i+i等；也即每個非終結符代表著由一些終結符和非終結符且滿足一定規(guī)則的符號串組成的集合。,產(chǎn)生式是定義語法實體的一種書寫規(guī)則。一個語法實體的相關規(guī)則可能不止一個。 P1，P2，，Pn 可將這些有相同左部的產(chǎn)生式合并為一個，即縮寫成 P12n 其中，每個i(i=1,2,,n)稱為P的一個候選式，直豎“”讀為“或”，它與“”一樣是

7、用來描述文法的元語言符號(即不屬于的字符)。,例2.1 文法G=(VN, VT, P, S)，其中VN=S， VT=0,1，P=S0S1, S01。 例2.2 文法G=(VN, VT, P, S)，其中VN=,, ，VT=a,,z,0,,9， P= a||z 0||9 S=,,習慣上只將產(chǎn)生式寫出。并有如下約定： 第一條產(chǎn)生式的左部是開始符號 用尖括號括起的是非終結符，否則為終結符?；蛘叽髮懽帜副硎痉墙K結符，小寫字母表示終結符 G可寫成GS，其中S是開始符號,,定義 直接推導&直接規(guī)約 設文法G=(VT,VN,S,P)且、(VTVN)*，如果存在產(chǎn)生式A((VTVN)*)，則稱A可直接推導出

8、，或者說是A的直接推導，記做 A 其中“”表示直接推導出，是應用產(chǎn)生規(guī)則進行推導的記號。反過來，則稱可直接規(guī)約到A，或者說A是的直接規(guī)約。,注意“”與“”不同，“”是產(chǎn)生式中的定義記號。直接推導是對文法符號串A中的非終結符A用相應的產(chǎn)生式A的右部來替換，從而得到。 例如，對例2.1和例2.2的文法G，可以給出一些直接推導的例子： 0S10011, S0S1, 0S100S11 ,S0S1, S01, a||z 0||9,定義 推導&規(guī)約的傳遞閉包 如果存在一個自1至n的直接推導序列：123n(n1)，則我們稱1可推導出n，或稱n規(guī)約到1，記為1+n，它表示從1出發(fā)經(jīng)過一步或若干步可推導出n。

9、 定義 推導&規(guī)約的自反傳遞閉包 如果有1+n或1=n，則記1*n，表示從1出發(fā)，經(jīng)過0步或若干步可推導出n。,,例如， 對例2.1的文法，0S100+001100，當然也可以是0S100*001100。 對2.2的文法，+x1，當然也可以是*x1。,S0S1, S01, a||z 0||9,定義 句型&句子 設GS是一文法，S是它的開始符號，如果S*，(VTVN)*，則稱是文法GS的一個句型；如果VT*，則稱是文法GS的一個句子。 例如，S，0S1，000111都是例2.1的文法G的句型，其中000111是G的句子。，，a1等都是例2.2的文法G的句型，其中a1是G的句子。,S0S1, S

10、01, a||z 0||9,定義 文法的語言 文法GS產(chǎn)生的句子的全體稱為由文法GS產(chǎn)生的語言，記為L(G)，即有L(G)=S*且VT*。 例如，例2.1的文法產(chǎn)生的語言的句子具有0n1n的形式。 定義 文法等價 若L(G1)=L(G2)，則稱文法G1和G2是等價的。 例如，文法GA: A0R，A01，RA1。和例2.1的文法等價。,S0S1, S01,2.1.2 Chomsky譜系 語言學家Noam Chomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應的形式語言，并分別與相應的識別系統(tǒng)相聯(lián)系，它對程序語言的設計、編譯方法、計算復雜性等方面都產(chǎn)生了重大影響。 Chomsk

11、y把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在于對產(chǎn)生式施加不同的限制。,,0型文法與0型語言(對應圖靈機) 如果文法G的每一個產(chǎn)生式具有下列形式： 其中，V*VNV*，即至少含有一個非終結符；V*；則稱文法G為0型文法或短語結構文法，記為PSG(Phrase Structure Grammar)。0型文法相應的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turing)機。,,1型文法與1型語言(對應線性界限自動機) 文法G的產(chǎn)生式 在0型文法的基礎上增加了字符長度上滿足||||的限制，則稱文法G為1型文法或上下文有關文法，記為CSG (Context-Sensi

12、tive Grammar)。1型文法相應的語言稱為1型語言或上下文有關語言，它的識別系統(tǒng)是線性界限自動機。,,1型文法的另一種定義方法是文法G的每一個產(chǎn)生式具有下列形式： A 其中，AV*，AVN，V+；顯然它滿足前述定義的長度限制，但它更明確地表達了上下文有關的特性，即A必須在、的上下文環(huán)境中才能被所替換。 自然語言的語法應屬于上下文有關文法。,,2型文法與2型語言(對應下推自動機) 文法G的每一個產(chǎn)生式具有下列形式： A 其中，AVN，V*，則稱文法G為2型文法或上下文無關文法，記為CFG (Context-Free Grammar)。2型文法相應的語言稱為2型語言或上下文無關語言，它的識

13、別系統(tǒng)是下推自動機。 程序設計語言的語法是上下文無關的。,3型文法與3型語言(對應有限自動機) 文法G的每個產(chǎn)生式具有下列形式： A或AB 其中，A、BVN， VT*，則文法G稱為右線性文法。若每個產(chǎn)生式具有下列形式： A或AB 則文法G稱為左線性文法。右線性和左線性文法都稱為3型文法、正規(guī)文法，記為RG (Regular Grammar)。3型文法相應的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機。,,例2.1和例2.2中的文法都是上下文無關的。 例2.3 設G=(VN, VT, P, S)，VN=S, B, E，VT=a, b, e， P=SaSBE, SaBE, EBBE, aBa

14、b, bBbb, bEbe, eEee 文法G是上下文有關的，L(G)=anbnen|n1,S0S1, S01, a||z 0||9,,S aSBE (SaSBE) aaBEBE (SaBE) aabEBE (aBab ) aabBEE (EBBE ) aabbEE (bBbb) aabbeE (bEbe) aabbee (eEee) S aSBEaaSBEBEaaaBEBEBE,,四類文法的聯(lián)系與區(qū)別 聯(lián)系：從0型文法到3型文法逐漸增加限制。13型文法都屬于0型文法，2、3型文法均屬于1型文法，3型文法屬于2型文法。 區(qū)別：(1)1型文法中不允許有形如“A”的產(chǎn)生式存在，而2、3型文法則

15、允許形如“A”的產(chǎn)生式存在；(2)0、1型文法的產(chǎn)生式左部存在含有終結符號的符號串或兩個以上的非終結符，而2型和3型文法的產(chǎn)生式左部只允許是單個的非終結符號。,,文法的應用 在編譯方法中，通常用3型文法來描述高級程序語言的詞法部分，然后用有限自動機FA來識別高級語言的單詞；利用2型文法來描述高級語言的語法部分，然后用下推自動機PDA(Push-Down Automata)來識別高級語言的各種語法成分。,,貫穿詞法分析和語法分析始終如一的思想是：語言的描述和語言的識別是表示一個語言的兩個不同的側面，二者缺一不可。用正規(guī)文法和上下文無關文法描述語言時的識別方法(即自動機)不同。通常，正規(guī)文法適合于

16、描述線性結構，如標識符、關鍵字和注釋等；而上下文無關文法則適合于描述具有嵌套(層次)性質的非線性結構，如不同結構的語句if-else、while等。,2.2 推導與分析(語法)樹,上下文無關文法有足夠的能力描述現(xiàn)今程序設計語言的語法結構，比如描述算術表達式和各種語句等。 例2.6 文法GE： EE+EE*E(E)i 非終結符E表示一類算術表達式。i表示程序設計語言中的變量，該文法定義了由變量、+、*、(和)組成的算術表達式的語法結構。,,分析樹 對程序語言來說，有兩個問題需要解決：其一是判別程序在語法上是否正確；其二是句子的識別或分析。在編譯方法中，為了便于識別或分析句子而引入了分析樹這一重要

17、的輔助工具。分析樹以圖示化的形式把句子分解成各個組成部分來描述或分析句子的語法結構，這種圖示化的表示與所定義的文法規(guī)則完全一致，但更為直觀和完整。,對文法G=(VT, VN, S, P) ，滿足下列條件的樹稱為GS的句型的分析樹： (1) 結點用GS的一個終結符或非終結符標記； (2) 根結點用文法開始符S標記； (3) 內部結點(指非葉結點)一定是非終結符，如果某內部結點A有n個分支，它的所有子結點從左至右依次標記為x1、x2、、xn，則Ax1x2xn一定是文法GS的一條產(chǎn)生式； (4) 如果某結點標記為，則它必為葉結點且是其父結點的唯一子結點。,,例2.7 例2.6的文法的一棵分析樹 句

18、子i+i*i的分析樹,EE+EE*E(E)i,,在一棵分析樹生長過程中的任何時刻，所有那些沒有后代的樹葉結點自左至右排列起來就是一個句型。 分析樹表示了在推導過程中施用了哪個產(chǎn)生式和施用在哪個非終結符上，它并沒有表明施用產(chǎn)生式的順序。 例如，上面的分析樹表示的句子i+i*i可以有不同的推導過程： EE+Ei+Ei+E*Ei+i*Ei+i*i EE+EE+E*EE+E*iE+i*ii+i*i,,最左（最右）推導 推導序列中的每一步推導都是對句型中的最左（最右）非終結符用相應產(chǎn)生式的右部進行替換，這樣的推導稱為最左（最右）推導。最右推導常被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型。規(guī)范推導的

19、逆過程便是規(guī)范規(guī)約。 例如，前面的第一個推導就是最左推導，而第二個推導就是最右推導。,,因此，一棵語法樹表示了一個句型種種可能的不同推導過程，包括最左(最右)推導。如果我們堅持使用最左(或最右)推導，那么一棵語法樹就完全等價于一個最左(或最右)推導，這種等價性也包括語法樹的每一步生長和推導的每一步展開的這種完全一致性。,,介詞短語附著歧義 He saw a boy with a telescope. 他通過望遠鏡看到一個男孩。 他看到一個帶望遠鏡的男孩。,,文法的二義性 一個句型是否只對應唯一的一棵語法樹呢？一個句型是否只有唯一的一個最左（最右）推導呢？非也。 例如，例2.6的文法G的句子i+

20、i*i就有兩個不同的最左推導： EE+Ei+Ei+E*Ei+i*Ei+i*i EE*EE+E*Ei+E*Ei+i*Ei+i*i 對應有兩棵不同的語法樹：,,,,文法GS的一個句子如果能找到兩個不同的最左推導(或最右推導)，或者存在兩棵不同的語法樹，則稱這個句子是二義性的。一個文法如果包含二義性的句子，則這個文法是二義文法，否則是無二義文法。,再如，條件語句的文法GS為： GS: Sif B S Sif B S else S SA /*A指其它語句*/ 其中，VN = B,S,A，VT = if , else。 句型if B if B S else S所對應的兩棵不同語

21、法樹： 因此，文法GS是二義性文法。,,注意：一個文法是二義性的，并不說明該文法所描述的語言也是二義性的。也即，對于一個二義性文法GS，如果能找到一個非二義性文法GS，使得L(G)=L(G)，則該二義性文法的二義性是可以消除的。如果找不到這樣的GS，則二義性文法描述的語言為先天二義性的。,文法二義性消除的方法 不改變文法中原有的語法規(guī)則，僅加進一些語法的非形式規(guī)定。 如對例子2.6的文法，不改變已有的四條規(guī)則，僅加進運算符的優(yōu)先順序和結合規(guī)則，即*優(yōu)先于+，且*、+都服從左結合。 構造一個等價的無二義性文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。 例2.8 可以將例2.6的文

22、法改寫為無二義性的文法GE如下：EE+TT TT*FF F(E)i,EE+EE*E(E)i,,注： 1）二義性會給語法分析帶來不確定性。 2）文法的二義性是不可判定的，即不存在算法，能夠在有限步數(shù)內確切判定一個文法是否為二義文法。 3）若要證明是二義性，只要舉出一例，即給出文法的某個句子有兩個不同的最左（最右）推導，或兩棵不同的語法樹。 4）若能控制文法的二義性，即加入人為的附加條件，則二義文法的存在并非壞事。,,自頂向下的語法分析 例：文法G：ScAd Aab Aa識別輸入串 w = cabd是否該文法的句子 推導過程：S cAd cabd,S,,自底向上的語法分析

23、規(guī)約過程： S cAd cabd,,句法分析的有關問題 1）如何選擇使用哪個產(chǎn)生式進行推導？ 假定要被代換的最左非終結符號是V，且有n條規(guī)則：VA1|A2||An，那么如何確定用哪個右部去替代V？ 2）如何識別可歸約串？ 在自底向上的分析方法中，在分析程序工作的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結符號，該子串稱為“可歸約串”素短語和句柄。,,短語 設是文法GS的一個句型，如果有： S*A且A+ 則稱是句型關于非終結符A的一個短語，或稱是的一個短語。特別是有A產(chǎn)生式時，稱為句型的一個直接短語或簡單短語。 一個句型的最左直接短語稱為該句型的句柄。 注意，一個句型的直接短語可能不

24、只一個，但最左直接短語則是唯一的。 含有終結符的短語，如果它不存在也具有同樣性質的真子串，則該短語為素短語。,,子樹和短語 只含有單層分枝的子樹稱為簡單子樹。 (1) 短語：子樹的葉子結點組成的符號串是相對于子樹根的短語； (2) 直接短語：簡單子樹的葉子結點組成的符號串是相對于簡單子樹根的直接短語； (3) 句柄：最左簡單子樹的葉子結點組成的符號串為句柄； (4) 素短語：子樹的葉子結點組成的符號串含終結符，且在該子樹中不再有包含有終結符的更小子樹。,,例2.9 例2.8的文法的句子i1+i2*i3 短語：i1+i2*i3，i1，i2*i3，i2，i3 直接短語：i1，i2，i3 句柄：i1 素短語：i1，i2，i3,,,,,,,,,EE+TT TT*FF F(E)i,