《文法和語言》PPT課件.ppt

1、第二章 文法和語言,2020/11/8,1,內(nèi)容提要,字母表與符號串 文法(定義,推導,句型與句子) 語言 遞歸規(guī)則與遞歸文法 語法樹（短語、簡單短語和句柄） 語法樹與文法的二義性,2020/11/8,2,2.1 字母表與符號串,字母表 符號串 符號串及集合的運算,2020/11/8,3,2.1.1 字母表,字母表是符號的非空有窮集合。 例如： 1.機器語言字母表：由符號“0”和“1”組成的字母表,=0，1 2. ASCII字符集 3. Pascal字母表為： =AZ, az, 09, +, -, *, /, ,:, , ; ，.， , (, ), , , , ,2020/11/8,4,2.1

2、.2 符號串,定義： (1)是上的一個符號串。 (2)若x是上的符號串，而a是的元素,則xa是上的符號串。 (3)y是上的符號串,當且僅當它由(1)和(2)導出。 即：符號串由字母表中的符號所組成的任何有窮序列。,2020/11/8,5,2.1.3 符號串及其集合的運算,1.符號串的長度：指符號串x中所含符號的個數(shù)，記為|x|。 如|xyz|=3，|123+321|=7，而|=0 2.符號串相等：若x、y是字母表上的兩個符號串，當且僅當組成x的各符號與組成y的各符號依次相等時，則符號串x與符號串y相等，記作x=y。 如： 當x=abbc，y=abbc時，則x=y； 而當x=ab，y=ba 時，

3、則xy 3.符號串的前綴：指從符號串x的末尾刪除0或多個符號后得到的符號串，如u、uni、university都是university的前綴。 4.符號串的后綴：指從符號串x的開頭刪除0或多個符號后得到的符號串，如ty、sity、university都是university的后綴。,2020/11/8,6,5.符號串的子串：指從符號串x的開頭和末尾刪除0或多個符號后得到的符號串，如ver是university的子串, 符號串的前綴、后綴都是它的子串。 6.符號串的連接：若x、y是兩個符號串，則xy表示連接，是將符號串y連接在符號串x的后面。若x、y是字母表上的兩個符號串，則xy也是字母表上的符

4、號串。 例如： x = ab，y = ba，則 xy = abba 注意：連接沒有交換律，即 xy yx 而對于空串有 x=x=x,2020/11/8,7,7.集合的乘積運算：令A、B為兩個符號串集合，A和B的乘積AB定義為： AB=xy|xA，yB 例如：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=xn-1x,其中n0 例如：x=abc, x0=, x1=abc, x2=abcabc,2020/11/8,8,9.集合的冪運算：設A為符號

5、串集合，則A的冪運算定義為： A0= A1=A A2=AA An=AAA=AAn-1 =An-1A，其中 n0,例如：A =a，b， 則 A0= A1=a,b A2=aa,ab,ba,bb,2020/11/8,9,10.集合的正閉包和集合的閉包：設A為一個集合，則集合A的正閉包用A+表示，定義為： A+ =A1A2 An 集合A的閉包用A*表示，定義為： A* =A0A+ 例如：A =a，b， 則A+ =a,b,aa,ab,ba,bb,aaa,aab, A* =,a,b,aa,ab,ba,bb,aaa,aab,2020/11/8,10,2.2 文法,文法是描述語言語法結(jié)構(gòu)的形式規(guī)則。 文法需要

6、說明語言的語法成分，句子中的符號以及語法結(jié)構(gòu)。,例：能夠描述句子“the monkey ate the banana”的文法：, ,該例中語法成分，句子中的符號，語法結(jié)構(gòu)是什么？,2020/11/8,11,2.2.1 文法形式定義,文法的形式定義：文法可表示為一個四元組 G=（Vn ，Vt，P，Z） Vn:非空有窮集合,其元素為非終結(jié)符號。 Vt:非空有窮集合,其元素為終結(jié)符號且VtVn=,VtVn是該文法的字母表。 P：非空有窮集合,其元素為產(chǎn)生式或規(guī)則。產(chǎn)生式的形式為:或:=；是產(chǎn)生式左部且不能為空,是產(chǎn)生式右部,并且、（VtVn)* ,“”或“:=”含義相同，表示“定義為”或“由組成”。

