第三章 文法和語言

1、盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站1指導(dǎo)教師指導(dǎo)教師:楊建國楊建國二零零七年十一月二零零七年十一月盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站2第三章文法和語言v第一節(jié)第一節(jié) 文法的直觀概念文法的直觀概念v第二節(jié)第二節(jié) 符號(hào)和符號(hào)串符號(hào)和符號(hào)串v第三節(jié)第三節(jié) 文法和語言的形式定義文法和語言的形式定義v第四節(jié)第四節(jié) 文法的類型文法的類型v第五節(jié)第五節(jié) 上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹v第六節(jié)第六節(jié) 句型分析句型分析v第八節(jié)第八節(jié) 典型例題及解答典型例題及解答v第七節(jié)第七節(jié) 有關(guān)文法實(shí)用中的一些說明有關(guān)文法實(shí)用中的一些說明盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站3知識(shí)結(jié)構(gòu)知識(shí)結(jié)構(gòu)盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站43.1

2、 文法的直觀概念 第三章 文法和語言v所謂一個(gè)語言的所謂一個(gè)語言的語法語法是指一組是指一組規(guī)則規(guī)則，用它可，用它可以形成和產(chǎn)生一個(gè)合適的程序以形成和產(chǎn)生一個(gè)合適的程序v目前廣泛使用的手段是目前廣泛使用的手段是上下文無關(guān)文法上下文無關(guān)文法，即，即用上下文無關(guān)文法作為程序設(shè)計(jì)語言語法的描用上下文無關(guān)文法作為程序設(shè)計(jì)語言語法的描述工具述工具盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站5v程序設(shè)計(jì)語言的描述：程序設(shè)計(jì)語言的描述：語法：語法：語義：語義：語用：語用：程序的程序的結(jié)構(gòu)或形式結(jié)構(gòu)或形式語言所代表的語言所代表的含義含義語言的實(shí)際語言的實(shí)際應(yīng)用應(yīng)用盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站6例如，對于賦值語句例如，對于賦值語

3、句x : = a + b x : = a + b * * c c的非形式描的非形式描述是：述是：語法：賦值語句語法：賦值語句變量變量:=:=表達(dá)式表達(dá)式語義：先求右部，然后把結(jié)果給左部變量語義：先求右部，然后把結(jié)果給左部變量語用：賦值語句可用來計(jì)算和保存表達(dá)式的值語用：賦值語句可用來計(jì)算和保存表達(dá)式的值形式化方法：用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系形式化方法：用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來描述問題的理論和方法來描述問題的理論和方法形式語言：一種不考慮含義的符號(hào)語言形式語言：一種不考慮含義的符號(hào)語言盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站7v程序設(shè)計(jì)語言的語義分成：程序設(shè)計(jì)語言的語義分成：靜態(tài)語義靜態(tài)語義：是

4、一系列：是一系列限定規(guī)則限定規(guī)則，并確定哪些合乎，并確定哪些合乎語法的程序是合適的語法的程序是合適的動(dòng)態(tài)語義動(dòng)態(tài)語義（運(yùn)行語義、執(zhí)行語義）：表明程序要（運(yùn)行語義、執(zhí)行語義）：表明程序要做什么做什么，要計(jì)算什么，要計(jì)算什么盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站8v以自然語言為例，人們無法列出全部句子，以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來說但是人們可以給出一些規(guī)則，用這些規(guī)則來說明（或者定義）句子的組成結(jié)構(gòu)：明（或者定義）句子的組成結(jié)構(gòu)：盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站9v例如例如, , 有一組規(guī)則有一組規(guī)則: : : = : = : = : = : = the : =

5、the : = a : = a : = big : = big : = : = : = ate : = ate : = : = : = cat : = cat : = mouse : = mouse 顯然顯然, , 由這一組規(guī)則可以產(chǎn)生句子由這一組規(guī)則可以產(chǎn)生句子: :The big cat / mouse ate a mouse / cat The big cat / mouse ate a mouse / cat 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站10v 這樣的語言描述稱為文法這樣的語言描述稱為文法v 使用文法作為工具，不僅為了嚴(yán)格地定義句使用文法作為工具，不僅為了嚴(yán)格地定義句子的結(jié)構(gòu)，也是為了

6、用適當(dāng)條數(shù)的規(guī)則把語子的結(jié)構(gòu)，也是為了用適當(dāng)條數(shù)的規(guī)則把語言的全部句子描述出來，可以說言的全部句子描述出來，可以說文法文法是是以有以有窮的集合刻畫無窮的集合的一個(gè)窮的集合刻畫無窮的集合的一個(gè)工具工具。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站113.2 符號(hào)和符號(hào)串一一. .字母表和符號(hào)串字母表和符號(hào)串1.1.語言語言可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的則構(gòu)成的一切基本符號(hào)串組成的集合集合2.2.字母表字母表（符號(hào)集）：是一個(gè)（符號(hào)集）：是一個(gè)非空非空有窮集合有窮集合3.3.符號(hào)符號(hào)（字符）：字母表中的元素（字符）：字母表中的元素4

7、.4.符號(hào)串符號(hào)串：符號(hào)的有窮：符號(hào)的有窮序列序列。注意：。注意： 表示空符號(hào)串！表示空符號(hào)串！5.5.符號(hào)串集合符號(hào)串集合：字母表：字母表 上若干個(gè)符號(hào)串組成的集合上若干個(gè)符號(hào)串組成的集合盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站12v 重要約定：重要約定： 小寫字母小寫字母 a, b, c, a, b, c, , r , r 表示符號(hào)表示符號(hào) 小寫字母小寫字母 s, t, u, s, t, u, , z , z 表示符號(hào)串表示符號(hào)串 大寫字母大寫字母 A, B, C, A, B, C, , Z , Z 表示符號(hào)串集合表示符號(hào)串集合盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站13二二. .符號(hào)串的運(yùn)算符號(hào)串的運(yùn)算1.1.

