第三章文法和語言

1、第第3章章 文法和語言文法和語言3.1 文法的直觀概念文法的直觀概念文法文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。：描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。1）描述單詞）描述單詞單詞的組成規(guī)則單詞的組成規(guī)則 BNF范式、正規(guī)式范式、正規(guī)式2）描述語句）描述語句語句的組成規(guī)則語句的組成規(guī)則BNF范式、語法圖范式、語法圖3.1 文法的直觀概念文法的直觀概念例如：判斷例如：判斷“ 我是大學(xué)生我是大學(xué)生”是否為句子是否為句子文法如下：文法如下：:= := | := 我我 | 你你 | 他他 :=王明王明| 大學(xué)生大學(xué)生|工人工人|英語英語:= :=是是 |學(xué)習(xí)學(xué)習(xí):= | “我是大學(xué)生我是

2、大學(xué)生”的推導(dǎo)過程：的推導(dǎo)過程： - - - 我我 - 我我 - 我是我是 我是我是 - 我是大學(xué)生我是大學(xué)生 依次可以推導(dǎo)出句子依次可以推導(dǎo)出句子“王明是大學(xué)生王明是大學(xué)生”、“我學(xué)習(xí)英語我學(xué)習(xí)英語”等等等等文法作用文法作用（1）定義句子的結(jié)構(gòu)；）定義句子的結(jié)構(gòu)；（2）用適當(dāng)條數(shù)的規(guī)則把語言的全部句子描述出來，以有窮集合刻劃）用適當(dāng)條數(shù)的規(guī)則把語言的全部句子描述出來，以有窮集合刻劃無窮集合。無窮集合。3.2 符號和符號串符號和符號串一、基本概念一、基本概念1.字母表字母表符號的符號的非空有窮非空有窮集合集合用符號用符號或或V表示。表示。例如：例如：=a，b，c 和和 V=0，1都是字母表都是

3、字母表相當(dāng)于語言中的字符集相當(dāng)于語言中的字符集2.符號符號語言中不可再分的基本單位語言中不可再分的基本單位3.符號串符號串字母表中的符號組成的任何字母表中的符號組成的任何有窮序列有窮序列。說明說明（1）符號的順序，如）符號的順序，如ab與與ba不同；不同；（2）符號串長度：符號串內(nèi)所含符號的個數(shù)）符號串長度：符號串內(nèi)所含符號的個數(shù)其中其中 不含任何符號的符號串稱為空符號串不含任何符號的符號串稱為空符號串，長度，長度| |03.2 符號和符號串符號和符號串4.句子句子字母表上符合某種規(guī)則構(gòu)成的串字母表上符合某種規(guī)則構(gòu)成的串包含單詞和語句包含單詞和語句5.語言語言 句子的集合句子的集合3.2 符號

4、和符號串符號和符號串二、符號串的計算二、符號串的計算1.符號串的連接符號串的連接設(shè)設(shè)x和和y是符號串，它們的連接是符號串，它們的連接xy是把是把y的符號寫在的符號寫在x的符號之后的符號之后得到的符號串。得到的符號串。例如：例如：x=abc，y=def，則，則xy=abcdef2.符號串的方冪符號串的方冪 設(shè)設(shè)x是符號串，把是符號串，把x自身連接自身連接n次得到的符號串次得到的符號串z，即，即z=xxxx，稱為符號串稱為符號串x的方冪，記作的方冪，記作z=xn，即把符號串，即把符號串x重復(fù)地寫重復(fù)地寫n次。次。例如：例如： x0= ， x1= x ，x2=xx， x3=xxx 設(shè)設(shè)x=ab 則則

5、x3= ababab 當(dāng)當(dāng)n0時，時， xn x xn-1 = xn-1 x3.2 符號和符號串符號和符號串三、符號串集合的運算三、符號串集合的運算 連接（乘積）：連接（乘積）：設(shè)符號串集合設(shè)符號串集合A、B，則，則 ABxy | x A且且y B 例如：例如：A=a, b，B=c, d，則集合，則集合AB=ac, ad, bc, bd A = A = A； 一般而言，一般而言，AB BA，但，但(AB)C=A(BC)注意：注意：1)串集自身的連接稱為串集的方冪串集自身的連接稱為串集的方冪2）A0=3）字母表）字母表A的的n次方冪表示字母表次方冪表示字母表A上長度為上長度為n的字符串集的字符串

