《文法和語(yǔ)言》PPT課件.ppt

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

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

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

4、號(hào)串。 例如： x = ab，y = ba，則 xy = abba 注意：連接沒(méi)有交換律，即 xy yx 而對(duì)于空串有 x=x=x,2020/11/8,7,7.集合的乘積運(yùn)算：令A(yù)、B為兩個(gè)符號(hào)串集合，A和B的乘積AB定義為： AB=xy|xA，yB 例如：A=a，b B=c，d，則AB=ac，ad，bc，bd 對(duì)于空集合有有： A=A=A 8.符號(hào)串的冪運(yùn)算：若x是符號(hào)串，則x的冪運(yùn)算定義為： 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.集合的冪運(yùn)算：設(shè)A為符號(hào)

5、串集合，則A的冪運(yùn)算定義為： 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.集合的正閉包和集合的閉包：設(shè)A為一個(gè)集合，則集合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 文法,文法是描述語(yǔ)言語(yǔ)法結(jié)構(gòu)的形式規(guī)則。 文法需要

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

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

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

9、如1、2 、n，可縮寫(xiě)為: 1|2 |n 上例文法的13條規(guī)則可縮寫(xiě)成： | 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.元符號(hào)“”：用于括起由中文字組成的非終結(jié)符號(hào)或由多個(gè)字母組成的符號(hào)。如、等。 3.元符號(hào)“”和“”：表示可重復(fù)連接，tnm表示符號(hào)串t可重復(fù)連接n到m次，而t表示符號(hào)串t可重復(fù)連接0到無(wú)窮次。例如， 13 與 | 相同 EE+T|T 與 ET+T相同 而字母打頭、后面可跟數(shù)字或字母的不超過(guò)8個(gè)字符的標(biāo)識(shí)符文法則為

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

11、, ,直接推導(dǎo)的定義 (1) 是文法G=(VN ,VT ,P,S)的規(guī)則，和是(VN VT )*中的任意符號(hào),若有符號(hào)串V,W滿(mǎn)足： V=，W 則說(shuō)V是直接產(chǎn)生W 或W是V的直接推導(dǎo) 或W直接歸約到V,記作 V W,2.3 推導(dǎo),推導(dǎo)：用產(chǎn)生式右部替代左部,V=S，W0S1 W是否是V的直接推導(dǎo) 直接推導(dǎo)：S 0S1 V=0S1，W=00S11 W是否是V的直接推導(dǎo) 直接推導(dǎo)： 0S100S11,例：文法G =（VN ,VT ,P，S）, 其中 VN=S，VT =0，1， P=S 0S1，S 01 V0S1，W=0011 W是否是V的直接推導(dǎo) 直接推導(dǎo)：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,+,+,*,若存在直接推導(dǎo)的序列： V=W0 W1 W2 Wn W (n0) 則 稱(chēng)V推導(dǎo)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,請(qǐng)構(gòu)造aabbaa的推導(dǎo)過(guò)程,（1）每次替換最右邊非終結(jié)符 SaAS aAa aSbAa aSbbaa aabbaa （2）每次替換最左邊非終結(jié)符 SaAS aSbASaabASaabbaSaabbaa （3）無(wú)固定的推導(dǎo)方向 SaAS aSbASaSbAaaabAaaabbaa,每步推導(dǎo)只能替換一個(gè)非終結(jié)符,2020/11/8,23,練習(xí)： 文法GS=(S, A, B,a, b, c, d, e, S aAcBe A b A Ab B d,S） 構(gòu)符號(hào)串a(chǎn)bbcde的推導(dǎo)過(guò)程,S aAcBe aAbcBe abbcBe abbcde,S aAcBe aAcde aAbcde abbcde

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

15、所有終結(jié)符 號(hào)組成的句型,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ī)范推導(dǎo)產(chǎn)生的句型。每個(gè)句子都有一個(gè)規(guī)范推導(dǎo),但并非每個(gè)句型都有規(guī)范推導(dǎo)。 例如，對(duì)文法： ； |； 0|1|2|3|4|5|6|7|8|9 有句型“2”,其推導(dǎo)過(guò)程如下: 2 第步推導(dǎo)變換的不是最右邊非終結(jié)符號(hào)，故句型“2”不是規(guī)范句型。 對(duì)于句型“3”，其推導(dǎo)過(guò)程如下: = =3 =3 每一步推導(dǎo)都變換的是最右邊非終結(jié)符號(hào)，故句型“3”是規(guī)范句型。,2020/11/8

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

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