8、符號(hào)串相等符號(hào)串相等 設(shè)設(shè)x x、y y是字母表是字母表 上的兩個(gè)符號(hào)串，若上的兩個(gè)符號(hào)串，若x x與與y y的諸符號(hào)依次相等，則該兩符號(hào)串相等，記為的諸符號(hào)依次相等，則該兩符號(hào)串相等，記為x=yx=y。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站142.2.符號(hào)串長度符號(hào)串長度 設(shè)設(shè)x x是字母表是字母表 上的符號(hào)串，符號(hào)串中包含符號(hào)上的符號(hào)串，符號(hào)串中包含符號(hào)的個(gè)數(shù)稱為符號(hào)串的個(gè)數(shù)稱為符號(hào)串x x的長度，用的長度，用 x x 表示表示例例: :（1 1） | | |= 0 ; |= 0 ; （2 2） |ax|=|xa|=|x| + 1(a)|ax|=|xa|=|x| + 1(a)【注】【注】對于字母表A

9、=begin,if,real,end【1】符號(hào)串beginif的長度是多少？ 2【2】 begini或eginif是不是A上的符號(hào)串盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站153.3.符號(hào)串的連結(jié)符號(hào)串的連結(jié) 設(shè)設(shè)x x與與y y是字母表是字母表 上的兩個(gè)符號(hào)串，把上的兩個(gè)符號(hào)串，把y y的所的所 有符號(hào)相繼寫在有符號(hào)相繼寫在x x的符號(hào)之后所得到的符號(hào)串稱為的符號(hào)之后所得到的符號(hào)串稱為 x x與與y y的連結(jié)，用的連結(jié)，用xyxy表示表示注意注意: : |xy|=|x|+|y| |xy|=|x|+|y| x = xx = x = x = x xy yx ( xy yx ( 一般說來一般說來 ) )盛威網(wǎng)

10、：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站164.4.符號(hào)串的逆符號(hào)串的逆X(1)(1)若若x=abcd,x=abcd,則則 = dcba = dcba (2) = (2) = X 設(shè)設(shè)x x是字母表是字母表 上的符號(hào)串，其逆為符號(hào)串上的符號(hào)串，其逆為符號(hào)串x x的的倒置，記為倒置，記為 。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站175.5.符號(hào)串的前綴、后綴和子串符號(hào)串的前綴、后綴和子串 設(shè)設(shè)x x、y y、z z是字母表是字母表 上的符號(hào)串，則稱上的符號(hào)串，則稱x x為為符號(hào)串符號(hào)串xyxy的前綴，的前綴，y y是符號(hào)串是符號(hào)串xyxy的后綴，的后綴，x x、y y、z z、xyxy、yz yz 是符號(hào)串是符號(hào)串xyzx

11、yz的子串的子串例例: : 字母表字母表A=a,b,cA=a,b,c上的符號(hào)串上的符號(hào)串x=abcx=abc，則，則x x的的 前綴前綴有有 ,a,ab,abc,a,ab,abc；后綴后綴有有 ,c,bc,abc,c,bc,abc；真真 前綴前綴有有 ,a,ab,a,ab；真后綴真后綴有有 ,c,bc,c,bc。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站186.6.符號(hào)串集合的乘積符號(hào)串集合的乘積設(shè)設(shè)A A、B B為兩個(gè)符號(hào)串集合，其乘積為為兩個(gè)符號(hào)串集合，其乘積為AB=xy|xAB=xy|x A,yA,y BB例例: (1): (1)若若A = ab, cd ,B = ef, gh A = ab, cd

12、,B = ef, gh 則則AB = abef, abgh, cdef, cdgh AB = abef, abgh, cdef, cdgh (2) (2) x = x x = x = x = x A = A A = A = A = A盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站197.7.空集空集 不含任何元素的集合，記為不含任何元素的集合，記為 注意注意: (1) : (1) A = A A = A = = ; ; (2) (2) 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站208.8.符號(hào)串的冪符號(hào)串的冪 設(shè)設(shè)x x是字母表是字母表 上的符號(hào)串，則上的符號(hào)串，則x x的冪運(yùn)算的冪運(yùn)算為為x x0 0= = x x1 1=

13、x x=x x2 2=xx =xx x xn n=x=xn-1n-1x(xxx(xxn-1n-1) )例例: :若若x=ab,x=ab,則則x x0 0= = ,x,x1 1=ab,x=ab,x2 2=abab,=abab, , x xn n=abab=abababab盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站219.9.符號(hào)串集合的冪符號(hào)串集合的冪 設(shè)設(shè)A A是符號(hào)串集合，則符號(hào)串是符號(hào)串集合，則符號(hào)串A A的冪運(yùn)算為：的冪運(yùn)算為： A A0 0= A A1 1=A A=A A2 2=AA =AA A An n=A=An-1n-1A (AAA (AAn-1n-1) ) 例例: :若若A=ab,cd A=a

14、b,cd 則則:A:A0 0 = ,A,A1 1=ab,cd, =ab,cd, A A2 2=abab,abcd,cdab,cdcd,=abab,abcd,cdab,cdcd,盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站22注意注意: :A A* *=A=A0 0AA+ + A A+ +=AA=AA* *= =A A* *A A 若若A=a,b A=a,b 則則:A:A* *= ,a,b,aa,ab,ba,bb,aaa,a,b,aa,ab,ba,bb,aaa, A A+ +=a,b,aa,ab,ba,bb,aaa,=a,b,aa,ab,ba,bb,aaa, 10.10.集合集合A A的閉包與正閉包的閉包與正閉

15、包正閉包表示為正閉包表示為 A+ ，集合集合A A的閉包表示為的閉包表示為 A* ， A UA UA UA A K1K32 1U A UA UA UUA A A K0K32 10*U盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站233.3 文法和語言的形式定義一一. .如何來描述一種語言如何來描述一種語言 如果語言是如果語言是有窮有窮的（只含有的（只含有有窮有窮多個(gè)句子），可以多個(gè)句子），可以將句子逐一列出來表示將句子逐一列出來表示 如果語言是如果語言是無窮無窮的，找出語言的有窮表示。語言的的，找出語言的有窮表示。語言的有窮表示有兩個(gè)途經(jīng)：有窮表示有兩個(gè)途經(jīng)： 生成方式生成方式 （文法）：（文法）：語言中的每個(gè)

