思考题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
时间: 2024-03-11 08:49:19 浏览: 91
为了方便描述,我们先将输入串转换为语法树,如下所示:
```
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
```
阅读全文