課件，編譯原理，編譯原理課件，屬性文法，語(yǔ)法制導(dǎo)，2005課件說(shuō)明，第四章(完整版)
【正文】 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 38 規(guī)范推導(dǎo) 規(guī)范句型 最左（最右）推導(dǎo)：在推導(dǎo)的任何一步α ?β ，其中 α 、 β 是句型，都是對(duì) α 中的最左（右）非終結(jié)符進(jìn)行替換 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。 K= VN ∪{ N}, N為一個(gè)新?tīng)顟B(tài) ,它不在 VN中 如文法 G1[A]： A→DB 與 G2[S]： S→0S1 等價(jià) A→DE S→01 E→AB D→0 B→1 18 文法的類型 通過(guò)對(duì)產(chǎn)生式施加不同的限制， Chomsky將文法分為四種類型： 0型文法：對(duì)任一產(chǎn)生式 α → β ，都有α ∈(V N∪V T)+， β ∈(V N∪V T)* 1型文法： 對(duì)任一產(chǎn)生式 α → β ，都有 |β |≥| α |， 僅僅 S→ ε 除外 2型文法： 對(duì)任一產(chǎn)生式 α → β ，都有 α ∈V N 3型文法： 任一產(chǎn)生式 α → β 的形式都為 A→aB 或A→a ，其中 A∈V N ， B∈V N ， a∈V T * 19 文法的類型 例： 1型（上下文有關(guān)）文法 文法 G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→a BD→bD D→b Aa→bD 20 文法的類型 例： 2型（上下文無(wú)關(guān)）文法 文法 G[S]： S→AB A→BS|0 B→SA|1 21 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 22 文法的類型 2型文法 1型文法 0型文法 四類 文法 之間 的 逐級(jí) “ 包含 ” 關(guān)系 3型文法 23 文法和語(yǔ)言 0型文法產(chǎn)生的語(yǔ)言稱為 0型語(yǔ)言 1型文法或上下文有關(guān)文法（ CSG ） 產(chǎn)生的語(yǔ)言稱為 1型語(yǔ)言 或上下文有關(guān) 語(yǔ)言（ CSL） 2型文法或上下文無(wú)關(guān)文法（ CFG ） 產(chǎn)生的語(yǔ)言稱為 2型語(yǔ)言 或上下文無(wú)關(guān) 語(yǔ)言（ CF L ） 3型文法或正則（正規(guī)）文法（ RG ） 產(chǎn)生的語(yǔ)言稱為 3型語(yǔ)言 正則（正規(guī)） 語(yǔ)言（ RL ） 24 文法和語(yǔ)言 四種文法之間的關(guān)系 是將產(chǎn)生式做進(jìn)一步限制而定義的。 ? 稱為規(guī)則的左部， ? 稱作規(guī)則的右部。1 第四章 文法和語(yǔ)言 為語(yǔ)言的語(yǔ)法描述尋求工具 工具要對(duì)程序設(shè)計(jì)語(yǔ)言給出精確無(wú)二義的語(yǔ)法描述。 6 文法的定義 例 文法 G=（ VN， VT， P， S） VN = { S }, VT ={ 0, 1 } P={ S→ 0S1, S→ 01 } S為開(kāi)始符號(hào) 例 文法 G=（ VN， VT， P， S） VN ={標(biāo)識(shí)符，字母，數(shù)字 } VT ={a,b,c,…x,y,z,0,1,…,9} P={標(biāo)識(shí)符 → 字母 標(biāo)識(shí)符 → 標(biāo)識(shí)符 字母 標(biāo)識(shí)符 → 標(biāo)識(shí)符 數(shù)字 字母 → a … 字母 →z 數(shù)字 →0 … 數(shù)字 →9 } S=標(biāo)識(shí)符 8 文法的寫(xiě)法 元 符號(hào) : → ∷= | 習(xí)慣 大寫(xiě)字母表示非終結(jié)符 小寫(xiě)字母表示終結(jié)符 (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 9 推導(dǎo)的定義 直接推導(dǎo) “ ?” α → β 是文法 G的產(chǎn)生式，若有 v,w滿足：v=γ α δ ,w= γ β δ , 其中 γ ∈V *,δ ∈V * 則稱 v直接 推導(dǎo) 到 w,記作 v ? w 也稱 w直接 歸約 到 v 例： G： S→ 0S1， S→ 01 0S1 ?00S11 00S11 ?000S111 000S111 ?00001111 S ?0S1 10 推導(dǎo) 程序 ?分程序 . (程序 ? 分程序 . ) 分程序 . ? 變量說(shuō)明部分 語(yǔ)句 . (分程序 ? 變量說(shuō)明部分 語(yǔ)句 ) VAR標(biāo)識(shí)符 。 語(yǔ)言之間的關(guān)系依次：有不是上下文有關(guān)語(yǔ)言的 0型語(yǔ)言，有不是上下文無(wú)關(guān)語(yǔ)言的1型語(yǔ)言，有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)言。 A=S 由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型 39
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1