第三章文法和語(yǔ)言

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

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

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

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

5、x3= ababab 當(dāng)當(dāng)n0時(shí)，時(shí)， xn x xn-1 = xn-1 x3.2 符號(hào)和符號(hào)串符號(hào)和符號(hào)串三、符號(hào)串集合的運(yùn)算三、符號(hào)串集合的運(yùn)算 連接（乘積）：連接（乘積）：設(shè)符號(hào)串集合設(shè)符號(hào)串集合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上長(zhǎng)度為上長(zhǎng)度為n的字符串集的字符串

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

7、中 “”讀讀為為“是是”或或“定義為定義為”；非終結(jié)符：非終結(jié)符：在規(guī)則中用在規(guī)則中用括起來(lái)括起來(lái)非終結(jié)符用非終結(jié)符用VN表示表示終結(jié)符終結(jié)符語(yǔ)言中不可再分的字符串語(yǔ)言中不可再分的字符串終結(jié)符用終結(jié)符用VT表示表示定義定義3.1 文法文法G G是一個(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：文法的開(kāi)始符號(hào)，：文法的開(kāi)始符號(hào)，S S V VN NP P：產(chǎn)生式集合：產(chǎn)生式集

8、合( (非空、有窮非空、有窮) )，產(chǎn)生式的形式是產(chǎn)生式的形式是 和和 屬于屬于 ( (V VT T V VN N) )* *開(kāi)始符開(kāi)始符S S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。3.3 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義例：例： 文法文法G =（VN，VT，P，S） VN標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(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 = 注意：注意：有時(shí)不用將文法有時(shí)不用將文法G G的四元組顯示的表示出來(lái)，而只寫產(chǎn)生式的四元組顯示的表示出來(lái)，而

9、只寫產(chǎn)生式 約定：第一個(gè)產(chǎn)生式的左部是開(kāi)始符號(hào)約定：第一個(gè)產(chǎn)生式的左部是開(kāi)始符號(hào) 可將可將G寫成寫成GS，S為文法為文法G的開(kāi)始符號(hào)的開(kāi)始符號(hào)下面是一個(gè)文法的等價(jià)寫法下面是一個(gè)文法的等價(jià)寫法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是是一個(gè)產(chǎn)生式，且一個(gè)產(chǎn)生式，且、(V VN NV VT

10、 T) )* * 符號(hào)符號(hào) =指推導(dǎo)一步，即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則指推導(dǎo)一步，即推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則（產(chǎn)生式）（產(chǎn)生式）2、長(zhǎng)度為長(zhǎng)度為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)過(guò)一步或若干步，可推導(dǎo)出出發(fā)經(jīng)過(guò)一步或若干步，可推導(dǎo)出an 。3、長(zhǎng)度為長(zhǎng)度為n（n0）的推導(dǎo)）的推導(dǎo) a1 an 表示：從表示：從a1出發(fā)經(jīng)過(guò)出發(fā)經(jīng)過(guò)0步（步（ a1 an ）或若干步，可推導(dǎo)出）或若干步，可推導(dǎo)出an 。例：例： 文法文法G ： | | a|b|c|x|y|z 0|1|

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