7、 Z：Vn中一個特殊的非終結(jié)符號，稱為文法的識別符號或開始符號。必須至少在某個產(chǎn)生式的左部出現(xiàn)一次。,2020/11/8,12,2.2.1 文法形式定義,按文法形式定義表示“the monkey ate the banana”文法。 解：根據(jù)文法的形式定義，文法G1=（ Vn， Vt，P，Z） 非終結(jié)符號集合: Vn=句子，主語，謂語，冠詞，名詞，動詞，直接賓語 終結(jié)符號集合: Vt= the，ate，banana，monkey 產(chǎn)生式集合P由下面8條規(guī)則組成: 識別符號Z：, the ate banana monkey,2020/11/8,13,2.2.1 文法形式定義,上下文無關(guān)文法：產(chǎn)生

8、式左部是一個非終結(jié)符，右部是由非終結(jié)符和終結(jié)符組成的有窮符號串?？梢院喕硎?。 例：有如下簡化表示文法，只給出規(guī)則集，寫出該文法的終結(jié)符號集合、非終結(jié)符號集合和識別符號。,1. 2. 3. 4.0 5.1 6.2 7.3 8.4 9.5 10.6 11.7 12.8 13.9,解： 非終結(jié)符號集合： Vn=, 終結(jié)符號集合： Vt=0,1,2,3,4,5,6,7,8,9 識別符號Z：,2020/11/8,14,2.2.2 文法的EBNF表示,EBNF在書寫文法的規(guī)則時采用一些特殊的符號，提高文法規(guī)則的表達能力。各種元符號的含義如下。,1.元符號“|”：表示“或”，對于具有相同左部的那些規(guī)則,

9、如1、2 、n，可縮寫為: 1|2 |n 上例文法的13條規(guī)則可縮寫成： | 0|1|2|3|4|5|6|7|8|9,1. 2. 3. 4.0 5.1 6.2 7.3 8.4 9.5 10.6 11.7 12.8 13.9,2020/11/8,15,2.2.2 文法的EBNF表示,2.元符號“”：用于括起由中文字組成的非終結(jié)符號或由多個字母組成的符號。如、等。 3.元符號“”和“”：表示可重復連接，tnm表示符號串t可重復連接n到m次，而t表示符號串t可重復連接0到無窮次。例如， 13 與 | 相同 EE+T|T 與 ET+T相同 而字母打頭、后面可跟數(shù)字或字母的不超過8個字符的標識符文法則為

10、：|07,2020/11/8,16,2.2.2文法的EBNF表示,4.元符號“”和“ ”：表示括起的內(nèi)容可選。 例如：IF THEN IF THEN ELSE 可寫成： IF THEN ELSE 5.元符號“（”和“）”：表示括號內(nèi)的成分優(yōu)先。常用于在規(guī)則中提取公因子。 例如，Uxy|xw|xz 可寫成：Ux（y|w|z）,2020/11/8,17,2.3 推導,給定文法，可從文法的開始符號根據(jù)文法規(guī)則進行推導產(chǎn)生文法定義的句型或句子。 根據(jù)文法規(guī)則可從開始符號出發(fā)， 使用產(chǎn)生式構(gòu)造出符號串。 例如： 其中“”表示一步推導, 上述推導過程表示經(jīng)過兩步推導，從可推導出。,2020/11/8,18

