语法分析器 YACC实验报告

大学 学 院实 验 报 告 学号： 姓名： 专业： 班级： 第 周课程名称 编译原理课程设计实验课时实验项目基于YACC的语法分析器实验时间实验目的 1 学习基于YACC的语法分析器的构造方法。2 学习C-的语法结构。实验环境 Parser GeneratorVC+ 6.0实验内容（算法、程序、步骤和方法） 基于YACC构造词法分析器的方法1 YACC文件格式Lex文件分成三个部分，分别为definitions、rules以及auxiliary routines，中间用%分割开。Definitions包括要加入到生成的C程序的头部的代码，包括#include语句、#define语句及一些全局变量的定义。token也在Definitions部分定义，YACC规定，必须自己定义token，他将token定义为一系列从258开始的正整数，如在Definition部分加入了如下定义：%token NUMBER, 则在生成的C代码中：#define NUMBER 258。当然这个值也可以由用户定义。Definitions中同时还定义了YACC中的返回值类型，由于rules部分是由固定符号来代替一个Symbol的返回值，其默认类型为int，如果用户希望返回其他类型的值（如ParseTree树结点），则可以在Definition中定义Symbol的返回值。首先使用一个%union包含所有需要的返回值类型，定义%type 其中包含所有返回值为t的Symbol。Definitions中可以定义语法的结合性来消除二义性，包括两个符号%left表示左结合和%right表示右结合。rules部分定义所有语法，以及语法识别出后执行的操作。例如：declaration:var_declaration $ = $1; |fun_declaration $ = $1; ;%表示产生式左边，$n表示产生式右边第n个字符的返回值，这条规则表示var_declaration或fun_declaration识别出后，将其赋值给declaration。Auxiliary部分包括rules部分使用的一些辅助函数，同时，main函数也在其中定义。YACC中会自动调用yylex()获取token，默认yylex()返回int，代表识别出的token，如果文件结束返回0。因此一般会进行如下定义：static Type yylex(void) return getToken(); Type就是int，专门代表token值。Auxiliary部分还可以定义YACC的出错处理函数，yyerror(char *s)，其中s是YACC在遇到错误时产生的错误信息。YACC的入口函数为：yyparse()，调用这个函数即开始语法分析过程。2 数据结构我们需要再YACC中构造Parse Tree,必须定义树结点，观察C-的语法，我们可以将语法分为三类：Declaration : 包括函数与变量的声明。Statement : 包括各种语句，如循环语句，选择语句等。Expression : 包括各种表达式及各种变量、常量。我们也将节点类型分为Dec、Stmt、Exp。节点类型定义如下： typedef struct treeNode /儿子 struct treeNode* childMAXCHILDREN; /兄弟 struct treeNode* sibling; /结点在source中的行数 int lineno; /如果结点是函数或变量的话，记录其类型 Type type; /结点的大类型 NodeKind nodekind; /结点的小类型 union StmtKind stmt; ExpKind exp; DecKind dec; kind; /结点的值 union Type op; /如果是非叶结点，则应该有token类型 int value;/C Minus中只有一种数据类型int，如果是叶结点，一定是int char* name; /如果是ID类型，则有名字 attr;TreeNode;由于我们的最终目的是构造Parse Tree，因此YACC的返回类型应当为Symbol对应的子树的根结点。而type_specifer、addop、relop、mulop我们不希望为他们构造结点，而直接返回其对应值，因此在YACC中进行如下声明：%type program declaration_list declaration var_declaration fun_declaration params param_list param compound_stmt local_declarations statement_list statement expression_stmt selection_stmt iteration_stmt return_stmt expression var simple_expression additive_expression term factor call args arg_list%type type_specifier relop addop mulop将除type_specifier relop addop mulop外所有Symbol返回树结点，这四个Symbol直接返回其对应的Token。3 编译过程实现C-共有29条规则，在YACC不需消除左递归与左因子，因此只需定义29条rules即可，当一条规则识别出后，执行操作遵循以下规则：1.如果有NUM，则立刻用一个变量暂存，因为后面的识别会把TokenValue覆盖掉。如：type_specifier id LBRACKET NUM /*记录NUM*/ currentNum = atoi(tokenString); RBRACKET SEMICOLON2.如果有ID，与NUM同理，用立刻一个字符串暂存。3.如果产生式右边有多余一个的Symbol，则必须为$建立结点，并将右面的Symbol作为他的儿子，如果有ID、NUM、type_specfier，和关键字，则不需建立结点，直接赋值给结点中的变量或忽略（结点类型自动说明）。如：iteration_stmt:WHILE LPARENTHESIS expression RPARENTHESIS statement$ = newStmtNode(WhileK);$ - child0 = $3;$ - child1 = $5;4如果右边仅有一个Symbol，如果为Token，则返回Token值，如果为Nonterminal，直接$ = $1。如：statement:expression_stmt $ = $1; 5.如果有左递归，则统一用下面代码处理，注意，左递归的结点存储在sibling中而不是child中。tatement_list:statement_list statementTreeNode* t = $1;if( t != NULL )while(t-sibling != NULL)t = t-sibling;t-sibling = $2;$ = $1;else$ = $2;|$ = NULL; YACC是由yylex()提供Token，因此需要编写getToken()函数，使用lex或手工实现均可，但需注意，其返回的Token值必须是YACC中定义的int,也就是说，不能在别处定义TokenType。 在main函数中调用yyparse()即可进行编译。 数据记录和计算 实验源程序如下：/* a program to perform selection sort on a 10 element array. */int x10;int minloc( int a, int low, int high )int i; int x; int k;k = low;x = alow;i = low + 1;while ( i high )if ( ai x )x = ai;k = i; return k;结 论（结 果） 生成的Parse Tree如下所示：|_Arr name:x, type:INT |_Number type:INT, value:10|_FunDec name:minloc, return:INT |_ArrParam name:a, type:INT |_ValParam name:low, type:INT |_ValParam name:high, type:INT |_Comp |_Var name:i, type:INT |_Var name:x, type:INT |_Var name:k, type:INT |_Assign |_VarId name:k |_VarId name:low |_Assign |_VarId name:x |_ArrId name:low |_VarId name:low |_Assign |_VarId name:i |_Expression type:+ |_VarId name:low |_Number type:INT, value:1 |_While |_Expression type: |_VarId name:i |_VarId name:high |_Comp |_Return |_VarId name:k 可见ParseTree中所需结点都被生成，并且ID、NUM、type_specifier都被记录在结点中。小 结 1. 通过本实验，我熟悉了C-的语法规则，学习了ParseTree的构造方法。2. 学习了通过