編譯原理：第2章 形式語(yǔ)言概論

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

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

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

4、y B符號(hào)串的方冪。同一符號(hào)串的連接可寫成方冪形式設(shè)x是一符號(hào)串，則定義 x0= x1=x x2=xx x3=x2x=xx2=xxx 例如，x=abc，x2=abcabc，x3=abcabcabc符號(hào)串的運(yùn)算 (2)符號(hào)串集合的方冪。同一符號(hào)串集合的乘積也可以寫成方冪形式設(shè)符號(hào)串集合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 符號(hào)串的運(yùn)算 (3)符號(hào)串集合的正閉包：設(shè)符號(hào)串集合A，

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

6、終結(jié)符集； VN：非終結(jié)符集； P ：產(chǎn)生式集； S ：開始符號(hào)； 文法及其分類 文法：G(VN,VT, P,S) 0型文法：P: 其中：（VNVT）+,（VNVT）* 1型文法（上下文有關(guān)文法）： P: 其中：| 或1A212 ，1，（VNVT）* AVN （VNVT）+ 2 型文法（上下文無(wú)關(guān)文法）： P: A AVN （VNVT）+ 3型文法（右線性文法、正規(guī)文法）： P: Aa|aB A,BVN aVT0型文法 在2.2.1節(jié)中定義的文法即為0型文法(無(wú)限制的文法)。其產(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、文無(wú)關(guān)文法）在1型文法的產(chǎn)生式中上下文1和2用空符號(hào)串代替，則有以下形式的產(chǎn)生式稱為2型文法： A其中，AVN，(VNVT)+。2型文法（上下文無(wú)關(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á)式是由運(yùn)算符連接運(yùn)算量的式子表達(dá)式表達(dá)式+項(xiàng)|表達(dá)式-項(xiàng)|項(xiàng) 項(xiàng)項(xiàng)因子|項(xiàng)因子|因子 因子運(yùn)算量|(表達(dá)式)2型文法（上下文無(wú)關(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中的每個(gè)產(chǎn)生式(S例外，S為文法的開始符號(hào))只有兩種形式：Aa ，AaB 。其中 A，BVN ，aVT。此外，如果S是P中的一個(gè)產(chǎn)生式，那么S不能出現(xiàn)在任何產(chǎn)生式的右邊。例 正規(guī)文法G5(S)SdB|+A|-A|GAdB|GBdB|H|dGdHHdH|d 其中d代表十進(jìn)制數(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）*，則稱符號(hào)串為用產(chǎn)生式的直接推導(dǎo)，記為 多步推導(dǎo) 0步或多步推導(dǎo) 推導(dǎo)和規(guī)范推導(dǎo)(2)定義2.6:最左推導(dǎo):在 的直接推導(dǎo)中，若xVT*, UVNU是符號(hào)串 中的最左非終結(jié)符，則稱此直接推導(dǎo)為最左直接推導(dǎo)。每一步都為最左直接推導(dǎo)。 定義2.7:最右推導(dǎo):在 的直接推導(dǎo)中，若yVT*, UVNU是符號(hào)串 中的最右非終結(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. 確定下列文法的語(yǔ)言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)句型、句子和語(yǔ)言 定義2.8:設(shè)S是文法G的開始符號(hào)，如果 ，u（VNVT）*，稱u為文法G的句型。定義2.9:設(shè)S是文法G的開始符號(hào)，如果 ，uVT*，稱u為文法G的句子。定義2.10：設(shè)S是文法G的開始符號(hào)，文法G的 語(yǔ)言短語(yǔ)與句柄定義6.1: 設(shè)S是文法G的開始符號(hào)，若 UVN, x,y（VNVT）*, 稱是句型xUy相對(duì)于U的短語(yǔ)。又若UVN*， x,y（VNVT）*， 稱是句型xUy相對(duì)于U的直接短語(yǔ)或簡(jiǎn)單短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱該句型的句柄。 構(gòu)造下列語(yǔ)言的文法 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| 語(yǔ)法樹 設(shè)文法 G=(VT，VN，P，S)，對(duì)于文法G的任意一個(gè)句型都存在一個(gè)相應(yīng)的語(yǔ)法樹： 樹中每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，該標(biāo)記是VNVT中的一個(gè)符號(hào)； 樹的根結(jié)點(diǎn)標(biāo)記是文法的識(shí)別符號(hào)S； 若樹的一個(gè)結(jié)點(diǎn)至少有一個(gè)葉子結(jié)點(diǎn)，則該結(jié)點(diǎn)的標(biāo)記一定是一個(gè)非終結(jié)符； 若樹的一個(gè)結(jié)點(diǎn)有多個(gè)葉子結(jié)點(diǎn)，該結(jié)點(diǎn)的標(biāo)記為A，這些葉子結(jié)點(diǎn)的標(biāo)記從左到右分別是B1，B2，BN，則(A

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

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

17、U不出現(xiàn)在其它任何規(guī)則的右部，也應(yīng)刪除。 (U例外)。 無(wú)用VN、不可達(dá)VN舉例例如，對(duì)于文法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則進(jìn)一步要求能從U推導(dǎo)出終結(jié)符號(hào)串。 顯然，如果存在某個(gè)非終結(jié)符號(hào)U，它不滿足上述兩條件，則以U為左部的那些規(guī)則必是多余的。 二義性定義2.13 一個(gè)文法，如果它的一個(gè)句子有 兩棵或兩棵以上的語(yǔ)法樹，則稱 此句子具有二義性。如果一個(gè)文 法含有二義性的句子，則該文法 具有二義

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