11、, ,直接推導的定義 (1) 是文法G=(VN ,VT ,P,S)的規(guī)則，和是(VN VT )*中的任意符號,若有符號串V,W滿足： V=，W 則說V是直接產(chǎn)生W 或W是V的直接推導 或W直接歸約到V,記作 V W,2.3 推導,推導：用產(chǎn)生式右部替代左部,V=S，W0S1 W是否是V的直接推導 直接推導：S 0S1 V=0S1，W=00S11 W是否是V的直接推導 直接推導： 0S100S11,例：文法G =（VN ,VT ,P，S）, 其中 VN=S，VT =0，1， P=S 0S1，S 01 V0S1，W=0011 W是否是V的直接推導 直接推導：0S1 0011,使用規(guī)則：S 01 0

12、，1， S， 01,規(guī)則： S 0S1 ， S， 0S1,規(guī)則： S 0S1 0 ， 1 S， 0S1,若有 VW或 V = W ，則記作VW 例： V0S1 00S11 000S111 00001111 W 記作： 0S1 00001111 0S1 00001111,+,+,*,若存在直接推導的序列： V=W0 W1 W2 Wn W (n0) 則 稱V推導W (或W歸約到V)，記作V W,*,相同,文法G =(VN ，VT ，P，S)，其中VN=S，VT =0，1， P=S 0S1，S 01,例：G=( S,A,a,b,P,S )，其中P為：,S aAS A SbA A SS S a A b

13、a,請構(gòu)造aabbaa的推導過程,（1）每次替換最右邊非終結(jié)符 SaAS aAa aSbAa aSbbaa aabbaa （2）每次替換最左邊非終結(jié)符 SaAS aSbASaabASaabbaSaabbaa （3）無固定的推導方向 SaAS aSbASaSbAaaabAaaabbaa,每步推導只能替換一個非終結(jié)符,2020/11/8,23,練習： 文法GS=(S, A, B,a, b, c, d, e, S aAcBe A b A Ab B d,S） 構(gòu)符號串a(chǎn)bbcde的推導過程,S aAcBe aAbcBe abbcBe abbcde,S aAcBe aAcde aAbcde abbcde

14、,2.3 規(guī)范推導,規(guī)范推導：亦稱最右推導，即每步推導只變換最右邊的非終結(jié)符號。其形式定義為： 對直接推導xy xy，如果y只包含終結(jié)符號或為空符號串,則該推導稱為規(guī)范推導或最右推導（如果只包含終結(jié)符號或為空符號串,則為最左推導），記作: xyxy , 其中yVt* 。 如果推導0n的每一步都是規(guī)范的,則推導0n稱為規(guī)范的,記作:0 n,2020/11/8,24,+,+,+,2.4 句型和句子,文法GS （1）句型：x是句型 S x,且xV*； （2）句子：x是句子 S x, 且xVT*； （3）語言：L（GS）=x |xVT*,S x ；,+,+,文法GS所產(chǎn)生的 所有句子的集合,*,句子是

15、所有終結(jié)符 號組成的句型,GE： EE+E|E*E|(E)|i,句型： E+E E+E*E E+E*i E+i*i,句子： i+i i*i i+i*i (i+i)*i,2020/11/8,25,2.4 句型和句子,規(guī)范句型：用規(guī)范推導產(chǎn)生的句型。每個句子都有一個規(guī)范推導,但并非每個句型都有規(guī)范推導。 例如，對文法： ； |； 0|1|2|3|4|5|6|7|8|9 有句型“2”,其推導過程如下: 2 第步推導變換的不是最右邊非終結(jié)符號，故句型“2”不是規(guī)范句型。 對于句型“3”，其推導過程如下: = =3 =3 每一步推導都變換的是最右邊非終結(jié)符號，故句型“3”是規(guī)范句型。,2020/11/8

16、,26,Why?,2.5 語言,定義：文法GZ所產(chǎn)生的所有句子的集合L(GZ), 稱為文法GZ所定義的語言, 即: L(GZ)=x|x Vt* ,且Z =x 形式語言理論可以證明以下兩點： （1）G L（G）； （2）L(G)G1，G2，Gn；。 已知文法，求語言，通過推導； 已知語言，構(gòu)造文法，無形式化方法，更多是憑經(jīng)驗,2020/11/8,27,+,2.5 語言,例:已知文法GZ為： 1)ZaZb 2)Zab 求該文法確定的語言。 解：從識別符號開始推導,反復用規(guī)則1可得: Z=aZb=a2Zb2=an-1Zbn-1 最后用規(guī)則2可得: Z=aZb=a2Zb2=an-11Zbn-1 = a

