編譯原理：第2章 形式語言概論

1、第2章形式語言概論2.1 語言成分 一個語言的成分包括字母表（Alphabet）,文法(Grammar)以及它的語義。 本章將主要討論字母表、符號串、產(chǎn)生式文法系統(tǒng)以及句子分析等方面的內(nèi)容。 2.1 語言成分字母表與符號 ：字母表是元素的非空有窮集合。字母表中的元素稱為符號。 符號串及其運算 ： 符號串。 符號串的長度。 符號串的連接。 符號串集合的乘積。 符號串的方冪。 符號串集合的方冪。 符號串集合的正閉包。 符號串集合的自反閉包。 字母表與符號串字母表：是符號的非空有窮集合，用表示符號串：由字母表中的符號所組成的任何有窮序列被稱之為該字母表上的符號串 設(shè)有字母表=a，b，c，那么: 序列

2、ab是上的一個符號串； 同樣序列ba，序列abc； 序列bcca等都是上的符號串 符號串的長度 | s |在語言的理論中，術(shù)語“句子”和“字”常常用作術(shù)語“符號串”的同義語。符號串s的長度記作| s |，是組成該符號串的符號的個數(shù)。例如，上述上的符號串a(chǎn)b的長度是2，記作 | ab |=2。符號串a(chǎn)bc的長度是3，記作| abc |3?？辗柎涀?，它由零個符號組成，于是|0。 與符號串有關(guān)的幾個術(shù)語(1) 符號串s 的前綴：移走符號串s的尾部的零個或多于零個符號所得到的一個符號串。 例如ban是符號串banana的一個前綴。符號串 s 的后綴：刪去符號串s的頭部的零個或多于零個符號所得到的

3、一個符號串。 例如nana是符號串banana的一個后綴。符號串s的子串：從 s 中刪去一個前綴和一個后綴而得到的符號串。 與符號串有關(guān)的幾個術(shù)語(2)符號串s的真前綴、真后綴、真子串： 任何非空符號串 x ，相應(yīng)地，是s的前綴、后綴或子串，并且sx。符號串 s 的子序列：從符號串 s 中刪去零個或多于零個符號(這些符號不要求是連續(xù)的)而得到的符號串。術(shù)語“語言”表示某個確定的字母表上的符號串的任何集合。 符號串的運算 (1)符號串的連接：設(shè)x , y 是符號串，則 xy 稱為 x 與 y 的連接 符號串集合的乘積：設(shè) A，B是符號串集合，AB表示A 與B的乘積，則定義 AB=xy| xA,

4、y B符號串的方冪。同一符號串的連接可寫成方冪形式設(shè)x是一符號串，則定義 x0= x1=x x2=xx x3=x2x=xx2=xxx 例如，x=abc，x2=abcabc，x3=abcabcabc符號串的運算 (2)符號串集合的方冪。同一符號串集合的乘積也可以寫成方冪形式設(shè)符號串集合A，則定義 A0= A1=A A2=AA A3=A2A=AA2 An=An-1A=AAn-1 例如，A=a，bc，A2=AA=aa，abc，bca，bcbc，A3=A2A=aaa，abca，bcaa，bcbca，aabc，abcbc，bcabc，bcbcbc 符號串的運算 (3)符號串集合的正閉包：設(shè)符號串集合A，

5、A的正閉包記為A+，則有 A+=A1A2An 即A+為集合A上所有符號串的集合符號串集合的自反閉包：符號串集合A的自反閉包記為A*，則有 A*=A+=A+ 語言之上的幾個重要運算 假設(shè)L和M表示兩個語言 語言L和M的合并(union)，記作LM，定義為： LM=S|S is in L or S is in M 語言L和M的連接(concatenation),記作LM,定義為： LMst|s is in L and t is in M 語言L的Kleene閉包，記作L*，定義為： L*=LiL0L1L2L3. 文法與語言的形式定義 定義 文法G是一個四元組： G=(VT，VN， P，S) VT：