18、唯一確定語(yǔ)言，反之不成立！ 定義： G和G是兩個(gè)不同的文法，若 L(G) = L(G) ,則G和G為等價(jià)文法。,2020/11/8,30,練習(xí)：已知語(yǔ)言構(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,思考題：設(shè)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中有相同個(gè)數(shù)的a和b。 用歸納法證明下面結(jié)論（對(duì)w的長(zhǎng)度） ： (1)S w,當(dāng)且僅當(dāng)w中含有相同個(gè)數(shù)的a和b。 (2)A w,當(dāng)且僅當(dāng)w中a的個(gè)數(shù)比b的個(gè)數(shù)多一個(gè)。 (3)B w,當(dāng)且僅當(dāng)w中b的個(gè)數(shù)比a的個(gè)數(shù)多一個(gè)。,*,*,*,2020/11/8,2.6 遞歸規(guī)則與遞歸文法,給定文法，就確定了語(yǔ)言。句子的個(gè)數(shù)是有窮還是無(wú)窮取決于文法是否遞歸。,1.遞歸規(guī)則：規(guī)則右部有與左部相同的符號(hào) 左遞歸規(guī)則：AA 右遞歸規(guī)則：AA 自嵌入

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

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

22、記ii+i 為i1i2+i3 EFi2+i3 且F i1，i1是句型i1i2+i3的相對(duì)非終結(jié)符F的短語(yǔ)和簡(jiǎn)單短語(yǔ)，而且是句柄。,*, 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的相對(duì)非終結(jié)符F的短語(yǔ)和簡(jiǎn)單短語(yǔ)。,*, 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的相對(duì)非終結(jié)符F的短語(yǔ)和簡(jiǎn)單短語(yǔ)。, 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的相對(duì)于T的短語(yǔ)。,*,+, 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的相對(duì)于T的短語(yǔ)。,*,+, 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相對(duì)于T的短語(yǔ)。,*, 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相對(duì)于E的短語(yǔ)。,*, 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的短語(yǔ)，且i1，i2，i3均為簡(jiǎn)單短語(yǔ)，其中i1是最左簡(jiǎn)單短語(yǔ)（句柄） 問(wèn)題：如何有效的找出所有短語(yǔ)？,EE 且 Ei1i2+i3，i1i2+i3是句型i1i2+i3相對(duì)于E的短語(yǔ)。,*,+, 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,練習(xí)：G=( S,A,a,b,P,S )，其中P為：,S aAS A SbA A SS S a A ba,SaAS aAa aSbAa aSbbaa aabbaa 求句子的短語(yǔ)、簡(jiǎn)單短語(yǔ)，句柄。,2.8 語(yǔ)法樹(shù),設(shè)G=（VN，VT，P，S）,G的一棵語(yǔ)法樹(shù)滿(mǎn)足如下條件： 1. 每個(gè)結(jié)點(diǎn)有一個(gè)標(biāo)記，此標(biāo)記是VTVN中的符號(hào)。 2根的標(biāo)記是S。 3如果一個(gè)結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)，其標(biāo)記A必在VN中

