【正文】 語言稱為文法。1 第四章 文法和語言 本章目的 為語言的語法描述尋求工具 工具要對程序設計語言給出精確無二義的語法描述。這里僅僅涉及漢語句子的結構描述。 幽默 、 雙關語和謎語就是利用這兩方面意義間的差異 。 符號串：由字母表 ?中的符號組成的任何有窮序列稱為該字母表上的符號串。 Σ +稱為 Σ 的正閉包 。 語言 L和 M的并為 L?M， 是一個語言 : {w|w is in L or is in M} 如： L1 ={a,b,… y,z} M1 ={1,2… 8,9 } L1?M1={a,b,… y,z， 1,2… 8,9 } 語言 L和 M的連接 是一個語言，記 為 LM LM={st |s∈ L且 t∈ M} 如： L1M1 ={a1,b1,… y1,z1,a2,b2… a9… z9} 有 L ?ε ?= ?ε ?L=L。 24 Define a grammar A grammar G is defined as a 4tuple (VN， VT， P， S ) VN is a set of nonterminals VT is a set of terminals P is a set of productions， each production consists of a left side,an arrow(or ‘::=‘),and a right side S is a designation of one of the nonterminals as the start symbol V =VN ∪ VT is the alphabet of G 25 文法的定義 例 文法 G=（ VN， VT， P， S） VN = { S }, VT ={ 0, 1 } P={ S→ 0S1, S→ 01 } S為開始符號 例 文法 G=（ VN， VT， P， S） VN ={標識符，字母，數(shù)字 } VT ={a,b,c,…x,y,z,0,1,…,9} P={標識符 → 字母 標識符 → 標識符 字母 標識符 → 標識符 數(shù)字 字母 → a,…, 字母 →z 數(shù)字 →0, … , 數(shù)字 →9 } S=標識符 27 文法的寫法 1 G： S→aA b A→ab A→aA b A→ ε 2 G[S]： A→ab A→aA b A→ ε S→aS b 3 G[S]： A→ab |aA b |ε S→aS b 元 符號 : → ∷= | 習慣表示 大寫字母：終結符 小寫字母：非終結符 S – AB A – Ax | y B – z 29 推導的定義 直接推導 “ ?” α → β 是文法 G的產生式，若有 v,w滿足：v=γ α δ ,w= γβδ, 其中 γ ∈V *,δ ∈V * 則稱 v直接 推導 到 w,記作 v ? w 也稱 w直接 歸約 到 v 例： G： S→ 0S1， S→ 01 0S1 ?00S11 00S11 ?000S111 000S111 ?00001111 S ?0S1 30 程序 ?分程序 . 分程序 . ? 變量說明部分 語句 . VAR標識符 。 如文法 G1[A]： A→0R 與 G2[S]： S→0S1 等價 A→01 S→01 R→A1 41 文法的類型 通過對產生式施加不同的限制， Chomsky將文法分為四種類型： 0型文法：對任一產生式 α → β ，都有α ∈(V N∪V T)+， β ∈(V N∪V T)* 1型文法： 對任一產生式 α → β ，都有 |β |≥| α |， 僅僅 S→ ε 除外 2型文法： 對任一產生式 α → β ，都有 α ∈V N ， β ∈(V N∪V T)* 3型文法： 任一產生式 α → β 的形式都為 A→aB 或A→a ，其中 A∈V N ， B∈V N ， a∈V T 42 A hierarchy of grammars Type 0: free or unrestricted grammars These are the most general. Productions are of the form u – v where both u and v are arbitrary strings of symbols in V, with u nonnull. There are no restrictions on what appears on the left or righthand side other than the lefthand side must be nonempty. Type 1: contextsensitive grammars Productions are of the form uXw – uvw where u , v and w are arbitrary strings of symbols in V, with v nonnull, and X a single nonterminal. In other words, X may be replaced by v but only when it is surrounded by u and w . (. in a particular context). 43 Type 2: contextfree grammars Productions 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型文法產生的語言稱為 0型語言 1型文法或上下文有關文法（ CSG ） 產生的語言稱為 1型語言 或上下文有關 語言（ CSL） 2型文法或上下文無關文法（ CFG ） 產生的語言稱為 2型語言 或上下文無關 語言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ） 產生的語言稱為 3型語言 正則（正規(guī)） 語言（ RL ） 49 文法和語言 四種文法之間的關系 是將產生式做進一步限制而定義的。 K= VN ∪{ N}, N為一個新狀態(tài) ,它不在 VN中 若 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ī)產生式 S?r () 對形如 A?r1r2的 正規(guī)產生式： A?r1B B?r2 B?VN (R 2)對形如 A?r?r1的 正規(guī)產生式： A?rB A?r1 B?rB B?r1 B?VN (R 3)對形如 A?r1?r2的 正規(guī)產生式 : A?r1 A? r2 不斷應用 R做變換，直到每個產生式右端至多有一個 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