【正文】 第五章 語法分析 —自下而上分析 內(nèi)容 ? 自下而上分析基本問題 ? 算符優(yōu)先分析 自下而上分析基本問題 ? 自下而上分析基本問題 ?歸約 ?規(guī)范歸約 ?符號棧的使用 ?語法樹的表示 ? 算符優(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)行 “ 歸約 ” ?直至歸約到文法的開始符號 ?從 語法樹 的角度而言 ?從語法樹的末端開始 ?步步向上 “ 歸約 ” ?直到根結(jié) 自下而上分析法的基本思想 ? 自下而上分析法 ?是一種“ 移進(jìn) 歸約 ”法 ?基本思想 ?用一個寄存符號的 先進(jìn)后出棧 ?把輸入符號一個一個地 移進(jìn) 到棧里 ?當(dāng) 棧頂形成某個產(chǎn)生式的候選式 時，把棧頂?shù)倪@一部分替換成 (歸約 為 )該產(chǎn)生式的 左部符號 先進(jìn)后出棧 ? 例：設(shè)文法 G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 試對 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 試對 abbcde進(jìn)行 “ 移進(jìn) 歸約 ” 分析。 步驟 : 1 2 3 4 5 6 7 8 9 10動作 : 進(jìn) a 進(jìn) b 歸 (2 ) 進(jìn) b 歸 (3 ) 進(jìn) c 進(jìn) d 歸 (4 ) 進(jìn) e 歸 (1 )ed B Bb c c c cb A A A A A A Aa a a a a a a a a S 歸約的語法樹分析法 ? 分析樹和語法樹 ?不一定一致 ? 自下而上分析過程 ?邊輸入單詞符號，邊歸約 ? 核心問題 ?識別可歸約串 b d b a c e S A B A 規(guī)范歸約簡述 ? 定義：令 G是一個文法， S是文法的開始符號，假定 ???是文法 G的一個句型 ，如果有 且 ??AS *? ???A則 ?稱是句型 ???相對于非終結(jié)符 A的 短語 。 特別是，如果有 A??,則稱 ?是句型 ???相對于規(guī)則 A??的 直接短語 一個句型的最左直接短語稱為該句型的 句柄 規(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é)符為根的子樹中所有從左到右排列的葉子 ? 從文法開始符號經(jīng)過 0步推導(dǎo)得到 E1，從 E1經(jīng)過若干步推導(dǎo)得到id1+id2*id3， 所以 id1+id2*id3是句型 id1+id2*id3相對于 E1的短語 ? id1+id2不是句型 id1+id2*id3中相對于任何非終結(jié)符的短語，因?yàn)檎也坏饺魏我粋€非終結(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)句柄