1、第二章 文法和語言,編譯過程的核心就是翻譯，這是一個十分復雜的信息加工過程，其加工的對象是用某種高級語言編寫的程序。對于一個英文翻譯來說，首先必須對英文有很深的了解，掌握英文的語法和詞匯，才能進行翻譯。而編譯程序的任務就是將高級語言編寫的程序翻譯成機器語言程序，因此，在學習和掌握編譯技術之前，就需要對高級語言有深刻的了解。首先要了解如何確切地描述或定義一種程序設計語言，其次才能識別和分析這種語言。20世紀50年代，語言學家Noam Chomsky（喬姆斯基）提出了一個用來描述語言的數(shù)學系統(tǒng)，把用一組數(shù)學符號和規(guī)則來描述語言的方式叫做形式描述，而把能用數(shù)學符號和規(guī)則描述的語言稱為形式語言。這種理

2、論對程序設計語言的設計和編譯程序的構造有著重大的作用。程序設計語言就是形式語言,2.1 字母表和符號串,介紹文法和語言之前，首先介紹符號、符號串等基本概念。任何一種語言都是由該語言的基本符號所組成的符號串集合的子集。例如，英語的基本符號有26個字母和一些標點符號，由這些基本符號所組成的各種可能序列的符號串構成一個無窮的集合，而英語就是這個集合的子集。同理，C語言的基本符號有if,while,for,字母、數(shù)字和+、-、（、）、=等分界符，由這些符號組成的各種可能序列的符號串構成一個無窮的集合，而C語言就是這個集合的子集。任何一個C語言程序都是定義在這個集合上的符號串，即任何一個C語言程序都是由

3、這些基本符號所組成的序列。,2.1.1字母表,“字母表”是元素的非空有窮集合。字母表中的每個元素稱為“符號”，因此“字母表”也可稱為“符號集”。典型的符號有字母、數(shù)字、各種標點符號和各種運算符。 例如，集合a，b，c，+，*是一個含有5個符號的字母表，而字母表0，1只有兩個符號。,2.1.2符號串,“符號串”是由字母表上0個或多個符號所組成的任何有窮序列。例如有字母表a，b，c，+，*，則a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是該字母表上的符號串，而所有二進制數(shù)都是定義在字母表0，1上的符號串。要注意也是字母表上的符號串，它由0個符

4、號組成。顯然，一個字母表上的全部符號串所組成的集合是無窮的。,2.1.3 符號串及其集合的運算1,1.符號串的長度：指符號串x中所含符號的個數(shù)，記為|x|。 如|abc|=3，|abc+*abc|=8，而|=0 2.符號串相等：若x、y是字母表上的兩個符號串，那么當且僅當組成x的各符號與組成y的各符號依次相等時，則符號串x與符號串y相等，記作x=y。 如： 當x=abbc，y=abbc 時，則x=y ； 而當x=ab，y=ba 時，則xy 3.符號串的前綴：指從符號串x的末尾刪除0或多個符號后得到的符號串，如u、uni、university都是university的前綴。 4.符號串的后綴：指

5、從符號串x的開頭刪除0或多個符號后得到的符號串，如ty、sity、university都是university的后綴。,2.1.3 符號串及其集合的運算2,5.符號串的子串：指從符號串x的開頭和末尾刪除0或多個符號后得到的符號串，如ver是university的子串, 符號串的前綴、后綴都是它的子串。 6.符號串的連接：若x、y是兩個符號串，則xy表示連接，是將符號串y連接在符號串x的后面。若x、y是字母表上的兩個符號串，則xy也是字母表上的符號串。 例如： x=ab，y=ba，那么 xy=abba 注意：連接沒有交換率，即 xy yx 而對于空串有 x=x =x,2.1.3 符號串及其集合的

