編譯原理_第二章

1、第二章第二章 高級語言及其語法描述高級語言及其語法描述引言：關(guān)于引言：關(guān)于形式語言形式語言2.1程序語言的定義程序語言的定義 1、詞法規(guī)則詞法規(guī)則、語法規(guī)則語法規(guī)則p12-132、語義語義P142.2高級語言的一般特性高級語言的一般特性P14-25(關(guān)于算符的優(yōu)先順序關(guān)于算符的優(yōu)先順序p23、名字的左值和右值名字的左值和右值p24）2.3 程序語言的語法描述程序語言的語法描述p252.3 程序語言的語法描述程序語言的語法描述一、符號和符號串一、符號和符號串字母表字母表：字母表：字母表是符號元素的是符號元素的非空非空集合。集合。符號符號：字母表中的元素。：字母表中的元素。 符號串符號串：字母表中

2、的符號所組成的任何：字母表中的符號所組成的任何有窮有窮序列。序列。 例如，若有字母表例如，若有字母表=a,b則則a，b是字母表是字母表中的元素中的元素(符號符號)；a，b，aa，ab，ba都是符號串。都是符號串。注意：符號串中注意：符號串中的符號與順序有的符號與順序有關(guān)，關(guān)，ab和和ba是不是不同的符號串同的符號串特別定義特別定義:空符號串空符號串不含任何符號的符號串，不含任何符號的符號串，用用 表示。表示。 設(shè)有字母表設(shè)有字母表=az, AZ,09, 各種運(yùn)算符和其它特殊各種運(yùn)算符和其它特殊符號，符號，則，由這些字母表中的元素則，由這些字母表中的元素(符號符號)可以組成不同可以組成不同的符號

3、串：的符號串：Program example;Var sum,I: integer;Begin Sum := 0;For I:=1 to 10 do sum:=sum+I;12345:=sum;End.Write(sum=,sum);A=符號串的運(yùn)算符號串的運(yùn)算：符號串的連接（聯(lián)結(jié)、乘積）符號串的連接（聯(lián)結(jié)、乘積）：符號串：符號串x和和y的連接是指的連接是指x和和y的符號按先后順序排列在一起組成一個(gè)新的符號串，的符號按先后順序排列在一起組成一個(gè)新的符號串，用用xy表示。表示。 例，若字母表例，若字母表=a,b，符號串符號串x=ab，y=ba則則xy=abba符號串的長度符號串的長度：符號串中符

4、號的個(gè)數(shù)為符號串的長度。：符號串中符號的個(gè)數(shù)為符號串的長度。 注意注意: (1)連接運(yùn)算不滿足交換律，即連接運(yùn)算不滿足交換律，即xyyx (2)任何符號串任何符號串x與空串與空串的連接都等于的連接都等于x，即即： x=x=x。 若若ab是符號串，則是符號串，則|ab|表示符號串的長度。表示符號串的長度。 |ab|=2同理：同理：|aabb|=4 注意：特別規(guī)定注意：特別規(guī)定 |=0。若有兩個(gè)符號串若有兩個(gè)符號串x=ab,y=cde那么，那么，|xy|=?5符號串的前綴與后綴符號串的前綴與后綴(頭和尾頭和尾)：若有符號串若有符號串 z=xy(x,y是符是符號串號串),我們稱我們稱x為為z的前綴的

5、前綴，y為為z的后綴。的后綴。例例z=abcd則：則：z的頭有，的頭有， , a , ab , abc , abcd z的尾有，的尾有， ,d , cd , bcd , abcd符號串的冪運(yùn)算符號串的冪運(yùn)算：設(shè)設(shè)X是一個(gè)符號串，則：是一個(gè)符號串，則： X0=，X1=X，X2=XX，Xn=XX=Xn例：若有符號串例：若有符號串x=ab，則：則：x0= ,x1= ab,x2= abab,x3= ababab顯然，若顯然，若n0,則則Xn=XXn-1 =Xn-1X。 即：符號串的冪運(yùn)算服從結(jié)合律即：符號串的冪運(yùn)算服從結(jié)合律 符號串符號串集合集合的運(yùn)算的運(yùn)算：符號串集合的乘積運(yùn)算：符號串集合的乘積運(yùn)算

6、：設(shè)設(shè)A、B為符號串集合（集合為符號串集合（集合中各元素都是字母表上的字符串），兩個(gè)字符串集合中各元素都是字母表上的字符串），兩個(gè)字符串集合的乘積定義為：的乘積定義為：AB=xy|xA , yB（笛卡兒乘積）笛卡兒乘積）設(shè)有字母表設(shè)有字母表=a,b,c,d，令令A(yù)=aa,bb，B=cc,dd則則AB=aacc,aadd,bbcc,bbdd， BA=ccaa,ccbb,ddaa,ddbb。顯然顯然 AB BA，即符號串集合乘積不滿足交換律即符號串集合乘積不滿足交換律。注意：因注意：因x = x=x故，故， A=AA=A=A =A 特別定義：空符號串集合：特別定義：空符號串集合： 空集合：空集合：

7、= A = A= 符號串集合的冪運(yùn)算：符號串集合的冪運(yùn)算：設(shè)設(shè)A為符號串集合，則集合的冪為符號串集合，則集合的冪運(yùn)算定義如下運(yùn)算定義如下:A0=A1=AA2=AAAn=AAAn個(gè)個(gè)=AAn-1=An-1A符號串集合的閉包：符號串集合的閉包：設(shè)設(shè)A為符號串集合，則集合的閉包為符號串集合，則集合的閉包定義如下定義如下:A的的正閉包正閉包： A+=A1A2A的的閉包：閉包： A*=A0A1A2設(shè)集合設(shè)集合A=a,b，則則 A+=a,b,aa,ab,ba,bb,aaa, A*=,a,b,aa,ab,ba,bb,aaa, 顯然：顯然： A*=A0A+ A+=AA*二、上下文無關(guān)二、上下文無關(guān)文法文法 (

8、p26)文法文法(Grammar):是描述語言的語法結(jié)構(gòu)的形式是描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。規(guī)則（即語法規(guī)則）。The big monkey ate a banana.規(guī)則規(guī)則：規(guī)則又叫：規(guī)則又叫產(chǎn)生式產(chǎn)生式(production rule)，它是，它是語法單位結(jié)構(gòu)的一種表示，它引入了符號語法單位結(jié)構(gòu)的一種表示，它引入了符號“:=:=”或或“”表示表示“由由組成組成”，上述句子的結(jié)構(gòu)，上述句子的結(jié)構(gòu)可以表示如下：可以表示如下： the big ate a monkey banana句子的推導(dǎo)句子的推導(dǎo)：用規(guī)則：用規(guī)則(產(chǎn)生式產(chǎn)生式)按一定方式去推導(dǎo)按一定方式去推導(dǎo)或產(chǎn)生句子的過

9、程?；虍a(chǎn)生句子的過程。 the big ate a monkey banana The The big The big monkey The big monkey The big monkey ate The big monkey ate The big monkey ate a The big monkey ate a banana The big monkey ate a banana語法樹語法樹(Parse Tree):句子結(jié)構(gòu)的圖形表示方式句子結(jié)構(gòu)的圖形表示方式monkeybigTheatebananaa歸納：什么是文法歸納：什么是文法 the big ate a monkey ban

10、ana三、文法和語言的形式定義三、文法和語言的形式定義定義定義2 文法文法是一個(gè)四元組：是一個(gè)四元組：GS=(VN, VT, P, S)其中：其中：VN為非終結(jié)符集合；為非終結(jié)符集合； VT為終結(jié)符集合；為終結(jié)符集合； VNVT =，一般令一般令 V= VNVT ，V中的符號稱為文法符號；中的符號稱為文法符號；(V字匯表）字匯表）P為產(chǎn)生式集合；為產(chǎn)生式集合； P中的每個(gè)產(chǎn)生式寫為：中的每個(gè)產(chǎn)生式寫為：或或 =。S為開始符號為開始符號(或稱根符號，識別符號或稱根符號，識別符號)。定義定義1 產(chǎn)生式產(chǎn)生式(或規(guī)則或規(guī)則)是一有序?qū)κ且挥行驅(qū)?A, )，通常寫為：，通常寫為： A 或或A = 其中

