編譯原理-第02章(2)

1、2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 短語(yǔ)短語(yǔ) 令G是一個(gè)文法，S是文法的開(kāi)始符 號(hào)，假定是文法G的一個(gè)句型，如果 有 則稱 是相對(duì)于非終結(jié)符A的, 句型的 短語(yǔ)。 SA * + 且 A 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 則稱是直接短語(yǔ)。 直接短語(yǔ)直接短語(yǔ) SA * 且 A 令G是一個(gè)文法，S是文法的開(kāi)始符 號(hào)，假定是文法G的一個(gè)句型，如果 有 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 注意：短語(yǔ)和直接短語(yǔ)的區(qū)別 在于第二個(gè)條件, 直接短語(yǔ)中的第 二個(gè)條件表示有文法規(guī)則 A ， 因此，每個(gè)直接短語(yǔ)都是某規(guī)則右 部。 2.4 2.4 短

2、語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 句柄句柄 一個(gè)句型的最左直接短語(yǔ)稱為該句 型的句柄。 句柄特征： (1) 它是直接短語(yǔ)，即某規(guī)則右部。 (2) 它具有最左性。 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 注意: 短語(yǔ)、直接短語(yǔ)和句柄都 是針對(duì)某一句型的，都是指句型中 的哪些符號(hào)串能構(gòu)成短語(yǔ)和直接短 語(yǔ)，離開(kāi)具體的句型來(lái)談短語(yǔ)、直 接短語(yǔ)和句柄是無(wú)意義的。 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 例如 設(shè)有文法GS=(S,A,B,a,b,P,S) 其中P為： 求句型 baSb的全部短語(yǔ)、直接短語(yǔ)和句 柄。 SAB AAa | bB Ba | Sb 2.4

3、2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 對(duì)文法，首先建立該句型的推導(dǎo)過(guò)程： 最左推導(dǎo): 最右推導(dǎo): SAB AAa | bB Ba | Sb SAB ASbbBSbbaSb SAB baBbaSbbBB 分析 根據(jù)短語(yǔ)定義，可以從句型 的推導(dǎo)過(guò)程 中找出其全部短語(yǔ)、直接短 語(yǔ)和句柄。 句型 baSb 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 句型baSb中的子串Sb，是(相對(duì) 于非終結(jié)符B)句型baSb的短語(yǔ)， 且為直接短語(yǔ)。 SAB bBBbaBbaSb (2) SbaB * B Sb (1) SS * S baSb + 句型本身是(相對(duì)于非終結(jié)符S) 句型baSb

4、的短語(yǔ)。 根據(jù)最左推導(dǎo): S A * + A 2.4 2.4 短語(yǔ)、直接短語(yǔ)和句柄短語(yǔ)、直接短語(yǔ)和句柄 句型baSb中的子串a(chǎn)，是(相對(duì) 于非終結(jié)符B)句型baSb的短語(yǔ)， 且為直接短語(yǔ)、句柄。 句型baSb中的子串ba，是(相對(duì) 于非終結(jié)符A)句型baSb的短語(yǔ)。 B a (3) SbBSb * 根據(jù)最右推導(dǎo): SAB ASb bBSbbaSb (4) SASb * A ba + S A * + A 2.5 2.5 語(yǔ)法樹(shù)與文法的二義性語(yǔ)法樹(shù)與文法的二義性 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 1. 語(yǔ)法樹(shù)語(yǔ)法樹(shù) 對(duì)句型的推導(dǎo)過(guò)程給出一種圖形 表示, 這種表示稱為語(yǔ)法樹(shù)，也稱推 導(dǎo)樹(shù)。 2.5.1 2.

5、5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 例如 設(shè)有文法GE: 構(gòu)造句型i*i+i的語(yǔ)法樹(shù)。 首先給出句型的推導(dǎo)過(guò)程 (最左推導(dǎo)) ： EE+T | ET | T TT*F | T/F | F F(E) | i EE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 根據(jù)推導(dǎo)過(guò)程構(gòu)造句型i*i+i的語(yǔ)法樹(shù)如下： EE+T E E+T T+T T T*F+T T*F F*F+T F i*F+T i i*i+T i i*i+F F i*i+i i 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 由例可知，語(yǔ)法樹(shù)的構(gòu)造過(guò)程是從 文法的