16、句子可以用嚴(yán)語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。格定義的規(guī)則來構(gòu)造。 識(shí)別方式（自動(dòng)機(jī)）：識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一任用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止并回答并回答“是是”，若不屬于，要么能停止并回答，若不屬于，要么能停止并回答“不不是是”，（要么永遠(yuǎn)繼續(xù)下去），（要么永遠(yuǎn)繼續(xù)下去） 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站24二二. .相關(guān)概念相關(guān)概念1.1.規(guī)則規(guī)則（重寫規(guī)則、產(chǎn)生式、生成式）（重寫規(guī)則、產(chǎn)生式、生成式） 一個(gè)規(guī)則是一個(gè)二元組一個(gè)規(guī)則是一個(gè)二元組, ,通常寫作通常寫作:=:= 或或稱為

17、規(guī)則的稱為規(guī)則的左部左部，是字母表是字母表V V的正閉包的正閉包V+中的一個(gè)中的一個(gè)符號(hào)；符號(hào)；稱為規(guī)則的稱為規(guī)則的右部右部，是是V V*中的一個(gè)符號(hào)；中的一個(gè)符號(hào)；(:=)(:=)讀作讀作“定義為定義為”，這是一條關(guān)于，這是一條關(guān)于的規(guī)則（產(chǎn)的規(guī)則（產(chǎn)生式）生式）盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站252.2.文法文法定義定義3.13.1：文法文法G G定義為四元組（定義為四元組（V VN N，V VT T，P P，S S）V VN N ：非終結(jié)符（語法實(shí)體、變量）集非終結(jié)符（語法實(shí)體、變量）集V VT T ：終結(jié)符集終結(jié)符集P P：產(chǎn)生式產(chǎn)生式（ ）集合，）集合，(V(VN NV VT T) )*

18、 *且至少且至少包含一個(gè)非終結(jié)符，包含一個(gè)非終結(jié)符，(V(VN NV VT T) )* *V VN N、V VT T、P P是非空有窮集是非空有窮集出現(xiàn)在規(guī)則的左部、用出現(xiàn)在規(guī)則的左部、用括起來、表示一定語括起來、表示一定語法概念的詞。法概念的詞。 語言中不可再分割的字語言中不可再分割的字符串符串( (包括單個(gè)字符組成包括單個(gè)字符組成的串的串) )。注：終結(jié)符是組。注：終結(jié)符是組成句子的基本單位。成句子的基本單位。 用來定義符號(hào)串之間關(guān)系用來定義符號(hào)串之間關(guān)系的一組的一組( (語法語法) )規(guī)則規(guī)則 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站26S S：開始符開始符（識(shí)別符），它是一個(gè)非終結(jié)符，至（識(shí)別符）

19、，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)少要在一條規(guī)則中作為左部出現(xiàn)V VN NVVT T= = V=VV=VN NVVT T，稱為文法，稱為文法G G的字母表（字匯表）的字母表（字匯表）盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站27v例例3.13.1 文法文法G=G=（V VN N，V VT T，P P，S S），其中），其中V VN N = S = S ，V VT T = 0, 1 = 0, 1 ，P = SP = S0S1, S0S1, S 01 01 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站28v例例3.23.2文法文法G=G=（V VN N，V VT T，P P，S S），其中），其中V VN N

20、= =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(shù)字 V VT T =a,b,c,x,y,z,0,1,9 =a,b,c,x,y,z,0,1,9P P a a z z 0 0 9 9 S=S= 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站29v很多時(shí)候，不用將文法很多時(shí)候，不用將文法G G的四元組顯的四元組顯式地表示出來，而只將產(chǎn)生式寫出式地表示出來，而只將產(chǎn)生式寫出盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站30v一般約定：一般約定：第一條產(chǎn)生式的左部是識(shí)別符第一條產(chǎn)生式的左部是識(shí)別符用尖括號(hào)括起來的是非終結(jié)符（或者用大寫字母用尖括號(hào)括起來的是非終結(jié)符（或者用大寫字母表示）表示）不用尖括號(hào)括起來的是終結(jié)符（或者用小寫字母不用尖括號(hào)括起

21、來的是終結(jié)符（或者用小寫字母表示）表示）將將G G也寫成也寫成GSGS，其中，其中S S是識(shí)別符是識(shí)別符盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站31v推導(dǎo)：推導(dǎo)：定義定義V V* *中的符號(hào)之間的關(guān)系：中的符號(hào)之間的關(guān)系：直接推導(dǎo)：直接推導(dǎo)：長度為長度為n(n1)n(n1)的推導(dǎo)：的推導(dǎo)：長度為長度為n(n0)n(n0)的推導(dǎo)：的推導(dǎo)：*+盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站32v定義定義3.23.2：文法文法G G（V VN N，V VT T，P P，S S），）， 是是一條規(guī)則，一條規(guī)則，和和是是V V* *中的任意符號(hào)，若有符號(hào)串中的任意符號(hào)，若有符號(hào)串v v、w w滿足：滿足：v=v=，w= w= ，則稱

22、則稱v v直接推導(dǎo)到直接推導(dǎo)到w w，v v w w，或或w w直接歸約到直接歸約到v vv例：例：G G： S S0S10S1， S S0101 S S0S1 0S1 00S1100S11 000S111 000S111 0000111100001111盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站33v定義定義3.33.3：如果存在直接推導(dǎo)的序列：如果存在直接推導(dǎo)的序列：v=wv=w0 0w w1 1w w2 2w wn n=w (n0)=w (n0)則稱則稱v v推導(dǎo)出推導(dǎo)出w w（推導(dǎo)長度為（推導(dǎo)長度為n n），或稱），或稱w w歸約到歸約到v v，記作記作+盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站34v定義定義3

23、.53.5：若有若有S Sx x，則稱，則稱x x是文法是文法GSGS的的句句型型，若，若x x僅由終結(jié)符組成，則稱僅由終結(jié)符組成，則稱x x為為GSGS的的句子句子*v定義定義3.43.4：若有若有v vw w，或，或v=wv=w，則記作：，則記作：v wv w+*盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站35v定義定義3.63.6：文法文法G G所產(chǎn)生的語言定義為集合所產(chǎn)生的語言定義為集合L(G)=L(G)=x|Sx|Sx x，其中，其中S S為文法識(shí)別符號(hào)，且為文法識(shí)別符號(hào)，且xVxVT T* *v文法描述的語言是該文法一切句子的集合文法描述的語言是該文法一切句子的集合v例：例：G G：S S0S10

