Abstract Syntax⚓︎

Semantic Actions⚓︎

编译器接下来要对由分析器认为合法的句子做以下事情：

• 构建抽象语法树
• 执行语义分析
• 生成中间表示（IR）

分析器的语义动作(semantic actions) 可以对已分析的短语进行有用的处理，在以下情况中得到应用：

• 递归下降(recursive descent)
• Yacc 生成的分析器

Recursive Descent⚓︎

若想通过分析对输入字符串求值，将代码改为：

在递归下降分析器中，语义动作是分析函数返回的值、副作用，或两者兼有。

对于每个终结符和非终结符，为其关联一种语义值类型，这些值代表由该符号推导出的短语，而这种类型来源于编译器的实现语言。

例子

Yacc-Generated Parsers⚓︎

语法规则：

• { ... }：语义动作
• $i：第 i 个右侧符号的语义值
• $$：左侧非终结符的语义值
• %union：语义值可能携带的不同类型声明
• <variant>：声明每个终结符或非终结符的类型

语义值的实现：

• Yacc 生成的分析器维护一个与状态栈并行的语义值栈
• 当分析器执行规约时，必须执行相应的 C 语言语义动作
• 从栈顶的前 k 个元素中获取获取规则 A -> Y1 ... Yk 中的 $i
• 当解析器从符号栈弹出 Yk ... Y1 并压入 A 时，它同时会从语义值栈中弹出 k 个值，并将通过执行 C 语言语义动作的代码将获得的值压入栈中

例子

每个终结符和非终结符都可以关联其自身的语义值类型。以 A -> B C D 为例：

• 语义动作必须返回一个值，该值的类型应与非终结符 A 所关联的类型一致
• 它可以从匹配的终结符 B、C、D 以及非终结符所关联的值中构建这个值

LR 分析器能以确定且可预测的顺序执行归约及相关的语义动作：即对分析树进行自底向上、从左到右的遍历。而（虚拟）分析树的遍历采用后序(postorder) 遍历方式。

Abstract Parse Trees⚓︎

虽然可以在 Yacc f 分析器的语义动作短语内编写一个完整的编译器，但不仅难以阅读和维护，且必须得严格按照程序被分析的顺序进行分析。

所以我们将语法（分析）问题与语义（类型检查和机器代码翻译）问题分离。一种解决方案是由分析器生成可供后续阶段遍历的分析树。

具体分析树(concrete parse tree)：分析树为输入中的每个记号精确对应一个叶节点，并为分析过程中归约的每条语法规则对应一个内部节点

• 它代表了源语言的具体语法
• 使用起来不太方便：
  • 对于后续阶段来说，存在冗余且无用的标记，比如 (, )
  • 内存占用过于依赖语法规则，语法规则改变 -> 解析树随之变化

而抽象语法为分析器与编译器的后续阶段之间提供了一个清晰的接口，但并非用于分析过程。分析器利用具体语法来构建抽象语法的分析树就叫做抽象语法树(abstract syntax tree)，它传达了源程序的短语结构，所有分析问题均已解决，但未进行任何语义解释。

要在后续阶段使用抽象语法树，编译器需要将抽象语法树表示为数据结构并进行操作。具体来说，需要为每个非终结符定义类型别名，为每个产生式设计联合变体。

typedef struct A_exp_ *A_exp;
struct A_exp_ {
  enum {A_numExp, A_plusExp, A_timesExp} kind; 
  union {
    int num; 
    struct {A_exp left; A_exp right;} plus;
    struct {A_exp left; A_exp right;} times; 
  } u; 
};
A_exp A_NumExp(int num);
A_exp A_PlusExp(A_exp left, A_exp right);
A_exp A_TimesExp(A_exp left, A_exp right);

A_exp A_PlusExp(A_exp left, A_exp right) {
  A_exp e = checked_malloc(sizeof(*e));
  e->kind = A_plusExp;
  e->u.plus.left = left;
  e->u.plus.right = right;
  return e;
}

例子

使用以下数据结构和具体语法构建 2 + 3 * 4 的抽象语法树：

Yacc 或递归下降分析器通过分析具体语法来构建抽象语法树。

%left PLUS
%left TIMES

%%
exp : NUM               {$$=A_NumExp($1);}
     | exp PLUS exp     {$$=A_PlusExp($1,$3);}
     | exp TIMES exp    {$$=A_TimesExp($1,$3);}

Positions⚓︎

• 在单遍编译器 (one-pass compiler) 中，词法分析、语法分析和语义分析是同时进行的
• 如果存在必须向用户报告的类型错误，词法分析器的当前位置可以作为错误源位置的合理近似值
• 在单遍编译器中，词法分析器维护一个“当前位置”全局变量

• 对于使用抽象语法树数据结构的编译器：

  • 它不需要在一次遍历中完成所有解析和语义分析
  • 甚至在语义分析开始之前，词法器就已经到达文件末尾

• 抽象语法树的每个节点都必须记录其在源文件中的位置，具体来说，必须在抽象语法的数据结构中嵌入 pos 字段，这些字段用于指示生成这些抽象语法结构的字符在原始源文件中的具体位置

  例子

  

  • 词法分析器：必须将每个标记的起始和结束位置传递给语法分析器
  • 语法分析器：理想情况下，应维护一个与语义值栈并行的位置栈，使得每个符号的位置可供语义动作使用
    • Bison 可以实现这一点

    • 而 Yacc 则不能，不过有一种解决方案是定义一个非终结符 pos，其语义值为源位置（行号，或行号及行内位置），例如访问 PLUS 的位置：

      

评论区