利用flex&bison构建抽象语法树

利用flex&bison构建抽象语法树

Mr.GGLS 858 2021-11-29

分析目标

利用flex&bison完成词法分析和语法分析，并用graphiz打印出语法分析树

环境准备

  1. flex 2.6.4 和 bison 3.7.4

image-20211129103426505

  1. graphiz

  2. codeblocks

    • 修改codeblocks的默认编译参数（Settings->Compiler->Other settings->Advanced options）

    • image-20211129103822948

    • 修改语法分析文件*.y的编译输出参数

    • image-20211129103910136

    • 修改词法分析器文件*.l(是l不是I！)的编译输出参数

    • image-20211129104022814

    • 导入本项目

      • 点击build and run
      • image-20211129105406986

    • 即可运行

    • image-20211129105454853

测试代码（老师团队写的语言）

int x and skip;
x <== 1 and skip;
if (x<1)
then{
    x:=2
}
else{
    x:=3
};
x:=4

代码分析

  • 语言看上去是类C的
  • 语句的分隔靠 ";" 完成
  • and skip <== :=都为关键字，在词法分析器中要解释为token

词法分析器构建

%option noyywrap nodefault yylineno

%{
	#include <stdio.h>
	#include <stdlib.h>
	#include <stdarg.h>
	#include "com_assign.h"
	#include "com_assign.parser.h"
	void yyerror(char* s, ...);
%}

%%
"+" |
"-" |
"*" |
"/" |
"=" |
"|" |
"," |
";" |
"(" |
")" |
"{" |
"}" { return yytext[0]; }

">" { yylval.fn = 1; return CMP; }
"<" { yylval.fn = 2; return CMP; }
"<>" { yylval.fn = 3; return CMP; }
"==" { yylval.fn = 4; return CMP; }
">=" { yylval.fn = 5; return CMP; }
"<=" { yylval.fn = 6; return CMP; }
"<==" { return ASSIGN1; }
":=" { return ASSIGN2; }

"if"	{ return IF; }
"then"	{ return THEN; }
"else"	{ return ELSE; }
"and"   { return AND; }
"skip"  { return SKIP; }
"int"   { return INT; }
"#" 	{ return EOI; }

[a-zA-Z][a-zA-Z0-9]* {
	struct symbol *s = (struct symbol*)malloc(sizeof(struct symbol));
	s->name = strdup(yytext);
	s->value = 0;
	yylval.s = s;
	return NAME;
}

[0-9]+ { yylval.i = atoi(yytext); return NUM; }

\n { yylineno++; }
[ \t]+

.	{ yyerror("Mystery character %c\n", *yytext); }

%%
void yyerror(char* s, ...) {
	va_list ap;
	va_start(ap,s);

	fprintf(stderr, "%d: error: ", yylineno);
	vfprintf(stderr, s, ap);
	fprintf(stderr, "\n");
}

语法分析器构建

%{
# include <stdio.h>
# include <stdlib.h>
# include "com_assign.h"
extern void yyerror(char *s, ...);
struct ast *ast_root = NULL;
%}

%union{
	struct ast *a;
	int i;
	struct symbol *s;
	int fn;
}

%token <i> NUM
%token <s> NAME
%token IF THEN ELSE AND SKIP INT EOI

%nonassoc <fn> CMP
%right '=' ASSIGN1 ASSIGN2
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%type <a> exp stmt list iniv

%start topList
%%
stmt: IF exp THEN list { $$ = newflow('I',$2,$4,NULL); }
   | IF exp THEN list ELSE list { $$ = newflow('I',$2,$4,$6); }
   | exp
   | exp AND exp { $$ = newast('a',$1,$3); }
	| stmt ';' stmt {$$ = newast(';',$1,$3); }
	| stmt ';' { $$ = newast(';',$1,NULL); }
;

list: /* 空 */ { $$ = NULL; }
	| exp
;

exp: exp CMP exp { $$ = newcmp($2,$1,$3); }
   | exp '+' exp { $$ = newast('+',$1,$3); }
   | exp '-' exp { $$ = newast('-',$1,$3); }
   | exp '*' exp { $$ = newast('*',$1,$3); }
   | exp '/' exp { $$ = newast('/',$1,$3); }
   | '(' exp ')' { $$ = $2; }
   | '{' exp '}' { $$ = $2; }
   | '-' exp %prec UMINUS { $$ = newast('M',$2,NULL); }
   | NUM { $$ = newnum($1); }
   | SKIP { $$ = newast('s',NULL,NULL); }
   | INT exp { $$ = newast('i',$2,NULL); }
   | NAME { $$ = newasgn('0',$1,0); }
   | NAME '=' exp { $$ = newasgn('=',$1,$3); }
   | NAME ASSIGN1 exp {$$ = newasgn(666,$1,$3); }
   | NAME ASSIGN2 exp {$$ = newasgn(777,$1,$3); }
;

topList:
	| topList stmt EOI {
		ast_root=$2;
		printtree(ast_root,0);
		treefree($2);
	}
;

%%

C辅助代码

代码过长，请去项目中查看

测试结果

输入程序，以#号为结束标志

image-20211129114900388

生成的graphiz代码

0 [label = ";"]
0 -> 1 [label = "l"]
1 [label = "and"]
1 -> 2 [label = "l"]
2 [label = "int"]
2 -> 3 [label = "l"]
3 [label = "x"]
1 -> 4 [label = "r"]
4 [label = "skip"]
0 -> 5 [label = "r"]
5 [label = ";"]
5 -> 6 [label = "l"]
6 [label = "and"]
6 -> 7 [label = "l"]
7 [label = "<=="]
7 -> 8 [label = "l"]
8 [label = "x"]
7 -> 9 [label = "r"]
9 [label = "1"]
6 -> 10 [label = "r"]
10 [label = "skip"]
5 -> 11 [label = "r"]
11 [label = ";"]
11 -> 12 [label = "l"]
12 [label = "if"]
12 -> 13 [label = "l"]
13 [label = "cond"]
13 -> 14 [label = "l"]
14 [label = "<"]
14 -> 15 [label = "l"]
15 [label = "x"]
14 -> 16 [label = "r"]
16 [label = "1"]
12 -> 18 [label = "m"]
18 [label = "then"]
18 -> 19 [label = "l"]
19 [label = ":="]
19 -> 20 [label = "l"]
20 [label = "x"]
19 -> 21 [label = "r"]
21 [label = "2"]
12 -> 23 [label = "r"]
23 [label = "else"]
23 -> 24 [label = "l"]
24 [label = ":="]
24 -> 25 [label = "l"]
25 [label = "x"]
24 -> 26 [label = "r"]
26 [label = "3"]
11 -> 27 [label = "r"]
27 [label = ":="]
27 -> 28 [label = "l"]
28 [label = "x"]
27 -> 29 [label = "r"]
29 [label = "4"]

生成树

  1. 将输出保存到.dot文件下

    digraph ARG {
0 [label = ";"]
0 -> 1 [label = "l"]
1 [label = "and"]
1 -> 2 [label = "l"]
2 [label = "int"]
2 -> 3 [label = "l"]
...
}

  2. 在当前文件夹下使用命令行

  3. image-20211129115356371

  4. 输入如下命令

    dot -Tpdf tree.dot -o tree.pdf

  5. 即可生成有对应生成树的pdf

  6. image-20211129115533194

  7. 查看pdf

  8. image-20211129115553866

This is the end of today's blog : )

# flex # bison # graphiz # c