編譯原理2習(xí)題答案.pdf

2 2 設(shè)文法設(shè)文法 G S G S S L a S a L L S S 1 消除左遞歸和回溯 2 計(jì)算每個(gè)非終結(jié)符的 FIRST 和 FOLLOW 答 S L aS S S L SL L SL 2 FIRST 和 FOLLOW FIRST S a FIRST S a FIRST L a FIRST L 4 4 構(gòu)造正規(guī)式相應(yīng)的構(gòu)造正規(guī)式相應(yīng)的 NFA 1 0 1 101 NFA 1 0 1 101 解解 1 0 1 101 1 0 1 101 對對 應(yīng)應(yīng) 的的 NFA 為 4 4 已知文法已知文法 G S G S 為為 S aSb Sb b S aSb Sb b 試證明文法 試證明文法 G S G S 為二義文法 為二義文法 證明 由文法 G S S aSb Sb b 對句子 aabbbb 對應(yīng)的兩棵語法樹為 1 1 構(gòu)造正規(guī)式構(gòu)造正規(guī)式 1 1 1 1 0 0 1 10101 所描述語言所描述語言的的 DFADFA 的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖 解 先構(gòu)造 NFA 確定化 重新命名 令 AB 為 B AC 為 C ABY 為 D 得 所以 可得 DFA 為 2 2 對下面的文法對下面的文法 G G E TE E E T FT T T F PF F F P E a b 1 計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集 2 證明這個(gè)方法是 LL 1 的 3 構(gòu)造它的預(yù)測分析表 解 1 計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集 FIRST 集合有 FIRST E FIRST T FIRST F FIRST P a b FIRST E FIRST T FIRST T a b FIRST F FIRST P a b FOLLOW 集合有 FOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E 不包含 FOLLOW T FOLLOW T FIRST E FOLLOW E FOLLOW F FIRST T FOLLOW T a b 不包含 FOLLOW F FOLLOW F FIRST T FOLLOW T a b FOLLOW P FIRST F FOLLOW F a b 不包含 2 證明這個(gè)方法是 LL 1 的 各產(chǎn)生式的 SELECT 集合有 SELECT E TE FIRST T a b SELECT E E SELECT E FOLLOW E SELECT T FT FIRST F a b SELECT T T FIRST T a b SELECT T FOLLOW T SELECT F PF FIRST P a b SELECT F F SELECT F FOLLOW F a b SELECT P E SELECT P a a SELECT P b b SELECT P 可見 相同左部產(chǎn)生式的 SELECT 集的交集均為 空 所以文法 G E 是 LL 1 文法 3 構(gòu)造它的預(yù)測分析表 文法 G E 的預(yù)測分析表如下 1 1 考慮以下的文法 考慮以下的文法 E L a L L E E 1 為這個(gè)文法構(gòu)造 LR 0 項(xiàng)目集規(guī)范族 s 2 判斷這個(gè)文法是否是 LR 0 文法 若不是 請描述出 LR 0 沖突 如果是 則構(gòu)造 LR 0 分析表 3 判斷這個(gè)文法是否是 SLR 1 文法 若是 構(gòu)造 SLR 1 分析表 答 拓廣文法 0 E E 1 E L 2 E a 3 L L E 4 L E 是 LR 0 文法 LR 0 分析表為 ACTIONACTION GOTOGOTO a a E E L 0 0 S S3 3 S2 1 1 1 1 accacc 2 2 S3 S2 5 4 3 3 r2r2 r2r2 r2r2 r2r2 r2r2 4 4 S6 S7 5 5 r r4 4 r r4 4 r r4 4 r r4 4 r r4 4 6 6 r r1 1 r r1 1 r r1 1 r r1 1 r r1 1 7 7 S S3 3 S2 8 8 8 r r3 3 r r3 3 r r3 3 r r3 3 r r3 3 非終結(jié)符 Follow 集合 E E L 是 SLR 1 文法 a I0 E E E L E a I2 E L L L E