17、nbn 所以該文法確定的語言為：L(GZ)=(anbn|n1),若Z aZb|,如何？,2020/11/8,28,已知文法，求語言，通過推導,練習1：GS S bA A aA|a,練習2：GS S AB A aA|a B bB|b,2020/11/8,29,練習3：GS S 0A A 1B B 0|0S,2.5 語言,例2.5，已知語言為: L(G)=abna|n 1，構(gòu)造產(chǎn)生該語言的文法。 解：根據(jù)語言的形式，可構(gòu)造其文法G為: ZaBa BBb|b 還可構(gòu)造文法G1為: ZaBa BbB|b 可見G與G1是兩個不同的文法，但都可以描述語言abna|n1。,文法和語言之間無一一對應關(guān)系。文法

18、唯一確定語言，反之不成立！ 定義： G和G是兩個不同的文法，若 L(G) = L(G) ,則G和G為等價文法。,2020/11/8,30,練習：已知語言構(gòu)造文法,GS： S AB A aAb|ab BcB|,LG(S)=wcwR | w(a|b)*,LG(S)=anbnci |n1,i 0,LG(S)=anbncmdm | n 1，m 1 ,GS： S aSd | aAd A bAc | bc,LG(S)=anbmcmdn | n 1, m 1 ,GS： S aSa | bSb | c,GS： S AB A aAb | ab B cBd | cd,2020/11/8,31,32,思考題：設G=

19、(VT=a,b,VN=S,A,B,P,S) P由下列產(chǎn)生式組成（1）SaB|bA （2）Aa|aS|bAA （3）Bb|bS|aBB L(G)=w|wa,b+,且w中有相同個數(shù)的a和b。 用歸納法證明下面結(jié)論（對w的長度） ： (1)S w,當且僅當w中含有相同個數(shù)的a和b。 (2)A w,當且僅當w中a的個數(shù)比b的個數(shù)多一個。 (3)B w,當且僅當w中b的個數(shù)比a的個數(shù)多一個。,*,*,*,2020/11/8,2.6 遞歸規(guī)則與遞歸文法,給定文法，就確定了語言。句子的個數(shù)是有窮還是無窮取決于文法是否遞歸。,1.遞歸規(guī)則：規(guī)則右部有與左部相同的符號 左遞歸規(guī)則：AA 右遞歸規(guī)則：AA 自嵌入

20、遞歸規(guī)則：AA,2.遞歸文法：含有遞歸規(guī)則的文法，為直接遞歸文法,2020/11/8,33,遞歸文法,直接遞歸：若文法中至少包含一條遞歸規(guī)則,則稱文法是直接遞歸的。 間接遞歸：經(jīng)過幾步推導造成文法的遞歸性，則稱為間接遞歸。 例如，有文法為: UVx ， VUy|v 有推導過程U=Vx=Uyx構(gòu)成遞歸。 遞歸文法能用有窮的文法刻畫無窮的語言。 ZaBa BbB|b,2020/11/8,34,令GS是一文法，是文法G的一個句型。 (1) 如果有SA 且 A，則稱是句型相對于非終結(jié)符A的短語。 (2) 若有A，則稱是句型 相對A的簡單短語。 (3) 一個句型的最左簡單短語稱為該句型的句柄。,*,+,