6、運算3,7.集合的乘積運算：令A、B為兩個符號串集合，A和B的乘積AB定義為： AB=xy|x A ，y B 例如：A=a，b B=c，d，則AB=ac，ad，bc，bd 對于空集合有有： A=A =A 8.符號串的冪運算：若x是符號串，則x的冪運算定義為： X0=, x1=x , x2=xx ,，xn=xxx=xx n-1=x n-1 x ,其中 n0 例如：x=abc, x0= , x1=abc, x2=abcabc,2.1.3 符號串及其集合的運算4,9.集合的冪運算：設A為符號串集合，則A的冪運算定義為： A0= A1=A A2=AA An=AAA=AA n-1 =A n-1 A ，其

7、中 n0,例如：A =a，b， 則 A0= A1=a,b A2=aa,ab,ba,bb,2.1.3 符號串及其集合的運算4,10.集合的正閉包和集合的閉包：設A為一個集合，則集合A的正閉包用A+表示，定義為： A+ =A1 A2 . A n 集合A的閉包用A*表示，定義為： A* =A 0 A+ 例如：A =a，b， 則A+ =a,b,aa,ab,ba,bb,aaa,aab, A* = ,a,b,aa,ab,ba,bb,aaa,aab, 一個集合的閉包比正閉包多個。,2.2 文法,在學習英語時，我們知道句子由主語、謂語組成，主語由冠詞、形容詞及名詞組成等等，這就是說明句子組成的規(guī)則。而在形式語

8、言里，這種規(guī)則可采用“:=”、“:=”這種形式來表示。分析一個句子是否正確，就是根據(jù)這些規(guī)則進行的。文法實際上就是描述語言語法結構的形式規(guī)則。,2.2.1 文法形式定義1,在表示文法時，要說明語言的語法成分，句子中的符號以及語法結構。 例如，能夠描述句子“the monkey ate the banana”的文法如下：,這些規(guī)則說明句子由主語和謂語組成，主語由冠詞和名詞等等，而冠詞由the構成，名詞由banana或monkey構成。在這個文法里，一共有8條規(guī)則，每條規(guī)則中在:=左邊的符號其著語法成分的作用，它們可用:=右邊的符號代替。而像the、ate、banana這樣的符號只在規(guī)則中:=的右

9、邊出現(xiàn)，這些符號不能用其它符號代替。, := := := := := := := := ,2.2.1 文法形式定義2,文法的形式定義：文法可表示為一個四元組 G=（ Vn ， Vt ，P，Z） Vn是一個非空有窮集合，該集合中的每個元素稱為非終結符號。如上例中的符號、 等等。 Vt是一個非空有窮集合，該集合中的每個元素稱為終結符號。如上例中的符號the、ate、banana等等都是終結符號。并且VtVn=，即Vt集合與Vn集合的交集為空。而Vt和Vn并集VtVn就是該文法的字匯表（即字匯表字母表）。 P是一個非空的有窮集合，它的每個元素叫做產(chǎn)生式或規(guī)則。產(chǎn)生式的形式為： 或:= 是產(chǎn)生式的左部

10、且不能為空，是產(chǎn)生式的右部，并且、（VtVn）* ，“”或”“:=”含義相同，表示“定義為”或“由組成”。 Z是Vn集合的一個特殊的非終結符號，稱為文法的識別符號或開始符號。它至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。就是上例文法的識別符號。,2.1 文法形式定義3,文法分4種類型（見2.13小節(jié)），程序設計語言文法主要為2型文法，這種文法也叫上下文無關文法，本書后面說的文法都是指這種文法。在上下文無關文法中，產(chǎn)生式的左部是一個非終結符號，而右部是由終結符號和非終結符號組成的有窮符號串。這樣只要給出產(chǎn)生式集合，所有產(chǎn)生式的左部符號就構成了非終結符號集合Vn，而只出現(xiàn)在產(chǎn)生式右部的那些符號構成終結符號