24、S1， S S0101L(G)=0L(G)=0n n1 1n n|n1|n1*盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站36例例3.33.3文法文法文法文法GSGS：（1 1）S SaSBEaSBE（2 2）S SaBEaBE（3 3）EBEBBEBE（4 4）aBaBabab（5 5）bBbBbbbb（6 6）bEbEbebe（7 7）eEeEeeeeL L（G G）= a= an nb bn ne en n | n1 | n1 思考：思考：a a4 4b b4 4e e4 4怎么推導(dǎo)？怎么推導(dǎo)？盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站37v定義定義3.73.7：若若L(GL(G1 1) )L(GL(G2 2) )，

25、則稱文法，則稱文法G G1 1和和G G2 2是等是等價(jià)的價(jià)的v例如文法例如文法GAGA：A A0R0RA A0101R RA1A1和文法和文法GSGS：S S0S10S1S S0101等價(jià)等價(jià)L(G)=0L(G)=0n n1 1n n|n1|n1盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站383.4 文法的類型v喬姆斯基喬姆斯基(Chomsky)(Chomsky)于于19561956年建立形式語言的描述年建立形式語言的描述v他把文法分成：他把文法分成：0 0型、型、1 1型、型、2 2型、型、3 3型型v設(shè)設(shè)G G（V VN N，V VT T，P P，S S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式 是這

26、樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)：(V(VN NVVT T) )* *且且至少包含一個(gè)至少包含一個(gè)非終結(jié)符，非終結(jié)符， (V(VN NVVT T) )* *，則，則G G是是一個(gè)一個(gè)0 0型文法型文法（短語結(jié)構(gòu)文法、無限制文法短語結(jié)構(gòu)文法、無限制文法），），簡稱簡稱PSGPSG。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站39 設(shè)設(shè)G G（V VN N，V VT T，P P，S S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)產(chǎn)生式生式 是這樣一種結(jié)構(gòu)：是這樣一種結(jié)構(gòu)：(V(VN NVVT T) )+ +，(V(VN NVVT T) )* *，則，則G G是一個(gè)是一個(gè)0 0型文法型文法v思考：這樣定義可以嗎？思考：這樣定義可以

27、嗎？盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站40v設(shè)設(shè)G G（V VN N，V VT T，P P，S S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式均滿足：均滿足：| | | | |，僅僅，僅僅S S 除外，則文法除外，則文法G G是是1 1型文法型文法（上下文有關(guān)文法，上下文有關(guān)文法，上下文敏感文法上下文敏感文法），簡稱），簡稱CSGCSG。例例3.13.1、3.23.2、3.33.3盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站41例：例：文法文法GSGS： S SCDCDAbAbbAbA C CaCAaCABaBaaBaB C CbCBbCBBbBbbBbB AD ADaDaDC C BD BDbDbDD D Aa

28、AabDbDL(G)=w|wa,bL(G)=w|wa,b* * 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站42v有些定義中，將上下文有關(guān)文法的產(chǎn)生式的形有些定義中，將上下文有關(guān)文法的產(chǎn)生式的形式描述為式描述為1 1AA2 21 12 2，其中，其中1 1、2 2和和都在都在V V* *中，中，A A在在V VN N中中盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站43v設(shè)設(shè)G G（V VN N，V VT T，P P，S S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式 均滿足：均滿足：是是一個(gè)一個(gè)非終結(jié)符，非終結(jié)符，V V* *， 則文法則文法G G是是2 2型文法型文法（上下文無關(guān)文法上下文無關(guān)文法），簡稱），簡稱CFGCF

29、G。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站44v有時(shí)將有時(shí)將2 2型文法的產(chǎn)生式表示為型文法的產(chǎn)生式表示為A A的形式，的形式，其中其中AAV VN N，也就是用，也就是用取代非終結(jié)符取代非終結(jié)符A A時(shí)，與時(shí)，與A A所在的上下文無關(guān)，因此取名為所在的上下文無關(guān)，因此取名為上下文無關(guān)上下文無關(guān)。例例3.13.1、3.23.2盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站45例例3.43.4：文法：文法GSGS：S SaB|bAaB|bA A Aa|aS|bAAa|aS|bAA B Bb|bS|aBBb|bS|aBB盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站46v設(shè)設(shè)G G（V VN N，V VT T，P P，S S），如果它的），如

30、果它的每個(gè)每個(gè)產(chǎn)生產(chǎn)生式式A A B B或或A A （A A B B或或A A ），其中，其中A A和和B B都是非終結(jié)符，都是非終結(jié)符，V VT T* *，則文法，則文法G G是是3 3型文型文法法（正規(guī)文法，正則文法，有窮狀態(tài)文法正規(guī)文法，正則文法，有窮狀態(tài)文法），簡），簡稱稱RGRG。 例例3.5-13.5-1：文法：文法GSGS：S S0A|1B|00A|1B|0 A A0A|1B|0S0A|1B|0S B B1B|1|01B|1|0若文法中所有的產(chǎn)生式均為若文法中所有的產(chǎn)生式均為A A BB或或A A 形式，則此文法為右線性的形式，則此文法為右線性的若文法中所有的產(chǎn)生式均為若文法中所

31、有的產(chǎn)生式均為A A BB或或A A 形式，則此文法為左線性的形式，則此文法為左線性的盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站47例例3.5-23.5-2：文法：文法GSGS：S S0A|1B|00A|1B|0 A AA0|B1|0SA0|B1|0S B BB1|1|0B1|1|0第一，左邊有非終結(jié)符，所以此文法是第一，左邊有非終結(jié)符，所以此文法是0 0型文法型文法；第二，左邊符號(hào)串長度不大于右邊，所以此文法是第二，左邊符號(hào)串長度不大于右邊，所以此文法是1 1型文法型文法；第三，左邊只有一個(gè)非終結(jié)符，所以此文法是第三，左邊只有一個(gè)非終結(jié)符，所以此文法是2 2型文法型文法；第四，由于文法中既有左線性文法又有

32、右線性文法，所以此第四，由于文法中既有左線性文法又有右線性文法，所以此文法文法不是不是3 3型文法型文法；綜上所述，此文法是綜上所述，此文法是2 2型文法。型文法。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站48v四個(gè)文法類的定義是四個(gè)文法類的定義是逐漸增加限制逐漸增加限制的的0 0型型1 1型型2 2型型3 3型型 因此，每一種正規(guī)文法（因此，每一種正規(guī)文法（3 3型）都是上下文無關(guān)型）都是上下文無關(guān)的，每一種上下文無關(guān)文法（的，每一種上下文無關(guān)文法（2 2型）都是上下文有關(guān)型）都是上下文有關(guān)的，而每一種上下文有關(guān)文法（的，而每一種上下文有關(guān)文法（1 1型）都是型）都是0 0型文法。型文法。各類文法對應(yīng)的語