6、終結(jié)符集； VN：非終結(jié)符集； P ：產(chǎn)生式集； S ：開始符號； 文法及其分類 文法：G(VN,VT, P,S) 0型文法：P: 其中：（VNVT）+,（VNVT）* 1型文法（上下文有關(guān)文法）： P: 其中：| 或1A212 ，1，（VNVT）* AVN （VNVT）+ 2 型文法（上下文無關(guān)文法）： P: A AVN （VNVT）+ 3型文法（右線性文法、正規(guī)文法）： P: Aa|aB A,BVN aVT0型文法 在2.2.1節(jié)中定義的文法即為0型文法(無限制的文法)。其產(chǎn)生式具有以下形式： 其中，(VNVT)+，(VNVT)* 1型文法（上下文有關(guān)文法）1型文法G的產(chǎn)生式具有以下形式：

7、 其中: =1 A2； =12； 1，2(VNVT)*； AVN；(VNVT)+。1型文法（上下文有關(guān)文法）舉例(1)條件 P: 其中：| GS=(VN,VT,P,S) VN=S,A,B,C VT=a,b,c P=S aSBC, S aBC, aB ab, bB bb, bC bc, CB BC, cC cc或條件 P:1A212 CB BC 改為 CB CD，CD BD，BD BC1型文法（上下文有關(guān)文法）舉例(2)GS=(VN,VT,P,S) VN=S,X,Y,Z VT=x,y,z P=S xSYZ|xYZ, xY xy, yY yy, yZ yz, ZY YZ, zZ zz2型文法（上下

8、文無關(guān)文法）在1型文法的產(chǎn)生式中上下文1和2用空符號串代替，則有以下形式的產(chǎn)生式稱為2型文法： A其中，AVN，(VNVT)+。2型文法（上下文無關(guān)文法）舉例(1) 條件 P:A AVN, （VNVT）+ GE=(VN,VT,P,E) VN=E,T,F VT=+,-,*,/,i,(,) P=E E+T|E-T|T, T T*F|T/F|F, F i|(E)表達(dá)式是由運算符連接運算量的式子表達(dá)式表達(dá)式+項|表達(dá)式-項|項 項項因子|項因子|因子 因子運算量|(表達(dá)式)2型文法（上下文無關(guān)文法）舉例(2)G4N P: N ND |D; D 0|1|2|3|4|5|6|7|8|9;G7S P: S

9、aTd; T bT|cT|b|c;G9S P: S 0S1|01 ;3型文法（右線性文法和正規(guī)文法） 在正規(guī)文法中，P中的每個產(chǎn)生式(S例外，S為文法的開始符號)只有兩種形式：Aa ，AaB 。其中 A，BVN ，aVT。此外，如果S是P中的一個產(chǎn)生式，那么S不能出現(xiàn)在任何產(chǎn)生式的右邊。例 正規(guī)文法G5(S)SdB|+A|-A|GAdB|GBdB|H|dGdHHdH|d 其中d代表十進制數(shù)字。 3型文法（右線性文法、正規(guī)文法）舉例條件 P: Aa|aB A,BVN , aVT G5S P: S 0 | 1 | 1A | 0B A1A|0B B0 | 1 | 0BG4N P: N 0|1|2|3

10、|4|5|6|7|8|9 | 0N|1N|2N|3N|4N|5N|6N|7N|8N|9N;推導(dǎo)和規(guī)范推導(dǎo)(1) 定義2.3：文法 G=(VN，VT，P，S)， P，,（VNVT）*，則稱符號串為用產(chǎn)生式的直接推導(dǎo)，記為 多步推導(dǎo) 0步或多步推導(dǎo) 推導(dǎo)和規(guī)范推導(dǎo)(2)定義2.6:最左推導(dǎo):在 的直接推導(dǎo)中，若xVT*, UVNU是符號串 中的最左非終結(jié)符，則稱此直接推導(dǎo)為最左直接推導(dǎo)。每一步都為最左直接推導(dǎo)。 定義2.7:最右推導(dǎo):在 的直接推導(dǎo)中，若yVT*, UVNU是符號串 中的最右非終結(jié)符，則稱此直接推導(dǎo)為最右直接推導(dǎo)。每一步都為最右直接推導(dǎo)。 最右(直接)推導(dǎo)又稱為規(guī)范推導(dǎo)最左推導(dǎo)與最

