第3章文法和語言

1、 當(dāng)我們表述一種語言時(shí)，無非是說明這種語言當(dāng)我們表述一種語言時(shí)，無非是說明這種語言的句子，如果語言只含有有窮多個(gè)句子，則只需列的句子，如果語言只含有有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。言來講，存在著如何給出它的有窮表示的問題。3.1 文法的直觀概念 以自然語言為例，人們無法列出全部句子，但以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說明是人們可以給出一些規(guī)則，用這些規(guī)則來說明(或者或者定義定義)句子的組成結(jié)構(gòu)，比如漢語句子可以是由主語句子的組成結(jié)構(gòu)

2、，比如漢語句子可以是由主語后隨謂語而成，構(gòu)成謂語的是動(dòng)詞和直接賓語，我后隨謂語而成，構(gòu)成謂語的是動(dòng)詞和直接賓語，我們采用們采用EBNF來表示這種句子的構(gòu)成規(guī)則。來表示這種句子的構(gòu)成規(guī)則。BNF范式和語法圖1. 巴科斯范式:EBNF| 你|我|他王明|大學(xué)生|工人是|學(xué)習(xí) |帶的叫非終止符,不帶的叫終止符。True|False 例子： 我 我 我是 我是 我是大學(xué)生 “我是大學(xué)生我是大學(xué)生”的構(gòu)成符合上述規(guī)則，的構(gòu)成符合上述規(guī)則，而而“我大學(xué)生是我大學(xué)生是”不符合上述規(guī)則，我們不符合上述規(guī)則，我們說它不是句子。這些規(guī)則成為我們判別句說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話

3、說，這些子結(jié)構(gòu)合法與否的依據(jù)，換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。規(guī)則看成是一種元語言，用它描述漢語。這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中這里僅僅涉及漢語句子的結(jié)構(gòu)描述。其中一種描述元語言稱為文法。一種描述元語言稱為文法。語言概述語言概述 語言是由句子組成的集合，是由一組符語言是由句子組成的集合，是由一組符號所構(gòu)成的集合。號所構(gòu)成的集合。 漢語漢語-所有符合漢語語法的句子的全體所有符合漢語語法的句子的全體 英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體 程序設(shè)計(jì)語言程序設(shè)計(jì)語言-所有該語言的程序的全體所有該語言的程序的全體研究語言內(nèi)容包括：研究語言內(nèi)容包括：

4、每個(gè)句子構(gòu)成的規(guī)律每個(gè)句子構(gòu)成的規(guī)律 每個(gè)句子的含義每個(gè)句子的含義 每個(gè)句子和使用者的關(guān)系每個(gè)句子和使用者的關(guān)系研究程序設(shè)計(jì)語言研究程序設(shè)計(jì)語言 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系每個(gè)程序和使用者的關(guān)系語言研究的三個(gè)方面語言研究的三個(gè)方面 語法語法 Syntax 語義語義 Semantics 語用語用 Pragmatics語法語法 - 表示構(gòu)成語言句子的各個(gè)記號之間表示構(gòu)成語言句子的各個(gè)記號之間的組合規(guī)律的組合規(guī)律語義語義 - 表示各個(gè)記號的特定含義。（各個(gè)表示各個(gè)記號的特定含義。（各個(gè)記號和記號所表示的對象之間的關(guān)系）記號和記號所表示的

5、對象之間的關(guān)系）語用語用 -表示在各個(gè)記號所出現(xiàn)的行為中，表示在各個(gè)記號所出現(xiàn)的行為中，它們的來源、使用和影響。它們的來源、使用和影響。 每種語言具有兩個(gè)可識別的特性，即語言每種語言具有兩個(gè)可識別的特性，即語言的形式和該形式相關(guān)聯(lián)的意義。的形式和該形式相關(guān)聯(lián)的意義。 語言的實(shí)例若在語法上是正確的，其相關(guān)語言的實(shí)例若在語法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來看，其一是該句子聯(lián)的意義可以從兩個(gè)觀點(diǎn)來看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱為語言的語義，