33、言叫各類文法語言。各類文法對應(yīng)的語言叫各類文法語言。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站490 0型語言型語言-圖靈機(jī)圖靈機(jī)p四類語言與自動(dòng)機(jī)四類語言與自動(dòng)機(jī)1 1型語言型語言-線性界限自動(dòng)機(jī)線性界限自動(dòng)機(jī)2 2型語言型語言-下推自動(dòng)機(jī)下推自動(dòng)機(jī)3 3型語言型語言-有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站50 通常自然語言是通常自然語言是上下文有關(guān)上下文有關(guān)的，程序設(shè)計(jì)語的，程序設(shè)計(jì)語言也不例外。言也不例外。p四類語言與程序設(shè)計(jì)語言四類語言與程序設(shè)計(jì)語言例例1 1 語言語言wcwwcww w (a,b)(a,b)* * 表示一個(gè)句子中出現(xiàn)有第二表示一個(gè)句子中出現(xiàn)有第二個(gè)個(gè)w w時(shí)必須同

34、時(shí)出現(xiàn)有第一個(gè)時(shí)必須同時(shí)出現(xiàn)有第一個(gè)w w，如果讓，如果讓w w表示標(biāo)識(shí)符，且表示標(biāo)識(shí)符，且第一個(gè)第一個(gè)w w代表說明部分，第二個(gè)代表說明部分，第二個(gè)w w代表語句部分，則表明標(biāo)代表語句部分，則表明標(biāo)識(shí)符識(shí)符w w可以任意長，且標(biāo)識(shí)符可以任意長，且標(biāo)識(shí)符w w必須先說明后使用。這類語必須先說明后使用。這類語言是上下文有關(guān)的。言是上下文有關(guān)的。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站51例例2 2 設(shè)有語言設(shè)有語言 a an nb bm mc cn nd dm mn,m1,n,m1,其中其中a an n與與b bm m可以表示兩個(gè)可以表示兩個(gè)過程中的形參表，分別有過程中的形參表，分別有n n個(gè)和個(gè)和m m個(gè)

35、參數(shù)，而個(gè)參數(shù)，而c cn n與與d dm m則分別表則分別表示調(diào)用這兩個(gè)過程的實(shí)參表。示調(diào)用這兩個(gè)過程的實(shí)參表。a an n與與c cn n中及中及b bm m與與d dm m中分別具有相中分別具有相同的指數(shù)，表示實(shí)參與形參的個(gè)數(shù)必須相同。這類語言也是同的指數(shù)，表示實(shí)參與形參的個(gè)數(shù)必須相同。這類語言也是上下文有關(guān)的。上下文有關(guān)的。u與與詞法詞法有關(guān)的規(guī)則屬于有關(guān)的規(guī)則屬于正則文法正則文法u與與局部語法局部語法有關(guān)的規(guī)則屬于有關(guān)的規(guī)則屬于上下文無關(guān)文法上下文無關(guān)文法u與與全局語法和語義全局語法和語義有關(guān)的規(guī)則屬于有關(guān)的規(guī)則屬于上下文有關(guān)文法上下文有關(guān)文法盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站523.5

36、上下文無關(guān)文法及其語法樹【注】上下文無關(guān)文法所定義的語法范疇是完全獨(dú)立【注】上下文無關(guān)文法所定義的語法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的，即是和其上下于這種范疇可能出現(xiàn)的環(huán)境的，即是和其上下文無關(guān)的，不同于自然語言。文無關(guān)的，不同于自然語言。一一. .上下文無關(guān)文法上下文無關(guān)文法Context-Free GrammarContext-Free Grammar （2 2型文法型文法CFGCFG）v設(shè)設(shè)G G（V VN N，V VT T，P P，S S），如果它的），如果它的每個(gè)每個(gè)產(chǎn)生式產(chǎn)生式均滿足：均滿足：是是一個(gè)一個(gè)非終結(jié)符，非終結(jié)符，V V* *，則文法，則文法G G是是上下文無關(guān)文

