编译原理2习题答案.pdf

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