11、集合Vt，因此，在表示文法時只需給出規(guī)則集合并指定識別符號即可。為了進一步簡化，在給出規(guī)則集時，可約定將左部符號為識別符號的規(guī)則作為規(guī)則集合的第一條規(guī)則，這樣表示文法時只需給出規(guī)則的集合即可。顯然，上例就是一個簡化的文法表示。,2.1 文法形式定義4,例2.1，按文法形式定義表示上例文法。 解：根據(jù)文法的形式定義，文法 G1=（ Vn， Vt，P，Z） 非終結符號集合: Vn=句子，主語，謂語，冠詞，名詞，動詞，直接賓語 終結符號集合: Vt= the，ate，banana，monkey 產(chǎn)生式集合P由下面8條規(guī)則組成: 識別符號Z： , the ate banana monkey,2.1 文

12、法形式定義5,例2.2，有如下簡化表示文法，只給出規(guī)則集，寫出該文法的終結符號集合、非終結符號集合和識別符號。,1. 2. 3. 4.0 5.1 6.2 7.3 8.4 9.5 10.6 11.7 12.8 13.9,解：根據(jù)簡化約定，可確定： 非終結符號集合： Vn=, 終結符號集合： Vt=0,1,2,3,4,5,6,7,8,9 識別符號Z：,2.2.2文法的EBNF表示,所謂文法的EBNF表示，就是在書寫文法的規(guī)則時，可采用一些特殊的符號“|”、“”和“”、“”、“（” 和“）”、“” 和“”來表示文法，這些符號叫做元符號。其中“”和“”、“”、“（” 和“）”、“” 和“”這些元符號總

13、是成對出現(xiàn)。下面介紹各種元符號的含義。,1.元符號“|”：表示“或”.對于具有相同左部的那些規(guī)則 如 1、 、 n，可以縮寫為: 1 | 2 | n 例2.3，對例2.2文法的13條規(guī)則可縮寫成： := :=| :=0|1|2|3|4|5|6|7|8|9,2.2.2文法的EBNF表示,2.元符號“”：用于括起由中文字組成的非終結符號或由多個字母組成的符號。如、等等。 3.元符號“”和“”：表示可重復連接，tnm表示符號串t可重復連接n到m次，而t表示符號串t可重復連接0到無窮次。 例如， 13 與 | 相同 EE+T|T 與 ET+T 相同 而字母打頭、后面可跟數(shù)字或字母的不超過8個字符的標識

14、符文法則為： |07,2.2.2文法的EBNF表示,4.元符號“”和“ ”：表示括起的內容可有可無。如t表示符號串t可有可無。 例如：IF THEN IF THEN ELSE 可寫成： IF THEN ELSE 5.元符號“（”和“）”：表示括號內的成分優(yōu)先。常用于在規(guī)則中提取公因子。 例如，Uxy|xw|xz 可寫成：Ux（y|w|z） 從上述有關元符號的定義和例子可看出，這些元符號為表示文法提供了很大方便。,2.3 推導,給定了文法，就可以從文法的開始符號并根據(jù)文法規(guī)則進行推導。通過推導可產(chǎn)生文法定義的句子。 例如，根據(jù)例2.1文法的規(guī)則，可從開始符號推出，又根據(jù)規(guī)則，可從推出，這個推導過

15、程可表示成如下： = 其中“=”表示一步推導, 上述推導過程表示經(jīng)過兩步推導， 從可推導出。,2.5.1直接推導,假定G是一文法, 是該文法的一個產(chǎn)生式，現(xiàn)有一含非終結符號的符號串xy ，其中x和y是該文法的任意符號串(可為空),推導就是利用產(chǎn)生式將符號串xy中的非終結符號用替換，從而得到符號串xy。表示為： xy=xy 其中“=”表示一步推導。我們稱xy直接推導出xy,或xy直接產(chǎn)生xy。若從反方向看，則稱xy直接歸約到xy。,2.5.1直接推導,例如有文法 1）:= 2）:=| 3）:=0|1|2|3|4|5|6|7|8|9 對符號串利用規(guī)則1可直接推導出： = 對符號串利用規(guī)則2可直接推