6、集3.2 符號和符號串符號和符號串四、字母表的閉包和正閉包四、字母表的閉包和正閉包1.字母表字母表的閉包的閉包 * 0 1 2 n 即由即由上所有符號串組成的符號串集（包含空串）上所有符號串組成的符號串集（包含空串）2. 字母表字母表的的正閉包正閉包 + 1 2 n 即由即由上所有符號串組成的符號串集（不包含空串）上所有符號串組成的符號串集（不包含空串） 顯然有顯然有* 0 + ; + = *= * 對所有對所有 ，有，有 *。3.3 文法和語言的形式定義文法和語言的形式定義規(guī)則，也稱為產(chǎn)生式或生成式規(guī)則，也稱為產(chǎn)生式或生成式如一個產(chǎn)生式的形式是如一個產(chǎn)生式的形式是 （或（或:= )，其中，其

7、中 “”讀讀為為“是是”或或“定義為定義為”；非終結(jié)符：非終結(jié)符：在規(guī)則中用在規(guī)則中用括起來括起來非終結(jié)符用非終結(jié)符用VN表示表示終結(jié)符終結(jié)符語言中不可再分的字符串語言中不可再分的字符串終結(jié)符用終結(jié)符用VT表示表示定義定義3.1 文法文法G G是一個四元式組是一個四元式組 G=(VG=(VT T，V VN N，S S，P)P) 其中其中V VT T：終結(jié)符集合（非空、有窮）：終結(jié)符集合（非空、有窮）V VN N：非終結(jié)符集合（非空、有窮），且：非終結(jié)符集合（非空、有窮），且V VT T V VN N= =S S：文法的開始符號，：文法的開始符號，S S V VN NP P：產(chǎn)生式集合：產(chǎn)生式集

8、合( (非空、有窮非空、有窮) )，產(chǎn)生式的形式是產(chǎn)生式的形式是 和和 屬于屬于 ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。3.3 文法和語言的形式定義文法和語言的形式定義例：例： 文法文法G =（VN，VT，P，S） VN標(biāo)識符，字母，數(shù)字標(biāo)識符，字母，數(shù)字， VT a, b, c, , x, y, z, 0,1, , 8, 9 P= | | a|b|c|x|y|z 0|1|2|8|9 S = 注意：注意：有時不用將文法有時不用將文法G G的四元組顯示的表示出來，而只寫產(chǎn)生式的四元組顯示的表示出來，而

9、只寫產(chǎn)生式 約定：第一個產(chǎn)生式的左部是開始符號約定：第一個產(chǎn)生式的左部是開始符號 可將可將G寫成寫成GS，S為文法為文法G的開始符號的開始符號下面是一個文法的等價寫法下面是一個文法的等價寫法1）G=S,A,a,b,P,S其中其中P：S-aAb A-ab A-aAb A- 2） G: S-aAb A-ab A-aAb A- 3）GS: S-aAb A-ab A-aAb A- 4）GS: A-aAb|ab| S-aAb 有關(guān)推導(dǎo)的定義有關(guān)推導(dǎo)的定義1、直接推導(dǎo)直接推導(dǎo) 若若AA直接推導(dǎo)出直接推導(dǎo)出 ，即，即 A=A=，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)A A是是一個產(chǎn)生式，且一個產(chǎn)生式，且、(V VN NV VT

10、 T) )* * 符號符號 =指推導(dǎo)一步，即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則指推導(dǎo)一步，即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則（產(chǎn)生式）（產(chǎn)生式）2、長度為長度為n（n1）的推導(dǎo)）的推導(dǎo) 若存在直接推導(dǎo)序列若存在直接推導(dǎo)序列a0 a1 an，則，則稱稱a0可推導(dǎo)出可推導(dǎo)出an。 a0 an 表示：從表示：從a0出發(fā)經(jīng)過一步或若干步，可推導(dǎo)出出發(fā)經(jīng)過一步或若干步，可推導(dǎo)出an 。3、長度為長度為n（n0）的推導(dǎo)）的推導(dǎo) a1 an 表示：從表示：從a1出發(fā)經(jīng)過出發(fā)經(jīng)過0步（步（ a1 an ）或若干步，可推導(dǎo)出）或若干步，可推導(dǎo)出an 。例：例： 文法文法G ： | | a|b|c|x|y|z 0|1|