11、其中A是一個(gè)符號作為產(chǎn)生式左部，是一個(gè)符號作為產(chǎn)生式左部， 為有窮符號串作為產(chǎn)生為有窮符號串作為產(chǎn)生式的右部，式的右部，“ ”或或“ =”表示表示“定義為定義為”或或“由由組成組成”。另外：另外：GS也可簡寫為也可簡寫為G 在規(guī)則左部出現(xiàn)的在規(guī)則左部出現(xiàn)的符號稱為非終結(jié)符，符號稱為非終結(jié)符，它們的全體形成它們的全體形成VN在規(guī)則中只在右部在規(guī)則中只在右部出現(xiàn)的符號稱為終出現(xiàn)的符號稱為終結(jié)符，它們的全體結(jié)符，它們的全體形成形成VT例例 G1 =(N,0，1,N0N,N1N,N0,N1,N） 其中其中: 非終結(jié)符非終結(jié)符 VN =N終結(jié)符終結(jié)符VT =0，1V=N，0，1 P=N0N，N1N，N0

12、，N1開始符號開始符號S 為為N通常情況下，文法只用產(chǎn)生式集合表示：通常情況下，文法只用產(chǎn)生式集合表示：G1N: N0N N1N N0 N1定義定義3 符號串的符號串的推導(dǎo)與歸約推導(dǎo)與歸約：已給文法：已給文法G=(VN,VT,P,S)， V= VNVT，令令x,y,V* ，且且P，此時(shí)，由符號此時(shí)，由符號串串xy能夠直接產(chǎn)生出符號串能夠直接產(chǎn)生出符號串xy，我們稱：我們稱：符號串符號串xy是符號串是符號串xy的的直接推導(dǎo)直接推導(dǎo)；符號串符號串xy是符號串是符號串xy的的直接歸約直接歸約；記作記作: xy xy 對于上例中文法：對于上例中文法：G1N: N0N N1N N0 N1存在以下直接推導(dǎo)

13、：存在以下直接推導(dǎo)： N 1N 11xyxyx yx y若有若有1，2，nV* 且且1 2 ，n-1 n則稱則稱n是是1的推導(dǎo)的推導(dǎo)記作：記作： 1+n特別約定：若在推導(dǎo)關(guān)系特別約定：若在推導(dǎo)關(guān)系1n中允許中允許1=n，+則稱則稱n是是1 的廣義推導(dǎo)記作的廣義推導(dǎo)記作 1*nN +11N *N引用引用巴科斯范式巴科斯范式(BNF)表示文法：表示文法：對于具有相同左部的那些產(chǎn)生式，如：對于具有相同左部的那些產(chǎn)生式，如：Ux, Uy, Uz可以縮寫為：可以縮寫為：Ux|y|z (“|”可理解為可理解為“或或”)(1) (2) (3) (4) 0(5) 1(6) 2(7) 3(8) 4(9) 5(1

14、0) 6(11) 7(12) 8(13) 9(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|用此文法和直接推導(dǎo)的定義可以用此文法和直接推導(dǎo)的定義可以推導(dǎo)出任一無符號整數(shù)推導(dǎo)出任一無符號整數(shù)(56) 5 56可表示為可表示為:+56 V*，則稱則稱為文法為文法G的句型的句型 VT*，則稱則稱為文法為文法G的句子的句子 文法文法G所對應(yīng)的語言，記作所對應(yīng)的語言，記作L(G)=|VT*，且且S+例例:前面提到的文法前面提到的文法G = VN，VT，P，無符號整數(shù)無符號整數(shù)其中，其中，VT =0，1，2，3，4，5，6，7，8，9 VN =無符號整數(shù)，數(shù)字串，數(shù)字無

15、符號整數(shù)，數(shù)字串，數(shù)字 P： 0123456789 5 56 試給出該文法的試給出該文法的句型、句子舉例，句型、句子舉例，并說明它所確定并說明它所確定的語言。的語言。由此我們可以看出，文法和語言是密切相關(guān)的，根據(jù)文由此我們可以看出，文法和語言是密切相關(guān)的，根據(jù)文法可以推導(dǎo)出任一句型和句子，而所有句子的集合則為法可以推導(dǎo)出任一句型和句子，而所有句子的集合則為該文法所對應(yīng)的語言，即該文法所對應(yīng)的語言，即語言是所有句子構(gòu)成的集合，語言是所有句子構(gòu)成的集合，它是所有終結(jié)符號串所組成的集合它是所有終結(jié)符號串所組成的集合VT*的子集的子集：L(G) VT*定義定義4 句型和句子句型和句子:設(shè)設(shè)G=(VN,

16、VT,P,S)是一文法，若是一文法，若 S *那么，句型和句子的那么，句型和句子的區(qū)別是什么區(qū)別是什么?定義定義5 規(guī)范推導(dǎo)規(guī)范推導(dǎo)(歸約歸約):對于直接推導(dǎo)對于直接推導(dǎo)xy xy，如果如果y只只包含終結(jié)符號包含終結(jié)符號或?yàn)榭辗柎敲淳桶堰@種直接推導(dǎo)稱或?yàn)榭辗柎?，那么就把這種直接推導(dǎo)稱為規(guī)范為規(guī)范(最右最右)推導(dǎo)，跟其對應(yīng)的歸約稱為規(guī)范推導(dǎo)，跟其對應(yīng)的歸約稱為規(guī)范(最左最左)歸約，歸約，且記作：且記作：xy rxy下面的推導(dǎo)是否規(guī)范推導(dǎo)下面的推導(dǎo)是否規(guī)范推導(dǎo)： 5 56 6 6 56若推導(dǎo)：若推導(dǎo)：1+n中的每一步直接推導(dǎo)都中的每一步直接推導(dǎo)都是規(guī)范的，那么我們就是規(guī)范的，那么我們就把推

