編譯原理-自下而上的語法分析-展示頁
2025-05-25 04:33本頁面
【正文】 。第五章 語法分析 —自下而上分析 內(nèi)容 ? 自下而上分析基本問題 ? 算符優(yōu)先分析 自下而上分析基本問題 ? 自下而上分析基本問題 ?歸約 ?規(guī)范歸約 ?符號(hào)棧的使用 ?語法樹的表示 ? 算符優(yōu)先分析 自下而上分析 ? 自下而上分析 b d b a c e S A B A abbcde aAbcde (A ? b) aAcde (A ? Ab) aAcBe (B ? d) S (S ? aAcBe) ?從 輸入字符 的角度而言 ?從輸入開始 ?逐步進(jìn)行 “ 歸約 ” ?直至歸約到文法的開始符號(hào) ?從 語法樹 的角度而言 ?從語法樹的末端開始 ?步步向上 “ 歸約 ” ?直到根結(jié) 自下而上分析法的基本思想 ? 自下而上分析法 ?是一種“ 移進(jìn) 歸約 ”法 ?基本思想 ?用一個(gè)寄存符號(hào)的 先進(jìn)后出棧 ?把輸入符號(hào)一個(gè)一個(gè)地 移進(jìn) 到棧里 ?當(dāng) 棧頂形成某個(gè)產(chǎn)生式的候選式 時(shí)，把棧頂?shù)倪@一部分替換成 (歸約 為 )該產(chǎn)生式的 左部符號(hào) 先進(jìn)后出棧 ? 例：設(shè)文法 G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 試對(duì) abbcde進(jìn)行 “ 移進(jìn) 歸約 ” 分析。 a bbcde b Ab c ded abbcde e B S 移進(jìn) 歸約分析 ? 例：設(shè)文法 G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 試對(duì) abbcde進(jìn)行 “ 移進(jìn) 歸約 ” 分析。 特別是，如果有 A??,則稱 ?是句型 ???相對(duì)于規(guī)則 A??的 直接短語 一個(gè)句型的最左直接短語稱為該句型的 句柄 規(guī)范歸約例一 ? 例：文法 G[E]： E→E+T|T T→T*F|F F→(E)|–F|id 考慮文法 G[E]上的句子 id1+id2*id3 ? 其 最右推導(dǎo) 和 分析樹 如圖 (a)、 (b)所示 圖 id1+id2*id3的最右推導(dǎo)、分析樹與短語 (a) 最右推導(dǎo)； (b) 分析樹； (c) 短語 ( 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)直接短語 ： i d1( F 1) 、 i d2( F 3) 、 i d3( F 2)句柄 ： i d1( F 1)短語： 歸約的分析樹 ? 分析樹的葉子與短語、直接短語和句柄有下述關(guān)系 ?短語 ?以非終結(jié)符為根的子樹中所有從左到右排列的葉子 ?直接短語 ?只有父子關(guān)系的樹中所有從左到右排列的葉子 ?樹高為 2 ?句柄 ?最左邊父子關(guān)系樹中所有從左到右排列的葉子 ?句柄是唯一的 短語 ? 以非終結(jié)符為根的子樹中所有從左到右排列的葉子 ? 從文法開始符號(hào)經(jīng)過 0步推導(dǎo)得到 E1，從 E1經(jīng)過若干步推導(dǎo)得到id1+id2*id3， 所以 id1+id2*id3是句型 id1+id2*id3相對(duì)于 E1的短語 ? id1+id2不是句型 id1+id2*id3中相對(duì)于任何非終結(jié)符的短語，因?yàn)檎也坏饺魏我粋€(gè)非終結(jié)符，它的子樹中的所有葉子構(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)直接短語 ： i d1( F 1) 、 i d2( F 3) 、 i d3( F 2)句柄 ： i d1( F 1)短語： 直接短語與句柄 ? 只有父子關(guān)系的樹中所有從左到右排列的葉子 ? 從考慮推導(dǎo) E1 ? E2+id2*id3 ? T2+id2*id3 ? F1+id2*id3 ? id1+id2*id3 ? id1是相對(duì)于非終結(jié)符 E T2和 F1的短語 ? 特別地，相對(duì)于 F1的直接短語，也是句柄 ( 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
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1