16、導出： = 對符號串利用規(guī)則3可直接推導出2： = 2 將上述三個推導連接起來，可得如下推導過程： = = = 2 在這個推導過程中，直接推導出，直接推導出，直接推導出2。,2.3.2推導,如果存在一直接推導序列0=2=n，其中n0, 那么我們說 0產(chǎn)生n或n歸約到 1,并記作0 =+n,推導長度為n。 如果有0= + n 或0 = n, 即n 0,則記作0= * n 。 例如，從開始，分別利用規(guī)則1、2、2、3、3，可產(chǎn)生如下推導過程： = =2=23 這個推導過程可記作： = + 23 ， 其推導長度n=5， 表示產(chǎn)生23，或23歸約到。 而從到的推導，無須使用任何規(guī)則，可記作： =* ，

17、其推導長度n=0。,2.3.3規(guī)范推導,規(guī)范推導也叫最右推導，即每步推導只變換最右邊的非終結符號。其形式定義為： 對于直接推導xy=xy來說，如果y只包含終結符號或為空符號串,那么就把這種推導稱為規(guī)范推導或最右推導（如果只包含終結符號或為空符號串,則為最左推導），且記作: xUy=|=xuy , 其中y Vt* 。 如果推導0=+n的每一步都是規(guī)范的,那么推導0= + n稱為規(guī)范的, 且記作: 0 =|=+ n 例如，有如下推導序列： =3 =3 =23 該推導序列就是規(guī)范推導，且可記作： =|=+23,2.4 句型和句子,推導產(chǎn)生的結果可能是句型，也可能是句子。假設文法G的識別符號為Z，記為

18、GZ，其字匯表VtVn，則句型、句子的定義如下： 1. 如果Z =*x, 且xV*, 則稱x是文法GZ的一個句型。 2. 如果Z=+x,且xVt*,則稱x是文法GZ的一個句子。,句型是從識別符號開始經(jīng)過0步或多步推導出的可由終結符號和非終結符號組成的符號串。而句子是從文法的識別符號推導出來的完全由終結符號組成的符號串。句子是特殊的句型，是完全由終結符號組成的句型。從文法的開始符號利用規(guī)則進行推導，一旦推導出句子，推導過程就不能再繼續(xù)進行，因為句子中沒有非終結符號。假設符號串是某一推導的結果，那么，是句子的充分必要條件是從到的推導長度大于等于，即 Z =+x,而不可能是Z =*x。這是因為識別符

19、號Z是非終結符號，而是終結符號串，顯然，不可能與相等，所以不可能經(jīng)過步推導就等于。,2.4 句型和句子,在句型中，有一類句型叫做規(guī)范句型，它是能用規(guī)范推導產(chǎn)生的句型。每一個句子都有一個規(guī)范推導,但并非每一個句型都有規(guī)范推導，只有那些能用規(guī)范推導產(chǎn)生的句型才是規(guī)范句型。 例如，對于例2.3中的文法，有句型“2”,其推導過程如下: = =2 其中第步推導變換的不是最右邊的非終結符號，不滿足規(guī)范推導的要求，所以句型“2”不是規(guī)范句型。 而對于句型“3”，其推導過程如下: = =3 =3 其中的每一步推導都變換的是最右邊的非終結符號，所以，句型“3”是規(guī)范句型。,2.5 語言,一個文法GZ所產(chǎn)生的所有

20、句子的集合L(GZ), 稱為文法GZ所定義的語言, 即: L(GZ)=x|x Vt* , 且Z =+ x 一個文法所定義的語言是該文法的終結符號集合Vt上的所有符號串組成的集合的一個子集,該子集中的每個符號串都可從識別符號開始經(jīng)過至少一步推導出來，即: L(GZ) Vt* 例如，對例2.1的文法G，其語言只有下面4個句子： the monkey ate the banana the banana ate the monkey the monkey ate the monkey the banana ate the banana 而例2.3中的文法，其語言是所有無符號整數(shù)，句子是無窮的。 文法和