6、后者是其語用意義。幽前者稱為語言的語義，后者是其語用意義。幽默、雙關(guān)語和謎語就是利用這兩方面意義間的默、雙關(guān)語和謎語就是利用這兩方面意義間的差異。差異。 如果不考慮語義和語用，即只從語法這如果不考慮語義和語用，即只從語法這一側(cè)面來看語言，這種意義下的語言稱作形一側(cè)面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個(gè)數(shù)學(xué)系式語言。形式語言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。統(tǒng)?！靶问叫问健笔侵高@樣的事實(shí)：語言的所有是指這樣的事實(shí)：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述。形式語言理論是對符號串集合的表示法、結(jié)形式語言理論是對符號串集合的表示法、結(jié)構(gòu)

7、及其特性的研究。是程序設(shè)計(jì)語言語法分構(gòu)及其特性的研究。是程序設(shè)計(jì)語言語法分析研究的基礎(chǔ)。析研究的基礎(chǔ)。例子:整數(shù)(1)單個(gè)數(shù)字是整數(shù) (2)整數(shù)再接上數(shù)字仍是整數(shù)用BNF范式表示: 0|1|2|9 |所以合起來有： | 0|1|2|9 標(biāo)識符:以字母開頭以后由字母和數(shù)字組成的符號串。例子：的巴科斯范式 a|b|z 0|1|9例子：判定字符串a(chǎn)4y是 y y 4y 4y a4y2、語法圖 作用：直觀、形象的描述語法規(guī)則。例子：標(biāo)識符的語法圖表示標(biāo)識符字母字母數(shù)字例子：無符號數(shù)的語法圖表示 2.45E+12無符號數(shù)無符號整數(shù)數(shù)字E E無符號整數(shù)1、字母表:它是非空有窮集。 例如：=a,b,c或=1

8、,2,32、符號：字母表中的元素稱為符號。3、符號串：符號的有窮序列，符號串也稱為字。用來表示空符號串。 例如：a,ab,abc,dsfsd4、長度：符號串的長度是指該串所包含的符號個(gè)數(shù)。用|x|表示符號串x的長度。 例如：|a|=1，|abn|=35、連結(jié)：設(shè)x和y為符號串，則稱xy 為他們的連結(jié)。 例如：x=aa,y=bb,則xy=aabb6、空集：不含任何元素的集合,記為。7、乘積：設(shè)A和B是符號串集，則用AB表示A和B的乘積。A=a,b,B=c,d,則AB=ac,ad,bc,bd8、方冪：設(shè)A為符號串集，則定義 A0= A1=A An=An-1 A 例如：A=a,b 則有： A0= A

9、1=a,b A2=aa,ab,ba,bb9、正閉包：設(shè)A為符號串集，則用A+表示A的正閉包，其具體定義如下： A+=A1A2A3 例如：A=a,A+=a,aa,aaa,10、星閉包：設(shè)A為一集合，則定義A的星閉包為A* ，其具體定義如下A*=A0A+例如：A=a,A*=,a,aa,aaa,一、引言 例子： y:=a+b*x 3.3 3.3 文法與語言的形式定義文法與語言的形式定義 語法：賦值語句由變量加“:=”加表達(dá)式構(gòu)成。 語義：右邊表達(dá)式求值與左變量結(jié)合賦值。 用途：表達(dá)式的值的保存和計(jì)算。 形式化方法：用一整套帶有嚴(yán)格規(guī)定的符號體系來描述問題的理論和方法。 表示文法需要一種工具，其中最常

10、用的工具是所謂的巴克斯范式(BNF)。例子: A=an|n1 A=a2n|n1 其BNF表示有： 其BNF表示有： (1) Aa|aA (1) Aaa|aaA (2) Aa|Aa (2) Aaa|Aaa例子： A=abna|n1 其BNF表示有多種如下： (1) AaBa Bb|Bb (2) AaBa Bb|bB (3) AaB Bba|bB如何來描述一種語言？如何來描述一種語言？如果語言是有窮的（只含有有窮多個(gè)句子），可以如果語言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來表示將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的如果語言是無窮的，找出語言的有窮表示。語言的