11、2|8|9 句型、句子、語言例：例：證明終結(jié)符號串證明終結(jié)符號串( i*i+i )是文法是文法G：E E+E | E*E | (E)| i的一個句子的一個句子證明：證明： E =( E ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是從開始符號是從開始符號E到到( i*i+i )的一個推導(dǎo)。的一個推導(dǎo)。其中其中E、(E)、(E+E)、(E*E+E)、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是都是這個文法的一個句型這個文法的一個句型*1. 句型句型：設(shè)：設(shè)GS是一個文法，是一個文法，S是它的開始符號，若是它的開始符號，若S ,則則稱稱是文

12、法是文法GS的句型。的句型。2.句子句子：僅含終結(jié)符的句型是一個句子，即：僅含終結(jié)符的句型是一個句子，即S ，VT*, 則則是句子。是句子。3.語言語言：文法：文法G所產(chǎn)生的句所產(chǎn)生的句 子的全體是一個語言，記作子的全體是一個語言，記作L(G) L(G)=|S ,且且VT*語言的例子語言的例子例：文法例：文法G2：A bA | cc，證明，證明cc、bcc、bbcc、 屬于屬于L(G2)。證明：證明：VT=b, c ， VN=A， S=A A cc， A bA bcc， A bA bbA bbcc cc、bcc、bbcc、是屬于是屬于L(G2)的的例：文法例：文法GS為為 (1) S0S10S

13、1； (2) S01,GS(2) S01,GS的語言是什么。的語言是什么。解：通過對第一個產(chǎn)生式使用解：通過對第一個產(chǎn)生式使用n-1n-1次，然后使用第二個產(chǎn)生式一次，得次，然后使用第二個產(chǎn)生式一次，得到：到：S 0S1 00S11 0S 0S1 00S11 0n-1n-1S1S1n-1n-1 0 0n n1 1n n因此因此L(G)=0L(G)=0n n1 1n n|n |n 11 文法的文法的等價等價 若若L(G1) = L(G2)，則稱文法，則稱文法G1和和G2是等價的是等價的例如例如: 文法文法G1=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列產(chǎn)生式組成：由

14、下列產(chǎn)生式組成： (1) S0S10S1； (2) S01(2) S01； 文法文法G2=(VN, VT, P, S)， VN =A, R， VT =0, 1，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成： (1) A 0R ; (2) A 01; (3) R A13.4 文法的類型文法的類型 喬姆斯基建立的形式語言對計算機科學(xué)的發(fā)展具有深刻的喬姆斯基建立的形式語言對計算機科學(xué)的發(fā)展具有深刻的意義。意義。他把文法分成四種類型：他把文法分成四種類型：0型、型、1型、型、2型和型和3型。型。它們的差別在于對產(chǎn)生式施加不同的限制。它們的差別在于對產(chǎn)生式施加不同的限制。0型文法（或稱短語文法）l G=( VN

15、, VT, P, S)是是0型文法是指：型文法是指： 若它的每個產(chǎn)生式若它的每個產(chǎn)生式是這樣一種結(jié)構(gòu)是這樣一種結(jié)構(gòu): (VNVT)*且至少含有一個非終結(jié)符，且至少含有一個非終結(jié)符，(VNVT)*。l 0型文法又稱為短語文法型文法又稱為短語文法 。 0型文法的能力相當(dāng)于圖靈機型文法的能力相當(dāng)于圖靈機（計算機的一種簡單的理論模型）。（計算機的一種簡單的理論模型）。1型文法（或稱上下文有關(guān)文法）型文法（或稱上下文有關(guān)文法） 如果對如果對0型文法分別加以以下的限制，則可得到型文法分別加以以下的限制，則可得到1型文法。型文法。l設(shè)設(shè)G=( VN, VT, P, S)為一文法，若為一文法，若G的任何產(chǎn)生式

16、的任何產(chǎn)生式 均均滿足滿足| | (指符號串的長度指符號串的長度)，僅僅，僅僅S 例外。例外。 上下文有關(guān)就是對非終結(jié)符進(jìn)行替換時必須考慮上下文上下文有關(guān)就是對非終結(jié)符進(jìn)行替換時必須考慮上下文l例如：例如：1型文法型文法G的產(chǎn)生式也可寫成的產(chǎn)生式也可寫成A ，其中，其中、都在都在(VNVT)*中，且中，且 ，A VN ，則說明了非終結(jié)符，則說明了非終結(jié)符A必須在必須在、這樣一個上下文環(huán)境中才可以替換。這樣一個上下文環(huán)境中才可以替換。 2型文法（或稱上下文無關(guān)文法）型文法（或稱上下文無關(guān)文法） 設(shè)設(shè)G=( VN, VT, P, S)為一文法，若為一文法，若G的任何產(chǎn)生式形似的任何產(chǎn)生式形似 ，其

17、中，其中 VN， (VNVT)* 。例：例：G=(S,A,B,a,b,P,S)，其中，其中P由下列產(chǎn)生式組成由下列產(chǎn)生式組成SaB|bA Aa|aS|bAABb|bS|Abb例：例：G=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列產(chǎn)生式由下列產(chǎn)生式組成：組成： (1) S0S1； (2) S01； 上下文無關(guān)文法的說明上下文無關(guān)文法的說明 上下文無關(guān)，顧名思義就是非終結(jié)符的替換可以不必考上下文無關(guān)，顧名思義就是非終結(jié)符的替換可以不必考慮上下文。慮上下文。 由于這種文法對程序已基本可以描述，因此，上下文無由于這種文法對程序已基本可以描述，因此，上下文無關(guān)文法常簡稱為文

18、法。關(guān)文法常簡稱為文法。3型文法（或稱正規(guī)文法）型文法（或稱正規(guī)文法）設(shè)設(shè)G=( VN, VT, P, S)為一文法，若為一文法，若G的任何產(chǎn)生式的任何產(chǎn)生式A 或或A B ，其中，其中A、B VN ， VT* 。例：文法例：文法G=(S,A,B,0,1,P,S)，其中，其中P由下列產(chǎn)生式組成由下列產(chǎn)生式組成S 0A|1B|0A 0A|1B|0SB 1B|1|0例：設(shè)例：設(shè)G=(VN, VT, P, S)， VN =S, B, E， VT =a, b, e，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成： (1) S aSBE ； (2) S aBE ; (3) EB BE ; (4) aB ab ;

19、(5) bB bb ; (6) bE be ; (7) eE ee ;判斷以下文法屬于哪類文法？判斷以下文法屬于哪類文法？3.5 上下文無關(guān)文法及其語法樹上下文無關(guān)文法及其語法樹一、語法樹（推導(dǎo)樹）一、語法樹（推導(dǎo)樹）1.直觀定義：用圖表示上下文無關(guān)文法句型推導(dǎo)的直觀方法。直觀定義：用圖表示上下文無關(guān)文法句型推導(dǎo)的直觀方法。2. 形式定義形式定義給定文法給定文法G=( VN, VT, P, S)，對于，對于G的任何句型都能構(gòu)造與之相關(guān)聯(lián)的語法的任何句型都能構(gòu)造與之相關(guān)聯(lián)的語法樹，這棵語法樹滿足以下樹，這棵語法樹滿足以下4個條件：個條件：（1）根結(jié)點由開始符號）根結(jié)點由開始符號S所標(biāo)記；所標(biāo)記；

20、（2）每個結(jié)點都有一個標(biāo)記，此標(biāo)記是）每個結(jié)點都有一個標(biāo)記，此標(biāo)記是V(即即VN VT)的一個符號；的一個符號；（3） 若結(jié)點若結(jié)點n至少有一個除它自己以外的子孫結(jié)點，并且有標(biāo)記至少有一個除它自己以外的子孫結(jié)點，并且有標(biāo)記A，則，則A在在VN中；中；（4）如果結(jié)點）如果結(jié)點n的直接子孫，從左到右的次序是結(jié)點的直接子孫，從左到右的次序是結(jié)點n1,nk，其標(biāo)記為，其標(biāo)記為A1,A2,Ak，那么，那么A-A1A2Ak一定是一定是P中的一個產(chǎn)生式。中的一個產(chǎn)生式。 從根結(jié)點從根結(jié)點S開始推導(dǎo)，當(dāng)非終結(jié)符被它的某個候選式所替換時，這個非開始推導(dǎo)，當(dāng)非終結(jié)符被它的某個候選式所替換時，這個非終結(jié)符的相應(yīng)結(jié)點

21、就產(chǎn)生出下一代新結(jié)點，候選式中自左向右的每個符號終結(jié)符的相應(yīng)結(jié)點就產(chǎn)生出下一代新結(jié)點，候選式中自左向右的每個符號對應(yīng)一個新結(jié)點，并用這些符號標(biāo)記其相應(yīng)的新結(jié)點。每個新結(jié)點與其父對應(yīng)一個新結(jié)點，并用這些符號標(biāo)記其相應(yīng)的新結(jié)點。每個新結(jié)點與其父結(jié)點間都有一條連線。結(jié)點間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的末端結(jié)點自在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的末端結(jié)點自左向右排列起來就是一個句型。左向右排列起來就是一個句型。語法樹構(gòu)造的過程語法樹構(gòu)造的過程E(根根)（E）E+ +EE*Eiii層次層次12345例例1 文法文法G= ( E, +, *, i ,

22、(, ), P, E)，其中，其中P為：為： E E+E | E*E | (E) | i對該文法關(guān)于對該文法關(guān)于(i*i+i)的推導(dǎo)的語法樹如下所示：的推導(dǎo)的語法樹如下所示：例例2：G=（S，A，a,b,P,S),其中其中P為：為： (1) S aAS (2) A SbA (3) S a (4) A ba 求文法求文法G的句型的句型aabbaa的推導(dǎo)樹。的推導(dǎo)樹。最左推導(dǎo)最左推導(dǎo)/最右推導(dǎo)最右推導(dǎo)/規(guī)范句型規(guī)范句型最左推導(dǎo)最左推導(dǎo)是指：任何一步是指：任何一步= 都是對都是對中的最左非終結(jié)符進(jìn)行替換。中的最左非終結(jié)符進(jìn)行替換。同樣，可定義同樣，可定義最右推導(dǎo)最右推導(dǎo)（又稱規(guī)范推導(dǎo)）：任何一步（又

