编译原理课程设计说明书词法分析语法分析语义分析.docx
- 文档编号:12344932
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:45
- 大小:480.45KB
编译原理课程设计说明书词法分析语法分析语义分析.docx
《编译原理课程设计说明书词法分析语法分析语义分析.docx》由会员分享,可在线阅读,更多相关《编译原理课程设计说明书词法分析语法分析语义分析.docx(45页珍藏版)》请在冰点文库上搜索。
编译原理课程设计说明书词法分析语法分析语义分析
编译原理课程设计说明书
题目:
编译器原型设计与开发
院(系):
计算机科学与工程学院
专业:
计算机科学与技术
1引言
编译程序是现代计算机系统的基本组成部分之一,而且多数计算机系统都配有不止一个高级语言的编译程序,对有些高级语言甚至配置了几个不同性能的编译程序。
从功能上看,一个编译程序就是一个语言翻译程序。
语言翻译程序把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价程序。
一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节,使程序员和程序设计专家独立于机器,这对于当今机器的数量和种类持续不断地增长的年代尤为重要。
编译程序完成从源程序到目标程序的翻译工作,是一个复杂的整体的过程。
将编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。
1.1设计概述
编译原理程序结构框图
词法分析词法分析是编译过程的第一个阶段。
这个阶段的任务是从左到右有一个字符一个字符地读入源程序,对构成源程序的字符流进行扫描和分解,从而识别出一个个单词(也称单词符号或符号)。
这里所谓的单词是指逻辑上紧密相连的一组字符,这些字符基友具体含义。
比如标识符是由字母字符开头,后跟字母、数字字符的字符序列组成的一种单词。
保留字(关键字或基本字)是一种单词,此外还有算符、界符等。
语法分析语法分析是编译过程的第二个阶段。
语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语,如“程序”、“语句”、“表达式”等。
一般这种语法短语,也称语法单位,可表示成语法树。
语法分析所依据的是语言的语法规则,即描述程序结构的规则。
通过语法分析确定整个输入串是否构成一个语法上正确的程序。
语义分析语义分析是审查源程序有无语义错误,为代码生成阶段收集类型信息。
比如语义分析的一个工作是进行类型审查,审查每个算符是否具有语言规范允许的运算对象,当不符合语言规范时,编译程序应报告错误。
中间代码生成在进行了上述的语法分析和语义分析阶段的工作之后,有的编译程序将源代码变成一种内部表示形式,这种内部表示形式叫做中间语言或中间代码。
所谓“中间代码”是一种结构简单、含义明确的记号系统,这种记号系统可以设计为多种多样的形式,重要的设计原则为两点:
一是容易生成;二是容易将它翻译成目标代码。
很多编译程序采用了一种近似“三地址指令”的“四元式”的中间代码,这种四元式的形式为:
(运算符,运算对象1,运算对象2,结果)。
1.2设计目标
鉴于我们需要完成编译器的词法分析、语法分析、语义分析、中间代码生成的设计开发,本次课程设计主要完成以下任务:
词法分析:
1.消除白空格
2.消除注释
3.词法分析
语法分析:
4.递归下降手工编码
5.first集合的计算
6.follow集合的自动计算
7.selection表自动生成
8.递归下降自动生成
9.LL
(1)分析手工编码
10.LL
(1)自动生成
11.LR
(1)分析手工编码
12.左递归消除
语义分析以及中间代码生成:
13.中缀式转后缀式递归下降编码
14.中缀式转后缀式LL
(1)编码
15.中缀式转后缀式LR1)编码
16.表达式求值LL
(1)
17.表达式求值LR
(1)
18.四元式
1.3小组分工
2开发过程
2.1词法分析
2.1.1消除白空格以及注释
这个模块实现的功能主要是对代码中多余的白空格以及注释进行消除。
在文本中输入一段代码,其中可以有多余的空格和注释,经过这个程序运行后,将实现多余空格,注释去除。
设计思路:
这个模块一共有6个状态,设为0,1,2,3,4,5,其中状态转换图:
字符转换表Ch_Type_Table:
ASIC
4
3
13
10
非白’非’/’非’*’非’\r’
白’
/
*
\r,\n
0
1
2
3
4
说明:
白’表示空格、TAB(\t);而白是等于白’+\r,\n,把\r,\n独立出来是为了消除注释需要。
状态转换表state_Trans_Table:
符号
S_B
0
1
2
3
4
0
0
1
2
0
1
1
0
1
2
0
1
2
0
0
3
4
0
3
3
3
3
3
1
4
4
4
4
5
4
5
4
4
1
4
4
Action_Table:
S_A
S_B
0
1
2
3
4
5
0
f_留
f_改
f_删
/
/
/
1
f_留
f_删
f_删
/
/
/
2
f_补
/
/
f_删
f_删
/
3
/
f_改
/
f_删
/
/
4
/
/
/
/
f_删
f_删
5
/
f_改
/
/
f_删
/
其中在程序中f_留表示为f_save;f_改表示为f_change;f_补表示为f_add;f_删表示为f_delete;Action_Table表示为void(*Action_Table[6][6])(void)。
2.1.2词法分析
设计思路:
1、把消除白空格、消除注释、识别标识符id,识别整数di,识别运算符、识别界符、识别双引号内的注释分层次画状态机,使状态机清晰易懂,方便其他同学学习;
2、以0状态为中转,每一层次的状态机遇到不是该层次的内容(识别了一个词元,当前输入不是该词元的内容了),回到0状态去判断该字符应转向的状态。
3、使用了ungetc()函数,输入回退一个字符,回到0状态中转之前,如果该字符并没有做处理,要ungetc,回退到输入流,那么从0状态会再读出之前没有处理的字符,再判断转换;
4、词元存储,用结构体存储数组存储;不同类型的词元对应不同的表,词元结构体中存储的是,该词元的类型(也即表的类型)、在该表中的下标(可以通过该下标找到对应词元的相关信息,便于后期扩展)、该词元在测试代码中的坐标(x,y)。
不同类型的词元表有程序动态维护。
表的动态维护对与整个编译程序很重要。
structData{
inttype;//表类型:
id=0,num=1,运算符2界符3
intvalue;//在表中的下标
intpos_x,pos_y;//源代码位置
};
本模块一共有13个状态,0—12,其中词法分析状态转换图为:
说明:
1、字符转换表:
字母,下划线(_)化为一类,为识别标识符用。
0单独处理是用于识别单个0和以0开头的错误整数;这里的运算符是指可以和“=”连在一起作为一个词元的,如>=,<=,+=,-+,*=,/=;界符是指一个字符做为一个词元的,如{}();,等。
2、函数说明:
f_留,表示将当前字符存到缓冲数组里面;
f_读,提取词元,从缓冲数组里面读出当前词元,并将缓冲数组清空;f_回,转到中转0状态之前,将当前字符回退到输入流中。
f_留2:
为后面添加,单个字符组成的词元,不用存到缓冲数组里面,直接提取成一个词元,存到词元结构体数组里面。
3、字符转换表如下:
(状态转换表、动作转换表略)
白’
/
*
\r
字母、_
数字
0
运算符
界符
=
“
0
1
2
3
4
5
6
7
8
9
10
2.2.语法分析
2.2.1递归下降手工编码
这个模块是给定状态转换表,action表,之后对输入的表达式进行词法分析,判断表达式正误。
其中文法如下:
E:
=TE’
E’:
=+TE’|@
T:
=FT’
T’:
=*FT’|@
F:
=id|di|(E)
所定义的函数为:
voidf_exp();
voidf_term();
voidf_factor();
voidf_term_remains();
voidf_exp_remains();
2.2.2first集合的计算
这个模块进行的是first集合的计算。
定义的文法存储数据结构为:
structdefine{
charleft;
stringright;
};
设计思路:
整体上采用不动点算法
依次扫描每条文法右部,若遇到终止符,则将该终止符加入文法左部非终止符的first集中。
如果遇到非终止符,则先判断该终止符的first集合中是否包含@(“@”代表“可空”),如果不包含@,则将该非终止符的first集加到文法左部的非终止符的first集中;如果包含@,并且该非终止符不是最后一个非终止符,则将该非终止符的first集合去掉@后,加到文法左部的first集合中;否则直接将此非终止符的first集合加到文法左部的first集合中。
具体描述如下:
对于任意给定的LL
(1) 文法G,为了构造它的预测分析表M,我们就必须构造与文法G有关的集合First和fellow.首先我们对每一个X∈VT U Vn ,构造FIRST(X),办法是,连续使用下面的规则,直至每个集合FIRST不再增大为止.
(1)若X∈VT,,则FIRST(X)={X}.
(2)若X∈Vn ,且有产生式X->a……,则把a加入到FIRST(X)中,若X->ε,也是一条产
生式,则把ε也加到FIRST(X)中.
(3)若X->Y……是一个产生式且Y∈Vn,则把FIRST(Y)中所有非ε-元素都加到
FIRST(X)中,若X->Y1Y2……YK ,是一个连续的产生式, Y1Y2……Yi-1 都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj) 都含有ε(即Y1Y2……Yi-1=>ε),则把FIRST(Yi) 中的所有非ε-元素都加到FIRST(X)中,特别是,若所有的FIRST(Yj)均含有ε,j=1,2,……,k,则把ε加到FIRST(X)中.
辅助函数:
/*统计文法条数,非终止符个数,终止符个数,并把非终止符,终止符弄成一个字符串,用于查找下标*/
voidget_gene()//获得产生式,并统计
intget_index(charb);//得到终止符或非终止符的统一下标
voidadd(string&tLeft,strings);将s添加到tLeft中,即将右边的字符串添加到左边的字符串中,去掉重复,如果右边存在新的字符,要将flag置为1,用于不动点算法。
2.2.3左递归消除
设计思路:
将间接左递归变成左递归,然后消除直接左递归。
(1)把文法的所有非终止符按某一顺序排序,如:
A1,A2,…….An;
(2)从A1开始消除都为A1的产生式的直接左递归,然后把左部为A1的所有规则的右部逐个替换为A2开始的产生式中的A1,并消除左部位A2的产生式中的直接左递归,继而以同样的方式吧A2的右部代入左部为A3右部以A1或A2开始的产生式中,消除左部为A3的产生式之直接左递归,直到把左部为A1,A2,…….An-1的右部代入左部为An的产生式中,从An中消除直接左递归。
把上述算法归结为:
如非终止符的排序为:
A1,A2,…….An
FORi:
=1TONDO
BEGIN
FORj:
=1TOi-1DO
BEGIN
如Aj的所有产生式为:
Aj->a1|a2|….|ak
替换形成Ai->Ajr的产生式变为:
Ai->a1r|a2r|….|akr
END
消除Ai中的一切直接左递归.
END.
(3)去掉无用产生式。
2.2.4selection表自动生成
设计思路:
扫描文法,计算文法右部的first集合(“@”不计算在内),直接将文法去右部填入文法右部计算得到的相应first集合和文法左部对应的selection表项中。
此代码比较简单,附如下:
voidcount_selection(define*p,string*first,string*follow,string**selection,intcount,intcount_T)
{
for(inti=0;i { stringfirst_right=first_str(p[i].right); stringrights=p[i].right; charlefts=p[i].left; for(intj=0;j<(first_right.length());j++) { selection[get_index(lefts)][get_index(first_right[j])]=rights; } if(first[get_index(lefts)].find('@')! =-1)//如果@属于first[p[i].left] { stringfollows=follow[get_index(lefts)]; for(j=0;j { selection[get_index(lefts)][get_index(follows[j])]='@'; } } } } 2.2.5LL (1)手工编码 设计思路: 1.确定的selection表用二维String数组存储,其中%表示错误标志,@表示空,R表示E’,L表示T’。 stringselection[5][7]={ {"%","%","TR","TR","TR","%","%"}, {"+TR","%","%","%","%","@","@"}, {"%","%","FL","FL","FL","%","%"}, {"@","*FL","%","%","%","@","@"}, {"%","%","i","d","(E)","%","%"} }; 2.将当前测试的表达式存入Get_ch数组中,并记下数组的长度,用于依次遍历匹配。 3.如果[1]当前表达式没有遍历完,[2]当前出栈的文法不是%,@,非终止符,则将当前读入的表达式的字符转换成selection的y下标,当前出栈的文法转换成x下标,并查询selsection[x][y]。 如果当前出栈元素是%,则报错退出。 如果当前出栈元素是@,则继续出栈下一个元素。 如果当前出栈元素是非终止符,则与当前表达式读取的字符匹配,如匹配,则表示继续遍历下一个,继续出栈,如果不匹配,则报错退出。 4.用栈来存储查selection表所得的文法,并反序入栈,如查得+TR,则反序入栈,从栈底到栈顶元素为RT+。 5.如果表达式遍历完并且当前栈为空,则说明表示表达式匹配成功。 2.3语义分析 2.3.1表达式求值LR (1) LR分析法: 是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的k个(k≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约,因而也就能唯一地确定句柄LR分析过程是一种规范归约过程。 设计思路: 一个LR分析器由3个部分组成: (1)、总控程序,也可以称为驱动程序。 对所有的LR分析器总控程序都是相同的。 (2)、分析表或分析函数。 不同的文法分析表将不同,同一个文法采用的LR分析器不同,分析表也不同,分析表又可以分为动作(ACTION)表和状态转换(GOTO)表两个部分,它们都可以用二维数组表示。 (3)分析栈,包括文法符号栈和相应的状态栈。 分析表的生成比较复杂,此处只简述总控程序: ACTION[Si,a]规定了栈顶状态为Si时遇到输入符号a应执行的动作,动作有4种可能: (1)移进: 当Sj=GOTO[Si,a]成立,则把Sj移入到状态栈,把a移入到文法符号栈。 其中i,j表示状态号 (2)归约: 当在栈顶形成句柄为β时,则用β归约为相应的非终结符A,即当文法中有A—>Β产生式,而β的长度为r(即|β|=r),则从状态栈和文法符号栈中自栈顶向下去掉r个符号,即栈指针SP减去r。 并把A移入文法符号栈内,再把满足Sj=GOTO[Si,A]的状态移进状态栈,其中Si为修改指针后的栈顶状态 (3)接受acc: 当归约到文法符号栈中只剩文法的开始符号S时,并且输入符号串已结束即当前输入符是#,则为分析成功 (4)报错: 当遇到状态栈顶为某一状态下出现不该遇到的文法符号时,则报错,说明输入串不是该文法能接受的句子。 本模块功能主要对表达式进行LR (1)分析后,并对表达式进行求值。 产生式存储结构定义为: structdefine//产生式 { charleft; stringright; }; 其他定义: stack stack charGet_ch[100];//用于存储测试字符串 define*p=newdefine[10]; intcount=0;//用于记录测试字符串的长度 intcounts;//产生式个数 inttCount;//终止符个数 intntCount;//非终止符个数 strings_NT="",s_T=""; intget_index(charb); voidget_gene(); voidget_ch(); voidinit();//初始化 intparseInt(string);//将字符串转换为int 2.3.2四元式 本模块基于LR手工编码,主要是将表达式表示成四元式,如运算符,运算对象1,运算对象2,结果)。 四元式存储结构定义为: structfour_element//四元式结构体 { charop;//操作符 stringx1,x2;//两个操作数 stringre;//结果 }; 主要函数为: stringtest(stringAction[12][6],intGoto[12][3],stringinput); 3测试过程 消除白空格以及注释运行结果截图: 原文件: 输出文件: 词法分析运行结果截图: 递归自动生成运行结果截图: LR (1)手工编码运行结果截图: 消除左递归运行结果截图: 四元式运行结果截图: 4总结 这次的课程设计项目,我担任的是原型设计,并参与了部分编码工作。 在设计的时候遇到很多困难,并且由于编译原理本身的复杂性,系统性,让我在设计的时候对整体的把握和取舍上需要有一定的决策能力和判断能力。 例如词法分析中真正要考虑完全,会发现很多问题,要处理的细节太多,这样状态也太多,转换表以及action表比较难画,也比较容易出错,不利于初次原形设计和小组学习,于是我选择一个这种的方式,只考虑了一些常规的词元,并且状态图采用层次型,清晰,便于小组学习和深入,虽然这样做代码效率不高。 另外一些算法性、知识性较强的算法设计,如first、follow集合计算、消除左递归的,需要对上课讲诉的内容深入理解,并自己手工模拟才能深入理解,并设计原形。 设计原形后设计与编码人员的沟通问题;由于部分编码人员对算法思想不够理解,需要耐心沟通,并且对一些大家都要用到的数据结构进行统一,对某些通用的函数可以整合到一个.cpp文件,这样加强了小组代码的规整性。 经过这次课程设计,不仅让我学习到了编译器的编译过程,词法分析,语法分析,语义分析,中间代码生成,代码优化。 而且培养了我们的团队合作分工意识。 使我们认识到了,进行项目开发,不是单靠个人力量可以成功完成的。 按照每个人的专业擅长,给每个人分工,能力比较强的同学担任项目的原型设计工作,编码能力强的同学进行项目的编码工作,编码能力相对较弱的同学可以担任测试工作,管理能力较强的同学担任项目中组织以及管理的工作。 只有整个团队分工细致地合作,每个环节紧扣相应的环节,这样才能把项目做好,做强。 这次的课程设计让我们能把所学的知识运用到实际的项目编码中来,真的让我们成长起来了,这样的教学方式是值得肯定和支持的。 5参考文献 编译原理(第2版)张素琴清华大学出版社2012年5月 6代码附录 消除白空格以及注释: #include #include usingnamespacestd; voidf_save(); voidf_delete(); voidf_change(); voidf_add(); charsrcstr; ofstreamout("test1.txt",ios: : binary); intmain() { ifstreamin("test.txt",ios: : in|ios: : binary); charch_in,ch_in_Type; intS_B=0,S_A=0; intState_Trans_Table[6][5]={{0,1,2,0,1},{0,1,2,0,1},{0,0,3,4,0}, {3,3,3,3,1},{4,4,4,5,4},{4,4,1,4,4}}; charCh_Type_Table[128]={0}; Ch_Type_Table['\r']=Ch_Type_Table['\n']=4;//'\r','\n' Ch_Type_Table['/']=2;//'/' Ch_Type_Table['*']=3;//'*' Ch_Type_Table['']=Ch_Type_Table['\t']=1;//空格,/t //返回类型(指针变量名)(参数列表);定义函数指针 void(*Action_Table[6][6])(void)={{f_save,f_change,f_delete,NULL,NULL,NULL}, {f_save,f_delete,f_delete,NULL,NULL,NULL}, {f_add,NULL,NULL,f_delete,f_delete,NULL}, {NULL,f_change,NULL,f_delete,NULL,NULL}, {NULL,NULL,NULL,NULL,f_delete,f_delete}, {NULL,f_change,NULL,NULL,f_delete,NULL}}; while(in)//当文件读取没有结束 { S_B=S_A; in.get(ch_in); srcstr=ch_in; ch_in_Type=Ch_Type_Table[ch_in]; S_A=State_Trans_Table[S_B][ch_in_Type]; Action_Table[S_B][S_A](); } out.close(); in.close(); return0; } voidf_save(){//f_留 out< } voidf_delete(){//f_删 } voidf_change(){//f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 课程设计 说明书 词法 分析 语法 语义