編譯原理-第02章(2)

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

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

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

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

5、5.1 推導和語法樹推導和語法樹 例如 設(shè)有文法GE: 構(gòu)造句型i*i+i的語法樹。 首先給出句型的推導過程 (最左推導) ： 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 推導和語法樹推導和語法樹 根據(jù)推導過程構(gòu)造句型i*i+i的語法樹如下： 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 推導和語法樹推導和語法樹 由例可知，語法樹的構(gòu)造過程是從 文法的

6、開始符號出發(fā)，構(gòu)造一個推導的 過程。 因為文法的每一個句型 (句子) 都 存在一 個推導，所以文法的每個句型 (句子) 都存在一棵對應(yīng)的語法樹。 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 推導和語法樹推導和語法樹 對句型i*i+i，還可給出最右推導： E E+T T T*F F i i F i 2.5.1 2.5.1 推導和語法樹推導和語法樹 這也就是說，一棵語法樹表示了 一個句型的種種可能的(但未必是所 有的)不同推導過程, 包括最左(最右) 推導。 3.5.1 3.5.1 推導和語法樹推導和語法樹 2. 子樹 語法樹的子 樹是

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

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

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

10、2.5.2 文法的二義性文法的二義性 最左推導1 EE+EE*E+E i*E+Ei*i+E i*i+i 最左推導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 文法的二義性文法的二義性 如果一個文法存在某個句子對應(yīng)兩 棵不同的語法樹，則說這個文法是二義 性的。 或者說，若一個文法中存在某個句 子，它有兩個不同的最左 (最右) 推導， 則這個文法是二義性的。 E E+E | E*E | (E) | i 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 1. 不改變文法中原有的語法規(guī)則, 僅加

11、 進一些非形式的語法規(guī)定。 E E+E E *E i i i 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 2. 構(gòu)造一個等價的無二義性文法。即 把排除二義性的規(guī)則合并到原有文法中, 改寫原有的文法。 例如，對于上例文法GE，將運算符的 優(yōu)先順序和結(jié)合規(guī)則：*優(yōu)先于; 、* 左結(jié)合加到原有文法中, 可構(gòu)造出無二義 性文法如下 ： 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 則句子i*i+i只有 唯一一棵語法樹： 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 定義某程序語言條件語句的文法G為: 試證明該文法是二義性的并消除之。 分析 該文法的句子 if b if b A else A 對應(yīng)下面兩棵不同的語法樹： Sif b S | if b S else S | A (其它語句） 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ī)則，僅 加進一非形式的語法規(guī) 定：else與前面最接近 的不帶else的 if 相對。 S ifb S b S Sif A else A 文法G的句子 if b if b A else 只對應(yīng)唯一的一棵語 法樹，消除了二義。 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 2. 改寫文法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 (其它語句） G: 2.5.3 2.5.3 文法二義性的消除文法二義性的消除 這是

14、因為通過分析，得知引起 二義性的原因是: ifelse 語句的 if 后可是 if型，因此改寫文法時規(guī)定: if else之間只能是ifelse語 句或其他語句。 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 對改寫后的文法，句子 if b if b A else A 只對應(yīng)唯一的一棵語法 樹。 通常我們只說文法的二義性, 而不 說語言的二義性, 這是因為可能有兩個 不同的文法G和G ，而且其中一

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

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

17、)= P: S 0AB 1B 0 B SA | 01 A1 SB1 A0 S0B 2.6 2.6 文法和語言的分類文法和語言的分類 1型文法（上下文有關(guān)文法） 1型文法也稱為上下文有關(guān)文法， 相應(yīng) 的語言又稱為上下文有關(guān)語言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： , (VNVT)* ,AVN , 則稱G是1型文法。 1型文法描述的 語言是1型語言。 1型語言由線性 界限自動機識別。 (VNVT)+ 2.6 2.6 文法和語言的分類文法和語言的分類 例如，有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型語言為L1(GS)=anbncn | n1 2.6 2.6 文法和語言的分類文法和語言的分類 2型文法（上下文無關(guān)文法） 2型文法又稱上下文無關(guān)文法，其產(chǎn)生的 語言又稱為上下文無關(guān)的語言。 若文法G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A , 其中： AVN ,(VNVT)* 則稱G是2型文法。 2型文法描述的語 言是2型語言。 2型語言由下 推自動機識 別。 例如前面描述算術(shù)表達式的文法GE: EE+E | E*E | (E) | i 2.6 2.6 文法和語言的分類文法和