21、語言有如下關系： 1)給定一個文法,就能從結構上唯一的確定其語言,即: GL(G) 2)給定一種語言,能確定其文法,但不唯一,即: LG1 或G2 或。,2.5 語言,例例如 ，對例2.3的文法G，其語言為所有無符號整數(shù)組成的集合，即： L(G)= Vt+ 它是包括允許以“0”開頭的所有正整數(shù)。 例2.4，已知文法GZ為： 1)ZaZb 2)Zab 或寫成 Z aZb| ab 求該文法確定的語言。 解：從識別符號開始推導，反復用規(guī)則1可得: Z=aZb=a2Zb2=an-1 Zbn-1 最后用規(guī)則2可得: Z=aZb=a2Zb2=an-11 Zbn-1 = anbn 所以該文法確定的語言為：L

22、(GZ)=(anbn|n1),2.5 語言,例2.5，已知語言為: L(G)=abna|n 1，構造產(chǎn)生該語言的文法。 解：根據(jù)語言的形式，可構造其文法G為: ZaBa BBb|b 還可以構造文法G1為: ZaBa BbB|b 從例2.5可看出，G與G1是 兩個不同的文法，但它們 都可以描述語言abna|n1。,如果兩個不同的文法可描述相同的語言,那么我們稱這兩個文法為等價文法。例2.5的文法G和文法G1就是等價文法。等價文法的存在，對編譯技術的實現(xiàn)有很大幫助，使我們能在不改變文法所確定的語言前提下，為了某種目的而改寫文法。,2.6遞歸規(guī)則與遞歸文法,2.6.1遞歸規(guī)則 遞歸規(guī)則是指那些在規(guī)則

23、的右部含有與規(guī)則左部相同符號的規(guī)則。 例如：U:=xUy，右部含有與規(guī)則左部相同符號U，那么就是遞歸規(guī)則。 如果這個相同的符號出現(xiàn)在右部的最左端，則為左遞歸規(guī)則。 如 U:=Uy 如果這個相同的符號出現(xiàn)在右部的最右端，則為右遞歸規(guī)則。如 U:=xU,給定了文法，就確定了語言。再看例2.1和例2.3中的文法，發(fā)現(xiàn)例2.1文法只產(chǎn)生兩個句子，而例2.3的文法產(chǎn)生的句子卻有無數(shù)個。句子的個數(shù)是有窮還是無窮取決于文法是否是遞歸的。,2.6.2遞歸文法,若文法中至少包含一條遞歸規(guī)則,則稱文法是直接遞歸的。顯然，例2.3中的文法就是直接遞歸文法。 有些文法，表面看上去沒有遞歸規(guī)則，但經(jīng)過幾步推導，也能造成

24、文法的遞歸性，則稱為間接遞歸。 例如，有文法為: U:=Vx ， V:=Uy|v 表面上看，該文法的每條規(guī)則都不是遞歸規(guī)則，但有推導過程U=Vx=Uyx，所以該文法為間接遞歸文法。 對文法中的任一非終結符號,若能建立一個推導過程,推導所得的符號串中有出現(xiàn)了該非終結符號,則稱文法是遞歸的;否則就是無遞歸的。遞歸文法使我們能用有窮的文法刻畫無窮的語言。,2.6.2遞歸文法,例如，有文法GS: S:=aB|Bb，B:=a|b，該文法產(chǎn)生的語言為L(GS)=aa,ab,ba,bb，只有個句子，因為該文法不是遞歸的。例2.1的文法所描述的語言只有兩個句子，也是因為它不是遞歸文法。而文法G有遞歸規(guī)則,屬于