11、有窮表示有兩個(gè)途經(jīng)：有窮表示有兩個(gè)途經(jīng)： 生成方式生成方式 （文法）：語言中的每個(gè)句子可以用嚴(yán)（文法）：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。格定義的規(guī)則來構(gòu)造。 識別方式識別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一任（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答并回答“是是”，若不屬于，要麼能停止并回答，若不屬于，要麼能停止并回答“不不是是”，（要麼永遠(yuǎn)繼續(xù)下去。），（要麼永遠(yuǎn)繼續(xù)下去。） 文法即是生成方式描述語言的：語言中的文法即是生成方式描述語言的：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造每個(gè)句子可

12、以用嚴(yán)格定義的規(guī)則來構(gòu)造.下面給出文法的定義下面給出文法的定義.進(jìn)而在文法的定義進(jìn)而在文法的定義的基礎(chǔ)上的基礎(chǔ)上,給出推導(dǎo)的概念給出推導(dǎo)的概念,句型、句子和句型、句子和語言的定義語言的定義.定義定義文法G定義為四元組(VN，VT，P，S )其中VN為非終結(jié)符號(或語法實(shí)體，或變量)集；VT為終結(jié)符號集；P為產(chǎn)生式(也稱規(guī)則)的集合； VN，VT和P是非空有窮集。 S稱作識別符號或開始符號，它是一個(gè)非終結(jié)符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 VN和VT不含公共的元素，即VN VT = 用V表示VN VT ，稱為文法G的字母表或字匯表規(guī)則規(guī)則，也稱重寫規(guī)則重寫規(guī)則、產(chǎn)生式產(chǎn)生式或生成式生成式，是

13、形如或 =的(，)有序?qū)?，其中是字母表V的正閉包V+中的一個(gè)符號，是V*中的一個(gè)符號。稱為規(guī)則的左部，稱作規(guī)則的右部。文法的定義文法的定義例例 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號為開始符號例例 文法文法G=（VN，VT，P，S）VN =標(biāo)識符，字母，數(shù)字標(biāo)識符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, zz 0, 0, 99 S表示表示，是初始符號，是初始符號文法的寫法文法的寫法 1 G1 G：SaASaAb Aab Aab AaA AaAb A A 2 GS 2 GS： SaASaAb Aab

14、AaA Aab AaAb A A 3 GSGS： SaASaAb Aab |aA Aab |aAb | |二、文法和語言形式定義1、規(guī)則式，產(chǎn)生式例子例子： Bb|Bb Aa|A2、文法GZ：規(guī)則的非空有窮集合。Z：識別符號，開始符號。V：字母表，符號集合。例子例子：GS=S0，S，1 VS，0，1定義3.1 文法是一個(gè)四元組 G(VN，VT，P，Z)。 非終極符集記為VN(大寫字母) 終極符集記為VT(小寫字母) 產(chǎn)生式集記為P 初始符記為Z例子：自然數(shù)G1(VN,VT,P,Z)和標(biāo)識符G2(VN,VT,P,I)VN= N,D VT= 0,1,2,9P= ND|ND, D0|1|2|9 G1

15、：ND|ND D0|1|2|9標(biāo)識符G2(VN,VT,P,I)VN= I,D,L VT= 0,1,2,9,a,bzP= IL|IL|ID,La|b|z D0|1|2|9 G2：IL|IL|ID La|b|c|z D0|1|2|9定義3.21、直接推導(dǎo)：設(shè)x和y是符號串，若用一次產(chǎn)生式可從x導(dǎo)出y，則稱y為x的直接推導(dǎo)，并記為xy。 例子：x=Ab,y=ab,Aa,Abab2、推導(dǎo)：若用若干次產(chǎn)生式可從x串導(dǎo)出y串，則稱y為x的推導(dǎo)，并記為x y。+ 例子：X=AB,Aa,Bb ABaBab 即：AB ab +*3、星推導(dǎo):x y (當(dāng)且僅當(dāng)x=y或x y)。 例子：ABAB 0步 ABaB 1

