5.5 下面的文法产生对整型数和实型数应用 “+” 算符形成的表达式。两个整型数相加,结果仍为整型;否则为实型数,

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

(1) 给出一个确定每个子表达式类型的语法制导定义。

解:可以定义属性 kind,取值 real int

Production			Semantic Rule
E1 -> E2 + T 		E1.kind = (E2.kind == int && T.kind == int) ? int : real
E -> T				E.kind = T.kind
T -> num.num 		T.kind = real
E -> num     		E.kind = int

5.8 考虑如下产生 Pascal 声明语句的文法。

D -> L : T
T -> integer | real
L -> L, id | id

(1) 给出确定变量类型的语法制导定义。

解:

设 T.type,表示类型名

设 L.in,表示标识符 L 的类型信息

addtype (id.entry, type) 表示将 L.in 与符号表 id.entry 关联

Production			Semantic Rule
D -> L : T			L.in = T.type
T -> integer		T.type = integer
T -> real			T.type = real
L1 -> L2, id 		L2.in = L.in
L -> id				addtype(id.entry, L.in)

image-20211121232055269

5.10

解:

(1)

B.ht 依赖于子节点,是综合属性。

B.ps 依赖于左侧,满足 L-SDD 要求。因此是 L-SDD。

(2)

(2) 该语法制导定义的翻译方案如下:

$$ \begin{aligned} &\mathrm{S} \rightarrow\{\text { B.ps }=10\} \mathrm{B}\{\text { S.ht=B.ht }\} \\ &\mathrm{B} \rightarrow\left\{\mathrm{B}_{1} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps}\right\} \mathrm{B}_{1}\left\{\mathrm{~B}_{2} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps}\right\} \mathrm{B}_{2}\left\{\mathrm{~B} \cdot \mathrm{ht}=\max \left(\mathrm{B}_{1} \cdot \mathrm{ht}, \mathrm{B}_{2} \cdot \mathrm{ht}\right)\right\} \\ &\mathrm{B} \rightarrow\left\{\mathrm{B}_{1} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps}\right\} \mathrm{B}_{1} \text { sub }\left\{\mathrm{B}_{2} \cdot \mathrm{ps}=\operatorname{shrink}(\mathrm{B} \cdot \mathrm{ps})\right\} \mathrm{B}_{2}\left\{\mathrm{~B} \cdot \mathrm{ht}=\operatorname{disp}\left(\mathrm{B}_{1} \cdot \mathrm{ht}, \mathrm{B}_{2} \cdot \mathrm{ht}\right)\right\} \\ &\mathrm{B} \rightarrow \text { text }\{\text { B.ht=text.h } \times \mathrm{B} \cdot \mathrm{ps}\} \end{aligned} $$

(3)

$$ \begin{array}{|l|l|} \hline \text {产牛式} & \text {语义规则} \\ \hline \mathrm{S} \rightarrow \mathrm{LB} & \text { B.ps=L.s } \\ \hline \mathrm{L} \rightarrow \varepsilon & \text { S.ht=B.ht } \\ \hline & \text { L.s=10 } \\ \hline \mathrm{B} \rightarrow \mathrm{B}_{1} \mathrm{MB}_{2} & \mathrm{~B}_{1} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps} \\ & \mathrm{M} \cdot \mathrm{i}=\mathrm{B} \cdot \mathrm{ps} \\ & \mathrm{B}_{2} \cdot \mathrm{ps}=\mathrm{M} \cdot \mathrm{s} \\ & \mathrm{B} \cdot \mathrm{ht}=\max \left(\mathrm{B}_{1} \cdot \mathrm{ht}, \mathrm{B}_{2} \cdot \mathrm{ht}\right) \\ \hline & \mathrm{B}_{1} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps} \\ \mathrm{B} \rightarrow \mathrm{B}_{1} \mathrm{subNB}_{2} & \mathrm{~N} \cdot \mathrm{i}=\mathrm{B} \cdot \mathrm{ps} \\ & \mathrm{B}_{2} \cdot \mathrm{ps}=\mathrm{N} \cdot \mathrm{s} \\ & \mathrm{B} \cdot \mathrm{ht}=\mathrm{disp}\left(\mathrm{B}_{1} \cdot \mathrm{ht}, \mathrm{B}_{2} \cdot \mathrm{ht}\right) \\ \hline \mathrm{B} \rightarrow \mathrm{text} & \mathrm{B} \cdot \mathrm{ht}=\mathrm{text} \cdot \mathrm{h} \times \mathrm{B} \cdot \mathrm{ps} \\ \hline \mathrm{M} \rightarrow \varepsilon & \mathrm{M} \cdot \mathrm{s}-\mathrm{M} \cdot \mathrm{i} \\ \hline \mathrm{N} \rightarrow \varepsilon & \mathrm{N} \cdot \mathrm{s}=\mathrm{shrink}(\mathrm{N} \cdot \mathrm{i}) \\ \hline \end{array} $$