25、遞歸文法，所以它所描述的語言為所有無符號整數(shù)，是無窮的。 例2.6 判定如下文法所描述的語言是否是有窮的。 ZaBa BbB|b 解：因為文法中的第二條規(guī)則BbB|b是遞歸規(guī)則，所以該文法描述的語言是無窮的。該文法描述的語言為abna|n1。,2.7 短語、簡單短語和句柄,短語、簡單短語和句柄在分析中有著重要的作用，后面介紹自底向上的語法分析時就可看到如何找句柄是非常關鍵的。短語是句型的子串，是在句型的推導過程中能由某個非終結符號推導出的子串，而簡單短語則是能由某個非終結符號直接推導出的子串。它們的形式定義如下： 1. 短語：設GZ是一文法, w=xuy是一句型,如果有 Z=*xUy 且U=+

26、u , 其中UVn , uV+，那么,我們稱u是一個相對于非終結符號U的句型w的短語。 2.簡單短語：若有 Z=*xUy 且U=u，那么,我們稱u是一個相對于非終結符號U的句型w的簡單短語。 3.句柄：任一句型的最左簡單短語稱為該句型句柄。,2.7 短語、簡單短語和句柄,例2.7 對于文法G, 確定句型1的短語、簡單短語和句柄。 解：首先構造句型1的推導過程如下： = = =1 1)由于 =*,而 =+1, 對照定義，子串1是由非終結符號推出的，所以是相對的短語。 2) 由于=*,而=+數(shù)字串1,所以子串1是相對的短語。 3) 由于 =*,而=1，且1是由非終結符號直接推出的，所以子串1是相對

27、的短語,而且是簡單短語。 在句型1中,只有一個簡單短語1,所以它就是該句型的句柄。,2.8 語法樹,推導過程可用圖來表示，這就是語法樹，也叫推導樹。語法樹是一棵有序有向樹，每個節(jié)點都有標記。根節(jié)點代表文法的識別符號；每個內部節(jié)點（非葉節(jié)點）表示一個非終結符號，其子節(jié)點由這個非終結符號在這次推導中所用產(chǎn)生式的右部各個符號代表的節(jié)點組成；每個末端節(jié)點（葉節(jié)點）代表終結符號或非終結符號，它們從左向右排列起來，構成句型。如果葉節(jié)點都是終結符號，則從左向右構成句子。推導過程不同，生成語法樹的過程也不同，但最終生成的語法樹是相同的。,例2.8 根據(jù)如下推導過程構造語法樹。 = = =3 =3 =23 =2

28、3 =123,解：構造語法樹如圖2.1所示。,數(shù)字串,圖2.1 語法樹,2.9 子樹與短語,語法樹的子樹是由該樹的某個節(jié)點（子樹的根）連同它所有的后裔構成。子樹與短語一一對應。要找一個句型的短語，可先畫出該句型的語法樹。若句型中某些符號按從左到右的順序組成某個子樹的末端節(jié)點，那么由這些末端節(jié)點組成的符號串，就是相對于子樹根的短語。判明語法樹中的每棵子樹，那么每棵子樹的末端節(jié)點自左向右組成的符號串，就是相對于子樹根符號的短語。原則上語法樹中有多少棵子樹，就有多少個短語,例2.8 根據(jù)文法G，找句子123的短語、簡單短語和句柄。 解：首先畫出產(chǎn)生句子123的語法樹，見圖2.1。該語法樹共有7棵子樹

29、。 子樹1：樹根，末端節(jié)點1、2、3，短語為123 子樹2：樹根，末端節(jié)點1、2、3，短語為123 子樹3：樹根，末端節(jié)點1、2，短語為12 子樹4：樹根，末端節(jié)點1，短語為1 子樹5：樹根，末端節(jié)點1，短語為1，且為簡單短語、句柄 子樹6：樹根，末端節(jié)點2，短語為2，且為簡單短語 子樹7：樹根，末端節(jié)點3，短語為3，且為簡單短語,在這7個子樹中，只有子樹5、6、7的根節(jié)點與末端節(jié)點都是父子關系，所以這幾個子樹的末端節(jié)點形成的短語1、2、3都是簡單短語。而子樹5位于其中的最左端，所以短語1還是句柄。,2.10 由樹構造推導過程,根據(jù)已有的語法樹，即可從上而下、也可從下到上建立推導。如果按從上而

