【導(dǎo)讀】則稱β是直接短語。二個條件表示有文法規(guī)則A?它是直接短語，即某規(guī)則右部。于非終結(jié)符B)句型baSb的短語，構(gòu)造句型i*i+i的語法樹。(句子)都存在一棵對應(yīng)的語法樹。符號串是相對于簡單子樹根的直接短語。也就是，它是否只有唯一的一。對應(yīng)兩棵不同的語法樹。子，它有兩個不同的最左(最右)推導(dǎo)，進(jìn)一些非形式的語法規(guī)定。改寫原有的文法。

　　

【正文】 G[N]為 : N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1) G[N]所生成的語言是什么？ (2) 給出句子 0127的最左 、 最右推導(dǎo) 。 本章小結(jié) L(G[N])={α | α∈ {0,1,2, … 9}+} ={α | α為可帶前導(dǎo) 0的正整數(shù) } ={α | α為數(shù)字串 } 最左推導(dǎo) : N?ND?N7?ND7?N27?ND27 ? N127?D127?0127 最右推導(dǎo) : N?ND?NDD?NDDD?DDDD ?0DDD?01DD?012D?0127 N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 本章小結(jié) 例 3. 已知文法 G[S]=( {A,B},{a,b,c,d}, P, S ) , 其中 P 為 : 分析 ∵ S?AB?aAbB?a2Ab2B?… ?an1Abn1B?anbnB?anbncBd ? anbnc2Bd2 ? … ? anbncm1Bdm1?anbncmdm ∴ L(G[S])={anbncmdm | n ,m≥1 } 該文法 所生成的語言是什么？ A → aAb | ab B → cBd | cd S → AB 本章小結(jié) 3. 求句型的短語、直接短語和句柄 (1) 短語 、 直接短語和句柄是對某句 型而言的 。 (2) 短語總是句型的某個子串，它對應(yīng) 子樹未端結(jié)點(diǎn)形成的符號串。 (3) 直接短語是某條規(guī)則右部，它對應(yīng) 簡單子樹未端結(jié)點(diǎn)形成的符號串。 (4) 最左邊的直接短語是句柄。 本章小結(jié) 例 1 已知文法 G[E]： 證明 E+T*F是它的一個句型 ,指出這個句型的短語 ﹑ 直接短語和句柄 。 ∵ E?E+T?E+T*F 短語 : E+T*F、 T*F ∴ E+T*F是它的一個句型 。 畫出該句型的語法樹 : 句柄 : T*F 直接短語 : T*F E T F T + E * E→E+T | E T | T T→T *F | T/F | T T→(E) | i 本章小結(jié) 例 2 已知文法 G[S]： 試找出符號串 (a)和 (A((SaA)(b)))的短語 ﹑ 直接短語和句柄 (如果有的話 )。 S→(AS) | (b) A→(SaA) | (a) ∴ 符號串 (a))不是 文法的句型，因此 它 沒有 短語 ﹑ 直接短語和句柄。 分析 ∵ S?(AS)?((a)S)?(a)) / 本章小結(jié) ∵ S?(AS)?(A(AS))?(A(A(b))) ?(A((SaA)(b))) ∴ 符號串 (A((SaA)(b)))是文法的句型，畫出該句型的語法樹如下圖： S→(AS) | (b) A→(SaA) | (a) 本章小結(jié) 從句型的語法樹求 短語 : (A((SaA)(b))) ((SaA)(b)) (SaA) (b) 直接短語： (SaA)、 (b) 句柄： (SaA) S ( S a A ) ) b ( S→(AS) | (b) A→(SaA) | (a) 對于句型 (A((SaA)(b))) 本章小結(jié) 4．文法二義性的判斷 一個文法存在某個句子 對應(yīng)兩棵不同 的語法樹或?qū)?yīng) 兩個不同的 最左 （最右） 推導(dǎo) ，則該文法是二義性的。 本章小結(jié) 例 1 設(shè)有文法 G[S]: S→iSeS| iS | i 試證明文法 G[S]有二義性 。 分析 因?yàn)閷ξ姆ǖ木渥? iiiei 有如下 兩 棵不同的語法樹與之對應(yīng) ，所以該文法 是二義的 本章小結(jié) S→iSeS| iS | i 句子 iiiei 對應(yīng)下面兩顆語法樹： S S 本章小結(jié) N→SE | E S→SD | D E→ 0 | 2 | 4 | 6 | 8 | 10 D→0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 1. 試證明文法 G[N]有二義性 。 2. 此文法所描述的語言是什么 ？ 3. 試寫出另一文法 G39。使 L(G39。)=L(G)且 G39。是無二義性的 。 例 2 設(shè)有文法 G[N]: 本章小結(jié) 分析 因?yàn)閷ξ姆ǖ木渥?10有兩棵不同的語法樹與之對應(yīng)，所以該文法是 二義的 N E S 0 D 1 N E 0 1 N→SE | E S→SD | D E→ 0 | 2 | 4 | 6 | 8 | 10 D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 本章小結(jié) 該文法所描述的語言是所有 無符號偶數(shù) 的集合 (可以 0開頭 )。 改寫后的文法 G‘[S]為 : N→SE | E S→SD | D E→0 | 2 | 4 | 6 | 8 D→0 | 1 | 2 | 3 | 4 | 5| 6 | 7 | 8 | 9 N→SE | E S→SD | D E→ 0 | 2 | 4 | 6 | 8 | 10 D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 本節(jié)完