編譯原理與技術(shù)講義 第3章 程序語(yǔ)言的語(yǔ)法描述

1、編譯原理與技術(shù)第3章 程序語(yǔ)言的語(yǔ)法描述 青島大學(xué)信息工程學(xué)院主要內(nèi)容文法和語(yǔ)言文法的分類 文法的等價(jià)變換語(yǔ)法分析概述 編譯原理與技術(shù)2程序語(yǔ)言的語(yǔ)法描述 程序語(yǔ)言的定義 程序語(yǔ)言通常是一個(gè)能完整、準(zhǔn)確和規(guī)則地表達(dá)人們的意圖，并用以指揮或控制計(jì)算機(jī)工作的“符號(hào)系統(tǒng)”。它完整的定義包括語(yǔ)法、語(yǔ)義及語(yǔ)用三個(gè)方面。 一個(gè)程序語(yǔ)言的語(yǔ)法是指這樣一組規(guī)則，使用它可以形成和產(chǎn)生一個(gè)合適的程序。這些規(guī)則一部分稱為詞法規(guī)則，另一部分稱為語(yǔ)法規(guī)則（或產(chǎn)生規(guī)則）。 編譯原理與技術(shù)3程序語(yǔ)言的語(yǔ)法描述 一個(gè)程序語(yǔ)言的語(yǔ)義是指這樣一組規(guī)則，使用它可以定義一個(gè)程序的意義。靜態(tài)語(yǔ)義是一系列限定規(guī)則，確定哪些合乎語(yǔ)法的程序

2、是合適的；動(dòng)態(tài)語(yǔ)義也稱作運(yùn)行語(yǔ)義或執(zhí)行語(yǔ)義，表明程序要做些什么，要計(jì)算什么。語(yǔ)用表示語(yǔ)言符號(hào)及其使用者之間的關(guān)系，涉及符號(hào)的來(lái)源、使用和影響。編譯原理與技術(shù)43.1 文法和語(yǔ)言文法的形式定義 定義3.1: 定義四元組G=(VN，VT，P，S)是一個(gè)文法。其中VN , VT和 P都是非空有限集合，分別稱為非終結(jié)符號(hào)集合、終結(jié)符號(hào)集合及產(chǎn)生式集合。S稱作識(shí)別符號(hào)或開(kāi)始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 VN和VT不含公共元素，即VNVT = 。通常用V表示VNVT，稱為文法G的字母表。 編譯原理與技術(shù)53.1 文法和語(yǔ)言 例3.1：文法G1=(VN, VT, P, S)，其

3、中VN =S，VT =0, 1，P=S0S1, S01。 該文法只有一個(gè)非終結(jié)符S，有兩個(gè)終結(jié)符0和1，有兩條產(chǎn)生式，開(kāi)始符號(hào)是S。 很多時(shí)候，不用將文法G的四元組顯式地表示出來(lái)，而只將產(chǎn)生式寫(xiě)出。一般約定，第一條產(chǎn)生式的左部是開(kāi)始符號(hào)，用尖括號(hào)括起來(lái)的是非終結(jié)符號(hào)，不用尖括號(hào)括起來(lái)的是終結(jié)符號(hào)，或者用大寫(xiě)字母表示非終結(jié)符號(hào)，小寫(xiě)字母表示終結(jié)符號(hào)。另外也有一種習(xí)慣寫(xiě)法，將G寫(xiě)成GS，其中S是開(kāi)始符號(hào)。因此，例3.1還可以寫(xiě)成：G：S0S1 或 GS：S0S1 S01 S01 編譯原理與技術(shù)63.1 文法和語(yǔ)言 有時(shí)，為書(shū)寫(xiě)簡(jiǎn)潔，常把相同左部的產(chǎn)生式，形如A1,A2,An，縮寫(xiě)為：A1|2|n。

4、這里的元符號(hào) | 讀做“或”。 如，例3.1的產(chǎn)生式可以寫(xiě)成S 0S1 | 01。 注意元符號(hào)和源符號(hào)的區(qū)別： 文法中使用的元符號(hào)或 =表示左部由右部定義，| 表示定義同一個(gè)左部的幾個(gè)可選擇的右部。而源符號(hào)是指文法定義的語(yǔ)言中的符號(hào)，全部由文法的終結(jié)符構(gòu)成。 編譯原理與技術(shù)73.1 文法和語(yǔ)言 例3.2：文法G2=(VN, VT, P, S )，其中 VN =標(biāo)識(shí)符, 字母, 數(shù)字， VT =a, b, c, , x, y, z, 0, 1, , 9 ， P =標(biāo)識(shí)符字母|標(biāo)識(shí)符字母 |標(biāo)識(shí)符數(shù)字 字母a | b | | z 數(shù)字0 | 1 | |9 S =標(biāo)識(shí)符，這里使用尖括號(hào) 和 括起非終

5、結(jié)符。編譯原理與技術(shù)83.1 文法和語(yǔ)言例3.3：一個(gè)文法的幾種寫(xiě)法： G=( S, A, a, b, P, S ) 其中P= SaAb, Aab, AaAb, A G: SaAb Aab AaAb A GS: Aab AaAb A SaAb GS: Aab |aAb | SaAb編譯原理與技術(shù)93.1 文法和語(yǔ)言推導(dǎo)與歸約 定義3.2: 設(shè)是文法G=(VN，VT，P，S)的產(chǎn)生式，和是V*中的任意符號(hào)。若有符號(hào)串v，w滿足：v = ，w = ，則說(shuō)v直接產(chǎn)生w，或者說(shuō)，w是v的直接推導(dǎo)。記作vw。也可以說(shuō)w直接歸約到v。歸約是推導(dǎo)的逆過(guò)程。編譯原理與技術(shù)103.1 文法和語(yǔ)言對(duì)例3.1文法G

6、，可以給出直接推導(dǎo)的一些例子如下： v = 0S1，w = 0011， 直接推導(dǎo)：0S10011， 使用的規(guī)則：S01，這里 =0， =1。 v = S，w = 0S1， 直接推導(dǎo)：S0S1， 使用的規(guī)則：S0S1，這里 = ， = 。 v = 0S1，w = 00S11， 直接推導(dǎo)：0S100S11， 使用的規(guī)則：S 0S1，這里 = 0， =1。編譯原理與技術(shù)113.1 文法和語(yǔ)言 對(duì)例3.2文法G，直接推導(dǎo)的例子有： v =標(biāo)識(shí)符，w =標(biāo)識(shí)符字母， 直接推導(dǎo)：標(biāo)識(shí)符標(biāo)識(shí)符字母， 使用的規(guī)則：標(biāo)識(shí)符標(biāo)識(shí)符字母， 這里 = = 。 v =標(biāo)識(shí)符字母數(shù)字， w =字母字母數(shù)字， 直接推導(dǎo)：標(biāo)

