大学 学 院
实 验 报 告
学号： 姓名： 专业： 班级： 第 周
课程名称
编译原理课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
实验课时
实验项目
基于YACC的语法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
器
实验时间
实验目的
1． 学习基于YACC的语法分析器的构造
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。
2． 学习C-的语法结构。
实验环境
Parser Generator
VC++ 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
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示左结合和%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* child[MAXCHILDREN];
//兄弟
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 SEMICOLON
2.如果有ID，与NUM同理，用立刻一个字符串暂存。
3.如果产生式右边有多余一个的Symbol，则必须为$$建立结点，并将右面的Symbol作为他的儿子，如果有ID、NUM、type_specfier，和关键字，则不需建立结点，直接赋值给结点中的变量或忽略（结点类型自动说明）。
如：
iteration_stmt : WHILE LPARENTHESIS expression RPARENTHESIS statement
{
$$ = newStmtNode(WhileK);
$$ -> child[0] = $3;
$$ -> child[1] = $5;
}
4．如果右边仅有一个Symbol，如果为Token，则返回Token值，如果为Nonterminal，直接$$ = $1。
如：
statement : expression_stmt { $$ = $1; }
5.如果有左递归，则统一用下面代码处理，注意，左递归的结点存储在sibling中而不是child中。
tatement_list : statement_list statement
{
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,也就是说，不能在别处定义TokenType。
在main函数中调用yyparse()即可进行编译。
数据记录
和计算
实验源程序如下：
/* a program to perform selection sort on a 10
element array. */
int x[10];
int minloc( 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 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. 学习了通过YACC构造语法分析器的方法，了解了YACC的三个部分：declarations、rules、auxiliary 的声明、实现以及如何与Scanner进行继承。事实上YACC与Scanner的联系之处便在于统一的token定义（定义为一系列int），以及一个获取函数yylex()。
3. 学习了Parse的打印方法，模仿Windows中的目录树，使用符号|和_，达到了不错的效果。
指导老师评 议
成绩评定： 指导教师签名：
浙公网安备 33021202002483