21、2.7 短語、簡單短語和句柄,2.7 短語、簡單短語和句柄,對于文法G, 確定句型1的短語、簡單短語和句柄。 解：首先構(gòu)造句型1的推導過程如下： 1 1)由于 ,而 1, 對照定義，子串1是由非終結(jié)符號推出的，所以是相對的短語。 2) 由于 ,而 數(shù)字串1,所以子串1是相對的短語。 3) 由于 ,而1，且1是由非終結(jié)符號直接推出的，所以子串1是相對的短語,而且是簡單短語。 在句型1中,只有一個簡單短語1,所以是該句型的句柄。,2020/11/8,36,* ,+ ,* ,+ ,* ,例：文法GE：,E T | E+T T F | TF F( E ) | i,求句型iii的短語，簡單短語和句柄。,

22、記ii+i 為i1i2+i3 EFi2+i3 且F i1，i1是句型i1i2+i3的相對非終結(jié)符F的短語和簡單短語，而且是句柄。,*, i1 i2+i3 (=, = i1, = i2+i3 ) A Fi2+i3 (=, A= F, = i2+i3 ) A F i1,E T | E+T T F | TF F( E ) | i,EE+T T+T TF+T FF+T FF+F FF+i3 Fi2+i3 i1i2+i3,記ii+i 為i1i2+i3 Ei1F+i3 且Fi2，i2是句型i1i2+i3的相對非終結(jié)符F的短語和簡單短語。,*, i1 i2+i3 (= i1 , = i2, = +i3 )

23、A i1F+i3 (= i1 , A= F, = +i3 ) A F i2,E T | E+T T F | TF F( E ) | i,EE+T T+T TF+T FF+T FF+F FF+i3 i1F+i3 i1i2+i3,Ei1 i2 + F且Fi3，i3是句型i1i2+i3的相對非終結(jié)符F的短語和簡單短語。, i1i2+i3 (=i1i2+, = i3, = ) A i1i2+F (=i1i2+, A= F, = ) A F i3,E T | E+T T F | TF F( E ) | i,EE+T T+T TF+T FF+T FF+F Fi2+F i1i2+F i1i2+i3,ETi2

24、+i3 且Ti1，i1是句型i1i2+i3的相對于T的短語。,*,+, i1i2+i3 (=, = i1, = i2+i3 ) A Ti2+i3 (=, A= T, = i2+i3 ) A T i1,E T | E+T T F | TF F( E ) | i,+,EE+T T+T TF+T TF+F Ti2+F Ti2+i3 Fi2+i3 i1i2+i3,E i1 i2+T 且Ti3，i3是句型i1i2+i3的相對于T的短語。,*,+, i1i2+i3 (=i1i2+, = i3, = ) A i1 i2+T (=i1i2+, A= T, = ) A T i3,E T | E+T T F |

25、TF F( E ) | i,+,EE+T T+T TF+T FF+T i1F+T i1i2+T i1i2+F i1i2+i3,ET+i3 且T i1i2 ，i1 i2是句型i1i2+i3相對于T的短語。,*, i1i2+i3 (=, = i1i2, = +i3 ) A T+i3 (=, A= T, = +i3 ) A T i1i2,E T | E+T T F | TF F( E ) | i,+,EE+T T+T T+F T+i3 TF+i3 FF+i3 i1F+i3 i1i2+i3,EE+i3 且 Ei1i2， 則i1i2是句型i1i2+i3相對于E的短語。,*, i1i2+i3 (=, =

26、i1i2, = +i3 ) A E+i3 (=, A= E, = +i3 ) A E i1i2,E T | E+T T F | TF F( E ) | i,+,EE+T E+F E+i3 T+i3 TF+i3 FF+i3 i1F+i3 i1i2+i3,i1，i2，i3，i1i2和i1i2+i3都是句型i1i2+i3的短語，且i1，i2，i3均為簡單短語，其中i1是最左簡單短語（句柄） 問題：如何有效的找出所有短語？,EE 且 Ei1i2+i3，i1i2+i3是句型i1i2+i3相對于E的短語。,*,+, i1i2+i3 (= , = i1i2 +i3, = ) AE (= , A= E, =

27、) A E i1i2 +i3,E T | E+T T F | TF F( E ) | i,+,EE+T E+F E+i3 T+i3 TF+i3 FF+i3 i1F+i3 i1i2+i3,2020/11/8,46,練習：G=( S,A,a,b,P,S )，其中P為：,S aAS A SbA A SS S a A ba,SaAS aAa aSbAa aSbbaa aabbaa 求句子的短語、簡單短語，句柄。,2.8 語法樹,設G=（VN，VT，P，S）,G的一棵語法樹滿足如下條件： 1. 每個結(jié)點有一個標記，此標記是VTVN中的符號。 2根的標記是S。 3如果一個結(jié)點是內(nèi)部結(jié)點，其標記A必在VN中