7、識(shí)符字母數(shù)字 字母字母數(shù)字， 使用的規(guī)則：標(biāo)識(shí)符字母。 這里 = ， =字母數(shù)字。 v = abc數(shù)字，w = abc5， 直接推導(dǎo)：abc 數(shù)字 abc5, 使用的規(guī)則：數(shù)字5，這里 = abc, = 。 編譯原理與技術(shù)12 定義3.3: 如果存在直接推導(dǎo)的序列：v = w0 w1 w2 wn= w, (n0)，則稱v推導(dǎo)出w，推導(dǎo)長(zhǎng)度為n?；蛘叻Qw歸約到v。記作v w。若有v w，或v = w，則記作v w。 定義3.19: 設(shè)GS是一文法，如果符號(hào)串x是從開(kāi)始符號(hào)推導(dǎo)出來(lái)的，即有S x，則稱x是文法GS的句型。若x僅由終結(jié)符號(hào)組成，即S x，xVT*，則稱x為GS的句子。 3.1 文法和

8、語(yǔ)言編譯原理與技術(shù)133.1 文法和語(yǔ)言對(duì)例3.1文法，存在直接推導(dǎo)序列v = 0S100S11 000S111 00001111= w，即0S1 00001111，也可記作0S1 00001111。對(duì)例3.2文法，存在直接推導(dǎo)序列 v =標(biāo)識(shí)符 標(biāo)識(shí)符數(shù)字 字母數(shù)字 x數(shù)字 x1= w，即標(biāo)識(shí)符 x1，也可記作標(biāo)識(shí)符 x1。 S, 0S1, 000111都是例3.1的文法G的句型，其中000111是G的句子。標(biāo)識(shí)符字母, 字母數(shù)字, a1等都是例3.2文法G的句型，其中a1是G的句子。 編譯原理與技術(shù)143.1 文法和語(yǔ)言例3.4：終結(jié)符號(hào)串(i*i+i)是文法 EE+E | E*E | (

9、E) | i 的一個(gè)句子。因?yàn)橛袕拈_(kāi)始符號(hào)E至終結(jié)符號(hào)串(i*i+i ) 的一個(gè)推導(dǎo)：E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i ) 而E, (E), (E*E+E)等是文法的句型。 編譯原理與技術(shù)153.1 文法和語(yǔ)言 定義3.4: 若推導(dǎo)過(guò)程中每一步都是替換最左（右）邊的非終結(jié)符，則稱該推導(dǎo)為最左（右）推導(dǎo)。句型的最右推導(dǎo)稱為規(guī)范推導(dǎo)，其逆過(guò)程最左歸約稱為規(guī)范歸約。 例3.5：文法GS: SAB AA0|1B B0|S1 給出句子101001的最左和最右推導(dǎo)。 解：最左推導(dǎo)： S AB 1B B10B 10S1 10AB1 101BB1 1010B

10、1 101001 最右推導(dǎo)： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001 編譯原理與技術(shù)163.1 文法和語(yǔ)言 文法產(chǎn)生的語(yǔ)言 定義3.5: 文法G的全部句子組成的集合稱為G產(chǎn)生的語(yǔ)言，記為L(zhǎng)(G)，即 L(G)= x | S x，其中S為開(kāi)始符號(hào)，且xVT* 例3.1的文法G1 的語(yǔ)言是L(G)=0n1n | n1 。例3.2的文法G2的句子是字母打頭的、由字母和數(shù)字組成的符號(hào)串，也就是程序設(shè)計(jì)語(yǔ)言中用于表示名字的標(biāo)識(shí)符，因此產(chǎn)生的語(yǔ)言就是所有標(biāo)識(shí)符的集合。 編譯原理與技術(shù)173.1 文法和語(yǔ)言 例3.6：考慮文法G1: S bA A aA | a

11、 求它所定義的語(yǔ)言。 解：從開(kāi)始符S出發(fā)，可以推出如下句子： SbA ba SbA baA baa SbA baA baaA baaa 因此，文法G1產(chǎn)生以b開(kāi)頭、后面跟一個(gè)或多個(gè)a的所有符號(hào)串， 從而L(G1)=ban | n1。編譯原理與技術(shù)183.1 文法和語(yǔ)言 例3.7：設(shè)有文法G2: S P | aPb P ba | bQa Q ab 求語(yǔ)言L(G2)。 解：從開(kāi)始符S出發(fā)，可以推出如下句子： SPba SP bQa baba SaPbabab SaPbabQabababab 文法G2共能產(chǎn)生4個(gè)句子，因此L(G2)=ba, baba, abab, ababab 編譯原理與技術(shù)193

12、.1 文法和語(yǔ)言 例3.8：設(shè)G3=(VN，VT，P，S)， VN=S,B,E， VT=a,b,e，P由下列產(chǎn)生式組成： (1) SaSBE (2) SaBE (3) EBBE (4) aBab (5) bBbb (6) bEbe (7) eEee 求語(yǔ)言L(G3)。 解： L(G3)=anbnen|n1。 編譯原理與技術(shù)203.1 文法和語(yǔ)言語(yǔ)言的驗(yàn)證 一般來(lái)說(shuō)，對(duì)“文法G產(chǎn)生語(yǔ)言L”的證明包括兩部分：（1）證明由G產(chǎn)生的每個(gè)字符串都在L中。 （2）證明L中的每個(gè)字符串都能由G產(chǎn)生。 編譯原理與技術(shù)213.1 文法和語(yǔ)言 例3.9：驗(yàn)證文法G1 : S (S ) S | 產(chǎn)生語(yǔ)言L(G1)

