编译原理课程设计实验报告(川大张兵).doc
《编译原理课程设计实验报告(川大张兵).doc》由会员分享，可在线阅读，更多相关《编译原理课程设计实验报告(川大张兵).doc（68页珍藏版）》请在冰点文库上搜索。
编译原理课程设计 指导老师：
张兵 学生：
刘佳玉
编译原理课程设计报告
课题名称：
C-词法扫描器及语法分析器实现
提交文档学生姓名：
刘佳玉
提交文档学生学号：
2012141461134
同组成员名单：
无
指导教师姓名：
张兵
指导教师评阅成绩：
指导教师评阅意见：
.
.
提交报告时间：
2015年6月10日
目录
编译原理课程设计报告 1
1、课程设计目标 2
2、分析与设计 2
2.1程序结构 2
2.2程序流程 3
2.3词法分析 3
2.3.1代码结构分析 3
2.3.2token定义和类型 4
2.3.3DNF分析 4
2.4语法分析 5
2.4.1代码结构分析 5
2.4.2节点定义和类型 5
2.4.3递归下降语法分析 6
3、测试结果 11
3.1流程 11
3.2出错情况 15
4、总结 15
4.1收获 15
4.2特色 15
4.3不足 16
5、程序代码实现 16
5.1递归下降源代码 16
5.2C-文法 20
1、课程设计目标
学生在学习《编译原理》课程过程中，结合各章节的构造编译程序的基本理论，要求用C或C++语言描述及上机调试，实现一个C-Minus小编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。
要求：
实现scanner和parser功能
2、分析与设计
2.1程序结构
语法分析采用递归下降方法的程序结构：
本程序采用面向对象的思想编写，使用C语言实现，程序分为两部分：
词法分析（scan）和语法分析（parse），分别将两个处理阶段写在两个函数中，分别是scan（）和parse（），两个函数分别完成词法分析和语法分析的任务。
scan（）函数主要的工作是检查注释是否合法、词法分析获取token。
parse（）函数的主要工作是根据scan（）词法分析之后的token进行语法分析，生成语法树，最后并输出语法树。
2.2程序流程
递归下降方法的程序流程图
2.3词法分析
2.3.1代码结构分析
词法分析阶段的代码写在一个函数中——scan（）。
main函数读取程序数据，将其存储在一个二维数组中，调用函数zhushierror（），确定程序是否存在注释错误，注释的错误主要是注释的符号不匹配。
如果不存在注释错误，则调用scan（）函数进行词法分析，否则报错。
词法分析是对输入的数据一个字符一个字符的分析，将所分析出来的token存储在一个vector数组中，方便后面语法分析时调用。
词法分析没有什么错误限制，基本不会报错。
所以在分析的同时，就会将所分析出的token输出
2.3.2token定义和类型
token结构体定义如下：
structtoken//token结构体
{
Tokentypetokentype;//token类型
chartokenstring[1100];//token串
intlineno;//token行号
};
token类型：
//定义的Token的类型（29种），分别对应于else、if、int、return、void、while、
//+、-、*、/、<、<=、>、>=、==、
/////!
=、=、;、,、（、）、[、]、{、}、num、id、错误、结束
typedefenum
{
elsee=1,iff,intt,returnn,voidd,whilee,xiaoyudengyu,dayudengyu,dengyudengyu,budengyu,//10
jia,jian,cheng,chu,dayu,xiaoyu,dengyu,fenhao,douhao,zuokuohao,youkuohao,zuozhongkuohao,//22
youzhongkuohao,zuohuakuohao,youhuakuohao,num,id,error,end//29
}Tokentype;
2.3.3DNF分析
词法分析的DFA描述：
词法分析的DFA如下所示，一共分为5个状态：
START、INNUM、INID、INDBSYM、DONE。
状态START表示开始状态，状态INNUM表示数字类型（NUM）Token的状态，状态INID表示字符串类型Token的状态（如关键字和一般的标示符），状态INDBSYM表示双目运算符型Token的状态（如<=、>=、!
=、==），状态DONE表示接收状态。
2.4语法分析
2.4.1代码结构分析
语法分析阶段的代码中，每一条文法都有相对应的函数，通过函数之间的递归调用来达到语法分析的目的。
语法分析的过程主要是：
在语法分析之前进行词法分析，然后通过递归向下分析法根据C-语言的文法进行语法分析，并生成语法树，最后打印语法树。
下面是语法分析所用到的全局变量和函数的声明：
tokencurrenttoken;//当前token
tokenlasttoken;//上一个token
inttokenxb=0;//token下标
intblank=0;//先行空格
voidgettoken（）;//得到token
voidparseerror（）;//输出错误
voidmatch（Tokentypett）;//匹配
treenode*compound_stmt（）;//函数声明
voidprintspace（intn）;//打印空格
voidprinttree（treenode*t）;//打印语法分析树
treenode*newnode（Nodekindkind）;//创建新节点
treenode*args（）;
treenode*call（treenode*k）;//函数调用
treenode*factor（treenode*k）;
treenode*term（treenode*k）;
treenode*additive_expression（treenode*k）;//加成的表达式
treenode*simple_expression（treenode*k）;//简单表达式
treenode*varr（）;
treenode*expression（）;
treenode*expression_stmt（）;//表达式声明
treenode*return_stmt（）;//返回式声明
treenode*iteration_stmt（）;//while声明
treenode*selection_stmt（）;//if声明
treenode*statement（）;//复合语句后者种类
treenode*statement_list（）;//复合语句体后者
treenode*local_declaration（）;//复合语句体前者
treenode*param（treenode*k）;//函参
treenode*param_list（treenode*k）;//函参列表
treenode*compound_stmt（）;//函数内容，复合语句
treenode*params（）;//函数参数
treenode*declaration（）;//函数声明
treenode*declaration_list（）;//多个函数列表
treenode*parse（）;//语法分析
2.4.2节点定义和类型
节点定义：
structtreenode//树节点结构体
{
treenode*child;//子节点
treenode*brother;//兄弟节点
intlineno;//所在行
Nodekindnodekind;//节点类型
charnodestring[1100];//节点类型所代表的字符串，用于语法树打印
};
节点类型：
//19种节点类型，分别表示int、id、void、数值、变量声明、数组声明、函数声明、
//函数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、运算、
//数组元素、函数调用、函数调用参数列表、未知节点
typedefenum
{
ints,ids,voids,nums,var,shuzu,hanshu,hancanlist,hancan,fuheyuju,ifs,whiles,returns,
fuzhi,yunsuan,shuzuyuansu,hanshudiaoyong,hanshudiaoyongcanlist,unknown
}Nodekind;//节点种类
2.4.3递归下降语法分析
2.4.3.1C-语法
program→declaration-list
declaration_list→declaration{declaration}
declaration→var-declaration|fun-declaration
var_declaration→type-specifierID;|type-specifierID[NUM];
type-specifier→int|void
fun-declatation→type-specifierID（params）|compound-stmt
params→param_list|void
param_list→param{,param}
param→type-specifierID{[]}
compound-stmt→{local-declarationstatement-list}
local-declarations→empty{var-declaration}
statement-list→{statement}
statement→expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt
expression-stmt→[expression];
selection-stmt→if（expression）statement[elsestatement]
iteration-stmt→while（expression）statement
return-stmt→return[expression];
expression→var=expression|simple-expression
relop→<=|<|>|>=|==|!
=
var→ID|ID[expression]
simple-expression－>additive-expression{relopadditive-expression}
additive-expression→term{addopterm}
addop→+|-
term→factor{mulopfactor}
mulop→*|/
factor→（expression）|var|call|NUM
call→ID（args）
args→arg-list|empty
arg-list→expression{,expression}
2.4.3.2递归下降语法分析过程
以下表格列出了根据上文中的C-文法使用递归向下分析方法分析程序的过程，在代码部分只列出了函数名，具体函数见源代码。
待分析文法
program→declaration-list
分析函数
treeNode*parse（）
分析
说明C-语言编写的程序由一组声名序列组成。
parse（void）函数使用递归向下分析方法直接调用declaration_list（）函数，并返回树节点
代码
treenode*parse（）
待分析文法
declaration_list→declaration{declaration}
分析函数
treenode*declaration_list（）
分析
说明C-语言编写的程序由一组声名序列组成。
declaration_list（void）函数使用递归向下分析方法直接调用declaration（）函数，并返回树节点
代码
treenode*declaration_list（）
待分析文法
declaration→var-declaration|fun-declaration
var_declaration→type-specifierID;|type-specifierID[NUM];
fun-declatation→type-specifierID（params）|compound-stmt
type-specifier→int|void
分析函数
treenode*declaration（）
分析
说明C-语言的声明分为变量声明和函数声明。
declaration（void）函数并不是直接调用var-declaration或fun-declaration文法所对应的函数，令其返回节点，实际上程序并没有为var-declaration和fun-declaration文法定义函数，而是在declaration（void）函数中，通过求First集合的方式先确定是变量定义还是函数定义，然后分别根据探测的结果生成变量声明节点（Var_DeclK）或函数声明节点（FunK）。
所以var-declaration和fun-declaration文法在declaration→var-declaration|fun-declaration文法中就都已经分析了
代码
treenode*declaration（）
待分析文法
params→param_list|void
分析函数
treenode*params（）
分析
说明函数参数列表要么是void，要么是多个参数组成。
params（void）函数先判断第一个是void还是int，如果是int说明是由param_list组成，则调用param_list（TreeNode*k）函数递归向下分析；如果是void说明可能是void型的参数，也可能参数就是void，所以再求其Follow集合，如果集合求出来是右括号，则说明参数就是void，于是新建一个VoidK节点就行；如果集合求出来不是右括号则说明是void型的参数，然后再调用param_list（TreeNode*k）函数递归向下分析，并将已经取出VoidK节点传递给param_list（TreeNode*k）函数
代码
treenode*params（）
待分析文法
param_list→param{,param}
分析函数
treenode*param_list（treenode*k）
分析
说明参数列表由param序列组成，并由逗号隔开。
param_list（TreeNode*k）函数使用递归向下分析方法直接调用param（TreeNode*k）函数，并返回树节点
代码
treenode*param_list（treenode*k）
待分析文法
param→type-specifierID{[]}
分析函数
treenode*param（treenode*k）
分析
说明参数由int或void、标示符组成，最后可能有中括号表示数组。
param（TreeNode*k）函数根据探测先行Token是int还是void而新建IntK或VoidK节点作为其第一个子节点，然后新建IdK节点作为其第二个子节点，最后探测Follow集合，是否是中括号，而确定是否再新建第三个子节点表示数组类型
代码
treenode*param（treenode*k）
待分析文法
compound-stmt→{local-declarationstatement-list}
分析函数
treenode*compound_stmt（）
分析
说明复合语句由用花括号围起来的一组声明和语句组成。
compound_stmt（void）函数使用递归向下分析方法直接调用local_declaration（）函数和statement_list（）函数，并根据返回的树节点作为其第一个子节点和第二个子节点
代码
treenode*compound_stmt（）
待分析文法
local-declarations→empty{var-declaration}
分析函数
treenode*local_declaration（）
分析
说明局部变量声明要么是空，要么由许多变量声明序列组成。
local_declaration（void）函数通过判断先行的Token是否是int或void便可知道局部变量声明是否为空，如果不为空，则新建一个变量定义节点（Var_DeclK）
代码
treenode*local_declaration（）
待分析文法
statement-list→{statement}
分析函数
treenode*statement_list（）
分析
说明由语句列表由0到多个statement组成。
statement_list（void）函数通过判断先行Token类型是否为statement的First集合确定后面是否是一个statement，如果是，则使用递归向下分析方法直接调用statement（）函数
代码
treenode*statement_list（）
待分析文法
statement→expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt
分析函数
treenode*statement（）
分析
说明statement由表达式或复合语句或if语句或while语句或return语句构成。
statement（void）函数通过判断先行Token类型确定到底是哪一种类型。
如果是IF则是if语句类型，如果是WHILE，则是while语句类型，如果是RETURN，则是return语句类型，如果是左大括号，则是复合语句类型，如果是ID、SEMI、LPAREN、NUM，则是表达式语句类型
代码
treenode*statement（）
待分析文法
expression-stmt→[expression];
分析函数
treenode*expression_stmt（）
分析
说明表达式语句有一个可选的且后面跟着分号的表达式。
expression_stmt（void）函数通过判断先行Token类型是否为分号，如果不是则直接调用函数expression（）
代码
treenode*expression_stmt（）
待分析文法
selection-stmt→if（expression）statement[elsestatement]
分析函数
treenode*selection_stmt（）
分析
selection_stmt（void）函数直接调用expression（）函数和statement（）函数分别得到其第一个和第二个子节点，然后通过判断先行Token类型是否为ELSE，如果是则直接调用statement（）函数得到其第三个子节点
代码
treenode*selection_stmt（）
待分析文法
iteration-stmt→while（expression）statement
分析函数
treenode*iteration_stmt（）
分析
iteration_stmt（void）函数直接调用expression（）函数和statement（）函数分别得到其第一个和第二个子节点
代码
treenode*iteration_stmt（）
待分析文法
return-stmt→return[expression];
分析函数
treenode*return_stmt（）
分析
return_stmt（void）函数通过判断先行Token类型是否为分号，如果不是则直接调用函数expression（）得到其子节点
代码
treenode*return_stmt（）
待分析文法
expression→var=expression|simple-expression
分析函数
treenode*expression（）
分析
expression（void）函数通过判断先行Token类型是否为ID，如果不是说明只能是simple_expression情况，则调用simple_expression（TreeNode*k）函数递归向下分析；如果是ID说明可能是赋值语句，或simple_expression中的var和call类型的情况，所以再求其Follow集合，如果集合求出来是赋值类型的Token，则说明是赋值语句，于是新建一个AssignK节点就行；如果集合求出来不是赋值类型的Token则说明是simple_expression中的var和call类型的情况，然后再调用simple_expression（TreeNode*k）函数递归向下分析，并将已经取出IdK节点传递给simple_expression（TreeNode*k）函数
代码
treenode*expression（）
待分析文法
var→ID|ID[expression]
分析函数
treenode*varr（）
分析
varr（void）函数先新建一个IdK节点，再通过判断先行Token类型是否为左中括号，如果是则新建一个数组节点Arry_ElemK，将IdK作为Arry_ElemK节点的第一个子节点，再直接调用函数expression（）得到Arry_ElemK的第二个子节点，最后返回的节点时Arry_ElemK；如果先行Token类型不是左中括号，则将之前的IdK返回
代码
treenode*varr（）
待分析文法
simple-expression－>additive-expression{relopaddit
升级会员 