【正文】 ? 構(gòu)造產(chǎn)生式集 ? P’={Ai → ? |產(chǎn)生式 B→ ? ?P， B ?Wi ， ? ?VN}，此時(shí) P’中不含有單產(chǎn)生式。 ?將 S’加入到所得的產(chǎn)生式集中。 68 ε不屬于文法所產(chǎn)生的語言 ?已知文法 G=（ {S,A,B,C}， {a,b,c}， P， S），產(chǎn)生式 P的組成如下： ? S→aA A→BC B→bB ? C→cC B→ ε C→ ε ?執(zhí)行算法 3，得到 W={A,B,C} ?執(zhí)行算法 4，可得到 P’如下： ? 對于 S→aA, 將產(chǎn)生式 S→aA 、 S→a 放入 P’； ? 對于 A→BC , 將產(chǎn)生式 A→BC 、 A→B 、 A→C 放入 P’； ? 對于 B→bB ，將產(chǎn)生式 B→bB 、 B→b 放入 P’； ? 對于 C→cC ，將產(chǎn)生式 C→cC 、 C→c 放入 P’。 ?對于上述 W，如果 G中不含有可能導(dǎo)出 ε的符號，則 W= ? 。 62 示例 ?文法的定義 ? 已知文法 G=（ {S,U,V,W}， {a,b,c}， P， S），產(chǎn)生式 P的組成如下： ? S→aS S→W S→U U→a ? V→bV V→ac W→aW ?執(zhí)行算法 1 ?執(zhí)行算法 2 63 執(zhí)行算法 1 ?第一步，由于產(chǎn)生式 U→a 、 V→ac 的右部均為終結(jié)符號串，故置 VN(1) ={U， V}； ?第二步，對于產(chǎn)生式 S→U ，由于 U ? VN(1) ，故將 S置于中，所以 VN(1) ={S， U， V}； ?于是得到以下文法 G1： ?G1=（ {S,U,V},{a,b,c},P (1),S），其中 P (1)由如下產(chǎn)生式組成： ? S→aS S→U U→a ? V→bV V→ac 64 執(zhí)行算法 2 ?第一步，置 VN’ ={S}； ?第二步，因?yàn)?G1中含有產(chǎn)生式 S→U 、 U→a ，故應(yīng)將 U、 a分別置于，即 VN’ ={S， U} VT’ ={a}。 ?消除算法 ? 算法 1 ? 算法 2 ?示例 60 算法 1 ?分別置 VN(1)和 P(1) 為 ?； ?對于 P中的每一產(chǎn)生式 A → ?， 若 ? ?VT* ，則將 A置于 VN(1) 中； ?對于 P中的每一產(chǎn)生式 A →x 1x2… xm若每個(gè) xi都屬于 VN(1) 或 VT ，則將 A置于 VN(1) ； ?重復(fù)步驟 3，直到 VN(1)不再增大為止； ?對于 P中的每一產(chǎn)生式 B →y 1y2… yn ，若 B及每一個(gè) yi都屬于 VN(1) ∪ VT ，則將此產(chǎn)生 式 B →y 1y2… yn置于 P (1)。即 x必須同時(shí)滿足以下兩個(gè)條件： ? 存在 α 、 β ?V*，有 S?*∈αxβ ? 存在 w?VT*,αxβ?*w ? 否則就說 x是無用的。 ?若 G為上下文無關(guān)文法或正規(guī)文法，類似結(jié)論成立。 ?上下文無關(guān)文法的相關(guān)定理 ? 定理 ? 定理 57 定理 ?若 L是由文法 G=(VN， VT， P， S)產(chǎn)生的語言， P中的每一個(gè)產(chǎn)生式的形式均為 A→ α ，其中A∈ VN， α ∈( VN ∪ VT)*(即 α 可能為 ε )，則 L能由這樣一種文法產(chǎn)生：每一個(gè)產(chǎn)生式或者為 A→ β 形式，其中 A∈ VN， β ∈( VN ∪ VT)+(即 β ≠ ε )，或者 S→ ε 且 S不出現(xiàn)在任何產(chǎn)生式右邊。 56 上下文無關(guān)文法中的 ε規(guī)則 ?上下文無關(guān)文法中某些規(guī)則可具有形式A→ ε，稱這種規(guī)則為 ε規(guī)則。即 A t，其中 t∈ VT 。即有 S αAβ，其中 α， β屬于 (VT∪ VN)* 。一種是文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，所以任何句子的推導(dǎo)中不可能用到它。說它有害，是說它只會引起文法的二義性。 54 實(shí)用說明 ?有關(guān)文法的實(shí)用限制 ?上下文無關(guān)文法中的 ε規(guī)則 ?無用符號和無用產(chǎn)生式的消除 ?ε 產(chǎn)生式的消除 ?單產(chǎn)生式的消除 55 有關(guān)文法的實(shí)用限制 ?在實(shí)用中，我們將限制文法中不得含有有害規(guī)則和多余規(guī)則： ? 有害規(guī)則，是指形為 U→U 的產(chǎn)生式。 ?示例 52 示例：推導(dǎo)樹中找短語 53 句型分析的有關(guān)問題 ?在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ ? 假定要被代換的最左非終結(jié)符號是 B，且有 n條規(guī)則：B→ A1|A2|…|A n，那么如何確定用哪個(gè)右部去替代 B？ ?在自下而上的分析方法中如何識別可歸約的串？ ? 在分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號，該子串稱為“可歸約串”。 ?設(shè) A是句型 αβδ的某一子樹的根，其中 β是形成此子樹的末端結(jié)點(diǎn)的符號串，則其中 β是句型 αβδ的相對于 A的短語。 ? 雖然 i2+i3是句型 i1*i2+i3的一部分，并不是它的短語，因?yàn)楸M管有 E i2+i3，但不存在從文法開始符號 E到 i1*E的推導(dǎo)。 ? E E 且 E ? i1*i2+i3則 i1*i2+i3是句型 i1*i2+i3相對于 E的短語。 ? E i1*i2+T 且 T i3則 i3是句型 i1*i2+i3的相對于 T的短語。又有： ? E i1*F+i3 且 F?i2則 i2是句型 i1*i2+i3的相對于 F的短語，也是相對于規(guī)則F→i 的直接短語，還有： ? E i1*i2+F 且 F?i3則 i3也是句型 i1*i2+i3的相對于 F的短語，也是相對于規(guī)則F→i 的直接短語。為了敘述方便，將句型改寫為 i1*i2+i3。一個(gè)句型的最左直接短語稱為該句型的 句柄 。如果有： ? S αAδ且 A β則稱 β是句型 αβδ相對于非終結(jié)符 A的 短語 。 推導(dǎo)過程： S?cAd ?cabd 48 示例：自下而上分析 例： 考慮文法 G[S]； ① S→cAd ② A→ab ③ A→a 識別輸入串 w=cabd是否該文法的句子。 ?自下而上方法： ? 自下而上方法是從輸入符號串開始，以它做為語法樹的末端結(jié)點(diǎn)符號串，自底向上地構(gòu)造語法樹。 ? 示例： 例 ?自下而上分析法： ? 從輸入符號串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號。 ?從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進(jìn)而依次識別右邊的一個(gè)符號，直到分析結(jié)束。 44 句型的分析 ?句型分析 是識別一個(gè)輸入符號串是否為語法上正確的程序的過程。 43 二義性文法與二義性語言的區(qū)別 ?文法的二義性和語言的二義性是兩個(gè)不同的概念。 ?定義表達(dá)式的無二義文法 G[E]： E→T|E+T T→F|T*F F→(E)|i 它和上述文法產(chǎn)生的語言是相同的。我們所能做的事是為無二義性尋找一組充分條件 (當(dāng)然它們未必都是必要的 )。 ?如果產(chǎn)生上下文無關(guān)語言的每一個(gè)文法