13、= 配對(duì)的括號(hào)串的集合。 證明：（1）按推導(dǎo)步數(shù)進(jìn)行歸納證明：推出的是配對(duì)括號(hào)串 歸納基礎(chǔ)： S 歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對(duì)的括號(hào)串 歸納步驟：n步的最左推導(dǎo)如下S (S )S (x) S (x) y 其中x、y是配對(duì)的括號(hào)串，從而(x) y也是配對(duì)的 括號(hào)串，即n步的推導(dǎo)也產(chǎn)生配對(duì)的括號(hào)串。 因此，由G1產(chǎn)生的每個(gè)字符串都是配對(duì)的括號(hào)串都在 L(G1)中。 編譯原理與技術(shù)223.1 文法和語(yǔ)言（2）按符號(hào)串的長(zhǎng)度進(jìn)行歸納證明：配對(duì)括號(hào)串可由S推出 歸納基礎(chǔ)： S 歸納假設(shè)：長(zhǎng)度小于2n的配對(duì)括號(hào)串都可以從S推導(dǎo)出來(lái) 歸納步驟：考慮長(zhǎng)度為2n(n1)的w = (x) y，其中w、x、y

14、 均為配對(duì)括號(hào)串，有S (S )S (x) S (x) y 即長(zhǎng)度為2n的配對(duì)括號(hào)串都可以從S推導(dǎo)出來(lái)。 因此，L(G1)中的每個(gè)字符串都能由G1產(chǎn)生。 由（1）、（2）可知，文法G : S (S ) S | 產(chǎn)生語(yǔ)言L(G1) = 配對(duì)的括號(hào)串的集合。 編譯原理與技術(shù)23例3.10：驗(yàn)證文法G2: EE + aa 產(chǎn)生的語(yǔ)言是所有由若干個(gè)“+”分隔開(kāi)的a 組成的符號(hào)串，即L(G2) = a, a + a, a + a + a, a + a + a + a, . . . 證明：(1) 按a 的數(shù)目n歸納證明：每個(gè)符號(hào)串a(chǎn) + a + . . .+ a L (G2)。歸納基礎(chǔ)：因?yàn)镋a，所以Ea

15、， aL(G2)。即n=1時(shí)成立。歸納假設(shè)：假設(shè)s = a + a + . + aL (G2)，且有n-1個(gè)a，則存在 推導(dǎo)E s。 歸納步驟：使用產(chǎn)生式EE + a一次，再利用歸納假設(shè)可得推 導(dǎo)：E E + a s + a。因此，s + aL (G2)，其中 有n個(gè)a。 因此，所有形如a + a + . . .+ a的符號(hào)串在L (G2)中。 3.1 文法和語(yǔ)言編譯原理與技術(shù)24(2) 按推導(dǎo)的長(zhǎng)度n歸納證明：sL(G2)必滿足格式a + a + . + a。歸納基礎(chǔ)：推導(dǎo)的長(zhǎng)度為1時(shí)，只能為E a，而a是滿足格式。歸納假設(shè)：長(zhǎng)度為n-1的推導(dǎo)能推出滿足格式a + a + . + a。 歸納

16、步驟：考慮長(zhǎng)度為n1的推導(dǎo)E s。因?yàn)閚 1，因此第一步 推導(dǎo)必然使用產(chǎn)生式EE + a，從而E E + a s+ a = s ， 其中推導(dǎo)E s 長(zhǎng)度為n-1，由歸納假設(shè)可知s 滿足格式。 因此，s=s+ a 也滿足格式a + a + . + a。因此，L(G2)中的所有符號(hào)串都滿足格式a + a + . + a。 由（1）、（2）可知，文法G2 : EE + aa產(chǎn)生語(yǔ)言L(G2) = 配對(duì)的括號(hào)串的集合。 3.1 文法和語(yǔ)言編譯原理與技術(shù)253.1 文法和語(yǔ)言語(yǔ)言的文法表達(dá) 由已知語(yǔ)言求其文法描述，實(shí)際上就是討論語(yǔ)言中的句子，根據(jù)句子的特點(diǎn)利用層次分析的方法，構(gòu)造相應(yīng)的文法。構(gòu)造過(guò)程中經(jīng)

17、常會(huì)用到下面形式的產(chǎn)生式。右遞歸（right recursive） 產(chǎn)生式： A aA | a 產(chǎn)生a+ ，A aA | 產(chǎn)生a* 左遞歸（left recursive） 產(chǎn)生式： A Aa | a產(chǎn)生a+ ，A Aa |產(chǎn)生a* 編譯原理與技術(shù)263.1 文法和語(yǔ)言 例3.11：試構(gòu)造語(yǔ)言L1=anbnci | n1, i0=ab, aabb, , abc, aabbc, , abcc, aabbcc, 的文法。 解：L1中符號(hào)串的特點(diǎn)是：串中含一個(gè)或多個(gè)a并置，可以看作含有a+形式；串中含一個(gè)或多個(gè)b并置，可以看作含有b+形式；串中含有0個(gè)或多個(gè)c，可以看作是c*形式。因此，該語(yǔ)言可以看作

18、是a+、b+與c*的連接。 使用A aA | a 可以產(chǎn)生a+，使用B bB | b 可以產(chǎn)生b+，使用C cC | 可以產(chǎn)生c*。而要表示它們的連接，只需將非終結(jié)符A、B、C連接起來(lái)即可。 因此，滿足要求的文法為G(Z): Z ABC A aA | a B bB | b C cC | 編譯原理與技術(shù)273.1 文法和語(yǔ)言也可以使用左遞歸產(chǎn)生式，得到滿足要求的另一個(gè)文法G(Z): Z ABC A Aa | a B Bb | b C cC | 實(shí)際上，a+與b+的產(chǎn)生過(guò)程完全一致，可以將產(chǎn)生它們的產(chǎn)生式合并為A aAb | ab。則得到滿足要求的另一個(gè)文法G(Z): Z AB A aAb | a

19、b B cB | 由此可以看出，已知語(yǔ)言求文法，文法不唯一，可以有不同的表達(dá)方法。 編譯原理與技術(shù)283.1 文法和語(yǔ)言 例3.12：已知語(yǔ)言L2=x | xa,b,c*, 且x是回文字=, aa, bb, cc, aba, aca, bab, bcb, cac, cbc, aabaa, ，寫(xiě)出該語(yǔ)言的文法。 解：L2中符號(hào)串的特點(diǎn)是：串中若包含符號(hào)，則以a開(kāi)頭必以a結(jié)束，以b開(kāi)頭必以b結(jié)束，串中符號(hào)對(duì)稱出現(xiàn)?？梢栽O(shè)計(jì)文法為 G(Z): Z aZa | bZb | cZc | a | b | c | 。 編譯原理與技術(shù)293.1 文法和語(yǔ)言分析樹(shù)與語(yǔ)法樹(shù) 分析樹(shù)（parse tree） 定義3