6、開(kāi)始符號(hào)出發(fā)，構(gòu)造一個(gè)推導(dǎo)的 過(guò)程。 因?yàn)槲姆ǖ拿恳粋€(gè)句型 (句子) 都 存在一 個(gè)推導(dǎo)，所以文法的每個(gè)句型 (句子) 都存在一棵對(duì)應(yīng)的語(yǔ)法樹(shù)。 EE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 對(duì)句型i*i+i，還可給出最右推導(dǎo)： E E+T T T*F F i i F i 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 這也就是說(shuō)，一棵語(yǔ)法樹(shù)表示了 一個(gè)句型的種種可能的(但未必是所 有的)不同推導(dǎo)過(guò)程, 包括最左(最右) 推導(dǎo)。 3.5.1 3.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 2. 子樹(shù) 語(yǔ)法樹(shù)的子 樹(shù)是

7、由某一結(jié)點(diǎn) 連同所有分枝組 成的部分。 E E+T T T*F F i i F i 3.5.1 3.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 3. 簡(jiǎn)單子樹(shù) 語(yǔ)法樹(shù)的 簡(jiǎn)單子樹(shù)是指 只有單層分枝 的子樹(shù)。 E E+T T T*F F i i F i 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 句型的短語(yǔ)、直接短語(yǔ)和句柄的 直觀解釋是： 短語(yǔ)：子樹(shù)的末端結(jié)點(diǎn)形成的符號(hào)串是 相對(duì)于子樹(shù)根的短語(yǔ)。 直接短語(yǔ)：簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的 符號(hào)串是相對(duì)于簡(jiǎn)單子樹(shù)根的直接短語(yǔ)。 句柄：最左簡(jiǎn)單子樹(shù)的末端結(jié)點(diǎn)形成的 符號(hào)串是句柄。 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) E E+T T T*F F i

8、 i F i 短語(yǔ): ni*i+i ni*i n第一個(gè)i n第二個(gè)i n第三個(gè)i n三個(gè)i都是直接短語(yǔ) n第一個(gè)i是句柄 注意:i+i不是句型的短語(yǔ) 句子 i*i+i 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 前例 對(duì)文法GS=(S,A,B,a,b,P,S) 其中P為： 可用語(yǔ)法樹(shù)非常直觀地求出句型baSb 的全部短語(yǔ)，直接短語(yǔ)和句柄。 SAB AAa | bB Ba | Sb 2.5.1 2.5.1 推導(dǎo)和語(yǔ)法樹(shù)推導(dǎo)和語(yǔ)法樹(shù) 分析 首先根據(jù)句型baSb的推導(dǎo)過(guò)程畫(huà)出對(duì) 應(yīng)的語(yǔ)法樹(shù)如下： Sb 為句型的相對(duì)于B的短語(yǔ)、直接短語(yǔ) baSb 為句型的相對(duì)于S的短語(yǔ) ba 為句型的相對(duì)于A的

9、短語(yǔ) a 句型的相對(duì)于B的短語(yǔ)、直接短語(yǔ)和句柄 SABbBBbaBbaSb SABASbbBSbbaSb S AB bB Sb a 由語(yǔ)法樹(shù)可知 2.5.2 2.5.2 文法的二義性文法的二義性 從前面的討論可以看出，對(duì)于文法G中 任一句型的推導(dǎo)序列, 我們總能為它構(gòu)造 一棵語(yǔ)法樹(shù)，現(xiàn)在我們提出一個(gè)問(wèn)題： 文法的某個(gè)句型是否只對(duì)應(yīng)唯一的一棵 語(yǔ)法樹(shù)呢？也就是，它是否只有唯一的一 個(gè)最左(最右)推導(dǎo)呢？ 2.5.2 2.5.2 文法的二義性文法的二義性 例如 設(shè)有文法GE： 句子 i*i+i 有兩個(gè)不同的最左推導(dǎo)， 對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)。 E E+E | E*E | (E) | i 2.5.2

10、2.5.2 文法的二義性文法的二義性 最左推導(dǎo)1 EE+EE*E+E i*E+Ei*i+E i*i+i 最左推導(dǎo)2 EE*Ei*E i*E+Ei*i+E i*i+i E E*E E +E i i i E E+E E *E i i i 2.5.2 2.5.2 文法的二義性文法的二義性 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩 棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義 性的。 或者說(shuō)，若一個(gè)文法中存在某個(gè)句 子，它有兩個(gè)不同的最左 (最右) 推導(dǎo)， 則這個(gè)文法是二義性的。 E E+E | E*E | (E) | i 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 1. 不改變文法中原有的語(yǔ)法規(guī)則, 僅加

