语法制导翻译
编译器在做语法分析过程中除了回答程序语法是否合法外,还必须完成后续工作
- 可能的工作包括(但是不限于)
- 类型检查
- 目标代码生成
- 中间代码生成
- …等等
- 可能的工作包括(但是不限于)
这些后续的工作一般可通过语法制导的翻译完成
LR分析中的语法制导翻译
在之前的加法中实现语法制导翻译
%{
#include <stdio.h>
#include <stdlib.h>
int yylex();
void yyerror();
%}
%left '+'
%%
lines: line
| line lines
;
line: exp '\n' {
printf("value=%d\n", $1);}
;
exp: n {
$$=$1;}
| exp '+' exp {
$$=$1+$3;}
;
n: '1' {
$$=1;}
| '2' {
$$=2;}
| '3' {
$$=3;}
| '4' {
$$=4;}
| '5' {
$$=5;}
| '6' {
$$=6;}
| '7' | '8' | '9' | '0';
%%
int yylex()
{
return getchar();
}
void yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
return;
}
int main(int argc, char **argv)
{
yyparse();
return 0;
}
基本思想
- 给每条产生式规则附加一个语义动作
- 一个代码片段
- 语义动作在产生式“归约”时执行
- 即由右部的值计算左部的值
- 以自底向上的技术为例进行讨论
- 自顶向下的技术与此类似
抽象语法树
将分析树的浓缩过程生成的树是抽象语法树
分析树
- 分析树编码了句子的推导过程
- 但是包含很多不必要的信息
- 注意:这些节点要占用额外的存储空间
- 本质上,这里的那些信息是重要的?
- 对于表达式而言,编译只需要知道运算符和运算数
- 优先级、结合性等已经在语法分析部分处理掉了
- 对于语句、函数等语言其他构造而言也一样
- 例如:编译器不关系赋值符号是=还是:=或者其他符号
- 对于表达式而言,编译只需要知道运算符和运算数
具体语法和抽象语法
- 具体语法是语法分析器使用的语法
- 必须适合语法分析,如各种分隔符、消除左递归、提取左公因子等
- 抽象语法是用来表达语法结构的内部表示
- 现代编译器一般都采用抽象语法作为前端(词法语法分析)和后端(代码生成)的接口
抽象语法树的数据结构
- 在编译器中,为了定义抽象语法树,需要使用实现语言来定义一组数据结构
- 和实现语言密切相关
- 早期的编译器有的不采用抽象语法树数据结构
- 直接在语法制导翻译中生成代码
- 但现代的编译器一般采用抽象语法树作为语法分析器的输出
- 更好的系统支持
- 简化编译器的设计
抽象语法树的自动生成
在语法动作当中,加入生成语法树的diam
- 代码片段一般是语法树的构造函数
在产生式归约的时候,会自底向上构造整棵树
- 从叶子到根
抽象语法树是编译器前端和后端的接口
- 程序一旦被转换为抽象语法树,则源代码即被丢弃
- 后续的阶段只处理抽象语法树
所以抽象语法树必须编码足够多的源代码信息
- 例如:它必须编码每个语法结构在原代码中的位置(文件,行号、列号等)
- 这样,后续的检查阶段才能精确的报错
- 或者获取程序的执行刨面
抽象语法书必须仔细设计