20、.6: 語(yǔ)法分析樹(shù)用來(lái)描述句型的結(jié)構(gòu)，是句型推導(dǎo)的一種樹(shù)型表示，簡(jiǎn)稱分析樹(shù)。 給定文法G=(VN, VT, P, S)，對(duì)于G的任何句型都能構(gòu)造相應(yīng)的分析樹(shù)，這棵樹(shù)滿足下列條件： 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記。根結(jié)點(diǎn)的標(biāo)記是開(kāi)始符號(hào)S；非葉結(jié)點(diǎn) 的標(biāo)記是非終結(jié)符；葉結(jié)點(diǎn)的標(biāo)記是終結(jié)符或非終結(jié)符或。 如果一個(gè)非葉結(jié)點(diǎn)A有n個(gè)兒子結(jié)點(diǎn)，從左到右標(biāo)記為A1，A2， ，Ak，則AA1A2Ak一定是P中的一個(gè)產(chǎn)生式。 編譯原理與技術(shù)303.1 文法和語(yǔ)言例3.13：文法GS: S aAS | SA SbA | SS | ba 其句子aabbaa的語(yǔ)法分析樹(shù)如圖3.1所示。 圖3.1 aabbaa的語(yǔ)法分析樹(shù) 編

21、譯原理與技術(shù)313.1 文法和語(yǔ)言 語(yǔ)法樹(shù)表示了在推導(dǎo)過(guò)程中使用了哪個(gè)產(chǎn)生式和用在哪個(gè)非終結(jié)符上，它并沒(méi)有表明施用產(chǎn)生式的順序。 比如例3.13中句子aabbaa的推導(dǎo)過(guò)程可以列舉3個(gè)： 推導(dǎo)過(guò)程1：S aAS aAa aSbAa aSbbaa aabbaa 推導(dǎo)過(guò)程2：S aAS aSbAS aabAS aabbaS aabbaa 推導(dǎo)過(guò)程3：S aAS aSbAS aSbAa aabAa aabbaa 編譯原理與技術(shù)323.1 文法和語(yǔ)言語(yǔ)法樹(shù)（syntax tree） 定義3.7: 抽象語(yǔ)法樹(shù)用來(lái)表示程序?qū)哟谓Y(jié)構(gòu)，它把分析樹(shù)中對(duì)語(yǔ)義無(wú)關(guān)緊要的成分去掉，是分析樹(shù)的抽象形式，簡(jiǎn)稱語(yǔ)法樹(shù)，也稱

22、語(yǔ)法結(jié)構(gòu)樹(shù)或結(jié)構(gòu)樹(shù)。 語(yǔ)法樹(shù)可看作分析樹(shù)的濃縮，而分析樹(shù)可看成具體語(yǔ)法樹(shù)。 編譯原理與技術(shù)333.1 文法和語(yǔ)言 例3.14：條件語(yǔ)句產(chǎn)生式S if B-expr then S1 else S2的抽象語(yǔ)法樹(shù)與語(yǔ)法分析樹(shù)如圖3.2所示。(a) 語(yǔ)法樹(shù) (b) 分析樹(shù)圖3.2條件語(yǔ)句的語(yǔ)法樹(shù)與分析樹(shù) 抽象語(yǔ)法樹(shù)中，操作符和關(guān)鍵字都不作為葉結(jié)點(diǎn)出現(xiàn)，而是作為內(nèi)部結(jié)點(diǎn)。 編譯原理與技術(shù)343.1 文法和語(yǔ)言 例3.15：賦值語(yǔ)句產(chǎn)生式為賦值語(yǔ)句 i := E， 表達(dá)式的產(chǎn)生式為 E E+E | E*E | -E | id， 則a := b* -c + b * -c的語(yǔ)法樹(shù)與分析樹(shù)如圖3.3所示。(a)

23、 語(yǔ)法樹(shù) (b) 分析樹(shù)圖3.3 賦值語(yǔ)句的語(yǔ)法樹(shù)與分析樹(shù) 編譯原理與技術(shù)353.2 文法和語(yǔ)言文法的二義性 二義性文法 定義3.8: 給定一個(gè)文法G，如果其產(chǎn)生的語(yǔ)言L(G)中存在存在某個(gè)句子對(duì)應(yīng)兩棵或兩棵以上分析樹(shù)，則稱文法G是二義性的。 或者說(shuō)，若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)或兩個(gè)以上不同的最左(最右)推導(dǎo)，則該文法是二義的。 編譯原理與技術(shù)363.1 文法和語(yǔ)言 例3.16：對(duì)于簡(jiǎn)單表達(dá)式文法GE: EE+E | E-E | E*E | E/E | (E) | i 句子i*i+i有如下兩個(gè)不同的最左推導(dǎo)，它們所對(duì)應(yīng)的分析樹(shù)如圖3.4所示。 因此該文法是二義性文法。 推導(dǎo)一：E E+

24、E E*E+E i*E+E i*i+E i*i+i 推導(dǎo)二：E E*E i*E i*E+E i*i+E i*i+i(a) 推導(dǎo)一的分析樹(shù) (b) 推導(dǎo)二的分析樹(shù)圖3.4 句子i*i+i兩棵不同的分析樹(shù) 編譯原理與技術(shù)373.1 文法和語(yǔ)言 注意文法二義性和語(yǔ)言二義性的區(qū)別： 這是兩個(gè)不同的概念，因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G，其中G是二義的，但是卻有L(G)=L(G)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)該語(yǔ)言是二義的。編譯原理與技術(shù)383.1 文法和語(yǔ)言 文法二義性的消除 方法一：設(shè)置一個(gè)規(guī)則，該規(guī)則可在每個(gè)二義性情況下指出哪一個(gè)分析樹(shù)

25、（或語(yǔ)法樹(shù)）是正確的。這樣的規(guī)則稱作消除二義性規(guī)則（disambiguating rule）。 其優(yōu)點(diǎn)為：無(wú)需修改文法（可能會(huì)很復(fù)雜）就可消除二義性； 其缺點(diǎn)為：語(yǔ)言的語(yǔ)法結(jié)構(gòu)再也不能由文法單獨(dú)提供。 方法二：將文法改變成一個(gè)強(qiáng)制正確分析樹(shù)的構(gòu)造的格式，就可以解決二義性。 編譯原理與技術(shù)393.1 文法和語(yǔ)言 為了消除例題3.16中簡(jiǎn)單表達(dá)式文法中的二義性，可以設(shè)置消除二義性規(guī)則，它建立了3個(gè)運(yùn)算相互之間的優(yōu)先關(guān)系。其標(biāo)準(zhǔn)解決辦法是給予加法和減法相同的優(yōu)先權(quán)，而乘法和除法則有高一級(jí)的優(yōu)先權(quán)， 并按慣例規(guī)定它們都服從左結(jié)合。這樣句子i*i+i相當(dāng)于(i*i)+i，它有惟一的分析樹(shù)為圖3.4(a)