16、步 AB ab 2步 即：AB ab +*+4、句型：稱x為句型，若有Z x，其中Z是文法的開始符。凡是由初始符推出的任意符號集合叫句型。例子：ZAB,Aa,Z aB5、句子: 稱x為句子，若有Z x，且x中不包含非終極符的句型。不包含非終極符的句型叫句子。* 例子：GS:S0S1 S01解: S0S1 00S11 000111所以有:S=01,0011,000111 L(G)=0n1n|n16、語言:所有句子的集合稱為語言。設(shè)是G給定文法，Z是開始符，則語言L(G)可描述如下：定義3.3 設(shè)G1,G2為給定文法，如果L(G1)=L(G2),則稱G1和G2等價(jià)。L(G)=x|Z x,xVT*

17、*例1 已知文法求語言并判斷是否等價(jià) G1=(VN,VT,P,A) G2=(VN,VT,P,Z) VN=A VN=A,B VT=a,b VT=a,b P=Aab P=ABb,BaA1ab L(G1)=abA2Bbab L(G2)=ab G1與G2是等價(jià)的。例2: G3S: SA|S-A Aa|b|c G4S: SA|A-S Aa|b|c推導(dǎo)過程如下：SS-ASS-AAabcS-AS-A-AA-A-Aa-b-c G3與G4等價(jià)，但G3與G4的語義不同。推導(dǎo)過程如下：SA-SSA-SAA-SA-A-SA-A-Aa-b-cabca-b-c和a-b-c文法的等價(jià)文法的等價(jià)若若L（G1）=L（G2），則

18、稱文法），則稱文法G1和和G2是等是等價(jià)的。價(jià)的。如文法如文法G G1AA：A0R A0R 與與G G2SS：S0S1 S0S1 等價(jià)等價(jià) A01 S01A01 S01 RA1 RA1定義3.4 F 0型文法(短語結(jié)構(gòu)文法):產(chǎn)生式為：，其中和是符號串。F 1型文法(上下文有關(guān)文法)：產(chǎn)生式為：Au，其中AVN，u為非空串。 F 2型文法(上下文無關(guān)文法): A，其中AVN，為非空串。3.4 3.4 文法的類型文法的類型 F 3型文法(正則文法):產(chǎn)生式為：Aa,AbB,其中A,BVN, #a,bVT是符號串。例子: GZ:Za ZaA Ab|bB Bb所以:GZ是3型文法 文法的類型文法的類

19、型例：例：1 1型（上下文有關(guān)）文法型（上下文有關(guān)）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabD文法的類型文法的類型例：例：2 2型（上下文無關(guān)）文法型（上下文無關(guān)）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|13型文法型文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d文法的類型文法的類型2型文法型文

20、法1型文法型文法0型文法型文法四種文法之間的逐級四種文法之間的逐級“包含包含”關(guān)系關(guān)系3型文法型文法文法和語言文法和語言0型文法產(chǎn)生的語言稱為型文法產(chǎn)生的語言稱為0型語言型語言1 1型文法或上下文有關(guān)文法（型文法或上下文有關(guān)文法（ CSG ）產(chǎn)生的語言產(chǎn)生的語言稱為稱為1 1型語言型語言或上下文有關(guān)或上下文有關(guān)語言（語言（CSL）2 2型文法或上下文無關(guān)文法（型文法或上下文無關(guān)文法（ CFG ）產(chǎn)生的語言產(chǎn)生的語言稱為稱為2型語言型語言或上下文無關(guān)或上下文無關(guān)語言（語言（ CF L ） 3 3型文法或正則（正規(guī)）文法（型文法或正則（正規(guī)）文法（ RG ）產(chǎn)生的語言產(chǎn)生的語言稱為稱為3型語言型語

