语法分析器yacc试验报告

实验报告

学号： 课程名称 姓名：

专业： __________________ 班级： ________________ 第

周

?编译原理课程设计 实验课时 实验项目 基于YACC勺语法分析器 实验时间 1 . 实验目的 学习基于YACC勺语法分析器的构造方法。 学习C-的语法结构。 ?Parser Gen erator 2. 实验环境 VC++ 基于YACC勾造词法分析器的方法 1 YACC文件格式 Lex文件分成三个部分，分别为 definitions 、rules以及 auxiliary routines ，中间用 ％分割开。 Defin itio ns 包括要加入到生成的C程序的头部的代码，包括 #include 语句、#define语句及一些全局变量的定义。token也在 Definitions 部分定义，YACC®定，必须自己定义token，他将token 定义实验内容 （算法、程 法） 为一系列从258开始的正整数，如在Definition 部分加入了 如下定义：%token NUMBER则］在生成的C代码中：#define NUMBE 序、步骤和 方258。当然这个值也可以由用户定义。 Definitions 中同时还定义了 YACC中的返回值类型，由于 rules部分是由固疋符号来代替一个 Symbol的返回值，其默认类 型为int，如果用户布望返回其他类型的值（如ParseTree树结点）， 则可以在Definition 中定义Symbol的返回值。首先使用一 （%union{…}包含所有需要的返回值类型，疋义 ％type {…}其 中包含所有返回值为t的Symbol。 Defini tio ns 中可以定义语法的结合性来消除二义性， 包括两 个符号%left表示左结合和%right表示右结合。 rules部分定义所有语法，以及语法识别出后执行的操作。 例如： declarati on : | var_declarati on fun _declaratio n { $$ = $1; } { $$ = $1; } J %表示产生式左边，$n表示产生式右边第n个字符的返回值， 这条规则表示var_declaration 或fun_declaration 其赋值给declaration 。 识别出后，将 Auxiliary 部分包括rules部分使用的一些辅助函数，同时， main函数也在其中定义。YACC中会自动调用yylex()获取token， 默认yylex()返回int，代表识别出的token，如果文件结束返回0。 因此一般会进行如下定义： static Type yylex(void) { return getToke n(); } Type就是int，专门代表token 值。 Auxiliary 部分还可以定义YACC勺出错处理函数， yyerror(char *s)，其中s是YAC(在遇到错误时产生的错误信息。 YACC勺入口函数为：yyparse()，调用这个函数即开始语法分 析过程。 2数据结构 我们需要再YACC中构造Parse Tree,必须定义树结点，观察 C-的语法，我们可以将语法分为三类： Declaration : 包括函数与变量的声明。 Stateme nt :包括各种语句，如循环语句，选择语句等。 Expressi on : 包括各种表达式及各种变量、常量。 我们也将节点类型分为Dec、Stmt、Exp。节点类型定义如下： typedef struct treeNode { 果有NUM则立刻用一个变量暂存，因为后面的识别会把 Toke nV alue 覆盖掉。 女口： type_specifier id LBRACKET NUM { /* atoi(toke nStr in g); } RBRACKET SEMICOLON 记录 NUM*/ currentNum = 2. 如果有ID，与NU同理，用立刻一个字符串暂存。 3. 如果产生式右边有多余一个的Symbol,则必须为$$建立结 点，并将右面的Symbo作为他的儿子，如果有ID、NUM type_specfier ，和关键字，则不需建立结点，直接赋值给结点中 的变量或忽略(结点类型自动说明)。 如： iteration_stmt RPARENTHESIS stateme nt { $$ = newStmtNode(WhileK); $$ -> child[0] = $3; $$ -> child[1] = $5; } : WHILE LPARENTHESIS expression 4.如果右边仅有一个 Symbol,如果为Token,则返回Token 值，如果为 Nonterminal，直接 $$ = $1 。 如： stateme nt : expressi on _stmt { $$ = $1; } 5.如果有左递归，则统一用下面代码处理，注意，左递归的结 点存储在sibling 中而不是child中。

tateme nt_list

: {

stateme nt_list stateme nt

TreeNode* t = $1; if( t != NULL ) {

while(t->sibling != NULL)

t = t->sibli ng;

t->sibli ng = $2; $$ = $1; } else

$$ = $2;

} |

{$$ = NULL;}

YACC是由yylex()提供Token,因此需要编写getToken()函数,

使用lex或手工实现均可，但需注意，其返回的 Token值必须是

YACC中定义的int,也就是说，不能在别处定义 TokenTypeo

在main函数中调用yyparse()即可进行编译。

实验源程序如下:

/* a program to perform select ion sort on a 10 eleme nt array. */ int x[10];

int mini oc( int a[], int low, int high ) {

int i; int x; int k;

数据记录 k = low; 和计算

x = a[low];

i = low + 1; while ( i < high ) {

if ( a[i] < x ) {

x = a[i]; k = i; }

}

return k; } 生成的Parse Tree如下所示： |__Arr n ame:x, type:INT |__Number type:INT, value:10 |__Fun Dec n ame: mini oc, retur n:INT |__ArrParam n ame:a, type:INT |__ValParam n ame:low, type:INT |__ValParam n ame:high, type:INT |__Comp |__Var n ame:i, type:INT |__Var n ame:x, type:INT |__Var n ame:k, type:INT |__Assign 结论 （结果） |__VarId n ame:k |__VarId n ame:low |__Assign |__VarId n ame:x |__ArrId n ame:low |__VarId n ame:low |__Assign |__VarId n ame:i |__Expressi on type:+ |__VarId n ame:low |__Number type:INT, value:1 |__While |__Expressi on type:< |__VarId n ame:i 都被记录在结点中。 1. 通过本实验，我熟悉了 C-的语法规则，学习了 ParseTree的构造方法。 2. 学习了通过YACC勾造语法分析器的方法，了解了 declarations 、rules、auxiliary YACC勺三个部分： Scanner token 定 的声明、实现以及如何与 yylex()。 进行继承。事实上 YACC与 Scanner的联系之处便在于统一的 义(疋义为一系列int )，以及一个获取函数 小 结 3. 学习了 Parse的打印方法，模仿 Windows中的目录树，使用符 达到了不错的效果。 号|和_, ? 指导老师 评 议 成绩评定： 指导教师签名：