26、。 編譯原理與技術(shù)403.1 文法和語(yǔ)言 現(xiàn)在來(lái)看重寫(xiě)文法以消除二義性的方法。為了處理文法中的運(yùn)算優(yōu)先權(quán)問(wèn)題，就必須把具有相同優(yōu)先權(quán)的算符歸納在一組中，并為每一種優(yōu)先權(quán)規(guī)定不同的規(guī)則。 例如，將例3.11中文法分組為EE+E | E-E | TTT*T | T/T | FF (E) | i 在這個(gè)文法中，加法和減法則被歸在E規(guī)則下，乘法和除法被歸在T規(guī)則下。由于T只能由E生成，這就意味著加法和減法在分析樹(shù)和語(yǔ)法樹(shù)中將被表現(xiàn)地“更高一些”（也就是更接近于根結(jié)點(diǎn)），因此它們的優(yōu)先權(quán)就比乘法和除法低一級(jí)。這樣將算符放在不同的優(yōu)先權(quán)級(jí)別中的辦法是在語(yǔ)法說(shuō)明中使用BNF的一個(gè)標(biāo)準(zhǔn)方法。這種分組稱作優(yōu)先級(jí)

27、聯(lián)（precedence cascade）。編譯原理與技術(shù)413.1 文法和語(yǔ)言 分組后的文法未指出算符的結(jié)合性而且仍有二義性。原因在于形如EE+E| E-E的產(chǎn)生式，它既是左遞歸又是右遞歸，若要得到符號(hào)串i+i-i，既可以先使用E+E再對(duì)第二個(gè)E使用E-E，也可以先使用E-E再對(duì)遞一個(gè)E使用E+E。解決方法是強(qiáng)制匹配一邊的遞歸，用EE+T | E-T | T代替EE+E| E-E | T，使加法和減法都服從左結(jié)合。若要使它們服從右結(jié)合，則可以改為ET+E| T-E | T。也就是說(shuō)，左遞歸規(guī)則使得它的算符在左邊結(jié)合，而右遞歸規(guī)則使得它們?cè)谟疫吔Y(jié)合。 這樣，若統(tǒng)一規(guī)定服從左結(jié)合，則例3.16中

28、文法可以修改為EE+T | E-T | TTT*F | T/F | FF (E) | i 編譯原理與技術(shù)423.1 文法和語(yǔ)言可以驗(yàn)證，該文法是一個(gè)無(wú)二義文法。句子i+i*i-i惟一的分析樹(shù)與語(yǔ)法樹(shù)如圖3.5所示。 (a) 分析樹(shù) (b) 語(yǔ)法樹(shù)圖3.5 句子i+i*i-i的分析樹(shù)與語(yǔ)法樹(shù)編譯原理與技術(shù)43 下面介紹一種確定符號(hào)優(yōu)先關(guān)系的方法，稱簡(jiǎn)單優(yōu)先關(guān)系。它規(guī)定文法G中任意兩個(gè)符號(hào)的優(yōu)先關(guān)系如下：（1）X Y，當(dāng)且僅當(dāng)有產(chǎn)生式 ABY，且有推導(dǎo) B rX及Y a。 其中A、B為非終結(jié)符，X、Y為待定優(yōu)先關(guān)系的兩個(gè)任意符號(hào)，、和為由終結(jié)符和非終結(jié)符組成的任意符號(hào)串，可以是空串。a是終結(jié)符。

29、3.1 文法和語(yǔ)言編譯原理與技術(shù)443.1 文法和語(yǔ)言懸掛else問(wèn)題 考慮下面條件語(yǔ)句的文法： statement if-stmt | other if-stmt if (exp) statement | if (exp) statement else statement exp 0 | 1 該文法是二義的，符號(hào)串if (0) if (1) other else other兩棵分析樹(shù)，如圖3.6所示。 編譯原理與技術(shù)453.1 文法和語(yǔ)言 圖3.6符號(hào)串if (0) if (1) other else other兩棵不同的分析樹(shù)（一） 編譯原理與技術(shù)463.1 文法和語(yǔ)言 圖3.6 符號(hào)串i

30、f (0) if (1) other else other兩棵不同的分析樹(shù)（二） 編譯原理與技術(shù)473.1 文法和語(yǔ)言 第一棵分析樹(shù)將else部分與第一個(gè)if語(yǔ)句結(jié)合；第二棵分析樹(shù)將else與第2個(gè)if語(yǔ)句結(jié)合。這種二義性稱作懸掛else問(wèn)題（dangling else problem)。 一般的程序語(yǔ)言中，條件語(yǔ)句的else部分總是與沒(méi)有else部分的最近的if語(yǔ)句結(jié)合。這個(gè)消除二義性的規(guī)則被稱為用于懸掛else問(wèn)題的最近嵌套規(guī)則（most closely nested rule）。 編譯原理與技術(shù)483.1 文法和語(yǔ)言 解決懸掛else二義性比處理前面的二義性困難，修改后為：stateme

31、nt matched-stmt | unmatched-stmtmatched-stmt if (exp) matched-stmt else matched-stmt | otherunmatched-stmt if (exp) statement | if (exp) matched-stmt else unmatched-stmtexp 0 | 1 if語(yǔ)句中只允許有一個(gè)matched-stmt出現(xiàn)在else之前，這樣就迫使盡可能快地匹配所有的else部分。使用消除二義性后的文法，符號(hào)串if (0) if (1) other else other的分析樹(shù)如圖3.7所示。 編譯原理與技術(shù)4

32、93.1 文法和語(yǔ)言 圖3.7 消除二義性后的分析樹(shù) 編譯原理與技術(shù)503.2 文法的分類形式語(yǔ)言的分類 Chomsky對(duì)文法中的規(guī)則施加不同限制，將文法和語(yǔ)言分為四大類：0型文法1型文法2型文法3型文法 編譯原理與技術(shù)513.2 文法的分類0型文法 定義3.9: 文法G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式形如，其中V*VNV*，V*，則G是一個(gè)0型文法。其中V= VNVT。 0型文法也稱為短語(yǔ)文法（PSG, phrase structure grammars）。由定義可知，0型文法的產(chǎn)生式左端是由終結(jié)符和非終結(jié)符組成的字符串，并且至少含有一個(gè)非終結(jié)符。產(chǎn)生式右端是由終結(jié)符和非終結(jié)符組