11、 進(jìn)一些非形式的語(yǔ)法規(guī)定。 E E+E E *E i i i 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 2. 構(gòu)造一個(gè)等價(jià)的無(wú)二義性文法。即 把排除二義性的規(guī)則合并到原有文法中, 改寫(xiě)原有的文法。 例如，對(duì)于上例文法GE，將運(yùn)算符的 優(yōu)先順序和結(jié)合規(guī)則：*優(yōu)先于; 、* 左結(jié)合加到原有文法中, 可構(gòu)造出無(wú)二義 性文法如下 ： 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 則句子i*i+i只有 唯一一棵語(yǔ)法樹(shù)： EE+T | T TT*F | F F(E) | i E E+T T T * F F i i F i 2.5.3 2.5.3 文法二義性的消除文法二義性的消除

12、 例2 定義某程序語(yǔ)言條件語(yǔ)句的文法G為: 試證明該文法是二義性的并消除之。 分析 該文法的句子 if b if b A else A 對(duì)應(yīng)下面兩棵不同的語(yǔ)法樹(shù)： Sif b S | if b S else S | A (其它語(yǔ)句） 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 所以該文法是二義的。 S ifb S b S Sif A else A S bSS if A else A if b S Sif b S | if b S else S | A 句子 if b if b A else A 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 消除文法的二義性可采用下面兩

13、種方法： 1. 不改變已有規(guī)則，僅 加進(jìn)一非形式的語(yǔ)法規(guī) 定：else與前面最接近 的不帶else的 if 相對(duì)。 S ifb S b S Sif A else A 文法G的句子 if b if b A else 只對(duì)應(yīng)唯一的一棵語(yǔ) 法樹(shù)，消除了二義。 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 2. 改寫(xiě)文法G為G S S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 G: Sif b S | if b S else S | A (其它語(yǔ)句） G: 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 這是

14、因?yàn)橥ㄟ^(guò)分析，得知引起 二義性的原因是: ifelse 語(yǔ)句的 if 后可是 if型，因此改寫(xiě)文法時(shí)規(guī)定: if else之間只能是ifelse語(yǔ) 句或其他語(yǔ)句。 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 S S1 | S2 S1 if b S1 else S1 | A S2 if b S | if b S1 else S2 if b S bif A else A S S2 S1 S1S1 對(duì)改寫(xiě)后的文法，句子 if b if b A else A 只對(duì)應(yīng)唯一的一棵語(yǔ)法 樹(shù)。 通常我們只說(shuō)文法的二義性, 而不 說(shuō)語(yǔ)言的二義性, 這是因?yàn)榭赡苡袃蓚€(gè) 不同的文法G和G ，而且其中一

15、個(gè)是二 義性的，另一個(gè)是無(wú)二義性的, 但卻有 L(G)=L(G), 即這兩個(gè)文法所產(chǎn)生的語(yǔ)言 是相同的。 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 應(yīng)該指出的是文法的二義性和語(yǔ) 言的二義性是兩個(gè)不同的概念。 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 將一個(gè)語(yǔ)言說(shuō)成是二義性的，是 指對(duì)它不存在無(wú)二義性的文法，這樣 的語(yǔ)言稱為先天二義性的語(yǔ)言。 例如 L= ai bj ck | i=j 或 j=k 且 i, j, k1 便是這種語(yǔ)言。 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 著名的語(yǔ)言學(xué)家喬姆斯基(Chomsky) 將文法和語(yǔ)言分為四大類(lèi)，即0型、1型、