23、稱規(guī)范推導(dǎo)）：任何一步=都是對都是對中的最中的最右非終結(jié)符進(jìn)行替換。右非終結(jié)符進(jìn)行替換。由規(guī)范推導(dǎo)所得到的句型稱為由規(guī)范推導(dǎo)所得到的句型稱為規(guī)范句型規(guī)范句型。注意：從一個句型到另一個句型的推導(dǎo)過程往往是不唯一的。注意：從一個句型到另一個句型的推導(dǎo)過程往往是不唯一的。例如例如 E+E i+i（a）E+E = E+i = i+i 最右推導(dǎo)最右推導(dǎo)（b）E+E = i+E = i+i 最左推導(dǎo)最左推導(dǎo)一個句型是否只對應(yīng)唯一的一棵語法樹？一個句型是否只對應(yīng)唯一的一棵語法樹？例如例如 對于文法對于文法GE： E E+E | E*E | (E) | i，對于句子，對于句子(i*i+i)存存在語法樹：在語法

24、樹：E(根根)（E）E+ +EE*EiiiE(根根)（E）E*EE+Eiii 定義：定義： 一個文法的某個句子對應(yīng)兩棵不同的語法樹，則這個文法是一個文法的某個句子對應(yīng)兩棵不同的語法樹，則這個文法是二義的。二義的?；蚧?一個文法的某個句子有兩個不同的最左（右）推導(dǎo)，則這一個文法的某個句子有兩個不同的最左（右）推導(dǎo)，則這個文法是二義的。個文法是二義的。二義性二義性 二義性其它問題二義性其它問題 人們已證明，二義性問題是不可判定的，即不存在一個算法，人們已證明，二義性問題是不可判定的，即不存在一個算法，它能在有限步驟內(nèi)，確切地判斷一個文法是否是二義的。它能在有限步驟內(nèi)，確切地判斷一個文法是否是二義的

