【编译原理】3、语法制导翻译与抽象语法树

编译原理目录
1、词法分析
 2、语法分析（重点）
3、语法制导翻译与抽象语法树
 4、语义分析
 5、代码生成
 6、中间代码与程序分析
 7、代码优化

三、语法制导翻译与抽象语法树

3.1 语法制导的翻译

编译器在做语法分析的过程中，除了回答程序语法是否合法外，还必须完成后续工作，可能的工作包括(但不限)：类型检查、目标代码生成、中间代码生成等。这些后续的工作一般可通过语法制导的翻译完。

基本思想：

给每条产生式规则附加一个语义动作（一个代码片段）
语义动作在产生式“ 归约”时执行，即当右部分析完毕时刻，右部的值计算左部的值
自顶向下分析和自底向上分析采用的技术类似

示例： 计算表达式的值

0:  E -> E+E    {E = E1 + E2}
1:     | n      {E = n}

LR分析中的语法制导翻译：

在分析栈上维护三元组：$<symbol, value, state>$，其中symbol是终结符或非终结符， value是symbol所拥有的值， state是当前的分析状态。

示例：

0: S -> E $
1: E -> E+E     {E = E1 + E2}
2:     | n      {E = n}

以输入$7+8+9$为例进行语法制导翻译:

3.2 抽象语法树

以$15*(3+4)$为例：

考虑分析树：

“浓缩”成抽象语法树：

3.2.1 具体语法和抽象语法

具体语法是语法分析器使用的语法，必须适合于语法分析，如各种分隔符、消除左递归、提取左公因子，等等。
抽象语法是用来表达语法结构的内部表示。现代编译器一般都采用抽象语法作为前端（词法语法分析）和后端（代码生成）的接口。

3.2.2 抽象语法树数据结构

在编译器中，为了定义抽象语法树，需要使用实现语言来定义一组数据结构。（与语言密切相关）
早期的编译器有的不采用抽象语法树数据结构，直接在语法制导翻译中生成代码。但现代的编译器一般采用抽象语法树作为语法分析器的输出（更好的系统的支持、简化编译器的设计）

3.2.3 抽象语法树的定义

E -> n
   | E + E
   | E * E

(1) 数据结构的定义

C代码：

/* 数据结构 */
enum kind {
  E_INT,  //对应 n
  E_ADD,  // 对应 +
  E_TIMES // 对应 *
};
struct Exp {
  enum kind kind;
};
struct Exp_Int{
  enum kind kind;
  int n;
};
struct Exp_Add{
  enum kind kind;
  struct Exp *left;
  struct Exp *right;
};
struct Exp_Times{
  enum kind kind;
  struct Exp *left;
  struct Exp *right;
};

(2) "构造函数"的定义

struct Exp_Int *Exp_Int_new (int n)
{
    struct Exp_Int *p = malloc (sizeof(*p));
    p->kind = E_INT;
    p->n = n;
    return p;
}
struct Exp_Add *Exp_Add_new(struct Exp *left, struct Exp *right)
{
    struct Exp_Add *p = malloc (sizeof(*p));
    p->kind = E_ADD;
    p->left = left; p->right = right;
    return p;
}

(3) 示例1

/* 用数据结构来编码程序 “2+3*4” */
e1 = Exp_Int_new (2);
e2 = Exp_Int_new (3);
e3 = Exp_Int_new (4);
e4 = Exp_Times_new (e2, e3);
e5 = Exp_Add_new (e1, e4);

打印成树

/* 优美打印 */
void pretty_print (e){
    switch (e->kind) {
        case E_INT:
            printf ("%d", e->n);
            return;
        case E_ADD:
            printf ("("); pretty_print (e->left);
            printf (")"); // 需要适当的类型转换
            printf (" + ");
            printf ("("); pretty_print (e->right);
            printf (")");
            return;
        other cases: /* similar */
    }
}

(4) 示例2：树的规模

/* 节点的个数 */
int numNodes (E e)
{
    switch (e->kind) {
        case E_INT:
            return 1;
        case E_ADD:
        case E_TIMES:
            return 1 + numNodes (e->left) + numNodes (e->right);
        default:
            error (“compiler bug”);
    }
}

(3) 示例3：从表达式到栈式计算机Stack的编译器

/* 编译器：请参考课程第一部分的作业内容： Sum -> Stack*/
List all; // 存放生成的所有指令
void compile (E e)
{
    switch (e->kind) {
        case E_INT: emit(push e->n); break;
        case E_ADD:
        case E_TIMES:
            // 留作练习
        default:
            error (“compiler bug”);
    }
}

3.3 抽象语法树(ASF)的自动生成

LR分析中生成抽象语法树:

在语法动作中，加入生成语法树的代码片段，片段一般是语法树的“构造函数”。
在产生式归约的时候，会自底向上构造整棵树，从叶子到根。