抽象语法树
在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then 这样的条件跳转语句，可以使用带有三个分支的节点来表示。和抽象语法树相对的是具体语法树（通常称作分析树）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树，然后从分析树生成AST。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。下面是辗转相除法对应的抽象语法树
while (b != 0) {
if (a > b)
a = a − b;
else
b = b − a;
}
return a
辗转相除法抽象语法树
计算器实例
首先我们创建计算器的头文件fb3-1.h
/** 与词法分析器的解口*/
extern int yylineno; /*来自于词法分析器*/
void yyerror(char *s, ...);
int yylex();
/** ast中的节点*/
struct ast {
int nodetype;
struct ast *l;
struct ast *r;
};
struct numval {
int nodetype; /**类型k表明常量*/
double number;
};
/** 构造ast*/
struct ast *newast(int nodetype, struct ast *l, struct ast *r);
struct ast *newnum(double d);
/** 计算ast*/
double eval (struct ast *);
/**删除和释放ast*/
void treefree(struct ast *);
/**
* 抽象语法树由多个节点组成，每个节点都有一个节点类型。不同的节点可以有不同的域，但目前我们只有两种类型，一种是执行最多两个子节点的指针，另外一种包含一个数组。eval遍历ast，返回它所代表的表达式的值。
*
* */
然后我们创建Bison的语法分析规则文件fb_3_1.y
%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "fb_3_1.h"
%}
/*第一部分使用%union来生命语法分析器中符号值的类型
一旦联合类型被定义，我们需要告诉bison每种语法符号使用的值类型，这通过放置在尖括号<>中的联合类型的响应成员名字来确定。
新的声明 %type把值<a>赋给exp, factor, term，当我们创建ast时会用到他们
如果你不使用记号或者非终结符的值，你并不需要为他们声明类型。
当声明中存在%union时，如果你试图使用一个没有被赋予类型的符号值，bison将会报错。
*/
%union {
struct ast *a;
double d;
}
%token <d> NUMBER
%token EOL
%type <a> exp factor term
%%
calclist:/*空规则*/
| calclist exp EOL {
printf("=%4.4g\n", eval($2));
treefree($2);
printf("> ");
}
| calclist EOL { printf(">");} /*空行或注释*/
;
exp: factor
| exp '+' factor { $$ = newast('+', $1, $3);}
| exp '-' factor { $$ = newast('-', $1, $3);}
;
factor: term
| factor '*' term { $$ = newast('*', $1, $3); }
| factor '/' term { $$ = newast('/', $1, $3); }
;
term: NUMBER { $$ = newnum($1); }
| '|' term {$$ = newast('|', $2, NULL);}
|'(' exp ')' {$$ = $2;}
| '-' term {$$ = newast('M', $2, NULL);}
;
%%
void
yyerror(char *s, ...)
{
va_list ap;
va_start(ap, s);
fprintf(stderr, "%d: error: ", yylineno);
vfprintf(stderr, s, ap);
fprintf(stderr, "\n");
}
int
main(int argc, char **argv)
{
printf("> ");
return yyparse();
}
然后我们再创建fb_3_1.funcs.c文件来具体实现抽象语法树
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "fb_3_1.h"
struct ast *
newast(int nodetype, struct ast *l, struct ast *r)
{
struct ast *a = malloc(sizeof(struct ast));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = nodetype;
a->l = l;
a->r = r;
return a;
}
struct ast *
newnum(double d)
{
struct numval *a = malloc(sizeof(struct numval));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = 'k';
a->number = d;
return (struct ast *)a;
}
double
eval(struct ast *a)
{
double v;
printf("nodetype:%c\n", a->nodetype);
if (a->nodetype == 'k') {
printf("number:%f\n", ((struct numval *)a)->number);
}
switch(a->nodetype) {
case 'k': v = ((struct numval *)a)->number;break;
case '+': v = eval(a->l) + eval(a->r); break;
case '-': v = eval(a->l) - eval(a->r); break;
case '*': v = eval(a->l) * eval(a->r); break;
case '/': v = eval(a->l) / eval(a->r); break;
case '|': v = eval(a->l); if (v < 0) v = -v; break;
case 'M': v = eval(a->l); break;
default: printf("internal error: bad node %c\n", a->nodetype);
}
return v;
}
void
treefree(struct ast *a)
{
switch(a->nodetype) {
/**两颗子树*/
case '+':
case '-':
case '*':
case '/':
treefree(a->r);
/*一颗子树*/
case '|':
case 'M':
treefree(a->l);
/*没有子树*/
case 'k':
free(a);
break;
default: printf("internal error: bad node %c\n", a->nodetype);
}
}
最后我们创建Makefile文件来指定编译内容，
fb_3_1: fb_3_1.l fb_3_1.y fb_3_1.h
bison -d fb_3_1.y
flex -o fb_3_1.lex.c fb_3_1.l
gcc -o $@ fb_3_1.tab.c fb_3_1.lex.c fb_3_1.funcs.c
clean:
rm -rf fb_3_1.lex.c fb_3_1 fb_3_1.tab.c fb_3_1.tab.h
在终端窗口中执行编译和测试
% make
bison -d fb_3_1.y
flex -o fb_3_1.lex.c fb_3_1.l
gcc -o fb_3_1 fb_3_1.tab.c fb_3_1.lex.c fb_3_1.funcs.c
% ./fb_3_1
> 2 + 3
nodetype:+
nodetype:k
number:2.000000
nodetype:k
number:3.000000
= 5
> 6 * 7
nodetype:*
nodetype:k
number:6.000000
nodetype:k
number:7.000000
= 42
>
测试结果分析
当我们在测试代码中键入2 + 3回车后，首先Flex会进行词法分析，得到3个token,'2','+',"3",然后将数据喂给Bison，Bison利用语法规则匹配到最后一条term: NUMBER { $$ = newnum($1); }，在这里会调用newnum这个函数并将返回值赋给term，读取'+'号后，因暂时无法匹配任何规则，会移进到堆栈中，然后继续读取'3'，会像‘2’一样进行类似处理返回一个数字ast，然后堆栈中的内容可以匹配上第二条
exp: factor
| exp '+' factor { $$ = newast('+', $1, $3);}
会进行归约处理，调用newast这个函数构造出一个新的抽象语法树，语法树的结构如下：
语法树
将新生成的语法树移进之后，发现已输入结束，可匹配上第一条规则
calclist:/*空规则*/
| calclist exp EOL {
printf("=%4.4g\n", eval($2));
treefree($2);
printf("> ");
}
此时会调用eval这个函数，并将上面得到的语法树作为参数传递到函数中去（$2的值），在eval函数中首先会匹配上'+'号
eval(struct ast *a)
{
double v;
printf("nodetype:%c\n", a->nodetype);
if (a->nodetype == 'k') {
printf("nodetype:%f\n", ((struct numval *)a)->number);
}
switch(a->nodetype) {
...
case '+': v = eval(a->l) + eval(a->r); break;
...
}
return v;
}
然后会递归调用eval这个函数，不过传的参数分别是左子树和右子树，
double
eval(struct ast *a)
{
double v;
printf("nodetype:%c\n", a->nodetype);
if (a->nodetype == 'k') {
printf("nodetype:%f\n", ((struct numval *)a)->number);
}
switch(a->nodetype) {
case 'k': v = ((struct numval *)a)->number;break;
...
}
return v;
}
由于左右子树的类型都为k,那么直接返回其number值，分别为2和3，然后执行相加操作，得到最后的返回值5，再打印出来就得到了测试结果。
全部代码大家可以到我的github上去下载
