编译原理课程设计实验报告川大张兵Word格式.docx
《编译原理课程设计实验报告川大张兵Word格式.docx》由会员分享,可在线阅读,更多相关《编译原理课程设计实验报告川大张兵Word格式.docx(67页珍藏版)》请在冰点文库上搜索。
语法分析采用递归下降方法的程序结构:
本程序采用面向对象的思想编写,使用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*params();
//函数参数
treenode*declaration();
treenode*declaration_list();
//多个函数列表
treenode*parse();
//语法分析
2.4.2节点定义和类型
节点定义:
structtreenode//树节点结构体
treenode*child;
//子节点
treenode*brother;
//兄弟节点
//所在行
Nodekindnodekind;
//节点类型
charnodestring[1100];
//节点类型所代表的字符串,用于语法树打印
节点类型:
//19种节点类型,分别表示int、id、void、数值、变量声明、数组声明、函数声明、
//函数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、运算、
//数组元素、函数调用、函数调用参数列表、未知节点
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-文法使用递归向下分析方法分析程序的过程,在代码部分只列出了函数名,具体函数见源代码。
待分析文法
分析函数
treeNode*parse()
分析
说明C-语言编写的程序由一组声名序列组成。
parse(void)函数使用递归向下分析方法直接调用declaration_list()函数,并返回树节点
代码
treenode*parse()
treenode*declaration_list()
declaration_list(void)函数使用递归向下分析方法直接调用declaration()函数,并返回树节点
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*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*param_list(treenode*k)
说明参数列表由param序列组成,并由逗号隔开。
param_list(TreeNode*k)函数使用递归向下分析方法直接调用param(TreeNode*k)函数,并返回树节点
treenode*param(treenode*k)
说明参数由int或void、标示符组成,最后可能有中括号表示数组。
param(TreeNode*k)函数根据探测先行Token是int还是void而新建IntK或VoidK节点作为其第一个子节点,然后新建IdK节点作为其第二个子节点,最后探测Follow集合,是否是中括号,而确定是否再新建第三个子节点表示数组类型
treenode*compound_stmt()
说明复合语句由用花括号围起来的一组声明和语句组成。
compound_stmt(void)函数使用递归向下分析方法直接调用local_declaration()函数和statement_list()函数,并根据返回的树节点作为其第一个子节点和第二个子节点
treenode*local_declaration()
说明局部变量声明要么是空,要么由许多变量声明序列组成。
local_declaration(void)函数通过判断先行的Token是否是int或void便可知道局部变量声明是否为空,如果不为空,则新建一个变量定义节点(Var_DeclK)
treenode*statement_list()
说明由语句列表由0到多个statement组成。
statement_list(void)函数通过判断先行Token类型是否为statement的First集合确定后面是否是一个statement,如果是,则使用递归向下分析方法直接调用statement()函数
treenode*statement()
说明statement由表达式或复合语句或if语句或while语句或return语句构成。
statement(void)函数通过判断先行Token类型确定到底是哪一种类型。
如果是IF则是if语句类型,如果是WHILE,则是while语句类型,如果是RETURN,则是return语句类型,如果是左大括号,则是复合语句类型,如果是ID、SEMI、LPAREN、NUM,则是表达式语句类型
treenode*expression_stmt()
说明表达式语句有一个可选的且后面跟着分号的表达式。
expression_stmt(void)函数通过判断先行Token类型是否为分号,如果不是则直接调用函数expression()
treenode*selection_stmt()
selection_stmt(void)函数直接调用expression()函数和statement()函数分别得到其第一个和第二个子节点,然后通过判断先行Token类型是否为ELSE,如果是则直接调用statement()函数得到其第三个子节点
treenode*iteration_stmt()
iteration_stmt(void)函数直接调用expression()函数和statement()函数分别得到其第一个和第二个子节点
treenode*return_stmt()
return_stmt(void)函数通过判断先行Token类型是否为分号,如果不是则直接调用函数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*varr()
varr(void)函数先新建一个IdK节点,再通过判断先行Token类型是否为左中括号,如果是则新建一个数组节点Arry_ElemK,将IdK作为Arry_ElemK节点的第一个子节点,再直接调用函数expression()得到Arry_ElemK的第二个子节点,最后返回的节点时Arry_ElemK;
如果先行Token类型不是左中括号,则将之前的IdK返回
treenode*simple_expression(treenode*k)
simple_expression(TreeNode*k)函数先调用additive_expression(TreeNode*k)函数返回一个节点,然后再一直判断后面的Token是否为<
=、<
=、==、!
=,如果是则新建OpK节点,然后令之前的节点为其第一个子节点,然后继续调用additive_expression(TreeNode*k)函数返回一个节点,作为OpK节点的第二个节点
treenode*additive_expression(treenode*k)
additive_expression(TreeNode*k)函数先调用term(TreeNode*k)函数返回一个节点,然后再一直判断后面的Token