25、。我們所能做的就是為無二義性尋找一些充分條件我們所能做的就是為無二義性尋找一些充分條件例如對文法例如對文法GE： E E+E | E*E | (E) | i 修改，規(guī)定運算符修改，規(guī)定運算符“+”與與“*”的優(yōu)先關(guān)系和結(jié)合規(guī)則，設(shè)的優(yōu)先關(guān)系和結(jié)合規(guī)則，設(shè)“*”的優(yōu)先性高于的優(yōu)先性高于“+”，且服從，且服從左結(jié)合。左結(jié)合。G: E T | E+T T F | T*F F (E) | i 3.6 句型的分析句型的分析 句型分析的任務(wù)就是按文法的產(chǎn)生式，識別輸入的符號是否是句型分析的任務(wù)就是按文法的產(chǎn)生式，識別輸入的符號是否是該文法的句型。該文法的句型。我們把完成句型分析的程序稱為分析程序或識別程序

26、，分析算法我們把完成句型分析的程序稱為分析程序或識別程序，分析算法又稱識別算法。又稱識別算法。分析算法又分為：分析算法又分為：從左到右分析算法；從左到右分析算法；從右到左分析算法；從右到左分析算法；自上而下的分析法自上而下的分析法自下而上的分析法自下而上的分析法3.6.1自上而下的分析法自上而下的分析法 基本思想：從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋基本思想：從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找找“匹配匹配”輸入符號串的推導(dǎo)。即對任何輸入符號串，從文法的開輸入符號串的推導(dǎo)。即對任何輸入符號串，從文法的開始符號（根結(jié)）出發(fā)，自上而下地為輸入串建立一棵語法樹，直到始符號（根結(jié)）出