17、導(dǎo)：把推導(dǎo)：1+n稱為是規(guī)范的，且記作：稱為是規(guī)范的，且記作：1n+r+r56每次對符號串最右非終結(jié)每次對符號串最右非終結(jié)符號進(jìn)行替換符號進(jìn)行替換例例 文法文法GE : EE+E | E*E | (E) | i 給出句子給出句子i*i+ i的最右及最左推導(dǎo)的最右及最左推導(dǎo) 。例例2.1 p30例例2.2例例2.3同樣，可給出最左推導(dǎo)的定義。同樣，可給出最左推導(dǎo)的定義。p30-31形式語言理論可以證明以下兩點(diǎn)：形式語言理論可以證明以下兩點(diǎn)：(1)給定一個(gè)文法給定一個(gè)文法G，就可以從結(jié)構(gòu)上唯一地確定其語言：就可以從結(jié)構(gòu)上唯一地確定其語言：GL(G)(2)給定一種語言給定一種語言L，能確定其文法，但

18、這種文法可能不能確定其文法，但這種文法可能不是唯一的：是唯一的：LG1或或G2例例1：有文法：有文法GZ: (1)ZaZb (2)Z ab它確定的語言是什么？它確定的語言是什么？用用BNF表示：表示： Z aZb|ab由產(chǎn)生式由產(chǎn)生式(2)知：知： zab 故故ab是文法的一個(gè)句子是文法的一個(gè)句子用產(chǎn)生式用產(chǎn)生式(1)(2)：zaZba2b2 故故a2b2是文法的一個(gè)句子是文法的一個(gè)句子反復(fù)使用產(chǎn)生式反復(fù)使用產(chǎn)生式(1)： zaZba2Zb2 an-1Zbn-1 anbn所以，文法所確定的語言為：所以，文法所確定的語言為：L(GZ)=anbn | n 1例例2：已知語言為：已知語言為 L(G)

