課件編譯原理編譯原理課件屬性文法語(yǔ)法制導(dǎo)2005課件說(shuō)明第四章(文件)
【正文】 A→ab |aA b |ε S→aS b 9 推導(dǎo)的定義 直接推導(dǎo) “ ?” α → β 是文法 G的產(chǎn)生式，若有 v,w滿足：v=γ α δ ,w= γ β δ , 其中 γ ∈V *,δ ∈V * 則稱(chēng) v直接 推導(dǎo) 到 w,記作 v ? w 也稱(chēng) 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í)符 。BEGIN READ( A) END. (標(biāo)識(shí)符 ?A) 11 推導(dǎo)的定義 若存在 v =w0 ?w1 ?... ?wn=w,(n0) 則記為 v =+ w，稱(chēng)作 v推導(dǎo)出 w，或 w歸約到 v 若有 v =+ w 或 v=w， 則記為 v =* w 12 例： G： S→ 0S1， S→ 01 0S1 ?00S11 00S11 ?000S111 000S111 ?00001111 S ?0S1 ?00S11 ?000S111 ?00001111 S =+ 00001111 S =* S 00S11 =* 00S11 13 句型、句子的定義 ?句型 有文法 G，若 S =* x，則稱(chēng) x是文法 G的句型。 語(yǔ)言之間的關(guān)系依次：有不是上下文有關(guān)語(yǔ)言的 0型語(yǔ)言，有不是上下文無(wú)關(guān)語(yǔ)言的1型語(yǔ)言，有不是正則語(yǔ)言的上下文無(wú)關(guān)語(yǔ)言。其識(shí)別系統(tǒng)是不確定的下推自動(dòng)機(jī)。 A=S VT =∑ 由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型 39 語(yǔ)法樹(shù) 設(shè) G=( VN,VT,P,S)為一 cfg，若一棵樹(shù)滿足下列 4個(gè)條件，則此樹(shù)稱(chēng)作 G的語(yǔ)法樹(shù) (推導(dǎo)樹(shù) )(派生樹(shù)）： 1. 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是 V的一個(gè)符號(hào) 2. 根的標(biāo)記是 S 3. 若一結(jié)點(diǎn) n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記 A，則肯定 A∈V N 4. 如果結(jié)點(diǎn) n有標(biāo)記 A,其直接子孫結(jié)點(diǎn)從左到右的次序是 n1， n2， … ， nk，其標(biāo)記分別為 A1， A2， … ，Ak，那么 A→A 1A2， … ， Ak一定是 P中的一個(gè)產(chǎn)生式 語(yǔ)法樹(shù)的結(jié)果： 從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之 40 上下文無(wú)關(guān)文法的語(yǔ)法樹(shù) ?句型 aabbaa的可能 推導(dǎo) 序列和語(yǔ)法樹(shù) 例 : G[S]: S→ aAS A→ SbA A→ SS S→ a A→ ba S a A S S b A a a b a S?aAS?aAa?aSbAa?aSbbaa?aabbaa S?aAS?aSbAS?aabAS?aabbaS?aabbaa S?aAS?aSbAS?aSbAa?aabAa?aabbaa 41 語(yǔ)法樹(shù) 句型推導(dǎo) 的 直觀表示 給定文法 G=(VN,VT,P,S)，對(duì)于 G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù) (推導(dǎo)樹(shù) ) 定理： G為上下文無(wú)關(guān)文法， 對(duì)于 α ≠ ε ，有 S =* α ，當(dāng)且僅當(dāng) 文法 G有以 α 為結(jié)果的一棵語(yǔ)法樹(shù) (推導(dǎo)樹(shù) ) 42 一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的 (但未必是所有的 )不同推導(dǎo)過(guò)程，包括最左(最右 )推導(dǎo)。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。 從左到右的分析算法 ，即 總是從 左 到 右 地 識(shí)別輸入符號(hào)串 ，首先識(shí)別符號(hào)串中的 最左符號(hào)，進(jìn)而 依次識(shí)別右邊 的一個(gè)符號(hào)， 直到分析結(jié)束 。 自上而下方法 是從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串 自下而上方法 則是從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果，自底向上的構(gòu)造語(yǔ)法樹(shù) 49 自上而下的語(yǔ)法分析 例：文法 G： S → cAd A → ab A → a 識(shí)別輸入串 w=cabd是否為該文法的 句子 S S S c A d c A d a b 推導(dǎo)過(guò)程： S ? cAd cAd ? cabd 50 自下而上的語(yǔ)法分析 例：文法 G： S → cAd A → ab A → a 識(shí)別輸入串 w=cabd是否該文法的 句子 S A A c a b d c a b d c a b d 規(guī)約 過(guò)程構(gòu)造的推導(dǎo)： cAd ? cabd S ? cAd 51
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1