27、發(fā)，自上而下地為輸入串建立一棵語法樹，直到語法樹結(jié)果正好是輸入的符號串為止。語法樹結(jié)果正好是輸入的符號串為止。例如：文法例如：文法GS: S xAy A * | *，識別輸入串，識別輸入串x*y是否是該是否是該文法的一個句子。文法的一個句子。解：解：SS S S x A y (2) S S S x A y (3) * (1) 缺陷缺陷關(guān)鍵：關(guān)鍵：回溯問題回溯問題；（；（ 其分析過程是一種試探過程）其分析過程是一種試探過程） 回溯問題回溯問題是從各種可能的候選式中任選一個，進(jìn)行推導(dǎo)后發(fā)現(xiàn)是從各種可能的候選式中任選一個，進(jìn)行推導(dǎo)后發(fā)現(xiàn)該候選式是錯誤的，則退回去重新選擇候選式的方式。例如上例中該候選

28、式是錯誤的，則退回去重新選擇候選式的方式。例如上例中的的(3)。S S S x A y (3) 選用第選用第1個候選式個候選式 * 回溯的產(chǎn)生使算法代價極高，效率很低。回溯的產(chǎn)生使算法代價極高，效率很低。 * 3.6.2自下而上的分析法自下而上的分析法 基本思想：從輸入串開始，逐步進(jìn)行基本思想：從輸入串開始，逐步進(jìn)行“歸約歸約”，直至歸約到文，直至歸約到文法的開始符號。即從語法樹的末端開始，步步向上法的開始符號。即從語法樹的末端開始，步步向上“歸約歸約”，直到，直到根結(jié)。根結(jié)。 歸約：若歸約：若V= ，W=， 是文法的產(chǎn)生式，如有是文法的產(chǎn)生式，如有V=W，則，則W直接歸約到直接歸約到V。例：

29、例： 文法文法GS： (1)S aAcBe (2) A b (3)A Ab (4) B d 識別識別abbcde是否為文法是否為文法S的一個句子。的一個句子。解題思想：掃描解題思想：掃描abbcde，從中找出一個子串，該子串與某一產(chǎn)生式，從中找出一個子串，該子串與某一產(chǎn)生式的右部相匹配。的右部相匹配。解：a b b c d e(1)a b b c d eA A(2)a b b c d eAA(3)a b b c d eAA(4)Ba b b c d eAA(5)BAS例：例： 文法文法GS： (1)S aAcBe (2) A b (3)A Ab (4) B d自下而上分析法存在的問題自下而上分

30、析法存在的問題可歸約串的問題可歸約串的問題； 該分析的每一步就是從當(dāng)前串中找一個子串該分析的每一步就是從當(dāng)前串中找一個子串（稱（稱“可歸約串可歸約串”），將它歸約到某個非終結(jié)符號），將它歸約到某個非終結(jié)符號 自下而上分析法的關(guān)鍵就是找哪個子串是自下而上分析法的關(guān)鍵就是找哪個子串是“可歸約串可歸約串”，哪個，哪個不是不是“可歸約串可歸約串”。例：上例中的例：上例中的(3)a b b c d eA A(3) 用產(chǎn)生式(2)而非(3)，則不能歸約到S 因此必須精確定義因此必須精確定義“可歸約串可歸約串” 3.6.3 句型分析的有關(guān)問題句型分析的有關(guān)問題在自上而下的分析方法中，存在的缺陷是在自上而下的