19、=abna | n 1 試給出其文法。試給出其文法。G1Z: Z aBa B bB|bG2Z: Z aBa B Bb|b定義定義6 等價(jià)文法等價(jià)文法：如果：如果L(G1)=L(G2) ，那么稱那么稱G1和和G2為等價(jià)文法。為等價(jià)文法。定義定義7 遞歸產(chǎn)生式和遞歸文法遞歸產(chǎn)生式和遞歸文法：設(shè)給定文法：設(shè)給定文法G=(VN,VT,P,S) 若若x=且且y,則稱產(chǎn)生式則稱產(chǎn)生式A是是左遞歸產(chǎn)生式左遞歸產(chǎn)生式；若若x且且y=,則稱產(chǎn)生式則稱產(chǎn)生式A是是右遞歸產(chǎn)生式右遞歸產(chǎn)生式。B BbB bB(1)若存在產(chǎn)生式若存在產(chǎn)生式AP 且有且有 A xAy成立，則稱產(chǎn)生成立，則稱產(chǎn)生式式A是遞歸產(chǎn)生式；是遞歸

20、產(chǎn)生式； *若若具有具有xAy形式形式,則稱產(chǎn)生式則稱產(chǎn)生式A是是直接遞歸產(chǎn)生式直接遞歸產(chǎn)生式。(2)遞歸文法：遞歸文法： 若文法中至少存在一條直接遞歸產(chǎn)生式則稱該文法是若文法中至少存在一條直接遞歸產(chǎn)生式則稱該文法是直接遞歸的文法直接遞歸的文法；否則；否則 若有若有A +xAy ，或，或A +Ay ，或，或A +xA則稱文法為則稱文法為間接遞歸的文法間接遞歸的文法?？梢?，對于文法中任一非終結(jié)符號，若能建立一個(gè)推導(dǎo)過可見，對于文法中任一非終結(jié)符號，若能建立一個(gè)推導(dǎo)過程，在推導(dǎo)所得的符號串中又出現(xiàn)了該非終結(jié)符號本身，程，在推導(dǎo)所得的符號串中又出現(xiàn)了該非終結(jié)符號本身，則文法是遞歸的。則文法是遞歸的。