16、2型、3型。劃分的依據(jù)是對(duì)文法中的規(guī) 則施加不同的限制。 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 0型文法（無(wú)限制文法） 若文法G=(VN,VT, P, S)中的每條規(guī)則 是這樣一種結(jié)構(gòu)： 而且中至少含一個(gè)非終結(jié)符, 則稱G 是0型文法。 (VNVT)+ ,(VNVT)* 0型文法描述的語(yǔ)言是 0型語(yǔ)言。 0型文法沒(méi)有加任何限制條件，又稱為 無(wú)限制性文法，相應(yīng)的語(yǔ)言稱為無(wú)限制 性語(yǔ)言。 0型語(yǔ)言由 圖靈機(jī)識(shí)別。 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 例如，有0型文法G=(VN,VT, P, S) 其中：VN=A,B,S , VT=0,1 其描述的 0 型語(yǔ)言為 L0(GS

17、)= P: S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0B 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 1型文法（上下文有關(guān)文法） 1型文法也稱為上下文有關(guān)文法， 相應(yīng) 的語(yǔ)言又稱為上下文有關(guān)語(yǔ)言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： , (VNVT)* ,AVN , 則稱G是1型文法。 1型文法描述的 語(yǔ)言是1型語(yǔ)言。 1型語(yǔ)言由線性 界限自動(dòng)機(jī)識(shí)別。 (VNVT)+ 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 例如，有1型文法G=(VN,VT, P, S) 其中：VN=S,A,B , VT=a,b,c P: S a

18、SAB | abB BA BA BA AA AA AB bA bb bB bc cB cc 其描述的1型語(yǔ)言為L(zhǎng)1(GS)=anbncn | n1 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 2型文法（上下文無(wú)關(guān)文法） 2型文法又稱上下文無(wú)關(guān)文法，其產(chǎn)生的 語(yǔ)言又稱為上下文無(wú)關(guān)的語(yǔ)言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： AVN ,(VNVT)* 則稱G是2型文法。 2型文法描述的語(yǔ) 言是2型語(yǔ)言。 2型語(yǔ)言由下 推自動(dòng)機(jī)識(shí) 別。 例如前面描述算術(shù)表達(dá)式的文法GE: EE+E | E*E | (E) | i 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和

19、語(yǔ)言的分類(lèi) 其描述的語(yǔ)言為 L2(GS)=x | x a, b+ 且x中a和b的個(gè)數(shù)相同 例如，有2型文法G=(VN,VT, P, S) 其中：VN=S, A, B , VT=a, b P= S aB | bA A a | aS | bAA B b | bS | aBB 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 3型文法（正規(guī)文法） 右線性文法和左線性文法都稱為3型文法。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的形式 為A aB 或 A a , 其中： A , BVN, a VT*, 則稱G是右線性文法。 若文法G=(VN,

20、VT, P, S)中的每一條規(guī)則的形式 為A Ba 或 A a , 其中： A , BVN , a VT*, 則稱G是左線性文法。 3型文法描述的語(yǔ) 言是3型語(yǔ)言。 3型語(yǔ)言由有 窮自動(dòng)機(jī)識(shí)別。 3型文法也稱正規(guī)文法。正規(guī)文法產(chǎn)生的語(yǔ)言 稱為正規(guī)語(yǔ)言。 例如，用左線性正規(guī)文法和右線性 正規(guī)文法定義標(biāo)識(shí)符 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 用I代表標(biāo)識(shí)符; l代表任意一個(gè)字母; d代表任意一個(gè)數(shù)字; 則定義標(biāo)識(shí)符的文 法為： 左線性文法: P: I l | Il | Id 右線性文法: P: I l | lT Tl | d | lT| dT 例如，用左線性正規(guī)文法和右線性 正規(guī)文

21、法定義無(wú)符號(hào)整數(shù) 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 用N代表無(wú)符號(hào)整數(shù); d代表任意一個(gè) 數(shù)字；則定義的無(wú)符號(hào)整數(shù)文法為： 左線性文法: P: N Nd | d 右線性文法: P: N dN | d 2.6 2.6 文法和語(yǔ)言的分類(lèi)文法和語(yǔ)言的分類(lèi) 由上述四類(lèi)文法的定義可知, 從0型文 法到3型文法, 是逐漸增加對(duì)規(guī)則的限制 條件而得到的，因此每一種正規(guī)文法都 是上下文無(wú)關(guān)的文法，每一種上下文無(wú) 關(guān)的文法都是上下文有關(guān)的文法，而每 一種上下文有關(guān)的文法都是0型文法, 而 由它們所定義的語(yǔ)言類(lèi)是依次縮小的， 有 L0 L1 L2 L3 。 2.7 2.7 有關(guān)文法的實(shí)用限制和變換

