5.3 节的练习

5.3.1

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

E -> E + T | T
T -> num.num | num

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

解答

<table>
    <thead>
        <tr>
            <th></th>
            <th>产生式</th>
            <th>语法规则</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>1)</td>
            <td>E -> E_1 + T</td>
            <td>E.type = E_1.type === float || T.type === float ? float : int</td>
        </tr>
        <tr>
            <td>2)</td>
            <td>E -> T</td>
            <td>E.type = T.type</td>
        </tr>
        <tr>
            <td>3)</td>
            <td>T -> num.num</td>
            <td>T.type = float</td>
        </tr>
        <tr>
            <td>4)</td>
            <td>T -> num</td>
            <td>T.type = int</td>
        </tr>
    </tbody>
</table>

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。