31、分析方法中，存在的缺陷是“回溯回溯”，如何確定用，如何確定用哪個右部代替左部？哪個右部代替左部？在自下而上的分析方法中，解決的關(guān)鍵問題是在自下而上的分析方法中，解決的關(guān)鍵問題是“可歸約串可歸約串”。短語、直接短語、句柄短語、直接短語、句柄1、短語：、短語：令文法令文法G，開始符號為開始符號為S，是是G的句型的句型（即（即S ），如果），如果S A且且A ，則稱，則稱是句型是句型相對于非終結(jié)符相對于非終結(jié)符A的短語。的短語。 如果有如果有A=，則稱，則稱是句型相對于規(guī)則是句型相對于規(guī)則A 的的直接短語直接短語。3、句柄、句柄 一個句型的最左直接短語稱為該句型的句柄。一個句型的最左直接短語稱為該句

32、型的句柄。 解題方法解題方法例：文法例：文法GE: E T | E+T T F | T*F F (E) | i 證明證明i+i*i是是G的一個句型，并指出這個句型的所有短語、直接短語、的一個句型，并指出這個句型的所有短語、直接短語、句柄。句柄。證明：證明：E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i接上例接上例語法樹：EE+TTT*FFFi3i1i2第第1層層 i1+i2*i3 相對于相對于E第第2層層 i1 相對于相對于E ; i2*i3 相對于相對于T第第3層層 i1 ,i2 相對于相對于T; i3 相對于相對于F第第4層層 i1 ,i2

33、相對于相對于F(F i直接短語直接短語)第第5層層 i+i*i是是G的一個句型，其中的一個句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型都是句型i1+i2*i3 的的短語，且短語，且i1 , i2 , i3 為直接短語，為直接短語， i1為句柄為句柄分析說明分析說明(2)作為作為“短語短語”的兩個條件是不可缺少的，僅僅有的兩個條件是不可缺少的，僅僅有A ，未必意，未必意味著味著就是句型就是句型的一個短語，因為還需要有的一個短語，因為還需要有S A這個條件。這個條件。例如：上例中有例如：上例中有E i1+i2，但，但i1+i2并不是該句型的一個短語，因為并不是該

34、句型的一個短語，因為不存在從不存在從E（開始符號）到（開始符號）到E* i3的推導(dǎo)。的推導(dǎo)。(1)短語、直接短語、句柄是針對某一句型（短語、直接短語、句柄是針對某一句型（S ）而言的）而言的;3.7 有關(guān)文法實用中的一些說明有關(guān)文法實用中的一些說明在實際應(yīng)用中在實際應(yīng)用中對文法提出一些限制對文法提出一些限制對文法進(jìn)行擴充對文法進(jìn)行擴充3.7.1 有關(guān)文法實用限制有關(guān)文法實用限制 在實用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。在實用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。1、不含有害規(guī)則、不含有害規(guī)則有害規(guī)則是指形如有害規(guī)則是指形如PP的產(chǎn)生式，因為這樣的產(chǎn)生式除了引起二義的產(chǎn)生式，

35、因為這樣的產(chǎn)生式除了引起二義外，沒有任何用處。外，沒有任何用處。2、不含多余規(guī)則、不含多余規(guī)則(1)不可到達(dá)的不可到達(dá)的即文法中的某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，則任何句子推即文法中的某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，則任何句子推導(dǎo)不可能用到它。也就是說導(dǎo)不可能用到它。也就是說 對非終結(jié)符對非終結(jié)符P，不存在，不存在S P， , ( (VNVT) )* * 3.7.1 有關(guān)文法實用限制有關(guān)文法實用限制(2) 不可終止的不可終止的即文法中的某些非終結(jié)符不能夠從它推出終結(jié)符串。也就是說即文法中的某些非終結(jié)符不能夠從它推出終結(jié)符串。也就是說 對非終結(jié)符對非終結(jié)符P，不存在，不存在P t， t VT* * 若文法均滿足以上兩個條件，則稱這個文法為若文法均滿足以上兩個條件，則稱這個文法為簡化了的文法簡化了的文法。文法文法GS：(1)SBe(2)BCe(3)BAf(4)AAe(5)Ae(6)CCf(7)Df（7）、（）、（6）、（）、（2）多余規(guī)則）多余規(guī)則3.7.2 上下文無關(guān)文法的上下文無關(guān)文法的規(guī)則規(guī)則自學(xué)自學(xué)例例1： 證明文法證