編譯原理習(xí)題與答案-資料下載頁
2025-08-15 20:44本頁面
【正文】 S B4 r1r1r13 r2r2r22 s2s30 s3s211 a cc g狀態(tài)A C T I O N G O T Oa b T4 r13 r22 a cc1 s1s30 s12s3狀態(tài)A C T I O N G O T Oi k P?我們知道 ， LR(0)、 SLR(1)和 LR(1)分析表構(gòu)造的主要差別是構(gòu)造算法 。 其區(qū)別如下： (1) 對(duì) LR(0)分析表來說，若項(xiàng)目 A→α 屬于 Ik(狀態(tài) )，則對(duì) 任何終結(jié)符 a(包括 $)，置ACTION[k,a]為“用產(chǎn)生式 A→α 進(jìn)行歸約(A→α 為第 j個(gè)產(chǎn)生式 )”，簡(jiǎn)記為“ rj”。表現(xiàn)在 ACTION子表中，則是每個(gè)歸約狀態(tài)所在的行全部填滿“ rj”；并且， 同一行的“ rj”其下標(biāo) j相同，而不同行的“ rj”其下標(biāo) j是不一樣的。 (2) 對(duì) SLR(1)分析表來說 ， 若項(xiàng)目 A→ α 屬于 Ik，則對(duì)任何輸入符號(hào) a， 僅當(dāng) a∈ FOLLOW(A)時(shí)置ACTION[k,a]為 “ 用產(chǎn)生式 A→ α 進(jìn)行歸約 (A→ α為第 j個(gè)產(chǎn)生式 )”， 簡(jiǎn)記為 “ rj”。 表現(xiàn)在 ACTION子表中 ， 則存在某個(gè)歸約狀態(tài)所在的行并不全部填滿 rj， 并且不同行的 “ rj”其下標(biāo) j不同 。 第四章 (3) 對(duì) LR(1)來說 ， 若項(xiàng)目 [A→ α ,a]屬于 Ik(狀態(tài) )，則置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α 進(jìn)行歸約 ” ，簡(jiǎn)記為 “ rj”。 LR(1)是在 SLR(1)狀態(tài) (項(xiàng)目集 )的基礎(chǔ)上 ， 通過狀態(tài)分裂的辦法 (即分裂成更多的項(xiàng)目集 )， 使得 LR分析器的每個(gè)狀態(tài)能夠確切地指出當(dāng) α后跟哪些終結(jié)符時(shí)才容許把 α 歸約為 A。 例如 ， 假定[A→ α ,a]屬于 Ik(狀態(tài) )， 則置 ACTION[k,a]欄目為rj(A→ α 為第 j個(gè)產(chǎn)生式 )；而 [A→ α ,b]屬于 Im(狀態(tài) )， 則同樣置 ACTION[m,b]欄目為 rj。 表現(xiàn)在ACTION子表中 ， 則在不同的行 (即不同的狀態(tài) )里有相同的 rj存在 。 ?因此 ， 圖 312(a)的分析表為 LR(1)分析表(在不同行有相同的 r2存在 )；圖 312(b)為L(zhǎng)R(0)分析表 (有 rj的行是每行都填滿了 rj且同一行 rj的 j相同 ， 不同行 rj的 j不同 )；而圖 312(c)為 LR(0)分析表 (存在并不全部填滿 rj的行 ， 且不同行 rj的 j不同 )。 第四章 第五章 表達(dá)式 (┐ A∨ B)∧ (C∨ D)的逆波蘭表示為 。 有一語法制導(dǎo)翻譯如下所示： S→ bAb {print″ 1″ } A→ (B {print″ 2″ } A→ a {print″ 3″ } B→ Aa) {print″ 4″ } 若輸入序列為 b(((aa)a)a)b， 且采用自下而上的分析方法 ， 則輸出序列為 。 34242421 A┐B∨ CD∨∧ 給出文法 G[S]: S→ SaA|A A→ AbB|B B→ cSd|e ?請(qǐng)證實(shí) AacAbcBaAdbed是文法 G[S]的一個(gè)句型； ?請(qǐng)寫出該句型的所有短語 、 素短語以及句柄； ?為文法 G[S]的每個(gè)產(chǎn)生式寫出相應(yīng)的翻譯子程序 ， 使句型 AacAbcBaAdbed經(jīng)該翻譯方案 歸約后 ， 輸出為 131042521430。 第五章 第五章 (1) 根據(jù)文法 G[S]畫出AacAbcBaAdbed對(duì)應(yīng)的語法樹如圖所示 。 由 圖 可 知AacAbcBaAdbed是文法G[S]的一個(gè)句型 。 AaSSBAdScABbABbA edScAaSAB圖 AacAbcBaAdbed對(duì)應(yīng)的語法樹 第五章 (2) 由 圖 可 知 ， 句型AacAbcBaAdbed中的短語為： B, BaA, cBaAd, AbcBaAd, e, AbcBaAdbe, cAbcBaAdbed, A, AacAbcBaAdbed AaSSBAdScABbABbA edScAaSAB第五章 從圖可看出 ， 句型AacAbcBaAdbed的 素短語為： BaA和 e。 句柄 (最左直接短語 )為： A。 AaSSBAdScABbABbA edScAaSAB(3) 采用修剪語法樹的辦法 ， 按句柄方式自下而上歸約 ， 每當(dāng)一個(gè)產(chǎn)生式得到匹配時(shí) ， 則按歸約的先后順序與所給的輸出 131042521430順序進(jìn)行對(duì)應(yīng) 。 如：第一個(gè)句柄為 A， 它所對(duì)應(yīng)的產(chǎn)生式為 S→ A，所以它的語義動(dòng)作應(yīng)為 print(″ 1″ )；修剪后第二次找到的句柄為 B,它所對(duì)應(yīng)的產(chǎn)生式為 A→ B，此時(shí)它對(duì)應(yīng)輸出序列中的 “ 3”， 即它的語義動(dòng)作為 print(″ 3″ )， 依此類推 ， 得到每個(gè)產(chǎn)生式相應(yīng)的語義動(dòng)作如下： 第五章 第五章 S→ SaA {print(″0″)} S→ A {print(″1″)} A→ AbB {print(″2″)} A→ B {print(″3″)} B→ cSd {print(″4″)} B→ e {print(″5″)} AaSSBAdScABbABbA edScAaSAB句型 AacAbcBaAdbed經(jīng)該翻譯方案歸約后，輸出為 131042521430
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1