30、下的方式建立推導，則從樹根開始由上而下逐層地用子節(jié)點代替父節(jié)點。當一層中有兩棵以上子樹根時，原則上先選那一棵樹根替換都可以，而每步都對最右邊的樹根符號替換，則構造出的推導是規(guī)范推導（最右推導）。 我們還可以由下而上逐層地修剪子樹末端節(jié)點來建立推導。當有兩棵以上子樹時，原則上修剪那一棵都可以，如果每次總是修剪最左邊的子樹，即相當于每步都對歸約句型的句柄歸約，則稱為“最左歸約”或“規(guī)范歸約”。規(guī)范推導（最右推導）與規(guī)范歸約（最左歸約）互為逆過程。,例2.9，對圖2.1所示的語法樹，自底向上逐層地修剪子樹末端節(jié)點來建立推導。 解：語法樹的末端節(jié)點形成的符號串為123，句柄 1，歸約為數(shù)字 句型23，

31、句柄 ，歸約為 = = = 3 = 3 = 23=23=123,2.11 文法的二義性,算術表達式的運算規(guī)則是乘除高于加減，if語句規(guī)定else就近配對，為什么呢？這是為了解決文法的二義性問題。前面我們介紹語法樹時說過，推導過程不同，生成語法樹的過程也不同，但最終生成的語法樹是相同的，這是在文法沒有二義的條件下才成立。如果一個文法所定義的句子中有某個句子或句型，它存在兩棵不同的語法樹，那么這個句子或句型是二義性的，該文法是二義性文法。,例如2.9，有文法GE：E= E+E | E*E |（E）| i，分析該文法是否為二義性文法。 解：為了判斷該文法是否為二義性文法，我們找一個句子i+i*i，如

32、果能夠構造出兩個不同的語法樹，則說明該文法是二義性文法。下面兩個圖是為句子i+i*i構造的兩棵語法樹，如圖2.2(a)、(b)所示。由于這兩棵語法樹不同，所以可以肯定文法GE 是二義性文法。,2.11 文法的二義性,圖2.2(a) 語法樹1 圖2.2(b) 語法樹2,二義性產(chǎn)生的后果會導致分析結果不同，導致對句子的理解不同。 在圖2.2(a) 語法樹1中，根據(jù)規(guī)范歸約構造的推導過程為： E=E+E=E+E*E=E+E*i=E+i*i=i+i*i 在圖2.2(b) 語法樹1中，根據(jù)規(guī)范歸約構造的推導過程為： E=E*E=E*i=E+E*i=E+i*i=i+i*i 由于圖2.2(a)語法樹1中的*

33、先作為句柄歸約，可理解成*優(yōu)先于+進行運算，而圖2.2(b)語法樹2中的+先作為句柄歸約，表示+優(yōu)先于*進行運算。由于文法的二義性會造成不同的分析結果，所以算術表達式規(guī)定乘除高于加減，從而避免二義性。,2.11 文法的二義性,程序設計語言中的嵌套IF語句都要求ELSE與最近的IF配對，也是因為IF語句的文法存在二義性。 例2.10，IF語句文法如下： = IFTHEN |IFTHENELSE | 說明該文法是二義性文法。 解：假設有一個IF語句嵌套的句型為： IFTHEN IFTHENELSE 根據(jù)文法可構造兩棵語法樹如圖2.3(a)和圖2.3(b)所示：,2.11 文法的二義性,圖2.3(a

34、) IF語句語法樹1,圖2.3(b) IF語句語法樹2,由于這兩棵語法樹不同，所以該文法是二義性文法。圖2.3(a) IF語句的語法樹意味著ELSE和第2個THEN配對（就近配對），而圖2.3(b) IF語句的語法樹表示ELSE和第1個THEN配對。,2.11 文法的二義性,文法的二義性是不可判定的，即不存在一種算法，它能夠在有限步內確切地判定一個文法是否是二義性的。但我們常常能找到一些句型，通過構造不同的語法樹來判定文法的二義性，而且還能找到一些十分簡單、并且不瑣碎的條件，當文法滿足這些條件時，就使我們確信文法是無二義性的。這些條件是無二義性的充分條件，不是必要條件。如在IF語句中，要求EL

