语义分析 | Dasi's Blog

1. 程序任务

输入：语法树
符号表构建：遍历 AST，在遇到声明节点时向符号表插入新符号和它的属性，如类型（type）、作用域（scope）、偏移量（offset）等
语义检查：在每个运算节点，检查操作是否合法，报告错误
属性计算：综合属性从叶子向上累积，继承属性从父／左兄弟传下
输出：抽象语法树和符号表

2. 属性文法

2.1 定义

属性：对文法的每一个符号，都可以引入相关属性，X.a 表示符号 X 的属性 a

综合属性（synthetic）：由子节点向父节点计算或传递的信息，是自下而上的信息
继承属性（inherited）：由父节点或左侧兄弟节点向子节点计算或传递的信息，是自上而下的信息
终结符只有综合属性，终结符只会把自己的词素信息交给父节点
起始符没有继承属性，起始符是根节点，不存在父节点
每个属性在文法定义中要么是纯综合、要么是纯继承，绝不会同时具有两种性质

语义规则：为文法的每一个产生式配备的计算属性的规则，所描述的工作包括属性计算、语义检查、符号表构建、中间代码生成

2.2 类型

依赖图

节点：对应语法树上某个符号的某个属性，例如非终结符 E 的综合属性 val，或终结符 NUM 的词素属性 lexval
边：如果属性 X.a 的值在其语义规则中需要用到属性 Y.b，就在依赖图中画一条从节点 Y.b → X.a 的有向边，表示 “先计算 Y.b，再计算 X.a”
拓扑排序：对节点顺序 $N_1, N_2, \ldots, N_k$ 满足如果依赖图中有 $N_i \to N_j$ ，那么一定有 $i < j$

S-属性文法：

只有综合属性，没有继承属性
每个节点的属性值仅由其子节点的属性值计算而来
利用后序遍历，本质上是自底向上

L-属性文法

有综合属性，也有继承属性
继承属性只能依赖于父节点或左侧兄弟节点的属性
利用深度遍历，本质上是自顶向下

任何 S-属性文法都是一种特殊的 L-属性文法

3. 语义分析策略

3.1 SDD

语法制导定义：给上下文无关文法的每个符号定义若干属性，并对每条产生式 $A\to X_1\cdots X_n$ 规定属性的语义规则，从而表示这些属性之间的依赖关系

A → X Y Z {
  A.syn = f(X.syn, Y.inh)
  Y.inh = g(A.inh, X.syn)
}

3.2 SDT

语法制导翻译：在文法的产生式内部直接插入可执行的“语义动作”，在合适的时机直接执行语义动作

1	A → X { action1 } Y { action2 } Z

3.3 区别

策略	SDD	SDT
定义形式	语义规则写在文法外部	语义动作写在文法内部
特点	声明式	命令式
适用	更适合做形式化分析和依赖图求值	更适合直接在解析器中立即执行
触发时机	由后续算法（拓扑／后根／LL／LR）决定	直接随着解析（shift/reduce 或函数调用）触发

不是所有的 SDT 都适用于语法分析，如果语义动作在产生式的最开始，解析器还没读取到符号就要输出，显然是无法实现的

4. LR 实现 S-属性文法的 SDT

语义栈：每个综合属性维护一个语义栈，并且与符号栈保持一一对应，如果没有则用 - 占位

扩展 LR 分析器：当执行一次 reduce A→β 的时候，立刻调用这条产生式对应的“语义动作”

每次 shift 都要在语义栈 push 对应终结符的占位符 –
每次 reduce
1. 按产生式右部长度从三栈同时 pop 相同次数的元素
2. 将弹出的语义值用来在语义动作里计算新属性
3. 再把新属性值 push 回语义栈
4. 同步在符号栈/状态栈做 GOTO
语义栈始终与符号栈在位置上一一对应，语义栈的值就是符号对应属性的值，占位符 – 表示该符号没有属性值

5. LL 实现 L-属性文法的 SDT

将原始文法转变为 LL(1) 文法
用 SDD 的方式转变为属性文法
将 SDD 转化为 SDT
- 把产生式右边非终结符 A 的继承属性插入到 A 前面的位置
- 把产生式左边非终结符 A 的综合属性插入到产生式的末尾位置
消除左递归
- 情况一：不涉及任何语义计算，只是简单的输出信息，那么可以直接把语义动作当成终结符，利用通用方法 $A \to A\alpha \mid \beta$ 变为 $A \to \beta A', A' \to \alpha A' \mid \varepsilon$
- 情况二：只设计 S-属性的语义计算，可以将语义动作放在合适的位置
  1. 让 f(X.x) 的值最先确定，作为 R.i 的初始值
  2. 让 R.i 递归计算并缓存每一次 g(R.i, Y.y) 的值
  3. 当且仅当 R 不再递归，将 R.i 赋值给 R.s，然后一路向上传递给 A.a
将文法转化为递归下降的解析器

A → A Y    { A.a = g(A₁.a, Y.y); }
A → X      { A.a = f(X.x); }
转变为
A → X { R.i = f(X.x); } R { A.a = R.s }
R → Y { R'.i = g(R.i, Y.y); } R' { R.s = R'.s; }
R → ε { R.s = R.i; }
转变为
void parse() {
    int result = parseA();
    if (!match(EOF)) {
        error();
    }
    print(result);
}

int parseA() {
    if (!match(X_token)) {
        error();
    }
    int X_x = getXval();
    int R_i = f(X_x);
    int R_s = parseR(R_i);
    return R_s;
}

int parseR(int R_inh) {
    if (match(Y_token)) {
        int Y_y = getYval();
        int R_i = g(R_inh, Y_y);
        int R_s = parseR(R_i);
        return R_s;
    } 
    else {
        int R_s = R_inh;
        return R_s;
    }
}