19、語言的分類 其描述的語言為 L2(GS)=x | x a, b+ 且x中a和b的個數(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 文法和語言的分類文法和語言的分類 2.6 2.6 文法和語言的分類文法和語言的分類 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型文法描述的語 言是3型語言。 3型語言由有 窮自動機識別。 3型文法也稱正規(guī)文法。正規(guī)文法產(chǎn)生的語言 稱為正規(guī)語言。 例如，用左線性正規(guī)文法和右線性 正規(guī)文法定義標識符 2.6 2.6 文法和語言的分類文法和語言的分類 用I代表標識符; l代表任意一個字母; d代表任意一個數(shù)字; 則定義標識符的文 法為： 左線性文法: P: I l | Il | Id 右線性文法: P: I l | lT Tl | d | lT| dT 例如，用左線性正規(guī)文法和右線性 正規(guī)文

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

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

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)文法的實用限制和變換有關(guān)文法的實用限制和變換 若程序設(shè)計語言的文法含有多余規(guī)則， 其中必定有錯誤存在，因此檢查文法中是 否含有多余規(guī)則對我們來說是很重要的。 思考題 P26 2.1 2.2（2） 2.3 L2 ,L3 2.7 2.8 2.9 本章重點介紹了語言的語法結(jié)構(gòu)的形式描 述、語法樹以及文法的二義性, 主要內(nèi)容有： 1. 設(shè)計一個文法定義一個已知的語言 (1) 文法是一個四元組 G=(VN,VT, P,

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

25、bb,aabbb,aabbbb, aaabbb, aabbbb， AaAb | ab BbB | 本章小結(jié)本章小結(jié) 分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計出相 應(yīng)規(guī)則 例2. 給出語言 L1=a2n+1|n0 的文法 P1: AaB | aP1：AaAa | a 或或 L1=a, aaa, aaaaa, aaaaaaa, aaaaaaaaa， Baa | aBa 本章小結(jié)本章小結(jié) 本章小結(jié)本章小結(jié) 分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計出相 應(yīng)規(guī)則 例3. 給出語言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. 寫一個 文法,使其語言是正偶數(shù)的集合,每 個偶數(shù)不以0開頭。 P4: NE | AE N0 | 2 | 4 | 6 | 8 |BN 或或 分析 不以0開頭的偶數(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. 給出語言L=1n0m1m0n | n,m0的 文法。 分析 根據(jù)語言句子的結(jié)構(gòu)特征, 設(shè)計 出相應(yīng)規(guī)則 L=,01,0011,10,1100,1010,100110, 110100,11001100 本章小結(jié)本章小結(jié) P : S a | 0S0 | 1S1 例6. 給出語言L=WaWt | W0|1*,Wt 表示W(wǎng)的逆的文法。 分析 根據(jù)語言句子的結(jié)構(gòu)特征，設(shè)計 出相應(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. 已知一個文法，確定該文法所定義的 語言。 (2) 給定一個文法，可根據(jù)語言和推導定 義推導出文法的句子，從而確定出該文法 所定義的語言。 (1) 文法所定義的語言 L(GS)=x|S x且xVT* * 本章小結(jié)本章小結(jié) 自然語言描述。 例如, L=x|xa,b+且x中a,b個數(shù)相同 式子描述。例如 L=a2nbb | n0。 正規(guī)式描述。 (3) 語言可用 本章小結(jié)本章小結(jié) 例1 文法GA=(A,a,b,AbA | a, A) 所生成的語言是什么？ 分析 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所生成的語言是什么？ (2) 給出句子0127的最左、最右推導。 本章小結(jié)本章小結(jié) L(GN)= | 0,1,2, 9+ = | 為可帶前導0的正整數(shù) = | 為數(shù)字串 最左推導: NNDN7ND7N27ND2 7 N127D1270127 最右推導: 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 該文法 所生成的語言是什么？ A aAb | ab B cBd | cd S AB 本章小結(jié)本章小結(jié) 3. 求句型的短語、直接短語和句柄 (1) 短語、直接短語和句柄是對某句 型而言的。 (2) 短語總是句型的某個子串，它對應(yīng) 子樹未端結(jié)點形成的符號串。 (3) 直接短語是某條規(guī)則右部，它對應(yīng) 簡單子

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