编译技术课后答案.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 ; pri