如何表示语义信息？—— 使用语义属性

为 CFG 中的文法符号设置语义属性，用来表示语法成分对应的语义信息。如：

id.value = 3

表示文法符号 id 的 value 属性值为 3.

语法规则：其实就是产生式

语法制导定义（SDD）

SDD

  • 将每个文法符号和一个语义属性集合相关联
  • 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值

例子：

产生式 语义规则
$D \to TL$ L.inh = T.type
$T \to \text{int}$ T.type = int
$T \to \text{real}$ T.type = real
$L \to L_1, \text{id}$ L1.ih = L.inh

语法制导翻译方案（SDT）

SDT 是在产生式右部嵌入了程序片段的 CFG, 这些程序片段称为语义动作。按照惯例，语义动作放在花括号内。

其实就是在推导的过程中顺带执行一些代码，从而一边推导一边完成计算

综合属性：说白了就是非终结符 A 的属性值依赖于子节点或它自己。即不存在与分析树依赖顺序相冲突的依赖项。

继承属性：若非终结符 A 的属性值依赖于兄弟节点、父节点和自己，则这个属性时继承属性。

例子：E.val = E1.val + T.val，若，依赖关系 E 依赖 E1, T。若 E1, T 任何一个是父节点或者兄弟节点，则这个属性是继承属性。如果 E1, T 均为子节点，则这个属性一定是综合属性。

SDD 的求值顺序

求值顺序取决于依赖关系，必须得到一个无环依赖图，对其排序后有序求值。

例子：

对于 SDD

$$ \begin{array}{|l|l|l|} \hline & {\text { 产生式}} & {\text { 语义规则}} \\ \hline(1) & D \rightarrow T L & \text { L.in }=T \text {.type } \\ (2) & T \rightarrow \text { int } & \text { T.type }=\text { int } \\ (3) & T \rightarrow \text { real } & \text { T.type }=\text { real } \\ (4) & L \rightarrow L_{1}, \text { id } & L_{1} . \text { in }=\text { L.in } \\ & & \text { addtype(id.lexeme, } \text { L.in }) \\ (5) & L \rightarrow \text { id } & \text { addtype(id.lexeme, } \text { L.in }) \\ \hline \end{array} $$

其依赖关系如下图蓝色部分所示：

image-20211105224557024

由于我们需要线性顺序的求值，因此对其进行拓扑排序

拓扑排序：对有向无环图进行排序，假设方向 $A \to B$ 表示 A 依赖 B，则经过拓扑排序，够得到一条执行路径，经过这条执行路径，每个遇到的节点所依赖的节点都被途径过。 必须是有向无环图，否则会有相互依赖，造成死锁无法排序

拓扑排序例子

S-SDD：只存在综合属性的 SDD。

对于 S-SDD，依赖路径就是解析树的路径，因此可以按照 Parse Tree 的任何自底向上顺序来计算它的各个属性值。

L-SDD：即依赖图的边只能从左到右，不能从右到左。（产生式 $A \to X_1 X_2 \cdots X_n$ 的右部符号 $X_i$ 的属性，不能依赖于右边的 $X_j (j>i)$ 的符号的属性）这是为了禁止循环依赖。

例如产生式 $A \to QR$ 的语义规则 $Q.i = q (R.s)$： $Q$ 依赖于其右边的 $R$，因此是非法的，不是 L-SDD.

语法制导翻译方案（SDT）

SDT 是 SDD 的实例。

S-SDD 到 SDT 的方法：将每个语义动作放到产生式的末尾即可。

如果 - - 个 L -SDD 的基本文法可以使用 LL 分析技术， 那么它的 SDT 可以在 LL 或 LR 语法分析过程中实现

【例子】根据下面的 SDD，为表达式 $(4 \star 7+1) \star 2$ 建立注释分析树

image-20211114211428792

解：

image-20211114213046801

image-20211114213115888

解：

image-20211114213638205

（2）拓扑排序后得到：

C.v = 2
B.u = S.u		// S.u
B.v = B.u		// S.u
A.u = B.v + C.v	// S.u + 2
A.v = 3 * A.u	// 3(S.u + 2)
S.v = A.v

（3）3(S.u + 2)

（4）

B.u = S.u
B.v = B.u		// S.u
C.u = B.v		// S.u
C.v = C.u - 2	// S.u - 2
A.u = B.v + C.v // 2S.u - 2
A.v = 3*A.u		// 6(S.u-1)
S.v = A.v		// 6(S.u-1)

6(S.u-1)

例子：算术表达式文法

  1. 翻译目标：计算表达式的值
  2. 确定产生式的语义
    1. $e\to E_1+T$

SDD：（CFG,attrs, rules）对于每个产生式 $A \to \alpha$，都有一组关联的语义规则 $b = f (c_1, c_2, \cdots ,c_n)$

$b$ 依赖 $c_1, c_2, \cdots ,c_n$

设解析树上的结点 N

N 上的非终结符 A 的综合属性：一个与 N 的产生式（$A \to \cdots$）关联的语义规则所定义的属性

N 上的非终结符 B 的继承属性：一个与 N 的父节点的产生式（$A \to \cdots$）关联的语义规则所定义的属性

Synthesized attribute an attribute defined wholly in terms of the attributes of the node, its children, and constants

如果某节点的某属性由此结点、子节点的属性确定，则这个属性是一个综合属性。

只使用综合属性定义的 DDT 称为 S 属性翻译

如果某节点的某属性不但依赖于此节点和子节点，还依赖于父节点或兄弟节点，则这个属性是一个继承属性。

Inherited attribute an attribute defined wholly in terms of the node’s own attributes and those of its siblings or its parent in the parse tree (plus constants)

S-attributed SDT :

  • If an SDT uses only synthesized attributes, it is called as S-attributed SDT.
  • S-attributed SDTs are evaluated in bottom-up parsing, as the values of the parent nodes depend upon the values of the child nodes.
  • Semantic actions are placed in rightmost place of RHS.

L-attributed SDT:

  • If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.
  • Attributes in L-attributed SDTs are evaluated by depth-first and left-to-right parsing manner.
  • Semantic actions are placed anywhere in RHS.