33、成的任意字符串。 編譯原理與技術(shù)523.2 文法的分類例3.17：文法G0S： SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 則該文法是一個(gè)0型文法，產(chǎn)生的語(yǔ)言為L(zhǎng)0=| iI+= aa, aaaa, aaaaaaaa, 由0型文法生成的語(yǔ)言稱為0型語(yǔ)言（或遞歸可枚舉語(yǔ)言）。它可由圖靈（Turing）機(jī)識(shí)別。 編譯原理與技術(shù)533.2 文法的分類1型文法 對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)，0型文法有很大的隨意性，還須加以限制。對(duì)0型文法產(chǎn)生式的形式進(jìn)一步加以限制，可以得到1型文法。 定義3.10: 文法G=(VN，VT，P，S)，如果它是0型文法，并且每個(gè)產(chǎn)生式形如1A2 1

34、2，其中1,2V*，V+，AVN，則G是一個(gè)1型文法。 1型文法也稱為上下文有關(guān)文法（CSG, context-sensitive grammars）。只有當(dāng)非終結(jié)符A的前后分別為1,2 時(shí)，才能將A替換為。即對(duì)非終結(jié)符進(jìn)行替換時(shí)，務(wù)必考慮上下文，這也是稱之為上下文有關(guān)文法的原因。并且一般不允許替換成空串。 編譯原理與技術(shù)543.2 文法的分類 1 型文法還有另一種定義形式： 定義3.11: 文法G=(VN，VT，P，S)，如果它是0型文法，并且每個(gè)產(chǎn)生式滿足|（產(chǎn)生式S例外，但S不得出現(xiàn)在任何產(chǎn)生式的右部），則G是一個(gè)1型文法。其中| 和| |分別為和的長(zhǎng)度。 由該定義可知，1型文法除了可能

35、有S外，其余產(chǎn)生式右端的符號(hào)串長(zhǎng)度大于等于左端符號(hào)串長(zhǎng)度。 上述兩種定義是等價(jià)的。即任一種形式定義的文法產(chǎn)生的語(yǔ)言都可由另一種形式定義的文法產(chǎn)生。需要注意的是，根據(jù)定義，含有產(chǎn)生式的文法不是1型文法。由于實(shí)際需要，我們將S作為1型文法的特例接受。 編譯原理與技術(shù)553.2 文法的分類例3.18：文法G1S： S | A AaABC AabC CBBC bBbb bCbc cCcc則該文法是一個(gè)1型文法，產(chǎn)生的語(yǔ)言為L(zhǎng)1=ai bi ci | i0=, abc, aabbcc, 1型文法產(chǎn)生的語(yǔ)言稱為上下文有關(guān)語(yǔ)言CSL，它可由線性限界自動(dòng)機(jī)識(shí)別。 編譯原理與技術(shù)563.2 文法的分類2型文法

36、對(duì)1型文法的產(chǎn)生式進(jìn)一步限制，可得2型文法。 定義3.12: 文法G=(VN，VT，P，S)，如果它是1型文法，并且每個(gè)產(chǎn)生式A滿足AVN，V+，（產(chǎn)生式S例外），則G是一個(gè)2型文法。 2型文法也稱為上下文無(wú)關(guān)文法（CFG, context-free grammars）。用取代非終結(jié)符A時(shí)，與A所在的上下文無(wú)關(guān)，因此取名為上下文無(wú)關(guān)文法。 由定義可知，2型文法所有產(chǎn)生式左端的符號(hào)都是單個(gè)的非終結(jié)符。除了可能有產(chǎn)生式S外，其余產(chǎn)生式右端不能是空串。 編譯原理與技術(shù)573.2 文法的分類例3.19：文法G2S： SaSb Sab 則該文法是一個(gè)2型文法，產(chǎn)生的語(yǔ)言為L(zhǎng)2=ai bi | i1=ab

37、, aabb, aaabbb, 程序設(shè)計(jì)語(yǔ)言的文法是上下文無(wú)關(guān)的，如C，Pascal。2型文法產(chǎn)生的語(yǔ)言稱為上下文無(wú)關(guān)語(yǔ)言CFL，它可由下推自動(dòng)機(jī)識(shí)別。 編譯原理與技術(shù)583.2 文法的分類3型文法 對(duì)2型文法的產(chǎn)生式進(jìn)一步限制，可得3型文法。 定義3.13: 文法G=(VN，VT，P，S)，如果它是2型文法，并且僅含有形如AaB或Aa 的產(chǎn)生式，則稱G為右線性文法。若僅含有形如ABa或Aa 的產(chǎn)生式，則稱G為左線性文法。其中A,B VN ，a VT。左線性文法和右線性文法都稱為3型文法。 3型文法也稱正規(guī)文法（RG, regular grammars）。 編譯原理與技術(shù)593.2 文法的分類

38、例3.20：文法G3S： S lA | l，A 0A | 0該文法是一個(gè)右線性文法，產(chǎn)生的語(yǔ)言為L(zhǎng)3=1 0i | i0=1, 10,100, 1000, 例3.21：文法G4S： S Bc|Sc，B Ab| Bb，A Aa|a 該文法是一個(gè)左線性文法，產(chǎn)生的語(yǔ)言為L(zhǎng)4=ai bj ck | i, j, k1例3.22：定義標(biāo)識(shí)符的3型（正規(guī)）文法為 GI: I lT | l，T lT | dT | l | d 其中l(wèi)是英文字母l，表示az中的任何一英文字母，d表示09中的任一數(shù)字。編譯原理與技術(shù)603.2 文法的分類 3型文法產(chǎn)生的語(yǔ)言稱為3型正規(guī)語(yǔ)言（或正規(guī)語(yǔ)言），它可由有限自動(dòng)機(jī)識(shí)別。正