22、有關(guān)文法的實(shí)用限制和變換 文法是用來(lái)描述程序設(shè)計(jì)語(yǔ)言的，在 實(shí)際應(yīng)用中需要對(duì)文法加一些限制條件。 1. 文法中不能含有形如A A 的規(guī)則。 這種規(guī)則我們稱之為有害規(guī)則。 對(duì)文法的實(shí)用限制有以下兩點(diǎn)： 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 2. 文法中不能有多余規(guī)則。所謂多余 規(guī)則是指文法中出現(xiàn)以下兩種規(guī)則： (1) 某條規(guī)則 A 的左部符號(hào)A不在 所屬文法的任何其他規(guī)則右部出現(xiàn)，即 在推導(dǎo)文法的所有句子中始終都不可能 用到的規(guī)則。 (2) 對(duì)文法中的某個(gè)非終結(jié)符A，無(wú)法 從它推出任何終結(jié)符號(hào)串來(lái)。 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 例

23、如 設(shè)有文法GS: P: S Bd A Ad | d B Cd | Ae C Ce D e 刪除多余規(guī)則后的 文法變換為: P: S Bd A Ad | d B Ae 2.7 2.7 有關(guān)文法的實(shí)用限制和變換有關(guān)文法的實(shí)用限制和變換 若程序設(shè)計(jì)語(yǔ)言的文法含有多余規(guī)則， 其中必定有錯(cuò)誤存在，因此檢查文法中是 否含有多余規(guī)則對(duì)我們來(lái)說(shuō)是很重要的。 思考題 P26 2.1 2.2（2） 2.3 L2 ,L3 2.7 2.8 2.9 本章重點(diǎn)介紹了語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式描 述、語(yǔ)法樹(shù)以及文法的二義性, 主要內(nèi)容有： 1. 設(shè)計(jì)一個(gè)文法定義一個(gè)已知的語(yǔ)言 (1) 文法是一個(gè)四元組 G=(VN,VT, P,

24、 S)， 文法四大要素中，關(guān)鍵是一組規(guī)則, 它定義 （或描述）了一個(gè)語(yǔ)言的結(jié)構(gòu)。 從文法定義可知, 文法對(duì)于程序設(shè)計(jì)者來(lái) 說(shuō)，文法給出了語(yǔ)言的精確定義和描述。 本章小結(jié)本章小結(jié) 本小結(jié)花時(shí)45分鐘2004/2/28 (2) 分析已知語(yǔ)言句子的結(jié)構(gòu)特征, 設(shè)計(jì) 出相應(yīng)的一組規(guī)則，但不唯一。 (4) 若語(yǔ)言是無(wú)窮集合, 設(shè)計(jì)該語(yǔ)言的文 法一定是遞歸的。 本章小結(jié)本章小結(jié) (3) 設(shè)計(jì)的文法必須能定義已知的語(yǔ)言, 不能超出或縮小所定義語(yǔ)言的范圍。 分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相 應(yīng)規(guī)則 例1. 給出語(yǔ)言 L2=an bm| mn1 的文法 P2: SAB L2=ab,abb,abbb, aa

25、bb,aabbb,aabbbb, aaabbb, aabbbb， AaAb | ab BbB | 本章小結(jié)本章小結(jié) 分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相 應(yīng)規(guī)則 例2. 給出語(yǔ)言 L1=a2n+1|n0 的文法 P1: AaB | aP1：AaAa | a 或或 L1=a, aaa, aaaaa, aaaaaaa, aaaaaaaaa， Baa | aBa 本章小結(jié)本章小結(jié) 本章小結(jié)本章小結(jié) 分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì)出相 應(yīng)規(guī)則 例3. 給出語(yǔ)言L3=anbmck| n,m,k0的文法 P3: AaA | bB | cC |P3: AaA | B 或或 L3=,a,aa,aaa,b

26、,bb,bbb,c,cc,ccc, , ab,abb, ,bc,bcc， CcC | BbB | cC | CcC | BbB | C 本章小結(jié)本章小結(jié) L4=0 ,2,4,6,8,10,12,14,16,18,20,22,24,26, 例4. 寫(xiě)一個(gè) 文法,使其語(yǔ)言是正偶數(shù)的集合,每 個(gè)偶數(shù)不以0開(kāi)頭。 P4: NE | AE N0 | 2 | 4 | 6 | 8 |BN 或或 分析 不以0開(kāi)頭的偶數(shù)集合中串的結(jié)構(gòu)特征: AD | AD E0 | 2 | 4 | 6 | 8 D1 | 2 | 3 | | 9 D0 | 1 | 2 | 3 | 9 B1 | 2 | 3 | | 9 |B0 P4

