2 2 設文法設文法 G S G S S L a S a L L S S 1 消除左遞歸和回溯 2 計算每個非終結符的 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 構造正規式相應的構造正規式相應的 NFA 1 0 1 101 NFA 1 0 1 101 解解 1 0 1 101 1 0 1 101 對對 應應 的的 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 對應的兩棵語法樹為 1 1 構造正規式構造正規式 1 1 1 1 0 0 1 10101 所描述語言所描述語言的的 DFADFA 的狀態轉換圖的狀態轉換圖 解 先構造 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 計算這個文法的每個非終結符的 FIRST 集和 FOLLOW 集 2 證明這個方法是 LL 1 的 3 構造它的預測分析表 解 1 計算這個文法的每個非終結符的 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 證明這個方法是 LL 1 的 各產生式的 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 可見 相同左部產生式的 SELECT 集的交集均為 空 所以文法 G E 是 LL 1 文法 3 構造它的預測分析表 文法 G E 的預測分析表如下 1 1 考慮以下的文法 考慮以下的文法 E L a L L E E 1 為這個文法構造 LR 0 項目集規范族 s 2 判斷這個文法是否是 LR 0 文法 若不是 請描述出 LR 0 沖突 如果是 則構造 LR 0 分析表 3 判斷這個文法是否是 SLR 1 文法 若是 構造 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 非終結符 Follow 集合 E E L 是 SLR 1 文法 a I0 E E E L E a I2 E L L L E