39、規(guī)語(yǔ)言可用正規(guī)表達(dá)式表示。 四個(gè)文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是上下文無(wú)關(guān)的，每一種上下文無(wú)關(guān)文法都是上下文有關(guān)的，而每一種上下文有關(guān)文法都是0型文法。它們之間是逐級(jí)“包含”的關(guān)系，由四種文法產(chǎn)生的語(yǔ)言也是逐級(jí)“包含”的關(guān)系。 編譯原理與技術(shù)613.2 文法的分類上下文無(wú)關(guān)文法 上下文無(wú)關(guān)文法擁有足夠強(qiáng)的表達(dá)力來(lái)表示大多數(shù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法。比如描述算術(shù)表達(dá)式，描述各種語(yǔ)句等等。實(shí)際上，幾乎所有程序設(shè)計(jì)語(yǔ)言都是通過(guò)上下文無(wú)關(guān)文法來(lái)定義的。另外，上下文無(wú)關(guān)文法足夠簡(jiǎn)單，可以構(gòu)造有效的分析算法來(lái)檢驗(yàn)一個(gè)給定符號(hào)串是否是由某個(gè)上下文無(wú)關(guān)文法產(chǎn)生。 編譯原理與技術(shù)623.2 文法的

40、分類例3.23：文法G=(E, +,*, i , ( , ) , P, E )，其中P=E E+E | E*E | (E) | i 該文法是上下文無(wú)關(guān)文法。這里的非終結(jié)符E表示一類算術(shù)表達(dá)式。i表示程序設(shè)計(jì)語(yǔ)言中的“變量”，該文法定義了(描述了)由變量、+、 *、 ( 和 ) 組成的算術(shù)表達(dá)式的語(yǔ)法結(jié)構(gòu)，即：變量是算術(shù)表達(dá)式；若E1和E2是算術(shù)表達(dá)式，則E1+ E2、E1*E2和 (E1) 也是算術(shù)表達(dá)式。例3.24：描述語(yǔ)句的產(chǎn)生式： 語(yǔ)句條件語(yǔ)句|賦值語(yǔ)句|循環(huán)語(yǔ)句 簡(jiǎn)單賦值語(yǔ)句的產(chǎn)生式為：賦值語(yǔ)句 i := E 條件語(yǔ)句的產(chǎn)生式： 條件語(yǔ)句 if條件then語(yǔ)句 | if條件then語(yǔ)句

41、else語(yǔ)句 它們都符合上下文無(wú)關(guān)文法CFG的產(chǎn)生式要求。 編譯原理與技術(shù)633.2 文法的分類正規(guī)文法和正規(guī)式 一個(gè)正規(guī)語(yǔ)言可以由正規(guī)文法定義，也可以由正規(guī)式定義，對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一個(gè)正規(guī)語(yǔ)言的正規(guī)式；反之，對(duì)每個(gè)正規(guī)式，存在一個(gè)生成同一語(yǔ)言的正規(guī)文法，有些正規(guī)語(yǔ)言很容易用文法定義，有些語(yǔ)言更容易用正規(guī)式定義，現(xiàn)在介紹兩者間的轉(zhuǎn)換，從結(jié)構(gòu)上建立它們的等價(jià)性。 編譯原理與技術(shù)643.2 文法的分類將上的一個(gè)正規(guī)式轉(zhuǎn)換成正規(guī)文法G=(VN，VT，P，S) 。 令VT=，確定產(chǎn)生式和VN的元素的方法如下： 對(duì)任何正規(guī)式r，選擇一個(gè)非終結(jié)符S生成產(chǎn)生式Sr，為區(qū)別文法中的產(chǎn)生式，把

42、這個(gè)產(chǎn)生式叫做正規(guī)產(chǎn)生式，并將S定為G的開(kāi)始符號(hào)。若x和y都是正規(guī)式，對(duì)形如Axy的正規(guī)產(chǎn)生式，重寫(xiě)成：AxB，By兩個(gè)正規(guī)產(chǎn)生式，其中B是新選擇的非終結(jié)符，即BVN。編譯原理與技術(shù)653.2 文法的分類對(duì)已形成的形如Ax* y的正規(guī)產(chǎn)生式，引入新的非終結(jié)符B，重寫(xiě)為：AxB | y BxB | y對(duì)形如Ax|y的正規(guī)產(chǎn)生式，重寫(xiě)為：Ax，Ay 不斷利用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式都符合三型文法的要求。 編譯原理與技術(shù)663.2 文法的分類例3.25：將R=a(a|d)* 轉(zhuǎn)換成相應(yīng)的正規(guī)文法。 解：令S是文法的開(kāi)始符號(hào)，首先形成Sa(a|d)*，然后形成SaA和A(a|d)*，重寫(xiě)第二條產(chǎn)

43、生式形成 SaAA(a|d)B AB(a|d)B B 進(jìn)而變換為正規(guī)文法： SaABaB AaBBdB AdBB A 編譯原理與技術(shù)673.2 文法的分類將正規(guī)文法轉(zhuǎn)換成正規(guī)式。 基本上是上述過(guò)程的逆過(guò)程，轉(zhuǎn)換規(guī)則列于表3.1 表3.1 正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則 .文法產(chǎn)生式正規(guī)式規(guī)則1規(guī)則2規(guī)則3AxB ByAxA|yAx AyA=xyA=x*yA=x|y 編譯原理與技術(shù)683.2 文法的分類例3.26：文法GS: SaASa AaAAdA Aa Ad寫(xiě)出其對(duì)應(yīng)的正規(guī)式。 解：先有S=aA|aA=(aA|dA)|(a|d)，再將A的正規(guī)式變換為A=(a|d)A|(a|d)，據(jù)表中規(guī)則2變換

44、為：A=(a|d)*|(a|d)，再將A 右端代入S的正規(guī)式得：S=a(a|d)*|a(a|d)|a，再利用正規(guī)式的代數(shù)變換可依次得到S=a(a|d)*|(a|d)|)，S=a(a|d)*。 a(a|d)* 即為所求。 編譯原理與技術(shù)693.3 文法的等價(jià)變換 定義3.14: 若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。 也就是說(shuō)，如果兩個(gè)文法定義的語(yǔ)言相同，則稱這兩個(gè)文法是等價(jià)的。 例如：下列兩個(gè)文法G1A與G2S等價(jià) G1A：A0R A01 RA1 G2S：S0S1 S01 L(G1) = L(G2) = 0n1n|n1。 編譯原理與技術(shù)703.3 文法的等價(jià)變換 定義3.15:

45、 對(duì)文法進(jìn)行變換，使變換后的文法滿足某種要求并與原文法等價(jià)，這種變換稱為文法的等價(jià)變換。 不存在一個(gè)能判定兩個(gè)文法是否等價(jià)的算法。但是ji我們經(jīng)常使用下列等價(jià)變換：增廣文法消除回溯消除左遞歸編譯原理與技術(shù)713.3 文法的等價(jià)變換增廣文法 對(duì)任一文法G1均可構(gòu)造文法G2，使得L(G1)=L(G2)，并且G2的初始符號(hào)不出現(xiàn)于產(chǎn)生式的右部。 定義3.16: 設(shè)文法GS= (VN,VT, P, S)，構(gòu)造文法GS = (VNS,VT,P,S )，其中P=A| APSS， 顯然L(G)=L(G)，稱G為文法G的增廣文法。 例3.27： G1Z: ZabZA|a，Ab 經(jīng)過(guò)等價(jià)變換后可得到增廣文法G2