35、SE與最近的IF配對，在算術表達式中，規(guī)定乘除高于加減，就避免了其二義性。有時，我們還可以把一個二義性文法變換成一個等價的、無二義性文法。,例2.11，改寫文法GE： E= E+E | E*E |（E）| i，使其無二義性。 解：新添非終結符號T和F，將文法寫成： E= T |E+T，T=F |T*F，F(xiàn)= (E) | i 這樣，就避免了二義性。用改寫后的文法給出句i+i*i的語法樹如圖2.4所示。此時的語法樹是唯一的。,圖2.4 語法樹,2.12 有關文法的實用限制,實用限制就是從實用的觀點出發(fā)，對文法做一些必要的限制。首先，文法不能是二義性的，這是一種對文法的實用限制。另外，還有下面列出的

36、一些限制條件： 1) 不能有U=U這樣的有害規(guī)則。 2) 不能有多余規(guī)則：一是推導中始終用不到的規(guī)則。二是一旦使用某規(guī)則后無法推出終結符號的規(guī)則。 檢查有害規(guī)則比較容易，而要檢查多余規(guī)則，則要檢查文法中每一條規(guī)則左部的每個非終結符號U是否滿足下述兩個條件： 1) U必須在某個句型中出現(xiàn)，即有：Z=*xUy 2) 必須能夠從U推導出終結符號串，即U=+t，tVt* 不滿足這兩個條件的規(guī)則就是多余規(guī)則。,2.12 有關文法的實用限制,例2.13，有文法：Z=Aa，A=Ca|Bb，B=Ba|a，C=Cb ，D=b， 去掉有害規(guī)則和多余規(guī)則。 解：該文法中，由于非終結符號D不出現(xiàn)任何規(guī)則的右部且D不是

37、開始符號，所以在句子的推導中不可能用到規(guī)則D=b，因此是多余規(guī)則，應該去掉。另外，規(guī)則C=Cb也是一條多余規(guī)則，因為一旦使用了這條規(guī)則以后，將使推導無窮地進行下去，即C=Cb=Cbb=Cbbb,無法推出終結符號串。而規(guī)則A=Ca因為會產(chǎn)生C，所以也要去掉。最后得到的文法為： Z=Aa A=Bb B=Ba|a 從上例可看出，文法中有的多余規(guī)則對文法描述的語言集合 不產(chǎn)生影響，如上例中的D=b規(guī)則，是名副其實的多余規(guī)則。而有的多余規(guī)則會導致不能最終產(chǎn)生終結符號串的錯誤，因此，檢查并去掉這種多余規(guī)則也是必須的。,2.13文法和語言分類,著名的語言學家喬姆斯基在1956年對形式語言進行了定義。他把文法定義為四元組： G=（Vn，Vt，P，Z） 其中：Vn為非終結符號集合 ， Vt為終結符號集合且VtV， P為有窮規(guī)則集合， Z識別符號，且ZVn。 文法所描述的語言為： L（G）=x|xVt+，Z= + x 根據(jù)文法中的規(guī)則的形式，可定義如下四類文法和相應的四種形式語言：,2.13文法和語言分類,1、 0型文法 若文法中有如下形式的規(guī)則： ，其中 V+