編譯原理第03章-文法和語言-資料下載頁

　　

【正文】 =(VN， VT， P， S)是一文法，我們說 G中的一個符號 x?(VN∪VT)是有用的指 x至少出現在一個句子的推導過程中。即 x必須同時滿足以下兩個條件： ? 存在 α 、 β ?V*，有 S?*∈αxβ ? 存在 w?VT*,αxβ?*w ? 否則就說 x是無用的。如果一個產生式的左部或右部含有無用符號，則此產生式稱之為無用產生式。 ?消除算法 ? 算法 1 ? 算法 2 ?示例 60 算法 1 ?分別置 VN(1)和 P(1) 為 ?； ?對于 P中的每一產生式 A → ?， 若 ? ?VT* ，則將 A置于 VN(1) 中； ?對于 P中的每一產生式 A →x 1x2… xm若每個 xi都屬于 VN(1) 或 VT ，則將 A置于 VN(1) ； ?重復步驟 3，直到 VN(1)不再增大為止； ?對于 P中的每一產生式 B →y 1y2… yn ，若 B及每一個 yi都屬于 VN(1) ∪ VT ，則將此產生 式 B →y 1y2… yn置于 P (1)。 61 算法 2 ?分別置 VN’ 、 VT’和 P’ 為 ?； ?將文法的開始符號 S置入 VN’中； ?對于 G (1)中任何形如 A →x 1|x2 | … | xm的產生式，若 A ? VN’ ，則將符號串 x1， x2 ， … ， xm中的全部非終結符號置于 VN’中，而將其中的全部終結符號置于 VT’中； ?重復步驟 3，直到 VN’和 VT’都不再增大為止； ?將 P中左右部僅含 VN’ ∪ VT’中符號的所有產生式置 P’ 。 62 示例 ?文法的定義 ? 已知文法 G=（ {S,U,V,W}， {a,b,c}， P， S），產生式 P的組成如下： ? S→aS S→W S→U U→a ? V→bV V→ac W→aW ?執行算法 1 ?執行算法 2 63 執行算法 1 ?第一步，由于產生式 U→a 、 V→ac 的右部均為終結符號串，故置 VN(1) ={U， V}； ?第二步，對于產生式 S→U ，由于 U ? VN(1) ，故將 S置于中，所以 VN(1) ={S， U， V}； ?于是得到以下文法 G1： ?G1=（ {S,U,V},{a,b,c},P (1),S），其中 P (1)由如下產生式組成： ? S→aS S→U U→a ? V→bV V→ac 64 執行算法 2 ?第一步，置 VN’ ={S}； ?第二步，因為 G1中含有產生式 S→U 、 U→a ，故應將 U、 a分別置于，即 VN’ ={S， U} VT’ ={a}。 ?因此得到等價的且不含無用符號和無用產生式的文法為 G2=（ {S， U}， {a}， P’， S），其中， P’由如下產生式組成： ? S→aS S→U U→a 65 ε產生式的消除 ?算法 3 ?算法 4（ ε不屬于文法所產生的語言） ?算法 5 （ ε屬于文法所產生的語言） ?示例： ? ε不屬于文法所產生的語言 ? ε屬于文法所產生的語言 66 算法 3 ?作集合 W1={A|產生式 A → ε?P}； ?作集合序列 WK+1=WKU{B| B→ ? ?P,且 ? ?WK+}； K ? 1 并使 WK+1 收斂； ?令 W= WK+1 ,則對于每一個 A?W，有 A?*ε。 ?對于上述 W，如果 G中不含有可能導出 ε的符號，則 W= ? 。 67 算法 4 ?利用算法 3，可將分 VN為兩個不相交的子集： W和 VN W； ?設 A →X 1X2 … Xm是 P中的任一產生式，則按以下規則將所有形如 A →Y 1Y2 … Ym的產生式置入 P’中： ? （ 1）若 Xi ? VN –W，則取 Yi = Xi ； ? （ 2）若 Xi ? W，則 Yi分別取 Xi 和 ε，若所有的均 Xi屬于 W，則不將所有 Yi的取 ε。 68 ε不屬于文法所產生的語言 ?已知文法 G=（ {S,A,B,C}， {a,b,c}， P， S），產生式 P的組成如下： ? S→aA A→BC B→bB ? C→cC B→ ε C→ ε ?執行算法 3，得到 W={A,B,C} ?執行算法 4，可得到 P’如下： ? 對于 S→aA, 將產生式 S→aA 、 S→a 放入 P’； ? 對于 A→BC , 將產生式 A→BC 、 A→B 、 A→C 放入 P’； ? 對于 B→bB ，將產生式 B→bB 、 B→b 放入 P’； ? 對于 C→cC ，將產生式 C→cC 、 C→c 放入 P’。 ?則消除 ε產生式之后的文法的產生式如下： ? S→aA S→a A→BC A→B A→C ? B→bB B→b C→cC C→c 69 算法 5 ?引入新的符號 S’（ S’?VNUVT）作為 G的開始符號，令 = VNU{S’}； ?作產生式集 ?P’=PU{S’→ ? |產生式 S→ ? ?P} ?對文法 G’=（ VN’， VT， P’ ， S’）執行算法 4消去 P’中全部 ε產生式。 ?將 S’加入到所得的產生式集中。 70 ε屬于文法所產生的語言 ?已知文法 G=（ {S,A,B}， {a,b,c}， P， S），產生式P的組成如下： ? S→cS S→AB A→aAb B→Bb A→ ε B→ ε ?引入新的符號 S’； ?作產生式集 P’= PU{S’→cS, S’→AB} ?利用算法 4消去 P’中的 ε產生式，并加入 S’→ ε，得到全部的產生式如下： ? S’→cS S’→c S’→AB S’→A S’→B S’ → ε ? S→cS S→c S→AB S→A S→B A→aAb ? A→ab B→Bb B→b 71 單產生式的消除 ?算法： ? 設 A={A1 , A2, … , An}，對于每一個 Ai，作集合序列 ? W1(Ai)={Ai} ? WK+1 (Ai) = WK(Ai)U{D|C→ D, C ? WK(Ai), D ? VN}，并使其收斂為 Wi。 ? 構造產生式集 ? P’={Ai → ? |產生式 B→ ? ?P， B ?Wi ， ? ?VN}，此時 P’中不含有單產生式。 ?示例 72 示例： 單產生式的消除 ?已知文法 G=（ {S,A,B}， {a,b}， P， S），產生式 P的組成如下： ? S→A S→B S→AB A→aAb B→Bb A→ ab B→ b ?對于 G，執行算法得到： ? W(S)={S,A,B} ? W(A)={A} ? W(B)={B} ?由此可構造產生式集 P’如下： ? S→AB S→aAb S→ ab S→Bb S→ b ? A→aAb A→ ab ? B→Bb B→ b