MENU

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

June 1, 2020 • Read: 805 • 编程之路,编译原理

编译原理目录
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是终结符或非终结符, valuesymbol所拥有的值, 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分析中生成抽象语法树:

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

示例:

E -> E + E    {$$ = Exp_Add_new ($1, $3);}
   | E * E    {$$ = Exp_Times_new ($1, $3);}
   | n        {$$ = Exp_Int_new ($1);}

3.4 源代码信息的保留和传播

  • 抽象语法树是编译器前端和后端的接口。程序一旦被转换成抽象语法树,则源代码即被丢弃,后续的阶段只处理抽象语法树。
  • 所以抽象语法树必须编码足够多的源代码信息。例如,它必须编码每个语法结构在源代码中的位置(文件、行号、列号等),这样,后续的检查阶段才能精确的报错,或者获取程序的执行刨面。
  • 抽象语法树必须仔细设计!
- - - 结束 - - -
  • 文章标题:【编译原理】3、语法制导翻译与抽象语法树
  • 文章链接:https://blog.canye365.cn/archives/307.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021