语法分析器yacc试验报告

大学学院实验报告学号：姓名：专业：班级：第周课程名称?编译原理课程设计实验课时实验项目基于YACC勺语法解析器实验时间实验目的实验环境

1.学习基于YACC勺语法解析器的构造方法。2.学习C-的语法构造。?ParserGeneratorVC++基于YACC勾造词法解析器的方法1YACC文件格式Lex文件分成三个部分，分别为definitions、rules以及auxiliaryroutines，中间用％切割开。实验内容（算法、程序、步骤和方法）

Definitions包括要加入到生成的C程序的头部的代码，包括#include语句、#define语句及一些全局变量的定义。token也在Definitions部分定义，YACC?定，必定自己定义token，他将token定义为一系列从258开始的正整数，如在Definition部分加入了以下定义：%tokenNUMBER则］在生成的C代码中：#defineNUMBE。自然这个值也能够由用户定义。Definitions中同时还定义了YACC中的返回值种类，由于rules部分是由固疋符号来代替一个Symbol的返回值，其默认种类为int，若是用户布望返回其他种类的值（如ParseTree树结点），则能够在Definition中定义Symbol的返回值。第一使用一（%union{}包括所有需要的返回值种类，疋义％type<t>{}其中包括所有返回值为t的Symbol。Definitions中能够定义语法的结合性来除掉二义性，包括两个符号%left表示左结合和%right表示右结合。rules部分定义所有语法，以及语法鉴别出后执行的操作。比方：declaration:var_declaration{$$=$1;}|fun_declaration{$$=$1;}J表示产生式左边，$n表示产生式右边第n个字符的返回值，这条规则表示var_declaration或fun_declaration鉴别出后，将其赋值给declaration。Auxiliary部分包括rules部分使用的一些辅助函数，同时，main函数也在其中定义。YACC中会自动调用yylex()获取token，默认yylex()返回int，代表鉴别出的token，若是文件结束返回0。因此一般会进行以下定义：staticTypeyylex(void){returngetToken();}Type就是int，特地代表token值。Auxiliary部分还可以够定义YACC勺出错办理函数，yyerror(char*s)，其中s是YAC(在遇到错误时产生的错误信息。YACC勺入口函数为：yyparse()，调用这个函数即开始语法解析过程。数据构造我们需要再YACC中构造ParseTree,必定定义树结点，观察C-的语法，我们能够将语法分为三类：Declaration:包括函数与变量的声明。Statement:包括各种语句，如循环语句，选择语句等。Expression:包括各种表达式及各种变量、常量。我们也将节点种类分为Dec、Stmt、Exp。节点种类定义以下：typedefstructtreeNode{果有NUM则立刻用一个变量暂存，由于后边的鉴别会把TokenValue覆盖掉。女口：

type_specifieridLBRACKETNUM{/*

记录

NUM*/currentNum=atoi(tokenString);}RBRACKETSEMICOLON若是有ID，与NU同理，用立刻一个字符串暂存。3.若是产生式右边有节余一个的右边的Symbo作为他的儿子，若是有字，则不需建立结点，直接赋值给结点中明)。如：

Symbol,则必定为$$建立结点，并将ID、NUMtype_specfier，和要点的变量或忽略(结点种类自动说iteration_stmt:WHILELPARENTHESISexpressionRPARENTHESISstatement{$$=newStmtNode(WhileK);$$->child[0]=$3;$$->child[1]=$5;}4.若是右边仅有一个Symbol,若是为Token,则返回Token值，若是为Nonterminal，直接$$=$1。如：statement:expression_stmt{$$=$1;}5.若是有左递归，则一致用下面代码办理，注意，左递归的结点储藏在sibling中而不是child中。tatement_list:statement_liststatement{TreeNode*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,也就是说，不能够在别处定义TokenTypeo在main函数中调用yyparse()即可进行编译。实验源程序以下:数据记录和计算

/*aprogramtoperformselectionsortona10elementarray.*/intx[10];intminioc(inta[],intlow,inthigh){inti;intx;intk;k=low;x=a[low];i=low+1;while(i<high){if(a[i]<x){x=a[i];k=i;}}returnk;}生成的ParseTree以下所示：|__Arrname:x,type:INT|__Numbertype:INT,value:10|__FunDecname:minioc,return:INT|__ArrParamname:a,type:INT|__ValParamname:low,type:INT|__ValParamname:high,type:INT|__Comp结论（结果）

|__Varname:i,type:INT|__Varname:x,type:INT|__Varname:k,type:INT|__Assign|__VarIdname:k|__VarIdname:low|__Assign|__VarIdname:x|__ArrIdname:low|__VarIdname:low|__Assign|__VarIdname:i|__Expressiontype:+|__VarIdname:low|__Numbertype:INT,value:1|__While|__Expressiontype:<|__VarIdname:i都被记录在结点中。经过本实验，我熟悉了C-的语法规则，学习了ParseTree的构造方法。2.学习了经过

YACC

勾造语法解析器的方法，认识了

YACC

勺三个部分：declarations

、rules

、auxiliary

的声明、实现以及如