12、法是文法GS的句型。的句型。2.句子句子：僅含終結(jié)符的句型是一個(gè)句子，即：僅含終結(jié)符的句型是一個(gè)句子，即S ，VT*, 則則是句子。是句子。3.語(yǔ)言語(yǔ)言：文法：文法G所產(chǎn)生的句所產(chǎn)生的句 子的全體是一個(gè)語(yǔ)言，記作子的全體是一個(gè)語(yǔ)言，記作L(G) L(G)=|S ,且且VT*語(yǔ)言的例子語(yǔ)言的例子例：文法例：文法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的語(yǔ)言是什么。的語(yǔ)言是什么。解：通過(guò)對(duì)第一個(gè)產(chǎn)生式使用解：通過(guò)對(duì)第一個(gè)產(chǎn)生式使用n-1n-1次，然后使用第二個(gè)產(chǎn)生式一次，得次，然后使用第二個(gè)產(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 文法的文法的等價(jià)等價(jià) 若若L(G1) = L(G2)，則稱文法，則稱文法G1和和G2是等價(jià)的是等價(jià)的例如例如: 文法文法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 文法的類型文法的類型 喬姆斯基建立的形式語(yǔ)言對(duì)計(jì)算機(jī)科學(xué)的發(fā)展具有深刻的喬姆斯基建立的形式語(yǔ)言對(duì)計(jì)算機(jī)科學(xué)的發(fā)展具有深刻的意義。意義。他把文法分成四種類型：他把文法分成四種類型：0型、型、1型、型、2型和型和3型。型。它們的差別在于對(duì)產(chǎn)生式施加不同的限制。它們的差別在于對(duì)產(chǎn)生式施加不同的限制。0型文法（或稱短語(yǔ)文法）l G=( VN

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

16、的任何產(chǎn)生式 均均滿足滿足| | (指符號(hào)串的長(zhǎng)度指符號(hào)串的長(zhǎng)度)，僅僅，僅僅S 例外。例外。 上下文有關(guān)就是對(duì)非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文上下文有關(guān)就是對(duì)非終結(jié)符進(jìn)行替換時(shí)必須考慮上下文l例如：例如：1型文法型文法G的產(chǎn)生式也可寫成的產(chǎn)生式也可寫成A ，其中，其中、都在都在(VNVT)*中，且中，且 ，A VN ，則說(shuō)明了非終結(jié)符，則說(shuō)明了非終結(jié)符A必須在必須在、這樣一個(gè)上下文環(huán)境中才可以替換。這樣一個(gè)上下文環(huán)境中才可以替換。 2型文法（或稱上下文無(wú)關(guān)文法）型文法（或稱上下文無(wú)關(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； 上下文無(wú)關(guān)文法的說(shuō)明上下文無(wú)關(guān)文法的說(shuō)明 上下文無(wú)關(guān)，顧名思義就是非終結(jié)符的替換可以不必考上下文無(wú)關(guān)，顧名思義就是非終結(jié)符的替換可以不必考慮上下文。慮上下文。 由于這種文法對(duì)程序已基本可以描述，因此，上下文無(wú)由于這種文法對(duì)程序已基本可以描述，因此，上下文無(wú)關(guān)文法常簡(jiǎn)稱為文

18、法。關(guān)文法常簡(jiǎ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 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)一、語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）一、語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）1.直觀定義：用圖表示上下文無(wú)關(guān)文法句型推導(dǎo)的直觀方法。直觀定義：用圖表示上下文無(wú)關(guān)文法句型推導(dǎo)的直觀方法。2. 形式定義形式定義給定文法給定文法G=( VN, VT, P, S)，對(duì)于，對(duì)于G的任何句型都能構(gòu)造與之相關(guān)聯(lián)的語(yǔ)法的任何句型都能構(gòu)造與之相關(guān)聯(lián)的語(yǔ)法樹(shù)，這棵語(yǔ)法樹(shù)滿足以下樹(shù)，這棵語(yǔ)法樹(shù)滿足以下4個(gè)條件：個(gè)條件：（1）根結(jié)點(diǎn)由開(kāi)始符號(hào)）根結(jié)點(diǎn)由開(kāi)始符號(hào)S所標(biāo)記；所標(biāo)記；

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

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

22、(, ), P, E)，其中，其中P為：為： E E+E | E*E | (E) | i對(duì)該文法關(guān)于對(duì)該文法關(guān)于(i*i+i)的推導(dǎo)的語(yǔ)法樹(shù)如下所示：的推導(dǎo)的語(yǔ)法樹(shù)如下所示：例例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)樹(shù)。的推導(dǎo)樹(shù)。最左推導(dǎo)最左推導(dǎo)/最右推導(dǎo)最右推導(dǎo)/規(guī)范句型規(guī)范句型最左推導(dǎo)最左推導(dǎo)是指：任何一步是指：任何一步= 都是對(duì)都是對(duì)中的最左非終結(jié)符進(jìn)行替換。中的最左非終結(jié)符進(jìn)行替換。同樣，可定義同樣，可定義最右推導(dǎo)最右推導(dǎo)（又稱規(guī)范推導(dǎo)）：任何一步（又

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

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

25、。我們所能做的就是為無(wú)二義性尋找一些充分條件我們所能做的就是為無(wú)二義性尋找一些充分條件例如對(duì)文法例如對(duì)文法GE： E E+E | E*E | (E) | i 修改，規(guī)定運(yùn)算符修改，規(guī)定運(yùn)算符“+”與與“*”的優(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)生式，識(shí)別輸入的符號(hào)是否是句型分析的任務(wù)就是按文法的產(chǎn)生式，識(shí)別輸入的符號(hào)是否是該文法的句型。該文法的句型。我們把完成句型分析的程序稱為分析程序或識(shí)別程序

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

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

28、式是錯(cuò)誤的，則退回去重新選擇候選式的方式。例如上例中的的(3)。S S S x A y (3) 選用第選用第1個(gè)候選式個(gè)候選式 * 回溯的產(chǎn)生使算法代價(jià)極高，效率很低?；厮莸漠a(chǎn)生使算法代價(jià)極高，效率很低。 * 3.6.2自下而上的分析法自下而上的分析法 基本思想：從輸入串開(kāi)始，逐步進(jìn)行基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約歸約”，直至歸約到文，直至歸約到文法的開(kāi)始符號(hào)。即從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上法的開(kāi)始符號(hào)。即從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約歸約”，直到，直到根結(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 識(shí)別識(shí)別abbcde是否為文法是否為文法S的一個(gè)句子。的一個(gè)句子。解題思想：掃描解題思想：掃描abbcde，從中找出一個(gè)子串，該子串與某一產(chǎn)生式，從中找出一個(gè)子串，該子串與某一產(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自下而上分析法存在的問(wèn)題自下而上分

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

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

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

33、相對(duì)于相對(duì)于F(F i直接短語(yǔ)直接短語(yǔ))第第5層層 i+i*i是是G的一個(gè)句型，其中的一個(gè)句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型都是句型i1+i2*i3 的的短語(yǔ)，且短語(yǔ)，且i1 , i2 , i3 為直接短語(yǔ)，為直接短語(yǔ)， i1為句柄為句柄分析說(shuō)明分析說(shuō)明(2)作為作為“短語(yǔ)短語(yǔ)”的兩個(gè)條件是不可缺少的，僅僅有的兩個(gè)條件是不可缺少的，僅僅有A ，未必意，未必意味著味著就是句型就是句型的一個(gè)短語(yǔ)，因?yàn)檫€需要有的一個(gè)短語(yǔ)，因?yàn)檫€需要有S A這個(gè)條件。這個(gè)條件。例如：上例中有例如：上例中有E i1+i2，但，但i1+i2并不是該句型的一個(gè)短語(yǔ)，因?yàn)椴⒉皇窃?/p>

34、句型的一個(gè)短語(yǔ)，因?yàn)椴淮嬖趶牟淮嬖趶腅（開(kāi)始符號(hào)）到（開(kāi)始符號(hào)）到E* i3的推導(dǎo)。的推導(dǎo)。(1)短語(yǔ)、直接短語(yǔ)、句柄是針對(duì)某一句型（短語(yǔ)、直接短語(yǔ)、句柄是針對(duì)某一句型（S ）而言的）而言的;3.7 有關(guān)文法實(shí)用中的一些說(shuō)明有關(guān)文法實(shí)用中的一些說(shuō)明在實(shí)際應(yīng)用中在實(shí)際應(yīng)用中對(duì)文法提出一些限制對(duì)文法提出一些限制對(duì)文法進(jìn)行擴(kuò)充對(duì)文法進(jìn)行擴(kuò)充3.7.1 有關(guān)文法實(shí)用限制有關(guān)文法實(shí)用限制 在實(shí)用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。在實(shí)用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。1、不含有害規(guī)則、不含有害規(guī)則有害規(guī)則是指形如有害規(guī)則是指形如PP的產(chǎn)生式，因?yàn)檫@樣的產(chǎn)生式除了引起二義的產(chǎn)生式，

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