21、應(yīng)當(dāng)注意，一般的文法都是遞歸的應(yīng)當(dāng)注意，一般的文法都是遞歸的，文文法法G只有遞歸定義，只有遞歸定義，L(G)中句子才是無窮的中句子才是無窮的 例：有文法例：有文法GS: S aB|bB B a|b是否是遞歸文法，確定什是否是遞歸文法，確定什么語言？么語言？非遞歸非遞歸文法，文法，L(GS)=aa,ab,ba,bb例：有文法例：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|該文法中有直接左遞歸產(chǎn)生式：該文法中有直接左遞歸產(chǎn)生式： 所以是遞歸文法。所以是遞歸文法。它是否為遞歸文法，確定的語言是什么？它是否為遞歸文法，確定的語言是什么？所確定的語言為：所

22、有無符號整數(shù)。所確定的語言為：所有無符號整數(shù)。L(G)=VT+若不用遞歸規(guī)則表示文法，就要用到無窮多條產(chǎn)生式：若不用遞歸規(guī)則表示文法，就要用到無窮多條產(chǎn)生式： | | |總之，總之，使用遞歸文法，可用有窮的產(chǎn)生式來描述無窮使用遞歸文法，可用有窮的產(chǎn)生式來描述無窮的語言的語言，反之，一個(gè)語言若是無窮的，則描述語言的，反之，一個(gè)語言若是無窮的，則描述語言的文法必定是遞歸的。文法必定是遞歸的。(程序設(shè)計(jì)語言一般是無窮的程序設(shè)計(jì)語言一般是無窮的)。 課堂練習(xí)課堂練習(xí)（見教案）（見教案）定義定義8 短語、簡單短語和句柄短語、簡單短語和句柄：設(shè)文法：設(shè)文法 G=(VN,VT,P,S) ， 且且 U VN，

23、x,y,u V*(1)若有若有SxUy*+xuy，則則u稱為句型稱為句型xuy的相對于的相對于U的的短語短語 ；(2)若有若有SxUy* xuy，則則u稱為句型稱為句型xuy的相對于的相對于U的的簡單簡單(直接直接)短語短語； 例例：有文法：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|因有：因有： *+6xyUyxuU= u= 6x,y= 6是句型是句型6相對于相對于的短語的短語(3)任一句型的任一句型的最左簡單短語最左簡單短語稱為該句型的稱為該句型的句柄句柄.因有：因有： *66是句型是句型6相對于相對于的短語，且為的短語，且為簡單短語簡單短語