21、言正則（正規(guī)）正則（正規(guī)）語言（語言（ RL ） 文法和語言文法和語言 四種文法之間的關(guān)系四種文法之間的關(guān)系 是將產(chǎn)生式做是將產(chǎn)生式做進(jìn)一步限制而定義的。進(jìn)一步限制而定義的。 語言之間的關(guān)系依次：有不是上下語言之間的關(guān)系依次：有不是上下文有關(guān)語言的文有關(guān)語言的0型語言，有不是上下文無型語言，有不是上下文無關(guān)語言的關(guān)語言的1型語言，有不是正則語言的上型語言，有不是正則語言的上下文無關(guān)語言。下文無關(guān)語言。根據(jù)形式語言理論根據(jù)形式語言理論,文法和識別系統(tǒng)間有這文法和識別系統(tǒng)間有這樣的關(guān)系樣的關(guān)系 0型文法（短語結(jié)構(gòu)文法）的能力相當(dāng)于型文法（短語結(jié)構(gòu)文法）的能力相當(dāng)于圖靈機(jī)，可以表征任何遞歸可枚舉集，

22、圖靈機(jī)，可以表征任何遞歸可枚舉集，而且任何而且任何0型語言都是遞歸可枚舉的。型語言都是遞歸可枚舉的。1型文法（上下文有關(guān)文法）：產(chǎn)生式的形型文法（上下文有關(guān)文法）：產(chǎn)生式的形式為式為1 1AA2 21 12 2，即只有，即只有A A出現(xiàn)在出現(xiàn)在1 1和和2 2的上下文中時(shí)，才允許的上下文中時(shí)，才允許取代取代A A。其識別系統(tǒng)是線性界限自動(dòng)機(jī)。其識別系統(tǒng)是線性界限自動(dòng)機(jī)。3型文法（正規(guī)文法型文法（正規(guī)文法RG）：產(chǎn)生的語言是）：產(chǎn)生的語言是有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)（FA）所接受的集合）所接受的集合 2型文法（上下文無關(guān)文法型文法（上下文無關(guān)文法CFG）：產(chǎn)生）：產(chǎn)生式的形式為式的形式為AA，取代取

23、代A A時(shí)與時(shí)與A A的上下的上下文無關(guān)。其識別系統(tǒng)是不確定的下推自文無關(guān)。其識別系統(tǒng)是不確定的下推自動(dòng)機(jī)。動(dòng)機(jī)。 3型文法產(chǎn)生的語言是有窮自動(dòng)機(jī)（型文法產(chǎn)生的語言是有窮自動(dòng)機(jī)（FA）所接）所接受的集合受的集合.定理定理 設(shè)設(shè)G=（VN，VT，P，S）是3 3型文法，則存在一個(gè)有窮自型文法，則存在一個(gè)有窮自 動(dòng)機(jī)動(dòng)機(jī) M=(K, , f, A, Z)M=(K, , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)NFA M NFA M 這樣構(gòu)造：這樣構(gòu)造： = = VT K= K= VN N, NN, N為一個(gè)新狀態(tài)為一個(gè)新狀態(tài), ,它不在它不在VN中 A=

24、S A=S Z=N Z=N 對對G G中的形如中的形如 DtBDtB的產(chǎn)生式的產(chǎn)生式,t,t為終結(jié)符或?yàn)榻K結(jié)符或,有有f(D,t)=Bf(D,t)=B； 對對G G中形如中形如DtDt的產(chǎn)生式，的產(chǎn)生式， t t為終結(jié)符或?yàn)榻K結(jié)符或,有有f(D,t)=N;f(D,t)=N; 對對VT中的每一個(gè)a ,有有f(N,a)=f(N,a)=G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab 使其右部為空字符串的產(chǎn)生式，稱為空產(chǎn)生式。產(chǎn)生式記為A或A例子: GS: SAaB AAB| BbB|所以:GS含有空產(chǎn)生式定義3.5 * 直接左遞歸：若

25、有產(chǎn)生式 AA* 直接右遞歸：若有產(chǎn)生式 AA* 左遞歸：若有推導(dǎo)式 A A* 右遞歸：若有推導(dǎo)式 A A* 遞歸：若有產(chǎn)推導(dǎo) A A +例子：直接遞歸：AAa BaBB左遞歸：SQc|c QRb|b RSa|aQRbSabQcab QQcab規(guī)范推導(dǎo)和句柄定義3.6 F 設(shè)xUyxuy是一直接推導(dǎo)。如果U是句型xUy中的最右非終極字符，則稱該推導(dǎo)為規(guī)范直接推導(dǎo)并記為xUy xuy。F 如果x y中的每步都是規(guī)范直接推導(dǎo)，則稱該推導(dǎo)為規(guī)范推導(dǎo)并記為x y。 r+r+3.5 3.5 上下無關(guān)文法及其語法樹上下無關(guān)文法及其語法樹 F 如果每步都是最右非終極字符，則也稱該規(guī)范推導(dǎo)為最右推導(dǎo)。例子：G

