編譯原理 - 自下而上的語(yǔ)法分析-文庫(kù)吧
2025-04-23 04:33 本頁(yè)面
【正文】 ： 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 i3 i2 規(guī)范歸約例二 ? 例：考慮文法 G[E] E?T|E+T T?F|T*F F?(E)|I 和句型 i1*i2+i3 ? 在一個(gè)句型對(duì)應(yīng)的語(yǔ)法樹(shù)中，以某非終結(jié)符為根的兩代以上的子樹(shù)的所有末端結(jié)點(diǎn)從左到右排列就是相對(duì)于該非終結(jié)符的一個(gè) 短語(yǔ) ，如果子樹(shù)只有兩代，則該短語(yǔ)就是 直接短語(yǔ) 。 ? E ? E+T ? E+F ? E+i3 ? T+i3 ? T*F+i3 ? T*i2+i3 ? F*i2+i3 ? i1*i2+i3 ? 短語(yǔ)： i1， i2， 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) 而得到的。 規(guī)范歸約簡(jiǎn)述 ? 把上例倒過(guò)來(lái)寫，則得到： ?S ? aAcBe? aAcde ? aAbcde ? abbcde ? 顯然這是一個(gè) 最右推導(dǎo) 。 ? 規(guī)范歸約是關(guān)于是一個(gè)最右推導(dǎo)的逆過(guò)程 ?最左歸約 規(guī)范推導(dǎo) ? 由規(guī)范推導(dǎo)推出的句型稱為 規(guī)范句型 。 ? 規(guī)范歸約的中心問(wèn)題： 確定句型的句柄 。 規(guī)范歸約簡(jiǎn)述 ? 最右推導(dǎo) ，推導(dǎo)的每一步結(jié)果都是一個(gè)右句型。該推導(dǎo)即分析樹(shù) “ 剪句柄 ”的全過(guò)程。 Sa A eA b c dBbSa A eA b c dBSa A edBSa A eB( a ) ( b) ( c ) ( d)S( e )圖 剪句柄的過(guò)程 (a) 句子； (b) 剪去 b之后； (c) 剪去 Abc之后； (d) 剪去 d之后； (e) 開(kāi)始符號(hào) 符號(hào)棧的使用與語(yǔ)法樹(shù)的表示 ? 從分析樹(shù)上直觀地看，“ 剪句柄 ”的方法十分簡(jiǎn)單。但是若在語(yǔ)法分析器中實(shí)現(xiàn)剪句柄，則有兩個(gè)問(wèn)題必須解決： ?① 確定右句型中將要?dú)w約的子串 (確定句柄 )； ?② 確定如何選擇 正確的產(chǎn)生式進(jìn)行歸約 。 ? 具體實(shí)現(xiàn)采用 移進(jìn) —?dú)w約 方法，用一個(gè) ?！坝涀 睂⒁?dú)w約句柄的前綴，并用一個(gè)分析表 來(lái)確定何時(shí)棧頂已形成句柄，以及形成句柄后選擇哪個(gè)產(chǎn)生式進(jìn)行歸約。 符號(hào)棧的使用與語(yǔ)法樹(shù)的表示 ? 在 移進(jìn) —?dú)w約分析模式 中，符號(hào)棧的使用有以下四種操作形式。 ?① 移進(jìn) (shift): 把當(dāng)前輸入中的下一個(gè)終結(jié)符移進(jìn)棧； ?② 歸約 (reduce): 句柄在棧頂已形成，用適當(dāng)產(chǎn)生式左部代替句柄； ?③ 接受 (accept): 宣告分析成功； ?④ 報(bào)錯(cuò) (error): 發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程。 ? 考察 文法 G[S]： S?aABe A?b A?Abc B?d 的輸入序列 abbcde，移進(jìn) — 歸約方法分析的符號(hào)棧變化過(guò)程如下所示。 步驟 棧內(nèi)容 當(dāng)前輸入 動(dòng)作 (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) a ab aA aAb aAbc aA aAd aAB aABe S abbcde bbcde bcde bcde cde de de e e shift shift reduced by A→b shift shift reduced by A→Abc shift reduced by B→d shift reduced by S→aABe accept 算符優(yōu)先分析 ? 自下而上分析基本問(wèn)題 ? 算符優(yōu)先分析 ?算符優(yōu)先文法及優(yōu)先表構(gòu)造 ?算符優(yōu)先分析算法 ?優(yōu)先函數(shù) ?算符優(yōu)先分析中的出錯(cuò)處理 算符優(yōu)先分析 ? 考慮二義文法文法 G(E)： G(E)： E
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1