24、xUyxyu說明：當(dāng)句型有兩個(gè)以上的簡單短語同時(shí)存在時(shí)，說明：當(dāng)句型有兩個(gè)以上的簡單短語同時(shí)存在時(shí)，我們把位于最左邊的那個(gè)簡單短語稱為我們把位于最左邊的那個(gè)簡單短語稱為“最左簡最左簡單短語單短語”，即該句型的句柄；若句型只有一個(gè)簡，即該句型的句柄；若句型只有一個(gè)簡單短語，那么，它就是最左簡單短語，即句柄。單短語，那么，它就是最左簡單短語，即句柄。例例1：在：在“6”中，中，6是句型是句型6中唯中唯一的一個(gè)簡單短語，所以它是句柄一的一個(gè)簡單短語，所以它是句柄.例例2：在：在“ 78”中，中， 、7和和8都都是是句型簡單短語，所以位于左邊的是是句型簡單短語，所以位于左邊的 是句柄是句柄.注意：可從

25、語法樹的角度理解短語和句柄。注意：可從語法樹的角度理解短語和句柄。p31例例：有文法：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|2.4語法樹和文法的二義性語法樹和文法的二義性語法樹語法樹: 設(shè)文法設(shè)文法G=(VN,VT,P,S) ，所謂語法樹是一張圖，這所謂語法樹是一張圖，這張圖表示一個(gè)句型的推導(dǎo)過程。語法樹結(jié)構(gòu)是一棵倒立的張圖表示一個(gè)句型的推導(dǎo)過程。語法樹結(jié)構(gòu)是一棵倒立的樹結(jié)構(gòu)，其中，結(jié)點(diǎn)的名字樹結(jié)構(gòu)，其中，結(jié)點(diǎn)的名字NV，根結(jié)點(diǎn)的名字根結(jié)點(diǎn)的名字S是文法是文法G的開始符號，樹中的中間結(jié)點(diǎn)是句型推導(dǎo)過程中使用的的開始符號，樹中的中間結(jié)點(diǎn)是句型

26、推導(dǎo)過程中使用的非終結(jié)符非終結(jié)符 ，樹的端末結(jié)點(diǎn)自左向右排列就是所給句型。，樹的端末結(jié)點(diǎn)自左向右排列就是所給句型。例例2.7 文法文法GE: EE+TT TT*FF FEi 句型句型E+F*i對應(yīng)的語對應(yīng)的語法樹如右圖所示：法樹如右圖所示： EE T+T *F F i可以看出，語法樹的生成過程直觀的給出了句型的推導(dǎo)過程?？梢钥闯觯Z法樹的生成過程直觀的給出了句型的推導(dǎo)過程。子樹子樹：由語法樹的某個(gè)結(jié)點(diǎn)：由語法樹的某個(gè)結(jié)點(diǎn)(子樹的根子樹的根)連同它下面發(fā)出的連同它下面發(fā)出的部分組成語法樹的子樹。只含有單層分支的子樹為簡單子部分組成語法樹的子樹。只含有單層分支的子樹為簡單子樹。樹。EE T+T *

27、F F i子樹與短語子樹與短語：在句型所對：在句型所對應(yīng)的語法樹中，若某些符應(yīng)的語法樹中，若某些符號按從左到右的順序組成號按從左到右的順序組成某棵子樹的末端結(jié)點(diǎn)，那某棵子樹的末端結(jié)點(diǎn)，那么由這些末端結(jié)點(diǎn)所組成么由這些末端結(jié)點(diǎn)所組成的符號串是相對于子樹根的符號串是相對于子樹根結(jié)點(diǎn)的短語。結(jié)點(diǎn)的短語。例如：例如：F是句型相對于是句型相對于T的短語，且為簡單短語的短語，且為簡單短語; i是句型相對于是句型相對于F的短語，且為簡單短語的短語，且為簡單短語; F*i 是句型相對于是句型相對于T的短語的短語; E+F*i是句型相對于是句型相對于E的短語的短語.補(bǔ)充補(bǔ)充2個(gè)例子（教案個(gè)例子（教案P30-31

