編譯原理-自下而上的語(yǔ)法分析(存儲(chǔ)版)
【正文】 ， i3， i1*i2， i1*i2+i3 ? 直接短語(yǔ)： i1， i2， i3 ? 句柄： i1 規(guī)范歸約簡(jiǎn)述 ? 可 用句柄來(lái)對(duì)句子進(jìn)行歸約 ? 例： 設(shè)文法 G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 句型 歸約規(guī)則 abbcde (2) A ? b aAbcde (3) A ? Ab aAcde (4) B ? d aAcBe (1) S ? aAcBe S b d b a c e S A B A 規(guī)范歸約簡(jiǎn)述 ? 定義：假定 ?是文法 G的一個(gè)句子，我們稱序列 ?n， ?n1， ? ， ?0 是一個(gè) 規(guī)范歸約 ，如果此序列滿足： ? 1 ?n= ? ? 2 ?0為文法的開(kāi)始符號(hào)，即 ?0=S ? 3 對(duì)任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號(hào) 而得到的。 特別是，如果有 A??,則稱 ?是句型 ???相對(duì)于規(guī)則 A??的 直接短語(yǔ) 一個(gè)句型的最左直接短語(yǔ)稱為該句型的 句柄 規(guī)范歸約例一 ? 例：文法 G[E]： E→E+T|T T→T*F|F F→(E)|–F|id 考慮文法 G[E]上的句子 id1+id2*id3 ? 其 最右推導(dǎo) 和 分析樹(shù) 如圖 (a)、 (b)所示 圖 id1+id2*id3的最右推導(dǎo)、分析樹(shù)與短語(yǔ) (a) 最右推導(dǎo)； (b) 分析樹(shù)； (c) 短語(yǔ) ( a ) ( b) ( c )E 1 ( 1)= E 2 + T 1 ( 2)= E 2 + T 3 * F 2 ( 3)= E 2 + T 3 * i d3 ( 4)= E 2 + F 3 * i d3 ( 5)= E 2 + i d2 * i d3 ( 6)= T 2 + i d2 * i d3 ( 7)= F 1 + i d2 * i d3 ( 8)= i d1 + i d2 * i d3 ( 9)E1E2 ＋ T1T2F1i d1T3 * F2F3i d2i d3 i d1+ i d2*i d3( E 1) i d2*i d3( T 1) i d1( E 2 , T 2, F 1) i d2( T 3 , F 3) i d3( F 2)直接短語(yǔ) ： i d1( F 1) 、 i d2( F 3) 、 i d3( F 2)句柄 ： i d1( F 1)短語(yǔ)： 歸約的分析樹(shù) ? 分析樹(shù)的葉子與短語(yǔ)、直接短語(yǔ)和句柄有下述關(guān)系 ?短語(yǔ) ?以非終結(jié)符為根的子樹(shù)中所有從左到右排列的葉子 ?直接短語(yǔ) ?只有父子關(guān)系的樹(shù)中所有從左到右排列的葉子 ?樹(shù)高為 2 ?句柄 ?最左邊父子關(guān)系樹(shù)中所有從左到右排列的葉子 ?句柄是唯一的 短語(yǔ) ? 以非終結(jié)符為根的子樹(shù)中所有從左到右排列的葉子 ? 從文法開(kāi)始符號(hào)經(jīng)過(guò) 0步推導(dǎo)得到 E1，從 E1經(jīng)過(guò)若干步推導(dǎo)得到id1+id2*id3， 所以 id1+id2*id3是句型 id1+id2*id3相對(duì)于 E1的短語(yǔ) ? id1+id2不是句型 id1+id2*id3中相對(duì)于任何非終結(jié)符的短語(yǔ)，因?yàn)檎也坏饺魏我粋€(gè)非終結(jié)符，它的子樹(shù)中的所有葉子構(gòu)成 id1+id2 ( a ) ( b) ( c )E 1 ( 1)= E 2 + T 1 ( 2)= E 2 + T 3 * F 2 ( 3)= E 2 + T 3 * i d3 ( 4)= E 2 + F 3 * i d3 ( 5)= E 2 + i d2 * i d3 ( 6)= T 2 + i d2 * i d3 ( 7)= F 1 + i d2 * i d3 ( 8)= i d1 + i d2 * i d3 ( 9)E1E2 ＋ T1T2F1i d1T3 * F2F3i d2i d3 i d1+ i d2*i d3( E 1) i d2*i d3( T 1) i d1( E 2 , T 2, F 1) i d2( T 3 , F 3) i d3( F 2)直接短語(yǔ) ： i d1( F 1) 、 i d2( F 3) 、 i d3( F 2)句柄 ： i d1( F 1)短語(yǔ)： 直接短語(yǔ)與句柄 ? 只有父子關(guān)系的樹(shù)中所有從左到右排列的葉子 ? 從考慮推導(dǎo) E1 ? E2+id2*id3 ? T2+id2*id3 ? F1+id2*id3 ? id1+id2*id3 ? id1是相對(duì)于非終結(jié)符 E T2和 F1的短語(yǔ) ? 特別地，相對(duì)于 F1的直接短語(yǔ)，也是句柄 ( a ) ( b) ( c )E 1 ( 1)= E 2 + T 1 ( 2)= E 2 + T 3 * F 2 ( 3)= E 2 + T 3 * i d3 ( 4)= E 2 + F 3 * i d3 ( 5)= E 2 + i d2 * i d3 ( 6)= T 2 + i d2 * i d3 ( 7)= F 1 + i d2 * i d3 ( 8)= i d1 + i d2 * i d3 ( 9)E1E2 ＋ T1T2F1i d1T3 * F2F3i d2i d3 i d1+ i d2*i d3( E 1) i d2*i d3( T 1) i d1( E 2 , T 2, F 1) i d2( T 3 , F 3) i d3( F 2)直接短語(yǔ) ： i d1( F 1) 、 i d2( F 3) 、 i d3( F 2)句柄 ： i d1( F 1)短語(yǔ)：E F F T T T i1 + * E F i
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1