编译技术课后答案.pdf

编译原理 习题参考答案 四 编译原理 习题参考答案 四 第四章第四章 4 1 根据表根据表 4 1 的语法制导定义 为输入表达式的语法制导定义 为输入表达式 5 4 3 2 构造 注释分析树 构造 注释分析树 Solution L E val 70 n T val 70 T val 5 F val 14 F val 5 E val 14 digit lexval 5 E val 12 T val 2 T val 12 F val 2 T val 4 F val 3 digit lexval 2 F val 4 digit lexval 3 digit lexval 4 4 3 为文法为文法 S L a L L S S a 写一个语法制导定义 它输出括号的对数 写一个语法制导定义 它输出括号的对数 b 写一个语法制导定义 它输出括号的最大深度 写一个语法制导定义 它输出括号的最大深度 Solution a S S n print S val S L S val L val 1 S a S val 0 L L1 S L val L1 val S val L S L val S val b S S n print S val S L S val L val 1 S a S val 0 L L1 S L val max L1 val S val L S L val S val 4 5 给出对表达式求导数的语法制导定义 表达式由给出对表达式求导数的语法制导定义 表达式由 和和 作用于 变量 作用于 变量 x 和常数组成 如和常数组成 如 x 3 x x x 并假定没有任何化简 例 如将 并假定没有任何化简 例 如将 3 x 翻译成翻译成 3 1 0 x Solution exp 为原表达式的字符串 s 为求导后的字符串 为串联接符 E E n print E s E E1 T E exp E1 exp T exp E s E1 s T s E T E exp T exp E s T s T T1 F T exp T1 exp F exp T s T1 s F exp T exp F s T F T exp F exp T s F s F E F exp E exp F s E s F num F exp num lexme F s 0 F x F exp x F s 1 4 6 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法 制导定义 例如 因为 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法 制导定义 例如 因为 和和 是左结合 是左结合 a b c d 可以 重写成 可以 重写成 a b c d Solution S E print E code E E1 T if T op plus then E code E1 code T code else E code E1 code T code E op plus E T E code T code E op T op T T1 F if F op plus or F op times then if T1 op plus then T code T1 code F code else T code T1 code F code else if T1 op plus then T code T1 code F code else T code T1 code F code T op times T F T code F code T op F op F id F code id lexme F op id F E F code E code F op E op 4 7 用用 S 的综合属性的综合属性 val 给出下面文法中给出下面文法中 S 产生的二进制数的值 例如 输入 产生的二进制数的值 例如 输入 101 101 时 时 S val 5 625 S L L L L L B B B 0 1 a 用综合属性决定用综合属性决定 S val b 用语法制导定义决定用语法制导定义决定 S val 在该定义中 在该定义中 B 的唯一综合属性是的唯一综合属性是 c 它给出由 它给出由 B 产生的位对最终值的贡献 例如 产生的位对最终值的贡献 例如 101 101 的最前一位和 最后一位对值 的最前一位和 最后一位对值 5 625 的贡献分别是的贡献分别是 4 和和 0 125 Solution a S L1 L2 S val L1 val L2 val power 2 L2 length S L S val L val L L1 B L val L1 val 2 B val L length L1 length 1 L B L val B val L length 1 B 0 B val 0 B 1 B val 1 power a b 为 a 的 b 次方 b 先将文法改写为 S L R L L B L B R R B B B 0 1 然后有 其中 i 是 B 的继承属性 val 和 c 是综合属性 S L R S val L val R val S L S val L val L B L1 B i L1 c 2 L c L1 c 2 L val L1 val B c L B B i 1 L c 1 L val B c R R1 B B i R1 c 2 R c R1 c 2 R val R1 val B c R B B i 0 5 R c 0 5 R val B c B 0 B c 0 B 1 B c 1 4 10 文法如下 文法如下 S L a L L S S a 写一个翻译方案 它输出每个写一个翻译方案 它输出每个 a 的嵌套深度 例如 对于句子的嵌套深度 例如 对于句子 a a a a 输出的结果是 输出的结果是 2 2 2 b 写一个翻译方案 它打印出每个写一个翻译方案 它打印出每个 a 在句子中是第几个字符 例如 当句子是 在句子中是第几个字符 例如 当句子是 a a a a a 时 打印的结果是时 打印的结果是 2 5 8 10 14 Solution a S S depth 0 S S L depth S depth 1 L S a print S depth L L1 depth L depth L1 S depth L depth S L S depth L depth S b S S in 0 S S L in S in 1 L S out L out 1 S a S out S in 1 print S out L L1 in