37、法上下文無關(guān)文法。1.1.定義定義盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站53u上下文無關(guān)上下文無關(guān)文法文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)。言的語法結(jié)構(gòu)。 算術(shù)表達(dá)式算術(shù)表達(dá)式 語句語句 賦值語句賦值語句 條件語句條件語句 讀語句讀語句 2.2.描述對象描述對象盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站54算術(shù)表達(dá)式文法表示算術(shù)表達(dá)式文法表示例例3.63.6 文法文法G=(E, +,G=(E, +,* *,i,(,), P, E,i,(,), P, E P:E i P:E i E E+E E E+E E E E E* *E E E (E) E (E)u賦值語句文法表示賦值語句文

38、法表示 i = Ei = Eu條件語句文法表示條件語句文法表示 ififthenthen | | ififthenthenelse else 注：注：無特殊說明，無特殊說明，“文法文法”均指上下文無關(guān)文均指上下文無關(guān)文法法盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站55一一. .語法樹語法樹( (推導(dǎo)樹推導(dǎo)樹Parse Tree)Parse Tree)1.1.定義定義 語法樹是這樣的一個(gè)語法結(jié)構(gòu)，它的結(jié)點(diǎn)由符語法樹是這樣的一個(gè)語法結(jié)構(gòu)，它的結(jié)點(diǎn)由符號(hào)組成。號(hào)組成。根結(jié)點(diǎn)根結(jié)點(diǎn)對應(yīng)于對應(yīng)于識(shí)別符號(hào)識(shí)別符號(hào)。只有。只有非終結(jié)符號(hào)非終結(jié)符號(hào)對應(yīng)的結(jié)點(diǎn)有對應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)。并且，一個(gè)結(jié)

39、點(diǎn)和它的子結(jié)點(diǎn)分別對應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。點(diǎn)分別對應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站56 語法樹語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點(diǎn)和有向邊組成。結(jié)點(diǎn)和有向邊組成。 結(jié)點(diǎn)結(jié)點(diǎn)：符號(hào)：符號(hào) 根結(jié)點(diǎn)根結(jié)點(diǎn)：識(shí)別符號(hào)識(shí)別符號(hào) 中間結(jié)點(diǎn)中間結(jié)點(diǎn)：非終結(jié)符非終結(jié)符 葉結(jié)點(diǎn)葉結(jié)點(diǎn)：終結(jié)符或非終結(jié)符終結(jié)符或非終結(jié)符 有向邊有向邊：表示結(jié)點(diǎn)間的派生關(guān)系：表示結(jié)點(diǎn)間的派生關(guān)系盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站572.2.引入語法樹的意義引入語法樹的意義 作為識(shí)別句子的輔助工具，語法樹可以表示句作為識(shí)別句子的輔助工具，語法

40、樹可以表示句子的結(jié)構(gòu)。這一點(diǎn)對于其后的語義分析有非常重要子的結(jié)構(gòu)。這一點(diǎn)對于其后的語義分析有非常重要的意義。的意義。3.3.作用作用 直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。給定文法給定文法G=(VG=(VN N,V,VT T,P,S),P,S)，對于，對于G G的任何句型都能的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。構(gòu)造與之關(guān)聯(lián)的語法樹。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站584.4.語法樹的相關(guān)概念語法樹的相關(guān)概念結(jié)點(diǎn)結(jié)點(diǎn)：每棵樹的結(jié)點(diǎn)對應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。邊邊：兩個(gè)結(jié)點(diǎn)之間的連線。根結(jié)點(diǎn)根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。分支分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其

41、結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）子樹子樹：語法樹的某個(gè)結(jié)點(diǎn)和它向下射出的部分末端結(jié)點(diǎn)末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號(hào)。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站594.4.語法樹的特征語法樹的特征u給定文法給定文法G G，G=(VG=(VN N,V,VT T,P,S),P,S)，對于，對于G G的任何句型都能構(gòu)的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征特征：1 1、根結(jié)點(diǎn)的標(biāo)記是、根結(jié)點(diǎn)的標(biāo)記是開始符號(hào)開始符號(hào)S S；2 2、每個(gè)結(jié)點(diǎn)的標(biāo)記都是、每個(gè)結(jié)點(diǎn)的標(biāo)記都是V V中的一個(gè)

42、符號(hào)；中的一個(gè)符號(hào)；3 3、若一棵子樹的根結(jié)點(diǎn)為、若一棵子樹的根結(jié)點(diǎn)為A A，且其所有直接子孫的標(biāo)記，且其所有直接子孫的標(biāo)記 從左向右的排列次序?yàn)閺淖笙蛴业呐帕写涡驗(yàn)锳 A1 1A A2 2AAR R ，那么，那么 AAAA1 1A A2 2AAR R一定是一定是P P中的一條規(guī)則；中的一條規(guī)則；盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站604 4、若一標(biāo)記為、若一標(biāo)記為A A的結(jié)點(diǎn)至少有一個(gè)除它以外的子的結(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則孫，則AVAVN N5 5、若樹的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為、若樹的所有葉結(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串字符串w w，則，則w w是文法是文法G G的的句型句型；若

43、；若w w中僅含中僅含終結(jié)終結(jié)符號(hào)符號(hào)，則，則w w為文法為文法G G所產(chǎn)生的所產(chǎn)生的句子句子。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站61線性推導(dǎo)：線性推導(dǎo)：我們稱用我們稱用符號(hào)進(jìn)行的推導(dǎo)為線符號(hào)進(jìn)行的推導(dǎo)為線性推導(dǎo)。性推導(dǎo)。樹型推導(dǎo)與線性推導(dǎo)的不同：樹型推導(dǎo)與線性推導(dǎo)的不同：線性推導(dǎo)指明線性推導(dǎo)指明了推導(dǎo)的順序，而樹型推導(dǎo)則沒有指明推導(dǎo)的了推導(dǎo)的順序，而樹型推導(dǎo)則沒有指明推導(dǎo)的順序。因此，句型一般只有一棵語法樹順序。因此，句型一般只有一棵語法樹( (如果如果無二義性無二義性) )，而線性推導(dǎo)則可很多。，而線性推導(dǎo)則可很多。句型推導(dǎo)過程句型推導(dǎo)過程句型語法樹的生長過程句型語法樹的生長過程盛威網(wǎng)：專業(yè)的計(jì)

44、算機(jī)學(xué)習(xí)網(wǎng)站62從推導(dǎo)構(gòu)造語法樹從推導(dǎo)構(gòu)造語法樹l方法：方法：把識(shí)別符號(hào)做為根結(jié)點(diǎn)，對每一個(gè)把識(shí)別符號(hào)做為根結(jié)點(diǎn)，對每一個(gè)直接推導(dǎo)畫一個(gè)分支，分支的名字是直接直接推導(dǎo)畫一個(gè)分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無分推導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無分支可畫結(jié)束。支可畫結(jié)束。從從識(shí)別符號(hào)識(shí)別符號(hào)開始，開始，逐步逐步建立建立推導(dǎo)推導(dǎo)序列。序列。由由根結(jié)點(diǎn)根結(jié)點(diǎn)開始，開始，自上而下自上而下建立建立語法樹語法樹。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站63 例如：推導(dǎo)例如：推導(dǎo)SBBdbaAcdcA AB B AcAcB Bd dA Accddccdd abccddabccddS S盛威網(wǎng)：專業(yè)的

45、計(jì)算機(jī)學(xué)習(xí)網(wǎng)站64從語法樹構(gòu)造推導(dǎo)自下而上自下而上地修剪子樹的末端結(jié)點(diǎn)，直至把整棵地修剪子樹的末端結(jié)點(diǎn)，直至把整棵樹剪掉（留根），每剪一次對應(yīng)一次樹剪掉（留根），每剪一次對應(yīng)一次歸約歸約。從句型開始，從句型開始，自右向左自右向左地逐步進(jìn)行地逐步進(jìn)行歸約歸約，建立推，建立推導(dǎo)序列。導(dǎo)序列。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站65 方法：方法：從分支建立直接推導(dǎo)，然后從語法從分支建立直接推導(dǎo)，然后從語法樹中剪去這個(gè)分支，直到無分支可剪。樹中剪去這個(gè)分支，直到無分支可剪。 語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個(gè)非終結(jié)符號(hào)上，但它并沒則和使用在哪個(gè)非終結(jié)符號(hào)上，

46、但它并沒有表明使用規(guī)則的順序。有表明使用規(guī)則的順序。 一棵語法樹可能對應(yīng)不止一種推導(dǎo)。一棵語法樹可能對應(yīng)不止一種推導(dǎo)。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站66從語法樹構(gòu)造推導(dǎo)的過程SBBdbaAcdc(1)(2)(3)(4) S ABABababBabcBdcBd abccdcdd 對于同一個(gè)句型或句子，可以通過不同的推導(dǎo)序列推對于同一個(gè)句型或句子，可以通過不同的推導(dǎo)序列推導(dǎo)出來，這是因?yàn)樵谕茖?dǎo)過程中所選擇的非終結(jié)符的次序?qū)С鰜?，這是因?yàn)樵谕茖?dǎo)過程中所選擇的非終結(jié)符的次序不同。不同。 abccdd(1)SAB AaAb|ab BcBd|cd Accdd(2)AcBd(3)存在下面的推導(dǎo)可能：AB(4)