28、。 4如果編號為n的結(jié)點有標記A,結(jié)點n1,n2,nk是點n的從左到右的兒子并分別有標記X1,X2,Xk，則AX1X2Xk必須是P中的產(chǎn)生式,2020/11/8,47,48,例 G=(VN，VT，P，S), 其中 P: SaASa A SbA SS ba,3,1,2,4,6,5,7,8,9,10,11,S,a,A,S,S,b,A,a,a,b,a,2020/11/8,49,根據(jù)推導序列，對每步推導畫相應分枝,A,S,a,S,b,S,A,a,a,b,a,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,畫出語法樹 (自頂向下）,2020/11/8,P: SaASa A SbA SSb

29、a,該推導是最左推導，由其最右推導構(gòu)造的語法樹是否相同？,50,根據(jù)歸約序列，對每步歸約畫相應分枝,A,S,a,S,b,S,A,a,a,b,a,aAa,aSbAa,aSbbaa,aabbaa,aAS,S,畫出語法樹 (自底向上）,2020/11/8,P: SaASa A SbA SSba,51,1. 一個句型推導用一棵樹結(jié)構(gòu)圖示，反映一個句子語法結(jié)構(gòu)的層次。 2. 對于一個句子的多種推導（若文法是無二義性的），采用各種推導過程，畫出的語法樹相同。 3. 用畫語法樹的過程解釋語法分析過程，用語法樹圖解語法結(jié)構(gòu)。,關(guān)于語法樹的幾點說明,2020/11/8,2.9 子樹與短語,語法樹的子樹是由該樹的

30、某個節(jié)點（子樹的根）連同其所有的后裔構(gòu)成。,S,A,b,S,a,S,b,a,A,a,a,2020/11/8,52,用子樹解釋短語，簡單短語，句柄,子樹與短語一一對應，原則上語法樹中有多少棵子樹，就有多少個短語。 短語：一棵子樹的所有葉子節(jié)點自左至右排列起來形成一個相對于子樹根的短語。 簡單短語：僅有父子兩代的一棵子樹，其所有葉子節(jié)點自左至右排列起來所形成的符號串。 句柄：一個句型的語法樹中最左那棵只有父子兩代的子樹的所有葉子節(jié)點的自左至右排列。,2020/11/8,53,例2.8 根據(jù)文法G，找句子123的短語、簡單短語和句柄。 解：首先畫出產(chǎn)生句子123的語法樹。,2020/11/8,54,

31、 | 0|1|2|3|4|5|6|7|8|9,子樹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é)點都是父子關(guān)系，所以這幾個子樹的末端節(jié)點形成的短語1、2、3都是簡單短語。而子樹5位于其中的最左端，所以短語1還是句柄。,2020/11/8,55,練習：文法GE：,E T | E+T T F

32、 | TF F( E ) | i,求句型iii的短語，簡單短語和句柄。,求句型iii的短語,簡單短語和句柄。,2020/11/8,57,E T | E+T T F | TF F( E ) | i,i1，i2，i3，i1i2和i1i2+i3都是句型i1i2+i3的短語，且i1，i2，i3均為簡單短語，其中i1是最左簡單短語（句柄）,2.10 由樹構(gòu)造推導過程,根據(jù)已有的語法樹，即可從上而下、也可從下到上建立推導。 從上而下：從樹根開始由上而下逐層地用子節(jié)點代替父節(jié)點；當一層中有多棵子樹根時，原則上可任選一棵；若每次都替換最右邊的樹根，則構(gòu)造出的推導是規(guī)范推導（最右推導）。 由下而上：逐層地修剪子

33、樹末端節(jié)點來建立推導；當有多棵子樹時，原則上可任意修剪一棵；若每次都修剪最左邊的子樹，則稱為“最左歸約”或“規(guī)范歸約”。 規(guī)范推導（最右推導）與規(guī)范歸約（最左歸約）互為逆過程。,2020/11/8,58,例：G句型10, , 0, 0,10,規(guī)范推導,2020/11/8,59,10,規(guī)范規(guī)約與規(guī)范推導互為逆過程,2020/11/8,60,61,1、描述一個句子的文法不是唯一的； 2、對于一個句子的分析應是唯一的。 考慮下面的表達式文法 GE,其產(chǎn)生式如下： EE+EE*E (E) a 對于句子a+a*a, 有如下兩個最左推導： EE+E a+E a+E*E a+a*E a+a*a E E*E

34、E+E*E a+E*E a+a*E a+a*a 如果對文法的某個句子或句型，存在兩棵不同的語法樹，那么這個句子或句型是二義性的，則該文法是二義性文法。,2.11文法的二義性,2020/11/8,62,EE+E a+E a+E*E a+a*E a+a*a,E E*EE+E*E a+E*Ea+a*E a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最左推導,2020/11/8,63,EE+E E+E*E E+E*a E+a*a a+a*a,E E*EE*a E+E*aE+a*a a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,

35、E,a,a,a,最右推導,2020/11/8,2.11 文法的二義性,例2.10 IF語句文法如下： IFTHEN |IFTHENELSE | 說明該文法是二義性文法。 解：假設有一個IF語句嵌套的句型為： IFTHEN IFTHENELSE 根據(jù)文法可構(gòu)造兩棵語法樹：,2020/11/8,64,2.11 文法的二義性,圖2.3(a) IF語句語法樹1,圖2.3(b) IF語句語法樹2,由于這兩棵語法樹不同，該文法是二義性文法。圖2.3(a)IF語句的語法樹意味著ELSE和第2個IF配對（就近配對），而圖2.3(b)IF語句的語法樹表示ELSE和第1個IF配對。,2020/11/8,65,可以

36、采用兩種途徑來解決文法的二義性問題 不改變文法中原有的規(guī)則，僅加進一些語法的非形式規(guī)定。例如：規(guī)定“*”運算優(yōu)先級高于“+”運算，且服從左結(jié)合 改寫文法，把排除二義性的規(guī)則合并到原有文法中,例2.11，改寫文法GE： E E+E | E*E |（E）| i，使其無二義性。 解：新添非終結(jié)符號T和F，將文法寫成： E T |E+T，T F |T*F，F(xiàn) (E) | i 用改寫后的文法給出句i+i*i的語法樹如圖。此時的語法樹是唯一的。,2020/11/8,66,2.12 有關(guān)文法的實用限制,實用限制就是從實用的觀點出發(fā)，對文法做一些必要的限制。 文法不能是二義性的 不能有U U這樣的有害規(guī)則。 不能有多余規(guī)則：一是推導中始終用不到的規(guī)則。二是一旦使用某規(guī)則后無法推出終結(jié)符號的規(guī)則。 多余規(guī)則不滿足以下兩個條件： 1) U必須在某個句型中出現(xiàn)，即有：Z xUy 2) 必須能夠從U推導出終結(jié)符號串，即U t，tVt*,2020/11/8,67,* ,+ ,2.12 有關(guān)文法的實用限制,例：有文法：Z Aa，A Ca|Bb，B Ba|a，C Cb ，D b ， 去掉有害規(guī)