L 属性定义的计算

#L 属性定义的自上而下计算

#L 属性定义

如果每个产生式 $A \rightarrow X _ { 1 } X _ { 2 } \cdots X _ { n }$ 的每条语义规则计算的属性是 A 的综合属性；或者是 $X_j$ 的继承属性，$1 \leq j \leq n$, 但它仅依赖：

• 该产生式中 $X_j$ 左边符号 $X _ { 1 } , X _ { 2 } , \dots , X _ { j - 1 }$ 的属性
• A 的继承属性

显然，S 属性定义属于 L 属性定义，因为上面的两条限制是对继承属性的限制。

#L 属性定义与 S 属性定义的区别

S 属性定义中，只要将产生式作为一个整体看待即可，语义规则可以视为是附着在整个产生式上。

L 属性定义则不一样，它跟属性所属的符号在产生式中的位置有关系，于是需要翻译方案。

#翻译方案

它的语义动作（在此不叫语义规则）放在花括号 {} 内，并且插入到产生式右部合适的地方。这是一种动作和分析交错的方法，以表示动作的执行时机。

只有综合属性时：

为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。

既有综合属性又有继承属性时：

• 产生式右部符号的继承属性必须在先于这个符号的动作中计算。
• 一个动作不能引用该动作右边符号的综合属性。
• 左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。计算该属性的动作通常放在产生式右端的末尾。

总的来说就是要保证动作在引用属性时其值已经可用，也就是要保证动作不会引用还没有计算出值的属性。

🌰对于文法

$S \rightarrow A_{1} A_{2}\quad \lbrace A_{1} . i n:=1 ; A_{2} . i n:=2 \rbrace$

$A \rightarrow a \quad \lbrace p r i n t ( A.in ) \rbrace$

不符合条件一。在分析 $A_1$ 时，要把它推导成 $a$ 然后输出 $A_1.in$，然而，这个时候还不知道 $A_1.in$ 的值，因为赋值动作在整个产生式的末尾。如果把第一条产生式改为 $S \rightarrow \lbrace A _ { 1 } .in : = 1 ; A _ { 2 } .in : = 2 \rbrace A _ { 1 } A _ { 2 }$，则是合理的翻译方案。

#预测分析器的设计

构造预测分析器时，必须要消除左递归，而消除左递归可能会引起继承属性的出现。原因是翻译分案的属性信息（语法树结点指针）的流动方向和归约的方向不一致。

#构造方法

(1) 函数的形参、返回值和局部变量

• 对每个非终结符 A构造一个函数过程，对 A 的每个继承属性设置一个形式参数。
• 函数的返回值为 A 的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，假设每个非终结只有一个综合属性。
• A 对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。

(2) 非终结符 A 对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。

(3) 每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：

• 对于带有综合属性 x 的终结符 X，把 x 的值存入为 X.x 设置的变量中。然后产生一个匹配 X 的调用，并继续读入一个输入符号。
• 对于每个非终结符 B，产生赋值语句 $c = B \left( b _ { 1 } , b _ { 2 } , \cdots , b _ { k } \right)$ 其中，$b _ { 1 } , b _ { 2 } , \cdots , b _ { k }$ 是为 B 的继承属性设置的变量，c 是为 B 的综合属性设置的变量。
• 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。

#用综合属性代替继承属性

#L 属性定义的自下而上计算

它能实现任何基于 LL(1) 文法的 L 属性定义，也能实现许多（但不是所有的）基于 LR(1) 的 L 属性定义。

#L 属性自下而上计算需要解决的问题

自下而上的分析中，语义动作的执行是在使用产生式对句柄进行归约的时候。但是，L 属性定义的继承属性的计算需要嵌在产生式右部不同的地方。

🌰对于文法 $A \rightarrow X Y \lbrace Z . i = X . x \rbrace Z$

在 $Z$ 还没有开始处理前，继承属性 $Z.i$ 在栈中就没有对应的 $val$ 条目供其使用。

#解决方案

通过改写文法，使得所有嵌入在产生式中间的动作变换成只在产生式的最右端出现。分以下三种情况讨论：

#删除翻译方案中嵌入的动作

在文法中加入推出空串的标记非终结符，让每个嵌入动作由不同的标记非终结符 M 代表，并把该动作放在产生式 $M \rightarrow \varepsilon$ 的右端。

🌰

$E \rightarrow T R$

$R \rightarrow + T \lbrace print \left( ^ { \prime } + ^ { \prime } \right) \rbrace R_{ 1 } | - T \lbrace print \left(^ { \prime } - ^ { \prime } \right) \rbrace R_{ 1 } | \varepsilon$

$T \rightarrow n u m \lbrace p r i n t (n u m. v a l) \rbrace$

删除嵌入动作后：

$E \rightarrow T R$

$R \rightarrow + T M R _ { 1 } \left| - T N R _ { 1 } \right| \varepsilon$

$M \rightarrow \varepsilon \lbrace print ( ^ { \prime } + ^ { \prime } )\rbrace$

$N \rightarrow \varepsilon \lbrace print ( ^ { \prime } - ^ { \prime } )\rbrace$

$T \rightarrow n u m \lbrace p r i n t (n u m. v a l) \rbrace$

#分析栈上的继承属性

第一种情况：所依赖的属性在分析栈上的位置能静态确定

对于产生式 $A\rightarrow XY$，因为 $Y$ 以下的任何子树在规约前，$X.s$ 的值已经在栈中，所以它的值可以被 $Y$ 继承。如果 $Y$ 的继承属性由复写规则 $Y.i=X.s$ 定义，$X.s$ 是综合属性，那么在需要使用 $Y.i$ 的地方，都可以使用 $X.s$ 代替，如果能静态的确定 $X.s$ 在栈中的位置。

第二种情况：所依赖的属性在分析栈上的位置不能静态确定

🌰

由于 B 可能在、也可能不在 A 和 C 之间，因此在使用 $C\rightarrow c$ 规约时 $C.i$ 的值（也就是 $A.s$ 的值）在 $stack[top-2].val$ 或者在 $stack[top-1].val$。

可以添加一个标志非终结符 M，使 $M.i$ 继承 A 的综合属性值，然后第二个产生式中的 C 继承 M 的综合属性值，这样，无论是用第一个产生式还是第二个产生式，$C.i$ 的值都可以在 $stack[top-1].val$ 中得到。

#模拟继承属性的计算

如果继承属性并不直接等于某个综合属性，而是它的一个函数，可以使用标记非终结符来模拟继承属性的计算。

🌰

#引进标记非终结符号对基础文法的影响

基础文法是 LL(1) 文法

没有影响，修改后的文法仍将保持 LL(1) 文法。因为每个标记非终结符号是唯一的，而且只有唯一一个的 $\varepsilon$ 产生式。任何一个 LL(1) 文法一定是 LR(1) 文法，因此加标记非终结符不会引起 LR 分析动作的冲突。

基础文法是 LR(1) 文法

可能使修改后的文法变成非 LR(1) 文法。