27、: 本章小結(jié)本章小結(jié) A 0A1 | P : S 1S0 | 0A1 | 例5. 給出語(yǔ)言L=1n0m1m0n | n,m0的 文法。 分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征, 設(shè)計(jì) 出相應(yīng)規(guī)則 L=,01,0011,10,1100,1010,100110, 110100,11001100 本章小結(jié)本章小結(jié) P : S a | 0S0 | 1S1 例6. 給出語(yǔ)言L=WaWt | W0|1*,Wt 表示W(wǎng)的逆的文法。 分析 根據(jù)語(yǔ)言句子的結(jié)構(gòu)特征，設(shè)計(jì) 出相應(yīng)規(guī)則 L=a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001,

28、W=,0, 1 ,01, 10, 00, 11, 101, 110, 100, 111, 本章小結(jié)本章小結(jié) 2. 已知一個(gè)文法，確定該文法所定義的 語(yǔ)言。 (2) 給定一個(gè)文法，可根據(jù)語(yǔ)言和推導(dǎo)定 義推導(dǎo)出文法的句子，從而確定出該文法 所定義的語(yǔ)言。 (1) 文法所定義的語(yǔ)言 L(GS)=x|S x且xVT* * 本章小結(jié)本章小結(jié) 自然語(yǔ)言描述。 例如, L=x|xa,b+且x中a,b個(gè)數(shù)相同 式子描述。例如 L=a2nbb | n0。 正規(guī)式描述。 (3) 語(yǔ)言可用 本章小結(jié)本章小結(jié) 例1 文法GA=(A,a,b,AbA | a, A) 所生成的語(yǔ)言是什么？ 分析 AbAbbAbbbAbnA

29、bna L(GA)= bna | n0 本章小結(jié)本章小結(jié) 例2 文法GN為: N ND | D D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1) GN所生成的語(yǔ)言是什么？ (2) 給出句子0127的最左、最右推導(dǎo)。 本章小結(jié)本章小結(jié) L(GN)= | 0,1,2, 9+ = | 為可帶前導(dǎo)0的正整數(shù) = | 為數(shù)字串 最左推導(dǎo): NNDN7ND7N27ND2 7 N127D1270127 最右推導(dǎo): NNDNDDNDDDDDDD 0DDD01DD012D0127 N ND | D D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

30、9 本章小結(jié)本章小結(jié) 例3. 已知文法GS=( A,B,a,b,c,d, P, S ) , 其中 P 為: 分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anbnc2Bd2 anbncm-1Bdm-1anbncmdm L(GS)=anbncmdm | n ,m1 該文法 所生成的語(yǔ)言是什么？ A aAb | ab B cBd | cd S AB 本章小結(jié)本章小結(jié) 3. 求句型的短語(yǔ)、直接短語(yǔ)和句柄 (1) 短語(yǔ)、直接短語(yǔ)和句柄是對(duì)某句 型而言的。 (2) 短語(yǔ)總是句型的某個(gè)子串，它對(duì)應(yīng) 子樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。 (3) 直接短語(yǔ)是某條規(guī)則右部，它對(duì)應(yīng) 簡(jiǎn)單子

31、樹(shù)未端結(jié)點(diǎn)形成的符號(hào)串。 (4) 最左邊的直接短語(yǔ)是句柄。 本章小結(jié)本章小結(jié) 例1 已知文法GE： 證明 E+T*F是它的一個(gè)句型,指出這個(gè)句 型的短語(yǔ)直接短語(yǔ)和句柄。 EE+TE+T*F 短語(yǔ): E+T*F、T*F E+T*F是它的一個(gè)句型。 畫(huà)出該句型的語(yǔ) 法樹(shù): 句柄: T*F 直接短語(yǔ): T*F E T FT +E * EE+T | E-T | T TT*F | T/F | T T(E) | i 本章小結(jié)本章小結(jié) 例2 已知文法GS： 試找出符號(hào)串(a)和(A(SaA)(b)的短語(yǔ) 直接短語(yǔ)和句柄(如果有的話)。 S(AS) | (b) A(SaA) | (a) 符號(hào)串(a)不是文法的句型，因此