翻译方案:

$$ \begin{aligned} &\mathrm{S} \rightarrow \mathrm{L}\{\mathrm{B} \cdot \mathrm{ps}=\mathrm{L} \cdot \mathrm{s}\} \mathrm{B}\{\mathrm{S} \cdot \mathrm{ht}=\mathrm{B} \cdot \mathrm{ht}\} \\ &\mathrm{B} \rightarrow\left\{\mathrm{B}_{1} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps}\right\} \mathrm{B}_{1} \mathrm{M}\left\{\mathrm{B}_{2} \cdot \mathrm{ps}=\mathrm{M} \cdot \mathrm{s}\right\} \mathrm{B}_{2}\left\{\mathrm{~B} \cdot \mathrm{ht}=\max \left(\mathrm{B}_{1} \cdot \mathrm{ht}, \mathrm{B}_{2} \cdot \mathrm{ht}\right)\right\} \\ &\left.\mathrm{B} \rightarrow\left\{\mathrm{B}_{1} \cdot \mathrm{ps}=\mathrm{B} \cdot \mathrm{ps}\right\} \mathrm{B}_{1} \text { sub } \mathrm{N}\left\{\mathrm{B}_{2} \cdot \mathrm{ps}=\mathrm{N} \cdot \mathrm{s}\right)\right\} \mathrm{B}_{2}\left\{\mathrm{~B} \cdot \mathrm{ht}=\operatorname{disp}\left(\mathrm{B}_{1} \cdot \mathrm{ht}, \mathrm{B}_{2} \cdot \mathrm{ht}\right)\right\} \\ &\mathrm{B} \rightarrow \text { text }\{\mathrm{B} \cdot \mathrm{ht}=\mathrm{text} \cdot \mathrm{h} \times \mathrm{B} \cdot \mathrm{ps}\} \\ &\mathrm{L} \rightarrow \varepsilon\{\mathrm{L} \cdot \mathrm{s}=10\} \\ &\mathrm{M} \rightarrow \varepsilon\{\mathrm{M} \cdot \mathrm{s}=\mathrm{M} \cdot \mathrm{i}\} \\ &\mathrm{N} \rightarrow \varepsilon\{\mathrm{N} \cdot \mathrm{s}=\operatorname{shrink}(\mathrm{N} \cdot \mathrm{i})\} \end{aligned} $$

(4)

$$ \begin{array}{|l|l|} \hline \text {产生式} & \text {语义规则} \\ \hline \mathrm{S} \rightarrow \mathrm{LB} & \text { val[ntop]=val[top] } \\ \hline \mathrm{L} \rightarrow \varepsilon & \text { val[ntop]=10 } \\ \hline \mathrm{B} \rightarrow \mathrm{B}_{1} \mathrm{MB}_{2} & \text { val[ntop]=max(val[top-2],val[top]) } \\ \hline \mathrm{B} \rightarrow \mathrm{B}_{1} \mathrm{subNB}_{2} & \text { val[ntop]=disp(val[top-3],val[top]) } \\ \hline \mathrm{B} \rightarrow \mathrm{text} & \text { val[ntop]=val[top]×val[top-1] } \\ \hline \mathrm{M} \rightarrow \varepsilon & \text { val[ntop]=val[top-1] } \\ \hline \mathrm{N} \rightarrow \varepsilon & \text { val[ntop]=shrink(val[top-2]) } \\ \hline \end{array} $$