26、S：SAB AAa|bB Ba|SbSABbBBbaB(最左推導(dǎo))SABASbAABbAAabAbBab (最右推導(dǎo)) SABASbbBSbbaSb(非左非右)語法樹與二義性 定義3.8 設(shè)G=(VN,VT,P,S)是給定文法,則稱滿足下面條件的樹為G的一棵語法樹。 每個(gè)結(jié)點(diǎn)都標(biāo)有G的一個(gè)文法符號,且根結(jié)點(diǎn)標(biāo)有初始符S,非葉結(jié)點(diǎn)標(biāo)有非終極符。 如果一個(gè)非葉結(jié)點(diǎn)A有n個(gè)兒子結(jié)點(diǎn)(從左到右)B1,B2,Bn,則AB1B2,Bn一定是G的一個(gè)產(chǎn)生式。 定義3.9* 由某一結(jié)點(diǎn)及其所屬分枝組成的部分樹稱為原樹的一棵子樹。* 只有單層分枝的子樹稱為簡單子樹。例子：ZAB Aa BbcSABacb定義3.

27、7 假設(shè)Z xUy，U u，則稱句型xuy中的u為該句型的短語，其中Z為初始符。 假設(shè)有Z xUy，Uu，則稱句型xuy中的u為該句型的簡單短語。 最左邊的簡單短語稱為句柄。 *+*3.6 3.6 句型的分析句型的分析 例子：GS：SAB AAa AbB Ba BSb 解：SAB bBB baB baSbyBSbuxUU Sb是句型baSb的短語，簡單短語S baB* 解：SAB ASb bBSb baSbyBauxU a是句型baSb的短語，且是簡單短語。US bBSb*yuxU ba是句型baSb的短語，但不是簡單短語。所以：ba, a, Sb 是句型baSb的短語 a, Sb 是句型ba

28、Sb的簡單短語 a 是句型baSb的句柄。US ASb*Aba 解：SABASbbBSbbaSb定理3.1 1、每個(gè)句型都有一棵語法樹，每個(gè)語法樹的葉組成一句型。2、每棵子樹的葉組成短語，每棵簡單子樹的葉組成簡單短語，最左簡單子樹的葉組成句柄。3、用語法樹可證明每個(gè)句子都有一規(guī)范推導(dǎo)。 構(gòu)造語法樹構(gòu)造語法樹GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE + T E + T T E E + T T FE EE+T T+T F+T a+T a+T*F a+F

29、*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E E + T E + T T T T T * * F F F F a F F a a a a a 看不出句型中的符號被替看不出句型中的符號被替代的順序代的順序例子：GS：SAB AAa|bB Ba|Sb 字符串：bBABb短語：bB,AB,ABb簡單短語：bB,AB句柄：bBSABbBbSBA上下文無關(guān)文法的語法樹的用處上下文無關(guān)文法的語法樹的用處用于描述上下文無關(guān)文法用于

30、描述上下文無關(guān)文法句型推導(dǎo)句型推導(dǎo)的的直觀方法直觀方法 例例: GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的語法樹語法樹（推導(dǎo)樹）（推導(dǎo)樹）葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號法符號串串，為，為GS的句型。也把該推導(dǎo)樹稱的句型。也把該推導(dǎo)樹稱為該句型的語法樹。為該句型的語法樹。上下文無關(guān)文法的語法樹上下文無關(guān)文法的語法樹推導(dǎo)過程中推導(dǎo)過程中施用施用產(chǎn)生式產(chǎn)生式的的順序順序 例例: GS:SaASASbAASSSaAba S a

