1. 假设某语言的表达式遵循如下的结合性和优先级规则： 优先级 最高 +，- *，/ 最低 **(乘方) 结合性 从右到左 +，-，*，/ 从左到右 ** (1)请写出下列表达式的运算顺序，以标注序号的括号表示，如表达式x + y – z * s 的运算顺序为：( (x + (y–z)1)2 * s)3 (i) a * b – c / d + a ** b ** c ** d (ii) a ** b + c ** d / a ** b + c ** d (iii) a * b + c ** d ** e (iv) (a * b) + c ** (d ** e) (2)请写出计算这些表达式的无二义文法，并写出表达式1+2*3**3**2-1的语法树。

(1)

(i) a * b - c / d + a ** b ** c ** d

1. b ** c
2. a ** (b ** c)
3. d ** e
4. c ** (d ** e)
5. b ** c ** d ** e
6. a ** (b ** c ** d ** e)
7. a * b
8. c / d
9. a * b - c / d
10. a * b - c / d + a ** (b ** c ** d ** e)

运算顺序为：(((((a * b) - (c / d)) + (a ** (b ** c ** d ** e))) - 1) + ((2 ** 3) ** 3) ** 1)

(ii) a ** b + c ** d / a ** b + c ** d

1. a ** b
2. c ** d
3. c ** d / (a ** b)
4. a ** b
5. c ** d / (a ** b) + c ** d
6. a ** b + c ** d / (a ** b) + c ** d

运算顺序为：(((a ** b) + ((c ** d) / (a ** b))) + c ** d)

(iii) a * b + c ** d ** e

1. d ** e
2. c ** (d ** e)
3. a * b
4. a * b + c ** (d ** e)

运算顺序为：(a * b) + (c ** (d ** e))

(iv) (a * b) + c ** (d ** e)

运算顺序为：(a * b) + (c ** (d ** e))

(2)

无二义文法如下：

expression -> term | expression + term | expression - term
term -> factor | term * factor | term / factor
factor -> atom | factor ** atom
atom -> number | variable | '(' expression ')'

其中，number表示数字，variable表示变量名。

以表达式1+2*3**3**2-1为例，语法树如下：

         -
       /   \
      +     1
     / \
    1   *
       / \
      2   **
         / \
        3   **
           / \
          3   2