47、S例如文法例如文法GS：盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站67例例3.73.7 句型句型aabbaaaabbaa的可能的可能推導(dǎo)序列和語法樹推導(dǎo)序列和語法樹GS:GS:SSa aASASASASb bA AASSASSSSa aAAbaba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站68二二. .規(guī)范推導(dǎo)與規(guī)范歸約規(guī)范推導(dǎo)與規(guī)范歸約 最左最左( (右右) )推導(dǎo)指對于一個(gè)推導(dǎo)序列中的每一直推導(dǎo)指對于一個(gè)推導(dǎo)序列中的每一直接推

48、導(dǎo)，被替換的總是當(dāng)前符號(hào)串中的最左接推導(dǎo)，被替換的總是當(dāng)前符號(hào)串中的最左( (右右) )非非終結(jié)符號(hào)。最右推導(dǎo)也稱為終結(jié)符號(hào)。最右推導(dǎo)也稱為規(guī)范推導(dǎo)規(guī)范推導(dǎo)。規(guī)范推導(dǎo)的逆過程，稱為最左歸約，也稱為規(guī)范推導(dǎo)的逆過程，稱為最左歸約，也稱為規(guī)范歸約規(guī)范歸約。用最左推導(dǎo)所推導(dǎo)出的句型稱為用最左推導(dǎo)所推導(dǎo)出的句型稱為最左句型最左句型用最右推導(dǎo)所推導(dǎo)出的句型稱為用最右推導(dǎo)所推導(dǎo)出的句型稱為最右句型最右句型，通常稱為，通常稱為規(guī)范句型規(guī)范句型盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站69【例】【例】 給出了下列文法給出了下列文法G G（1 1） （2 2） | | （3 3） 0|1|2|3|4|5|6|7|8|9 0|

49、1|2|3|4|5|6|7|8|9 V VT T =0,1,2,3,4,5,6,7,8,9 =0,1,2,3,4,5,6,7,8,9 V VN N= , , , 判斷數(shù)據(jù)判斷數(shù)據(jù)26342634是否是是否是C C語言合法的數(shù)據(jù)。語言合法的數(shù)據(jù)?！窘狻俊窘狻浚? 1）用最右推導(dǎo)，每次用產(chǎn)生式的規(guī)則替換最右邊）用最右推導(dǎo)，每次用產(chǎn)生式的規(guī)則替換最右邊的非終結(jié)符，推導(dǎo)過程如下：的非終結(jié)符，推導(dǎo)過程如下： 4 4 4 4 3434 3434 63463426342634盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站70（2 2）用最左推導(dǎo)，每次直接推導(dǎo)都替換最左邊的非）用最左推導(dǎo)，每次直接推導(dǎo)都替換最左邊的非終結(jié)符，推

50、導(dǎo)過程如下：終結(jié)符，推導(dǎo)過程如下： 2 2 2626 263263 26342634盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站71疑問疑問 一個(gè)句型是否只對應(yīng)唯一的一棵語法樹？一個(gè)句型是否只對應(yīng)唯一的一棵語法樹？一個(gè)句型是否只有唯一的一個(gè)最左（最右）推導(dǎo)？一個(gè)句型是否只有唯一的一個(gè)最左（最右）推導(dǎo)？不是不是課堂練習(xí)：課堂練習(xí)：GEGE：EE+E|EEE+E|E* *E|(E)|iE|(E)|i對于句子對于句子i ii i* *i i，給出兩種不同的，給出兩種不同的規(guī)范推導(dǎo)，并畫出語法樹。規(guī)范推導(dǎo)，并畫出語法樹。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站72EEE+EE*iiiEEE*EE+iii這兩種不同的推導(dǎo)對應(yīng)了兩種

