Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

5.3 节的练习

5.3.1

下面是涉及运算符 + 和整数或浮点运算分量的表达式的文法。区分浮点数的方法是看它有无小数点。

E -> E + T | T
T -> num.num | num
  1. 给出一个 SDD 来确定每个项 T 和表达式 E 的类型
  2. 扩展这个得到的 SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符 intToFloat 把一个整数转换为相等的浮点数。

解答

  1. 产生式 语法规则
    1) E -> E_1 + T E.type = E_1.type === float || T.type === float ? float : int
    2) E -> T E.type = T.type
    3) T -> num.num T.type = float
    4) T -> num T.type = int

5.3.2 !

给出一个 SDD，将一个带有 + 和 的中缀表达式翻译成没有冗余括号的表达式。比如因为两个运算符都是左结合的，并且 的优先级高于 +，所以 ((a*(b+c))*(d)) 可翻译为 a*(b+c)*d

解答

几个属性设置：

  • wrapped: 表达式最外层是否有括号。
  • precedence: 令 +，*，() 和单 digit 的优先级分别为 0，1，2，3。 如果表达式最外层有括号，则为去掉括号后最后被计算的运算符的优先级，否则为表达式最后被计算的运算符的优先级。
  • expr: 表达式。
  • cleanExpr: 去除了冗余括号的表达式。
产生式 语法规则
1) L -> En L.cleanExpr = E.wrapped ? E.cleanExpr : E.expr
2) E -> E_1 + T E.wrapped = false
E.precedence = 0
E.expr = E_1.expr || "+" || T.expr
E.cleanExpr = (E_1.wrapped ? E_1.cleanExpr : E_1.expr) || "+" || (T.wrapped ? T.cleanExpr : T.expr)
3) E -> T E.wrapped = T.wrapped
E.precedence = T.precedence
E.expr = T.expr
E.cleanExpr = T.cleanExpr
4) T -> T_1 * F T.wrapped = false
T.precedence = 1
T.expr = T_1.expr || "*" || F.expr
T.cleanExpr = (T_1.wrapped && T_1.precedence >= 1 ? T_1.cleanExpr : T_1) || * || (F.wrapped && F.precedence >= 1 ? F.cleanExpr : F.expr)
5) T -> F T.wrapped = F.wrapped
T.precedence = F.precedence
T.expr = F.expr
T.cleanExpr = F.cleanExpr
6) F -> (E) F.wrapped = true
F.precedence = E.precedence
F.expr = "(" || E.expr || ")"
F.cleanExpr = E.expr
7) F -> digit F.wrapped = false
F.precedence = 3
F.expr = digit
F.cleanExpr = digit

5.3.3 !

给出一个 SDD 对 x*(3*x+x*x) 这样的表达式求微分。表达式中涉及运算符 + 和 、变量 x 和常量。假设不进行任何简化，也就是说，比如 3\x 将被翻译为 3*1+0*x。