『compiler-6』syntax translation
语法制导翻译
一、翻译文法
输入文法：未插入动作符号的文法，可以推导产生输入序列
翻译文法：一种上下文无关文法，其终结符号集合由输入符号 + 动作符号（@）组成，可以推导产生活动序列
活动序列：插入了动作符号的输入序列，由终结符和动作符号组成
输入序列：从活动序列中抽去动作符号，得到输入序列（原始的程序输入）
输出序列：从活动序列中抽去输入序列，得到动作序列（执行动作序列完成翻译任务）
二、语法制导的翻译
- 语法制导翻译的定义：根据翻译文法的翻译获得动作序列，并执行该动作序列
- 语法制导翻译的实现方法：
- 在文法的适当位置插入语义动作符号
- 获得对偶序列，对偶的第一元为输入序列、第二元为动作符号序列
三、属性翻译文法
- 属性：在翻译文法的基础上，为非终结符、终结符、动作符号赋予属性，表示参数值
- 综合属性：按照自右向左、自底向上的顺序求值，如属性变量 \(\uparrow p\)
- 继承属性：按照自左向右、自顶向下的顺序求值，如属性变量 \(\downarrow q\)
四、L-属性翻译文法（L-ATG）
L-ATG 的定义：
文法中的终结符、非终结符、动作符号都带有属性
非终结符和动作符号的属性可分为继承属性和综合属性
开始符号的继承属性 和 终结符的综合属性具有指定初始值
继承属性的求值规则：
- 规则左部非终结符的继承属性，取自上面规则右部该符号的继承属性（取自己已有即可）
- 规则右部符号的继承属性，用该规则左部符号的继承属性or出现在该符号左侧符号的属性计算
注意：自顶向下（自左向右）：取自父节点的继承属性 或 依据父节点和左兄弟属性计算
综合属性的求值规则：
- 规则右部非终结符的综合属性，取自下面规则左部该符号的综合属性（取自己已有即可）
- 规则左部非终结符的综合属性，用该规则左部符号的继承属性or某个右部符号的属性计算
注意：自底向上（自右向左）：取自自己的继承属性 或 依据子节点属性计算 - 动作符号的综合属性使用该符号的继承属性或某个右部符号的属性计算
注意：理解继承属性和综合属性，可以从函数传参与返回值的角度考虑：
- 继承属性：作为入参（形参）
- 左部的继承属性：必然由其上方规则右部的继承属性值传入
- 右部的继承属性（形参）：只能使用该产生式已经求出（即左侧）的属性值计算
- 综合属性：作为返回值（地址）
- 右部的综合属性：必然由其下方规则左部的综合属性值返回
- 左部的综合属性：只能使用该产生式对应过程的入参（继承属性）or 右部属性（过程内部的局部变量）计算
五、简单赋值形式的 L-ATG（SL-ATG）
简单赋值形式的 L-ATG 文法：将属性求值规则简化为仅简单赋值形式的
SL-ATG 的定义：L-ATG 是一个 SL-ATG，当且仅当满足以下两个条件：
- 规则右部符号的继承属性是一个常量，其等于规则左部符号的继承属性值，或该符号左侧的综合属性值
- 规则左部符号的综合属性是一个常量，其等于规则左部符号的继承属性，或右部符号的综合属性
将 L-ATG 改写为 SL-ATG：设有求值函数 f 及其求值规则 I := f(R,S)
注意：如果将 @f 插入到 a 后 <B> 前，继承属性 \(\text{I}_2\) 就无法借助 S 求出值（违反了L-ATG中继承属性的求值规则）
六、自顶向下的语法制导翻译
翻译文法的自顶向下翻译（无参数）：直接在解析到对应位置时执行动作符号即可
属性翻译文法的自顶向下翻译（含形参与引用）
符号下的属性传递：
- 继承属性：属性名作为解析程序的形参（传值）
- 综合属性：属性名作为解析程序的指针参数（传地址），支持收集返回值
属性命名规定：
- 产生式左部的同名非终结符必须使用相同的属性名
- 具有相同值的属性拥有相同的属性名
翻译示例：设 \(\text{<A>}_{\uparrow \text{P}} \rightarrow c_{\uparrow U} @y_{\downarrow U} \text{ <A>}_{\uparrow Q} \text{ S}_{\downarrow z} @v_{\downarrow P}b\) ；求值规则为：P := Q + U、Z := U - 3
其中左部P是综合属性，传入指针P；U是终结符c的综合属性，自带初始值；Q和Z分别传值和地址