28、。 4如果編號(hào)為n的結(jié)點(diǎn)有標(biāo)記A,結(jié)點(diǎn)n1,n2,nk是點(diǎn)n的從左到右的兒子并分別有標(biāo)記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ù)推導(dǎo)序列，對(duì)每步推導(dǎo)畫(huà)相應(yīng)分枝,A,S,a,S,b,S,A,a,a,b,a,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,畫(huà)出語(yǔ)法樹(shù) (自頂向下）,2020/11/8,P: SaASa A SbA SSb

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

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

31、 | 0|1|2|3|4|5|6|7|8|9,子樹(shù)1：樹(shù)根，葉節(jié)點(diǎn)1、2、3，短語(yǔ)為123 子樹(shù)2：樹(shù)根，葉節(jié)點(diǎn)1、2、3，短語(yǔ)為123 子樹(shù)3：樹(shù)根，葉節(jié)點(diǎn)1、2，短語(yǔ)為12 子樹(shù)4：樹(shù)根，葉節(jié)點(diǎn)1，短語(yǔ)為1 子樹(shù)5：樹(shù)根，葉節(jié)點(diǎn)1，短語(yǔ)為1，且為簡(jiǎn)單短語(yǔ)、句柄 子樹(shù)6：樹(shù)根，葉節(jié)點(diǎn)2，短語(yǔ)為2，且為簡(jiǎn)單短語(yǔ) 子樹(shù)7：樹(shù)根，葉節(jié)點(diǎn)3，短語(yǔ)為3，且為簡(jiǎn)單短語(yǔ) 7個(gè)子樹(shù)中，只有子樹(shù)5、6、7的根節(jié)點(diǎn)與末端節(jié)點(diǎn)都是父子關(guān)系，所以這幾個(gè)子樹(shù)的末端節(jié)點(diǎn)形成的短語(yǔ)1、2、3都是簡(jiǎn)單短語(yǔ)。而子樹(shù)5位于其中的最左端，所以短語(yǔ)1還是句柄。,2020/11/8,55,練習(xí)：文法GE：,E T | E+T T F

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

33、樹(shù)末端節(jié)點(diǎn)來(lái)建立推導(dǎo)；當(dāng)有多棵子樹(shù)時(shí)，原則上可任意修剪一棵；若每次都修剪最左邊的子樹(shù)，則稱(chēng)為“最左歸約”或“規(guī)范歸約”。 規(guī)范推導(dǎo)（最右推導(dǎo)）與規(guī)范歸約（最左歸約）互為逆過(guò)程。,2020/11/8,58,例：G句型10, , 0, 0,10,規(guī)范推導(dǎo),2020/11/8,59,10,規(guī)范規(guī)約與規(guī)范推導(dǎo)互為逆過(guò)程,2020/11/8,60,61,1、描述一個(gè)句子的文法不是唯一的； 2、對(duì)于一個(gè)句子的分析應(yīng)是唯一的。 考慮下面的表達(dá)式文法 GE,其產(chǎn)生式如下： EE+EE*E (E) a 對(duì)于句子a+a*a, 有如下兩個(gè)最左推導(dǎo)： 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 如果對(duì)文法的某個(gè)句子或句型，存在兩棵不同的語(yǔ)法樹(shù)，那么這個(gè)句子或句型是二義性的，則該文法是二義性文法。,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,最左推導(dǎo),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,最右推導(dǎo),2020/11/8,2.11 文法的二義性,例2.10 IF語(yǔ)句文法如下： IFTHEN |IFTHENELSE | 說(shuō)明該文法是二義性文法。 解：假設(shè)有一個(gè)IF語(yǔ)句嵌套的句型為： IFTHEN IFTHENELSE 根據(jù)文法可構(gòu)造兩棵語(yǔ)法樹(shù)：,2020/11/8,64,2.11 文法的二義性,圖2.3(a) IF語(yǔ)句語(yǔ)法樹(shù)1,圖2.3(b) IF語(yǔ)句語(yǔ)法樹(shù)2,由于這兩棵語(yǔ)法樹(shù)不同，該文法是二義性文法。圖2.3(a)IF語(yǔ)句的語(yǔ)法樹(shù)意味著ELSE和第2個(gè)IF配對(duì)（就近配對(duì)），而圖2.3(b)IF語(yǔ)句的語(yǔ)法樹(shù)表示ELSE和第1個(gè)IF配對(duì)。,2020/11/8,65,可以

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