编译原理课程设计.doc
《编译原理课程设计.doc》由会员分享，可在线阅读，更多相关《编译原理课程设计.doc（21页珍藏版）》请在冰点文库上搜索。
编译原理实验报告
设计题目将FOR语句转换成四元式的程序实现
学生姓名
学号
专业班级计算机科学与技术08—3班
指导教师
罗珣
2010年12月25日
目录
引言...............................................................2
第一章概述.....................................................3
1.1设计内容....................................................3
1.2设计要求...................................................3
第二章设计的基本原理..........................................3
2.1词法分析...................................................3
2.2语法分析...................................................3
2.3语义分析...................................................3
2.4文法描述...................................................3
2.5属性文法描述...............................................4
2.6语法分析方法描述...........................................5
2.7操作符优先级...............................................6
2.8中间代码形式描述...........................................6
2.9中间代码序列的结构设计.....................................7
第三章程序设计.................................................7
3.1总体方案设计...............................................7
3.2各模块设计.................................................8
第四章程序测试.................................................9
4.1测试方法...................................................9
4.2测试结果...................................................9
第五章结论.....................................................16
参考文献...........................................................17
附录程序清单.................................................17
合肥工业大学课程设计任务书
设计
题目
将FOR语句转换成四元式的程序实现
成绩
主
要
内
容
设计内容及要求：
设计一个语法制导翻译器，将FOR语句翻译成四元式。
要求：
先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。
对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。
指
导
教
师
意
见
该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力。
程序设计方案。
论文论述，文理，格式。
程序运行结果。
程序验收时回答问题。
签名：
第一章概述
1.1设计内容
设计一个语法制导翻译器，将FOR语句翻译成四元式。
1.2设计要求
先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。
对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出（可按一定格式输出到指定文件中）。
第二章设计的基本原理
2．1词法分析
设计词法分析算法，每当语法分析程序需要一个单词时，则调用该算法函数。
词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词，送给语法分析器
2．2语法分析
采用递归下降方法，为对应文法中的每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。
若输入串是给定文法的句子，则从文法的开始符号出发一定能推导出与输入的单词串完全相同的句子。
2．3语义分析
在语法分析的同时可由语法分析程序调用相应的语义子程序进行语义处理，完成附加在所使用的产生式上的语义规则描述，并生成四元式的中间代码形式。
2．4文法描述
递归下降法要求文法满足LL
（1）文法，则消除左递归后的文法如下：
start→spsceof
spsc→for[parse;parse;parse]{spsclist}
|e
list→parse;list
|e
parse→cdexprmorecdexprs
morecdexprs→=cdexprmorecdexprs
|e
cdexpr→cdsexprmorecdsexprs
morecdsexprs→||cdsexprmorecdsexprs
|e
cdsexpr→cdtermmorecdterms
morecdterms→&&cdtermmorecdterms
|e
cdterm→cdstermmorecdsterms
morecdsterms→==cdstermmorecdsterms
|!
=cdstermmorecdsterms
|e
cdsterm→exprmoreexprs
moreexprs→ |<=exprmoreexprs
|>exprmoreexprs
|>=exprmoreexprs
|e
expr→termmoreterms
moreterms→+termmoreterms
|-termmoreterms
|e
term→factormorefactors
morefactors→*factormorefactors
|/factormorefactors
|e
factor→!
factor
|（cdexpr）
|id
|num
图1FOR循环语句文法描述
2．5属性文法描述
将语义规则附加在文法产生式的合适位置上，构成属性文法如下：
start→spsceof
spsc→for[parse;parse;parse]{spsclist}
|e
list→parse;list
|e
parse→cdexprmorecdexprs
morecdexprs→=cdexpr{print（“=”）}morecdexprs
|e
cdexpr→cdsexprmorecdsexprs
morecdsexprs→||cdsexpr{print（“||”）}morecdsexprs
|e
cdsexpr→cdtermmorecdterms
morecdterms→&&cdterm{print（“&&”）}morecdterms
|e
cdterm→cdstermmorecdsterms
morecdsterms→==cdsterm{print（“==”）}morecdsterms
|!
=cdsterm{print（“!
=”）}morecdsterms
|e
cdsterm→exprmoreexprs
moreexprs→ |<=expr{print（“<=”）}moreexprs
|>expr{print（“>”）}moreexprs
|>=expr{print（“>=”）}moreexprs
|e
expr→termmoreterms
moreterms→+term{print（“+”）}moreterms
|-term{print（“-”）}moreterms
|e
term→factormorefactors
morefactors→*factor{print（“*”）}morefactors
|/factor{print（“/”）}morefactors
|e
factor→!
factor{print（“!
”）}
|（cdexpr）
|id{print（id.lexeme）}
|num{print（num.value）}
图2FOR循环语句属性文法描述
2.6语法分析方法描述
递归下降分析方法是一种自顶向下语法分析方法，其目的是从文法的开始符号开始，根据输入字符串进行最左推导，试图推导出给定的字符串。
或者说，从根节点（文法开始符号）开始，自上而下，从左到右地为输入字符串建立一棵语法树，并以预先确定的顺序创建语法树的节点。
递归下降分析法可能需要回溯，即需要重复地扫描输入。
递归子程序法的实现思想是对应每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，能够按照LL
（1）形式唯一地确定选择某个候选式进行推导，因此首先要消除左递归。
其文法及属性文法如图1和图2所示。
由于递归下降法对每个过程可能存在直接或间接的递归调用，所以对某个过程在退出之前可能又要被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。
由于递归过程是遵循先进后出规律，通常开辟栈来处理。
2.7操作符优先级
在对for循环语句进行翻译时，涉及到对赋值表达式和布尔表达式语句的翻译。
在文法的描述中给出了算术运算符、关系运算符和逻辑运算符之间的优先级关系，其结合性由下表所示：
优先级
操作符
类型
操作对象的个数
结合性
1
（）
逻辑运算符
——
左—>右
2
!
逻辑非运算符
单目运算符
右—>左
3
*,/
算术运算符
双目运算符
左—>右
4
+，-
算术运算符
双目运算符
左—>右
5
<,<=,>,>=
关系运算符
双目运算符
左—>右
6
==,!
=
关系运算符
双目运算符
左—>右
7
&&
逻辑与运算符
双目运算符
左—>右
8
||
逻辑或运算符
双目运算符
左—>右
9
=
赋值运算符
双目运算符
右—>左
2.8中间代码形式的描述
常见的中间代码形式有逆波兰记号，三元式，四元式和树形表示。
本课题设计输出的中间代码的表示方法是四元式。
它是带有四个域的记录结构，这四个域分别称为算符op，第一运算对象arg1，第二运算对象arg2及结果result。
域op包含一个代表运算符的内部码。
例如x=yopz的四元式表示为（op,y,z,x）,即将y置于arg1域，z置于arg2域，x置于result域，=置于算符域op，如果op是单目运算符，例如非‘！
’（x=!
y）的四元式表示形式中不用填arg2。
通常，四元式中的arg1，arg2和result的内容都是一个指针，此指针指向有关名字的符号表入口。
这样，临时变量名也要填入符号表中。
2.9中间代码序列的结构设计
型如for[parse1;parse2;parse3]{list}的中间代码序列的结构设计如下：
parse1
parse2
parse3
list
TRUE
END
FALSE
图3中间代码序列结构设计
第三章程序设计
3．1总体方案设计
本程序采用递归下降的方法实现FOR循环语句的翻译，并以四元式的中间代码形式输出。
经过词法分析，语法分析，同时执行语法制导翻译将中间结果表达出来，然后通过一个函数转化成要求的四元式结构的中间代码。
上述的这个过程在一遍扫描过程中完成：
在语法分析的过程中调用词法分析来不断的分解出下一个句柄；在用递归下降方法进行语法分析的同时进行中间形式数据的保存，在分析出操作符号的同时结合当前栈中的数据输出四元式。
源文件
词法分析
语法分析
语义分析
中间代码
出错处理
3.2各模块方案设计
程序中各阶段的功能如下：
（1）词法分析阶段
对源程序流进行扫描，每识别出一个单词，若是标识符，则到符号表中查找，如果符号表中没有此标识符的记录，那么将此标识符插入符号表。
最后按照单词其所属的类别，把类标识返回，作为语法分析阶段的输入。
词法分析算法在symr.h头文件中：
voidsymbolnum（）；
voidsymbolchar（）；
voidsymbolothers（）；
intSymbolanalysis（）；
（2）语法及语义分析阶段
由文法开始符号对应的子程序控制for循环语句各个模块的执行顺序，并由文法开始符号对应的子程序递归调用其他的子程序，对各个模块采用自顶向下，自左至右的推导方法完成对输入字符进行匹配的工作，试图推导出与输入符号串一致的文法的句子。
voidFor_s1（int*k,int*j）；//初值赋值语句
voidFor_s2（int*k,int*j）；//条件判断语句
voidFor_s3（int*k,int*j）；//变量更新语句
voidTrans_for（）;//for语句入口
voidphrasinganalyse（）；//语法语义分析
（3）中间代码生成阶段
控制代码的输出形式，以四元式形式输出中间代码。
中间代码最终以cout语句和outfile、outfile2、oufile3文件输出结果。
第四章程序测试
4.1测试方法
由于本程序在设计上考虑到for循环语句的多种表现形式，如for嵌套的方式，条件语句的表述等，所以在理论上能完成的功能很全，因此为了测试程序在实际应用中能否完成这些功能，我设计了三种测试途径：
（1）输入最简单的for循环语句（无嵌套）
（2）增加条件语句的复杂度
（3）实现简单for嵌套，可包括多个赋值语句
4.2测试结果
（1）简单的for循环语句（无嵌套）
图5简单FOR循环输入文件
图6词法分析二元式结果
图7四元式输出
（2）增加条件语句的复杂度
图8FOR循环输入
图9词法分析结果
图10四元式输出
（3）简单for循环嵌套
图11内嵌FOR循环输入
图12词法分析结果
图13四元式输出
第五章结论
本程序实现的功能有：
简单for循环，for循环嵌套，赋值语句，能完成的计算功能有布尔表达式，基本的四则运算，能将各个功能结合起来形成for循环，赋值语句，布尔表达式，空语句的复合出现。
for语句的实现上，通过将之分解成三个表达式来分别调用，初值赋值语句、条件控制语句和变量更新语句。
在词法分析阶段，区分一元和二元操作符的方法是：
当取得的第一个字符为一元操作符时，继续取下一个字符，若仍为操作符，则返回宏定义的标号，若不是操作符则将其放回，返回一元操作符的标号。
在词法分析阶段在每一个类型判断中都需要进行放回操作。
对语法分析，词法分析，四元式输出分离设计，同步控制，使得代码更灵活，结构更紧凑，不必要对中间结果进行大量重复的存储后，然后逐一检索后使用。
此次课程设计让我想了老师说过的一句话：
“编译原理这门课很难”。
经过这次课程设计，我更体会到了这句话的含义。
编译原理这门课，不仅难理解而且很抽象。
很多知识需要仔细琢磨才能理解，很多概念都很抽象，不找到例子很难搞明白。
由于我本人C++编程并不好，很多的东西都不懂。
所以，这次课程设计，我参考和查找了很多资料，也找同学询问不懂的地方，请他们帮忙讲解。
经过几天的努力，按照以上所述的研制过程，终于做完了这次课程设计。
将一个抽象的过程转变为详细的结果，显示出来。
实现这个过程，是很有难度的。
在设计时，通过仔细分析各功能程序段之间的联系、函数的调用实现和程序代码的运行效率，最终制定出了完整的程序实现方案。
本程序采用C++语言编写，在编码的过程中使我熟悉了C++语言的语法和库函数的使用，以及数据结构的应用。
现在我能熟练的运用他们了，而且通过查看源代码，对大部分库函数的内部实现有了一个很好的把握。
通过此次课程设计，让我看到了自己的很多不足之处。
很多知识点知识浅尝辄止，只看到了皮毛，没有深入理解。
人都是有惰性的，我也不例外。
很多问题，都不愿意仔细思考。
做事没耐心，不能坚持到最后，轻易放弃也是我的重大缺点。
这些问题，以后我必须尽量改正。
只有这样，才能有利于自己的发展，自己才能成为一个合格的大学生。
参考文献
[1]陈火旺、刘春林、谭庆平、赵克佳、刘越．程序设计语言编译原理（第3版）．国防工业出版社．2007年8月第46次印刷
[2]李师贤、李文军等.面向对象程序设计.高等教育出版社.2008年4月第6次印刷
附录程序清单
3
#include"symr.h"
//S-->forS1S2S3Incycle
//S1-->（E1；
//S2-->E2;
//S3-->E1）
//Incycle-->E1;
//（E1为赋值语句）
//（E2为布尔表达式）
voidphrasinganalyse（）;
voideval（int*,int*）;
charjudge（string,string）;
voidTrans_for（）;
strings[10]={"T1","T2","T3","T4","T5","T6","T7","T8","T9","T10"};
stringad[5]={"Begin","Adress2","Again","Adress4","Exit"};
stringad_e[20]={"（0）","
（1）","
（2）","（3）","（4）","（5）","（6）","（7）","（8）","（9）","（10）","（11）","（12）","（13）","（14）","（15）","（16）","（17）","（18）","（19）"};
structgoto_adress{
stringname;
intvalue;
}adress[5];//跳转地址
structexpression_adress{
stringname;
intvalue;
}e_adress[20];//四元式地址
stacksqstacks;
stacksqstackr;
fstreamoutfile2（"outfile2.txt",ios:
:
out）;
fstreamoutfile3（"outfile3.txt",ios:
:
out）;
stringbuffer[50];
externintn;
externSymbolattributesymattri[100];
inti;
intmain（）{
i=Symbolanalysis（）;
phrasinganalyse（）;
cin>>i;
outfile2.close（）;
return0;
}
//语法语义分析
voidphrasinganalyse（）{
for（intm=0;m<5;m++）
adress[m].name=ad[m];
for（m=0;m<20;m++）
e_adress[m].name=ad_e[m];
stringtype;
stringch;
do{
type=symattri[i].stype;
if（type=="4"）{
ch=symattri[i].svalue;
if（ch=="for"）Trans_for（）;
}
i++;
}while（i return;
}
//跳转地址回填
voidbackpath（intl,int*j）{
adress[l].value=（*j）;
}
/*循环语句*/
voidIncircle（int*k,int*j）{
into=i;
cout<"< outfile2<"<<"\n";
backpath（2,j）;
while（symattri[i].svalue!
="）"）i++;
while（symattri[i].svalue=
升级会员 