46、Z: Z Z Z abZA|a A b 編譯原理與技術(shù)723.3 文法的等價(jià)變換提取左因子 定義3.17: 若文法中有產(chǎn)生式P 1 | 2 | . | n， 則稱該文法含有左因子。 其中P VN，, 1 , 2 , ., n ( VN VT)*。 假設(shè)P有產(chǎn)生式P 1 | 2 | . | n | 1 | 2 | . | n 其中i (i=1,2, . ,n)不以開(kāi)頭。則可將其改寫(xiě)為P P | 1 | 2 | . | n P 1 | 2 | . | n 編譯原理與技術(shù)733.3 文法的等價(jià)變換 例3.28：文法GS: S i E t S | i E t S e S | a E b 提取左因子后，

47、該文法變?yōu)椋?GS: S i E t S S | a S e S | E b 反復(fù)提取左因子，可以消除某些文法的回溯。相應(yīng)付出的代價(jià)是，引進(jìn)了較多新的非終結(jié)符。 編譯原理與技術(shù)743.3 文法的等價(jià)變換消除左遞歸 定義3.18: 若文法中存在推導(dǎo)P P，則稱該文法含有左遞歸。 若存在產(chǎn)生式P P，則稱文法含有直接左遞歸。 若存在產(chǎn)生式P P1，P1 P2，Pn-1 Pn，Pn P，則稱文法含有間接左遞歸。 其中P, P1, ., Pn VN，, ( VN VT)*。 左遞歸會(huì)導(dǎo)致推導(dǎo)過(guò)程中出現(xiàn)大量的死循環(huán)，因此需要消除文法中的左遞歸。 編譯原理與技術(shù)753.3 文法的等價(jià)變換直接左遞歸的消除

48、假設(shè)非終結(jié)符P存在產(chǎn)生式P P | ，其中是不以P開(kāi)頭的字符串。 (1) 刪除左遞歸產(chǎn)生式P P； (2) 引入新的非終結(jié)符消除文法中的左遞歸，得：P P P P | 一般地，若非終結(jié)符有產(chǎn)生式P P1 | P2 | . | Pm | 1 | 2 | . | n 其中i (i=1,2, . ,m)，i (i=1,2, . ,n)不以P開(kāi)頭。則消除左遞歸之后為P 1P | 2P | . |nP P 1P | 2P | . |mP | 編譯原理與技術(shù)763.3 文法的等價(jià)變換 例3.29: 文法GE：E E+T | T T T*F | F F (E) | i 消除左遞歸之后得到如下文法： G E：

49、ETE E +TE | T FT T *FT | F (E) | i 間接左遞歸的消除 (1) 將間接左遞歸轉(zhuǎn)化成直接左遞歸； (2) 消除直接左遞歸； (3) 化簡(jiǎn)文法，刪除含有從開(kāi)始符號(hào)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生式。 編譯原理與技術(shù)773.3 文法的等價(jià)變換 例3.30: 文法GS: S Aa | a A Bb | b B Sc | c 將B Sc | c代入A Bb | b得A Scb | cb | b，代入S Aa | a得S Scba | cba | ba | a。得到含直接左遞歸文法： G1S: S Scba | cba | ba | a A Scb | cb | b B Sc |

50、c 消除直接左遞歸得： G2S: S cbaS | ba S | a S S cbaS | A Scb | cb | b B Sc | c 其中A、B均不能由開(kāi)始符號(hào)S推出，因此刪除無(wú)用產(chǎn)生式后得： G S: S cbaS | ba S | a S S cbaS | 選擇其他的代入順序也可以得到消除左遞歸后的文法，所得的文法都是等價(jià)的。編譯原理與技術(shù)783.3 文法的等價(jià)變換算法3.1 消除左遞歸輸入： 無(wú)回路且無(wú)空產(chǎn)生式的文法GS輸出： 不含左遞歸的文法G S以某種順序?qū)⑽姆ǚ墙K結(jié)符排列P1 , P2, , Pnfor i = 1 to n do for j= 1 to i-1 do if

51、Pj 1 | 2 | | k then 將Pi Pj改寫(xiě)為Pi 1 | 2 | | k end for；消除Pi的直接左遞歸end for；化簡(jiǎn)得到的文法 編譯原理與技術(shù)793.4 語(yǔ)法分析概述 語(yǔ)法分析是編譯過(guò)程的核心部分。 語(yǔ)法分析的任務(wù)是： 按照文法，從源程序符號(hào)串中識(shí)別出各類語(yǔ)法成份，同時(shí)進(jìn)行語(yǔ)法檢查，為語(yǔ)義分析和代碼生成做準(zhǔn)備。執(zhí)行語(yǔ)法分析任務(wù)的程序稱為分析程序，也稱為語(yǔ)法分析器，它是編譯程序的主要子程序之一，在編譯程序中的地位如圖3.14所示。圖3.8 語(yǔ)法分析器在編譯程序中的地位編譯原理與技術(shù)803.4 語(yǔ)法分析概述 典型的語(yǔ)法分析方法有三類：通用方法，能分析任何文法。但這類方法在生成編譯器時(shí)效率太低。自頂向下的分析方法自底向上的分析方法 這兩類方法通常只能處理文法的一些子類，而這些子類中的某些文法足以用來(lái)描述程序語(yǔ)言的大部分語(yǔ)法結(jié)構(gòu)，如LL文法和LR文法。 編譯原理與技術(shù)813.4 語(yǔ)法分析概述自頂向下的語(yǔ)法分析 自頂向下的語(yǔ)法分析是從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，推導(dǎo)出句型，并一個(gè)符號(hào)一個(gè)符號(hào)地與給定終結(jié)符號(hào)串進(jìn)行匹配，尋找匹配于輸入串的推導(dǎo)。如果全部匹配成功，表示開(kāi)始符號(hào)可推導(dǎo)出給定終結(jié)符號(hào)串，由此判定給定的終結(jié)符號(hào)串是文法的句子。 編譯原理與技術(shù)823.4 語(yǔ)法分析概述 例3.30: 文法GZ: Z aBb | aD B b |