【文章內(nèi)容簡介】 are of the form X– v where v is an arbitrary string of symbols in V, and X is a single nonterminal. Wherever you find X, you can replace with v (regardless of context). Type 3: regular grammars Productions are of the form X– a or X– aY where X and Y are nonterminals and a is a terminal. That is the lefthand side must be a single nonterminal and the righthand side can be either a single terminal by itself or with a single nonterminal. These grammars are the most limited in terms of expressive power. 44 文法的類型 例： 1型（上下文有關）文法 文法 G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ ε BD→bD D→ ε Aa→bD 45 文法的類型 例： 2型（上下文無關）文法 文法 G[S]： S→AB A→BS|0 B→SA|1 46 3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 G[I]： I → lT I → l T → lT T → dT T → l T → d 47 文法的類型 2型文法 1型文法 0型文法 四種 文法 之間 的 逐級 “ 包含 ” 關系 3型文法 48 文法和語言 0型文法產(chǎn)生的語言稱為 0型語言 1型文法或上下文有關文法（ CSG ） 產(chǎn)生的語言稱為 1型語言 或上下文有關 語言（ CSL） 2型文法或上下文無關文法（ CFG ） 產(chǎn)生的語言稱為 2型語言 或上下文無關 語言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ） 產(chǎn)生的語言稱為 3型語言 正則（正規(guī)） 語言（ RL ） 49 文法和語言 四種文法之間的關系 是將產(chǎn)生式做進一步限制而定義的。 語言之間的關系依次：有不是上下文有關語言的 0型語言，有不是上下文無關語言的1型語言，有不是正則語言的上下文無關語言。 50 根據(jù)形式語言理論 ,文法和識別系統(tǒng)間有這樣的關系 0型文法（短語結(jié)構(gòu)文法）的能力相當于圖靈機，可以表征任何遞歸可枚舉集，而且任何 0型語言都是遞歸可枚舉的 1型文法（上下文有關文法）：產(chǎn)生式的形式為 α 1Aα 2→ α 1βα2，即只有 A出現(xiàn)在 α 1和 α 2的上下文中時，才允許 β 取代 A。其識別系統(tǒng)是線性界限自動機。 51 帶 a0 a1 a2 a3 a4 a5 a6 a7 a8 … an1 an 有限控制器 磁頭 任何能用圖靈機描述的計算都能機械實現(xiàn)，任何能在現(xiàn)代計算機上實現(xiàn)的計算都能用圖靈機描述 52 2型文法（上下文無關文法 CFG）：產(chǎn)生式的形式為 A→ β ， β 取代 A時與 A的上下文無關。其識別系統(tǒng)是不確定的下推自動機。 3型文法（正規(guī)文法 RG）：產(chǎn)生的語言是有窮自動機（ FA）所接受的集合 53 3型文法產(chǎn)生的語言是有窮自動機（ FA）所接受的集合 . 定理 設 G=（ VN， VT， P， S）是 3型文法，則存在一個有窮自 動機 M=(K, ∑ , f, A, Z) ，使得 L(M)=L(G) 有窮自動機 NFA M ∑= VT K= VN ∪{ N}, N為一個新狀態(tài) ,它不在 VN中 A=S Z={N} 對 G中的形如 D→tB 的產(chǎn)生式 ,t為終結(jié)符或 ε ,有 f(D,t)=B； 對 G中形如 D→t 的產(chǎn)生式， t為終結(jié)符或 ε ,有 f(D,t)=N。 對 VT中的每一個 a ,有 f(N,a)=φ 54 G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b B A S a a a b b b a,b D Z a b a b ? 55 定理 已知一有窮自動機 M= (K, ∑ , f, A, Z) ,存在有一個 3型文法 G = （ VN， VT， P， S） ,使得 L(G)=L(M) G 的定義： VT =∑ VN= K S = A 若 f(D,t)=B ，則 D→tB 在 P中 若 f(D,t)=B ，且 B在 Z中，則 D→t 在 P中 56 G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b D B A S a a a b b a,b b ? 57 正規(guī)文法和正規(guī)式 對 ?上的正規(guī)式 r ,存在一個 RG=(VN,VT,P,S)：L(G)=L(r) 初始， VT= ?,S ? VN ， 生成正規(guī)產(chǎn)生式 S?r () 對形如 A?r1r2的 正規(guī)產(chǎn)生式： A?r1B B?r2 B?VN (R 2)對形如 A?r?r1的 正規(guī)產(chǎn)生式： A?rB A?r1 B?rB B?r1 B?VN (R 3)對形如 A?r1?r2的 正規(guī)產(chǎn)生式 : A?r1 A? r2 不斷應用 R做變換，直到每個產(chǎn)生式右端至多有一個 VN 58 例 r=a(a?d)? S?a(a?d)? S?aA A?(a?d)? A?(a?d)B A?? B?(a?d)B B?? G[s]: S?aA A?? VT={a,d} A?aB VN={S,A,B} A?dB B?aB B?dB B?? 59 正規(guī)文法和正規(guī)式 對 G=(VN,VT,P,S),存在一個 ? =VT上的正規(guī)式 r : L(r)=L(G) A?xB , B?y ≈ A=xy A?xA?y ≈ A=x?y A?x?y ≈ A=x?y 60 正規(guī)文法和正規(guī)式 G[s]:S?aA|a A?aA?a?dA?d A?(a?d)A?(a?d) A?(a?d)?(a?d) S=a(a?d)?(a?d)?a =a((a?d)?(a?d)??) =a((a?d)???) R=a(a?d)? 61 上下文無關文法及其語法樹 上下文無關文法有足夠的能力描述程序設計語言的語法結(jié)構(gòu) 語法樹 句型推導 的 直觀表示 62 ?例文法 G=(｛ E｝ ,｛ +,*,i,(,)｝ ,P,E)其中 P為： {E→i , E→E+E , E→E*E , E→(E) } E表示算術表達式 , i表示程序的 “ 變量 ” ，該文法定義了由變量， +， *,(和 )組成的算術表達式的語法結(jié)構(gòu)，即： 變量是算術表達式；若 E1和 E2是算術表達式，則 E1+ E2， E1*E2和 (E1)也是算術表達式 ?描述一種簡單賦值語句的產(chǎn)生式： 〈 賦值語句 〉 →i ∶ =E ?描述條件語句的產(chǎn)生式： 〈 條件語句 〉 →if 〈 條件 〉 then〈 語句 〉 ｜ if〈 條件 〉 then〈 語句 〉 else〈 語句 〉 63 句型、推導 G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E?E+T ?E+T*F ?E+T*a ?E+F*a ?E+a*a ?T+a*a ?F+a*a ?a+a*a E?E+T ?T+T ?T+T*F ?F+T*F ?F+F*F ?a+F*F ?a+F*a ?a+a*a 64 規(guī)范推導 規(guī)范句型 最左（最右）推導：在推導的任何一步α ?β ，其中 α 、 β 是句型，都是對 α 中的最左（右）非終結(jié)符進行替換 最右推導被稱為規(guī)范推導。 由規(guī)范推導所得的句型稱為規(guī)范句型 65 語法樹 設 G=( VN,VT,P,S)為一 cfg，若一棵樹滿足下列 4個條件，則此樹稱作 G的語法樹 (推導樹 )(派生樹）： 1. 每個結(jié)點都有一個標記，此標記是 V的一個符號 2. 根的標記是 S 3. 若一結(jié)點 n至少有一個它自己除外的子孫，并且有標記 A，則肯定 A∈V N 4. 如果結(jié)點 n有標記 A,其直接子孫結(jié)點從左到右的次序是 n1， n2， … ， nk，其標記分別為 A1， A2， … ，Ak，那么 A→A 1A2， … ， Ak一定是 P中的一個產(chǎn)生式 語法樹的結(jié)果： 從左到右讀出葉子的標記而構(gòu)成的行謂之 66 語法樹 句型推導 的 直觀表示 給定文法 G=(VN,VT,P,S)，對于 G的任何句型都能構(gòu)造與之關聯(lián)的語法樹 (推導樹 ) 定理： G為上下文無關文法， 對于 α ≠ ε ，有 S =* α ，當且僅當 文法 G有以 α 為結(jié)果的一棵語法樹 (推導樹 ) 67 構(gòu)造語法樹 G[E]： E→E+T|T T→T*F|F F→(E)|a E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a E E E + T E + T T E