51、不同的語法樹這兩種不同的推導(dǎo)對應(yīng)了兩種不同的語法樹(1) E=E+E=E+E*E =E+E*i =E+i*i = ii * i(2) E= E*E = E*i = E+E*i = E+i*i = ii * i盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站73 我我沒說她偷了我的錢。（可是有人這么說）沒說她偷了我的錢。（可是有人這么說） 我我沒沒說她偷了我的錢。（我確實(shí)沒這么說）說她偷了我的錢。（我確實(shí)沒這么說） 我沒我沒說說她偷了我的錢。她偷了我的錢。( (可是我是這么暗示的）可是我是這么暗示的） 我沒說我沒說她她偷了我的錢。（可是有人偷了）偷了我的錢。（可是有人偷了） 我沒說她我沒說她偷偷了我的錢。了我的錢。

52、( (但她用這錢做了某事但她用這錢做了某事) ) 我沒說她偷了我沒說她偷了我我的錢。（她偷了別人的錢）的錢。（她偷了別人的錢） 我沒說她偷了我的我沒說她偷了我的錢錢。（她偷了別的東西）。（她偷了別的東西） 二義性盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站74三三. .二義性文法二義性文法1.1.定義定義（1 1）文法二義性）文法二義性 若一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語若一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是法樹，則稱這個(gè)文法是二義二義的。（或者，若一個(gè)的。（或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)）。導(dǎo)）。（2 2）語言先天二義）

53、語言先天二義 產(chǎn)生某上下文無關(guān)語言的每一個(gè)文法都是二產(chǎn)生某上下文無關(guān)語言的每一個(gè)文法都是二義的。義的。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站752.2.二義性文法的證明二義性文法的證明u要判定一個(gè)文法是否是二義性文法，或它是否產(chǎn)生一要判定一個(gè)文法是否是二義性文法，或它是否產(chǎn)生一個(gè)先天二義性的上下文無關(guān)語言，是個(gè)遞歸不可解的。個(gè)先天二義性的上下文無關(guān)語言，是個(gè)遞歸不可解的。即不存在一個(gè)算法，它能在有限的步驟內(nèi)，確切地判即不存在一個(gè)算法，它能在有限的步驟內(nèi)，確切地判斷出某個(gè)給定的文法是否是一個(gè)二義性文法。斷出某個(gè)給定的文法是否是一個(gè)二義性文法。u我們要證明一個(gè)文法是否是一個(gè)二義性文法，就是找我們要證明一個(gè)文

54、法是否是一個(gè)二義性文法，就是找到該文法的一個(gè)句型特例，能夠畫出這個(gè)句型的兩棵到該文法的一個(gè)句型特例，能夠畫出這個(gè)句型的兩棵語法樹，該文法就是二義性文法。語法樹，該文法就是二義性文法。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站763.3.為什么要避免文法有二義性為什么要避免文法有二義性 二義性的文法將給編譯程序的執(zhí)行帶來問題。當(dāng)編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進(jìn)行語法分析時(shí)，就會(huì)產(chǎn)生兩種甚至更多種不同的理解。語法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站774.4.解決途徑解決途徑可以采用兩種途徑來解決文法的二義性問題可以采用兩種途徑來

55、解決文法的二義性問題 1不改變文法中原有的規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。不改變文法中原有的規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定。如如1 1：對于文法對于文法 GE: Ei EE+E EEGE: Ei EE+E EE* *E E(E) E E(E) 規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即規(guī)定運(yùn)算符優(yōu)先順序和結(jié)合律，即* *優(yōu)先于優(yōu)先于+ +，+ +、* *服從左結(jié)合。服從左結(jié)合。 如如2 2：C C語言中二義性的消除是通過約定，在符合語言中二義性的消除是通過約定，在符合if if 語句中，語句中，elseelse子句總是屬于最近的尚無子句總是屬于最近的尚無elseelse子句的子句的那個(gè)那個(gè)ifif語句

56、。語句。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站78SifB thenSifB thenelseSSSifBthenelseSSifBthenS設(shè)文法設(shè)文法GSGS：Sif B then S|if B then S else S|iSif B then S|if B then S else S|i：=E=E給出符號(hào)串給出符號(hào)串if B then if B then S else Sif B then if B then S else S的語法樹。的語法樹。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站79改寫文法，把排除二義性的規(guī)則合并到原有文法中。改寫文法，把排除二義性的規(guī)則合并到原有文法中。2EiET+TF*iFTFi

57、例例: :算術(shù)表達(dá)式的文法算術(shù)表達(dá)式的文法 E:= E+T | T T := T*F | F F := (E) | iGE：EE+E|E*E|(E)|i 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站803.6 句型的分析u任務(wù): 句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程。對于程序設(shè)計(jì)語言來說，句型分析就是一個(gè)識(shí)別輸入符號(hào)串是否為語法上正確的程序的過程。盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站81q在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序分析程序或或識(shí)別程序識(shí)別程序。分析算法分析算法又稱又稱識(shí)別算法識(shí)別算法。q從左到右的分析算法從左到右的分析

58、算法，即總是從左到右地識(shí)別輸入，即總是從左到右地識(shí)別輸入符號(hào)串。句型分析算法采用從左到右的分析算法。符號(hào)串。句型分析算法采用從左到右的分析算法。q句型的分析算法句型的分析算法分類分類 自上而下分析法自上而下分析法 (Top-Down parsing)(Top-Down parsing) 從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)串匹配的式，尋找與輸入符號(hào)串匹配的推導(dǎo)推導(dǎo)。 自下而上分析法自下而上分析法 (Bottom-Up parsing)(Bottom-Up parsing) 從輸入符號(hào)串開始，逐步進(jìn)行從輸入符號(hào)串開始，逐步進(jìn)行歸約歸約，直

59、至歸，直至歸 約到文法的開始符號(hào)。約到文法的開始符號(hào)。 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站82 兩種方法反映了兩種兩種方法反映了兩種語法樹語法樹的構(gòu)造過程：的構(gòu)造過程：l自上而下方法自上而下方法是從文法符號(hào)開始，將它做為語是從文法符號(hào)開始，將它做為語法樹的根，向下逐步建立語法樹，使語法樹的法樹的根，向下逐步建立語法樹，使語法樹的結(jié)果正好是輸入符號(hào)串結(jié)果正好是輸入符號(hào)串l自下而上方法自下而上方法則是從輸入符號(hào)串開始，以它做則是從輸入符號(hào)串開始，以它做為語法樹的結(jié)果，自底向上地構(gòu)造語法樹為語法樹的結(jié)果，自底向上地構(gòu)造語法樹盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站83一一. .基本思想基本思想 自上而下的分析方法就是

60、從識(shí)別符號(hào)出發(fā)，看是自上而下的分析方法就是從識(shí)別符號(hào)出發(fā)，看是否能推導(dǎo)出待檢查的符號(hào)串，如果能推導(dǎo)出這個(gè)符號(hào)否能推導(dǎo)出待檢查的符號(hào)串，如果能推導(dǎo)出這個(gè)符號(hào)串，則表明此符號(hào)串是該文法的句型或句子，否則就串，則表明此符號(hào)串是該文法的句型或句子，否則就不是。不是?；蛘哒f或者說，以文法的識(shí)別符號(hào)作為根結(jié)點(diǎn)，看是，以文法的識(shí)別符號(hào)作為根結(jié)點(diǎn)，看是否能構(gòu)造出一棵語法樹，而且此語法樹所有葉子結(jié)點(diǎn)否能構(gòu)造出一棵語法樹，而且此語法樹所有葉子結(jié)點(diǎn)從左到右所構(gòu)成的符號(hào)串恰好是待檢查的符號(hào)串。如從左到右所構(gòu)成的符號(hào)串恰好是待檢查的符號(hào)串。如果能生成這樣的語法樹，則表明待檢查的符號(hào)串是該果能生成這樣的語法樹，則表明待檢