11、右推導(dǎo)舉例文法 GE E E+T|T； T T*F|F； F i|(E)；寫出i+(i+i)的最左推導(dǎo)與最右推導(dǎo)解：最左推導(dǎo)：E=E+T=T+T=F+T=i+T =i+F=i+(E) =i+(E+T) =i+(T+T) =i+(F+T) =i+(i+T) =i+(i+F) =i+(i+i) 最右推導(dǎo): E=E+T =E+F =E+(E) =E+(E+T) =E+(E+F) =E+(E+i) =E+(T+i) =E+(F+i) =E+(i+i) =T+(i+i) =F+(i+i) =i+(i+i)最左推導(dǎo)與最右推導(dǎo)舉例 1. 確定下列文法的語言GS：SABC|C; A1|2|3|4|5|6|7|

12、8|9|; BN|BN | C0|5 NA| 0 2. 已知文法 GZ：ZUV | VU UZ1 | 1 VZ0 | 0 試寫出01010110的最左推導(dǎo)和最右推導(dǎo)GZ：ZUV | VU UZ1 | 1 VZ0 | 0寫出01010110的最左和最右推導(dǎo)解：最左推導(dǎo)：Z=UV=Z1V =VU1V=Z0U1V=VU0U1V =0U0U1V=010U1V=010Z11V =010UV11V=0101V11V =0101011V=01010110 最右推導(dǎo)：Z=UV=U0=Z10=VU10=VZ110=VUV110=VU0110=V10110=Z010110=VU010110=V1010110=01

13、010110 GZ：ZUV | VU UZ1 | 1 VZ0 | 0寫出01011100的最左和最右推導(dǎo)句型、句子和語言 定義2.8:設(shè)S是文法G的開始符號，如果 ，u（VNVT）*，稱u為文法G的句型。定義2.9:設(shè)S是文法G的開始符號，如果 ，uVT*，稱u為文法G的句子。定義2.10：設(shè)S是文法G的開始符號，文法G的 語言短語與句柄定義6.1: 設(shè)S是文法G的開始符號，若 UVN, x,y（VNVT）*, 稱是句型xUy相對于U的短語。又若UVN*， x,y（VNVT）*， 稱是句型xUy相對于U的直接短語或簡單短語。一個句型的最左直接短語稱該句型的句柄。 構(gòu)造下列語言的文法 a3n|n

14、1; 解：GS: S aaaS|aaa 偶數(shù)集合 解：GN: N AB A DA| D 0|1|2|3|4|5|6|7|8|9 B 0|2|4|6|8 anbmck|n,m,k0解：GS: S ABC A aA| B bB| C cC| 語法樹 設(shè)文法 G=(VT，VN，P，S)，對于文法G的任意一個句型都存在一個相應(yīng)的語法樹： 樹中每個結(jié)點都有一個標(biāo)記，該標(biāo)記是VNVT中的一個符號； 樹的根結(jié)點標(biāo)記是文法的識別符號S； 若樹的一個結(jié)點至少有一個葉子結(jié)點，則該結(jié)點的標(biāo)記一定是一個非終結(jié)符； 若樹的一個結(jié)點有多個葉子結(jié)點，該結(jié)點的標(biāo)記為A，這些葉子結(jié)點的標(biāo)記從左到右分別是B1，B2，BN，則(A

15、，B1，B2BN) P。 語法樹 在自然語言中，可通過樹型表示直觀地分析句子結(jié)構(gòu)；在形式語言中，則是通過語法樹直觀地分析文法的句型結(jié)構(gòu)。句子結(jié)構(gòu)語法樹舉例文法 GE E E+T|T； T T*F|F； F i|(E)；E+i*(E+T)產(chǎn)生式樹 文法的句型可依據(jù)文法的產(chǎn)生式樹來生成相應(yīng)的語法樹。 產(chǎn)生式樹 文法的句型都可依據(jù)文法的產(chǎn)生式來生成相應(yīng)的語法樹。以句型E+(E+T)i為例： 以文法G的識別符號E作為語法樹根結(jié)點的標(biāo)記。選擇識別符E的一個產(chǎn)生式EE+T，然后生成根結(jié)點E的3個分支，根結(jié)點E的3個葉子結(jié)點的標(biāo)記，從左到右分別記為E、和T。 選擇產(chǎn)生式TTF，生成以結(jié)點T作為根結(jié)點的子樹。