31、A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa 一棵語法樹表示了一個(gè)句型的種種一棵語法樹表示了一個(gè)句型的種種可能的可能的( (但未必是所有的但未必是所有的) )不同推導(dǎo)過程，不同推導(dǎo)過程，包括最左包括最左( (最右最右) )推導(dǎo)。推導(dǎo)。 但是，一個(gè)句型是否只對應(yīng)唯一的但是，一個(gè)句型是否只對應(yīng)唯一的一棵語法樹呢一棵語法樹呢? ?一個(gè)句型是否只有唯一的一個(gè)句型是否只有唯一的一個(gè)最左一個(gè)最左( (最右最右) )推導(dǎo)呢推導(dǎo)呢? ?例：例：GE:GE:E iE iE

32、E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個(gè)不同的最左推導(dǎo)：的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E E*E+E i*E+E i*i+E i*i+i推導(dǎo)推導(dǎo)2：E E*E i*E i*E+E i*i+E i*i+i定義3.10如果一個(gè)文法G存在某個(gè)句子,使得它有兩棵語法樹,則稱G為二義性文法。例子：證明G:EE+E|E*E E(E)|i 是二義性文法。因?yàn)榫渥觟+i*i具有兩棵語法樹分別如

33、圖所示。EEE+i*EEiiEEE+i*EEii例子： 證明 GS: SIf B Then S SIf B Then S Else S是二義性文法。If B1 Then If B2 Then S2 Else S3 該句子具有二義性(其中S表示語句，Sx無條件語句，Bx表示布爾變量) ，分析情況如下：If B1 Then If B2 Then S2 Else S3If x1 then if x2 then y:=a else y:=b解釋1:If x1 then if x2 then y:=a else y:=bif x2 then y:=a else y:=b解釋2:If x1 then if

34、 x2 then y:=aif x2 then y:=a else y:=bIfBThenSElseSSIfBThenS第一種：If B1 Then If B2 Then S2 Else S3第二種：IfBThenSElseSSIfBThenSIf B1 Then If B2 Then S2 Else S3改寫文法如下：SM|UMIf B Then M Else M|S1UIf B Then S|If B Then M Else U怎樣排除二義性：語義上限制。改寫文法。M為匹配語句，U為非匹配語句。得到語法樹如下：UIfBThenSSIfBThenSElseMMS33.7 有關(guān)有關(guān)文法實(shí)用中的

35、一些說明文法實(shí)用中的一些說明 文法中文法中不含有不含有有害規(guī)則有害規(guī)則和和多余規(guī)則多余規(guī)則有害規(guī)則有害規(guī)則：形如：形如UU的產(chǎn)生式。會(huì)的產(chǎn)生式。會(huì)引起引起文法的文法的二義二義性性多余規(guī)則多余規(guī)則：指文法中：指文法中任何句子的推導(dǎo)任何句子的推導(dǎo)都都不會(huì)用到的規(guī)不會(huì)用到的規(guī)則則文法中文法中不含有不含有不可到達(dá)和不可終止的不可到達(dá)和不可終止的非終結(jié)符非終結(jié)符1）文法中某些）文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為該非終結(jié)符稱為不可到達(dá)不可到達(dá)。2）文法中某些）文法中某些非終結(jié)符非終結(jié)符，由它，由它不能推出終結(jié)符號不能推出終結(jié)符號串串，該非終結(jié)符稱，該非終

36、結(jié)符稱為為不可終止不可終止。1.文法中不含有AA的規(guī)則 例:S0S1|01 無二義性,可以改為:S0S1|01|S 句子0011有二義性。S0S101S0S101SS0S101S 2.文法中不包含多余規(guī)則不可到達(dá)：所有推導(dǎo)均不會(huì)用到此規(guī)則不可終止：推導(dǎo)不出終結(jié)符號串例子: 文法GS： (1) SBe (5)Ae (2) BCe不可終止 (6)CCf不可終止 (3) BAf (7)Df不可達(dá) (4) AAe 對文法G=(VN,VT,S,P),為了保證其任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn),必須滿足如下兩個(gè)條件：1.A必須在某句型中出現(xiàn)。即有S A,其中,屬(VTVN)*。 2.必須能夠從A推出終結(jié)符號串t來。即A t,其中t