编译原理目录
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分析中生成抽象语法树:
- 在语法动作中,加入生成语法树的代码片段,片段一般是语法树的“构造函数”。
- 在产生式归约的时候,会自底向上构造整棵树,从叶子到根。
示例:
E -> E + E {$$ = Exp_Add_new ($1, $3);}
| E * E {$$ = Exp_Times_new ($1, $3);}
| n {$$ = Exp_Int_new ($1);}
3.4 源代码信息的保留和传播
- 抽象语法树是编译器前端和后端的接口。程序一旦被转换成抽象语法树,则源代码即被丢弃,后续的阶段只处理抽象语法树。
- 所以抽象语法树必须编码足够多的源代码信息。例如,它必须编码每个语法结构在源代码中的位置(文件、行号、列号等),这样,后续的检查阶段才能精确的报错,或者获取程序的执行刨面。
- 抽象语法树必须仔细设计!
- - - 结束 - - -