16、 選擇產(chǎn)生式Fi，以中子樹最右邊的葉子結(jié)點F為根結(jié)點，延伸相應(yīng)的子樹。 選擇產(chǎn)生式TF，以中子樹的葉子結(jié)點T為根結(jié)點，延伸相應(yīng)的子樹。 選擇產(chǎn)生式F(E)，以中子樹的葉子結(jié)點F為根結(jié)點，延伸相應(yīng)的子樹，擴充相應(yīng)的子樹。產(chǎn)生式樹舉例文法 GE E E+T|T； T T*F|F； F i|(E)；無用VN、不可達(dá)VN 文法中規(guī)則的個數(shù)應(yīng)該是恰當(dāng)?shù)?。再少，不足以完全描述一個語言，再多，又無必要。 程序設(shè)計語言中存在有多余規(guī)則時，往往存在有錯誤 多余規(guī)則使句子的分析復(fù)雜和增加困難度。 明顯的多余規(guī)則有兩種。 一是形如UU的單規(guī)則，引起文法上的二義性。應(yīng)該首先把它們刪除去。另是規(guī)則Uu，其左都非終結(jié)符號

17、U不出現(xiàn)在其它任何規(guī)則的右部，也應(yīng)刪除。 (U例外)。 無用VN、不可達(dá)VN舉例例如，對于文法G Z： ZBe AAe | A | e BCe|Af CCf Df首先刪除規(guī)則AA;又由于D不出現(xiàn)在任何規(guī)則右部，應(yīng)刪去規(guī)則D。 規(guī)則不多余的條件：U 條件1 x,y（VNVT）*條件2 VT*。 條件1要求U在句型中出現(xiàn)，條件2則進一步要求能從U推導(dǎo)出終結(jié)符號串。 顯然，如果存在某個非終結(jié)符號U，它不滿足上述兩條件，則以U為左部的那些規(guī)則必是多余的。 二義性定義2.13 一個文法，如果它的一個句子有 兩棵或兩棵以上的語法樹，則稱 此句子具有二義性。如果一個文 法含有二義性的句子，則該文法 具有二義

18、性。 分析方法簡介一個分析器或分析自動機是這樣一種系統(tǒng)，它能夠根據(jù)給定的文法G，構(gòu)造語言L(G)的任意推導(dǎo)。分析也可看作是語法樹的構(gòu)造過程。我們主要討論右線性文法和CFG的分析器。 分析的方法很多，可歸納為兩類，一類是自上而下分析方法，另一類是自下而上分析方法。 2.6.1自上而下分析方法 自上而下分析方法的基本思想是從文法的開始符號出發(fā)，利用其中的產(chǎn)生式，逐步推導(dǎo)出待分析的符號串。如果能推導(dǎo)出這個符號串，則表明此符號串是該文法的一個句型或句子，否則便不是。 2.6.2 確定的自上而下分析方法 當(dāng)文法的某一個非終結(jié)符有幾條產(chǎn)生式、而且每條產(chǎn)生式右部首符號都是終結(jié)符時，應(yīng)保證它們是互不相同的終結(jié)符。 例 設(shè)文法G18S： SaBcbCd BeBf CdCc試檢查符號串a(chǎn)efc是不是該文法的句子。 2.6.2 確定的自上而下分析方法上例推導(dǎo)過程：SaBc ，SaBc ；BeB ， SaBcaeBc ；Bf ， SaBcaeBcaefc ；該例屬確定的