28、）原則上語法樹有多原則上語法樹有多少棵子樹，就有多少棵子樹，就有多少個(gè)短語少個(gè)短語哪個(gè)是句柄？哪個(gè)是句柄？文法的二義性文法的二義性：若一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的：若一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱此文法是二義性文法，運(yùn)用文法描述程序設(shè)語法樹，則稱此文法是二義性文法，運(yùn)用文法描述程序設(shè)計(jì)語言的語句成份，一般希望所給文法是非二義文法，但計(jì)語言的語句成份，一般希望所給文法是非二義文法，但是，有時(shí)候采用二義性文法比非二義文法要簡單的多，所是，有時(shí)候采用二義性文法比非二義文法要簡單的多，所以，經(jīng)常用二義性文法描述程序設(shè)計(jì)語言。以，經(jīng)常用二義性文法描述程序設(shè)計(jì)語言。 例例1： 文法文

29、法GE : EE+E | E*E | (E) | i 試為符號串試為符號串E*E+i構(gòu)造語法樹構(gòu)造語法樹. EEE+EE*iEEE*EE+i先乘后加先乘后加先加后乘先加后乘所以文法是二義性的。在進(jìn)行語法分析時(shí)通所以文法是二義性的。在進(jìn)行語法分析時(shí)通過人工干預(yù)過人工干預(yù)(規(guī)定算符的優(yōu)先級規(guī)定算符的優(yōu)先級)，確定歸約，確定歸約(分析分析)順序順序 例例2：if 語句語句(1)(2)(3)2.5文法的分類文法的分類 按照文法中產(chǎn)生式的不同情況，按照文法中產(chǎn)生式的不同情況，Chomsky把文法分把文法分成四種類型，四種類型的文法對應(yīng)著四種類型的語言。成四種類型，四種類型的文法對應(yīng)著四種類型的語言。0型

30、文法型文法： 產(chǎn)生式形式為產(chǎn)生式形式為: u v 且且 u V+ v V* u中應(yīng)至少含有一個(gè)非終結(jié)符號，這種文法又叫短語文中應(yīng)至少含有一個(gè)非終結(jié)符號，這種文法又叫短語文法，它所確定的語言稱為法，它所確定的語言稱為0型語言。型語言。1型文法型文法: 產(chǎn)生式形式為產(chǎn)生式形式為 xUy xuy 且且 U VN u V+ x,y V* 則稱該文法為則稱該文法為1型文法，也稱為上下文敏感文法或上下文有型文法，也稱為上下文敏感文法或上下文有關(guān)文法。關(guān)文法。 即只有在即只有在U的左部為符號串的左部為符號串x而右部為符號串而右部為符號串y時(shí)，才允時(shí)，才允許把非終結(jié)符許把非終結(jié)符U用符號串用符號串u來代替，即

31、來代替，即U必須在上下文必須在上下文xy中中才行。這種文法所對應(yīng)的語言為才行。這種文法所對應(yīng)的語言為1型語言。型語言。2型文法型文法: 產(chǎn)生式形式為產(chǎn)生式形式為 U u 且且 U VN u V* 則稱該文法為則稱該文法為2型文法，也稱為上下文無關(guān)文法。型文法，也稱為上下文無關(guān)文法。2型型文法所確定的語言為文法所確定的語言為2型語言，大部分程序設(shè)計(jì)語言都是型語言，大部分程序設(shè)計(jì)語言都是2型語言。型語言。例例: 文法文法G =（S，a,b，SaSb, Sab，S）3型文法型文法: 產(chǎn)生式形式為產(chǎn)生式形式為 UxV|y xV|y 或或 U Vx|y U Vx|y 且且 U,V VU,V VN N，x,yVx,yVT T+ + 則稱該文法為則稱該文法為3型文法，也稱線性文法、型文法，也稱線性文法、正則文法或正正則文法或正規(guī)文法規(guī)文法。這種文法所對應(yīng)