思考题4-12算术运算表达式,其文法为G[E]:E→E/E\E+E|(E)|id,其中除法运算的优先级高于加法,括号运算的优先级最高。该文法的实例(a/b+c)/d可视化图如图4.11所示。非终结符E和终结符id、＋、/有综合属性h和w ,分别表示其图形的高度和宽度﹐另有继承属性x和y ,表示图形左上角坐标。已知:①每个字符的占空高度和宽度分别为h。和w,/的占空高度为0.2h。;②整个表达式图的左上角坐标为(x0,y0)。请设计出绘画算术运算表达式的SDD,即求输入串中id、+、/的每一个实例的4个属性值。 b+c d

为了方便描述，我们先将输入串转换为语法树，如下所示：

    E
   /|\
  / | \
id  /  \
   /    \
  /      \
 /        \
/    E    \
a    / \   d
    /   \
   /     \
  E     E
 /|\   /|\
b  +  c  /
       |
       E
       |
       id

基于这个语法树，我们可以设计出如下的SDD：

1. 对于非终结符E，计算其综合属性h和w，使得h表示该E节点子树中最深的叶子节点到该节点的距离，w表示该E节点的左子树和右子树的宽度之和加上除号的宽度（即0.2h）。

   E.h = max{E1.h, E2.h} + h
   E.w = E1.w + E2.w + 0.2h

2. 对于终结符id，计算其综合属性h和w，使得h表示字符的高度，w表示字符的宽度。

   id.h = h
   id.w = w

3. 对于终结符+，计算其综合属性h和w，使得h表示加号的高度，w表示加号的宽度。

   +.h = h
   +.w = w

4. 对于终结符/，计算其综合属性h和w，使得h表示除号的高度，w表示除号的宽度。

   /.h = 0.2h
   /.w = w

5. 对于每个节点，计算其继承属性x和y，使得x表示该节点的左上角横坐标，y表示该节点的左上角纵坐标。

   E.x = E1.x + E1.w
   E.y = max{E1.y, E2.y} + h
   
   id.x = x
   id.y = y
   
   +.x = E1.x + E1.w
   +.y = E1.y + E1.h - h
   
   /.x = E1.x + E1.w
   /.y = E1.y + E1.h - 0.1h

根据这个SDD，我们可以递归计算出输入串中每个id、+、/的4个属性值。以题目示例(a/b+c)/d为例，计算过程如下：

1. 计算a/b+c的属性值

   E1: id.h = h, id.w = w, id.x = x, id.y = y
   E2: id.h = h, id.w = w, id.x = x + id.w + 0.2h, id.y = y
   E3: +.h = h, +.w = w, +.x = x + E1.w, +.y = E1.y + E1.h - h
   E4: /.h = 0.2h, /.w = w, /.x = x + E1.w, /.y = E1.y + E1.h - 0.1h
   E.h = max{E2.h, E3.h} + h = E2.h + h = h + h = 2h
   E.w = E2.w + E3.w + 0.2h = 2w + 0.2h
   E.x = E1.x + E1.w = x, E.y = max{E2.y, E3.y} + h = E3.y + h = E1.y + E1.h - h + h = E1.y + E1.h

2. 计算(a/b+c)/d的属性值

   E1: E.h = 2h, E.w = 2w + 0.2h, E.x = x, E.y = y
   E2: id.h = h, id.w = w, id.x = E1.x + E1.w + 0.2h, id.y = E1.y
   E3: /.h = 0.2h, /.w = w, /.x = E1.x + E1.w + id.w + 0.4h, /.y = E1.y + E1.h - 0.1h
   E4: id.h = h, id.w = w, id.x = E3.x + E3.w, id.y = E3.y
   E.h = max{E1.h, E4.h} + h = E1.h + h = 2h + h = 3h
   E.w = E1.w + E4.w + 0.2h = 2w + 2id.w + 0.6h
   E.x = E1.x, E.y = max{E1.y, E4.y} + h = E4.y + h = E1.y + E1.h

因此，输入串中每个id、+、/的4个属性值分别为：

a: h=1, w=1, x=x, y=y
b: h=1, w=1, x=x+1.2h, y=y
c: h=1, w=1, x=x+2.2h, y=y
+: h=1, w=1, x=x+1.2h, y=y+h
/: h=0.2h, w=1, x=x+1.2h, y=y+h+1h
d: h=1, w=1, x=x+3.4h, y=y+h