dowhile语句的翻译分析程序采用LL1法输出三地址.docx
《dowhile语句的翻译分析程序采用LL1法输出三地址.docx》由会员分享，可在线阅读，更多相关《dowhile语句的翻译分析程序采用LL1法输出三地址.docx（16页珍藏版）》请在冰点文库上搜索。
dowhile语句的翻译分析程序采用LL1法输出三地址
学号：
0120510680422
课程设计
题目
学院
计算机科学与技术
专业
软件工程
班级
软件0504
姓名
周峰
指导教师
李勇华
2008
年
6
月
22
日
课程设计任务书
学生姓名：
周峰专业班级：
软件0505班
指导教师：
李勇华工作单位：
计算机科学与技术学院
题目:
DO-WHILE循环语句的翻译程序设计（LL
（1）法、输出三地址表示）
初始条件：
理论：
学完编译课程，掌握一种计算机高级语言的使用。
实践：
计算机实验室提供计算机及软件环境。
如果自己有计算机可以在其上进行设计。
要求完成的主要任务:
（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
（1）写出符合给定的语法分析方法的文法及属性文法。
（2）完成题目要求的中间代码四元式的描述。
（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。
（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
（5）设计报告格式按附件要求书写。
课程设计报告书正文的内容应包括：
1系统描述（问题域描述）；
2文法及属性文法的描述；
3语法分析方法描述及语法分析表设计；
4给出中间代码形式的描述及中间代码序列的结构设计；
5简要的分析与概要设计；
6详细的算法描述（流程图或伪代码）；
7给出软件的测试方法和测试结果；
8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；
9参考文献（按公开发表的规范书写）。
时间安排：
设计安排一周：
周1、周2：
完成系统分析及设计。
周3、周4：
完成程序调试及测试。
周5：
撰写课程设计报告。
设计验收安排：
16周的星期五第1节课开始到实验室进行上机验收。
设计报告书收取时间：
17周的星期一上午10点。
指导教师签名：
2007年5月20日
系主任（或责任教师）签名：
2007年5月20日
DO-WHILE语句的翻译程序设计
（LL1文法输出3地址表达式）
1问题描述
1.1实验要求
按照课程设计的要求，写一个能识别while循环语句的文法，通过一定的变换使它符合LL
（1）法的要求，然后按照这个文法编写一个程序，该程序能识别输入的语句是否符合while语句的文法，或者能不能通过文法的开始符号推导出该语句。
该程序应该包括词法分析器，能对输入的语句进行词法分析，对输入的源程序从左到右进行扫描并将其分解为一个个的单词符号。
然后再对结果进行语法分析。
词法分析器应能识别关键字，标识符，常量，操作符等。
该程序的语法分析器能对输入的语法进行分析，判断输入语句能否满足while循环语句的文法。
如果不是则提示错误，如果满足while循环语句文法，判断是否符合LL
（1）法，运用最左推导对其进行分析，看能否通过开始符号推导出来。
将语法和语义分析的结果用输出三地址形式表示出来。
1.2实验中所用概念
（1）词法分析：
输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号：
关键字while、标识符、常量、操作符等。
（2）语法分析：
在词法分析的基础上，根据语法规则，把单词符号串分解成各类语法单位。
（3）语义分析与中间代码产生：
对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）LL
（1）文法：
LL
（1）文法是一种自上而下的语法分析方法。
对于产生式：
A->aA->b，当且仅当select（A->a）与select（A->b）相交为空时才为LL
（1）文法。
（5）预测分析程序：
实现LL
（1）法分析的一种有效方法，使用一张预测分析表和一个栈进行联合控制。
预测分析程序就是属于这种类型的LL
（1）分析器。
2文法及属性文法的描述
2.1do..While语句文法描述
G（s）:
S->doBwhileE,
B->b=a，
E->a>b|a非终结符集VN{S,B,E}
终结符集V*{do,while,a，b,>,=,<}
First集：
First（S）={do}；
First（B）={b}；
First（E）={a}；
Follow集：
Follow（S）={#};
Follow（B）={while};
Follow（E）={#};
SELET集：
Select（S-->doBwhileE）={do}；
Select（B->c:
=a）={b}；
Select（E->a>b）={a};
Select（E->a=b）={a};
Select（E->a预测分析表
do
while
a
b
>
<
=
S
-->doBwhilee
B
-->b=a
E
-->a>b|a2.2属性文法描述
G（s）:
S->doBwhileE,{S.begin:
=newlabel;
B.next:
=S.begin;
E.true:
=newlabel;
E.false:
=S.next;
S.code:
=gen（S.begin’:
’）‖B.code‖E.code‖
gen（E.true’:
’）‖gen（‘goto’S.begin）}
B->c:
=a{B.code:
=’c:
=a’}
E->a>b{E.code=gen（‘if’’a>b’’goto’E.true）‖
Gen（‘goto’E.false）}
E->true{E.code:
=gen（‘goto’E.true）}
E->false{E.code:
=gen（‘goto’E.false）}
3语法分析方法及中间代码形式的描述
3.1语法分析方法描述
LL1文法的定义：
First集：
设G={VT,VN,S,P}是上下文无关文法
First（α）={a|α=>aβ,a∈VT,α,β∈V*}
若a=>ε，则规定ε∈First（α），称为First（α）为α的开始符号集或首符号集。
FOLLOW集：
设G={VT,VN,S,P}是上下文无关文法
FOLLOW（A）={a|S=>μAβ且a∈VT,a∈First（β）,μ∈V*T,β∈V+}
若S=>μAβ,且β=>ε,则#∈FOLLOW（A）
SELECT集:
给定上下文无关文法的产生式A-->αA∈VN,α∈V*,若α≠>ε,则SELECT（A-->α）=First（α）
如果α=>ε,则SELECT（A-->α）=（First（α）-{ε}）UFOLLOW（A）.
LL
（1）文法:
一个上下文无关文法是LL
（1）文法的充分必要条件是,对每个非终结符A的两个不同的产生式,A-->αA-->β,满足
SELECT（A-->α）∩SELECT（A-->β）=ф
其中α,β不能同时推导出空.
3.2中间代码形式
三地址码是由下面一般形式的语句构成的序列：
x:
=yopz
其中，xyz为名字、常数或临时变量；op代表运算符号。
每个语句中只能有一个运算符。
三地址码类似于汇编语言代码。
语句可以带有符号标号，而且存在各种控制流语句，本程序输出中用到了：
复制语句x:
=y
条件转移语句ifxrelopygotoL//L为带标号L的三地址语句
无条件转移语句gotoL//转移到标号为L的三地址语句。
4简要的分析与概要设计
4.1基本框架
输入dowhile语句词法分析语法语义分析输出三地址代码
4.2构成图
4.2.1主函数构成
4.2.2语法分析函数构成
4.3各个部分构成
整个工程分为四个部分,词法分析部分,和语法分析部分,具体函数执行部分,以及语义分析部分（最终部分在main函数中执行的）
Wordanalyze（）-----程序的入口点，读入输入的待分析的字符串后,把其装入一给定数组,先进行词法分析，然后输出生成的词法分析结果。
ExpressionAnalyse（）-----语法分析阶段,利用Wordanalyze（）中分析出的词法,进行语法分析.如果不是LL
（1）文法则输出语法出错,仅对LL
（1）文法的输入进行分析.
具体函数执行部分-----定义了各种操作函数以方便调用,入读入输入的句字的函数,提
取字符函数,判断字符函数等等
语义分析式部分-------主函数中进行的输出,形式为给定句子的三地址表达式
5详细的算法描述
5.1词法分析的主要算法
intWordanalyze（）{
intjieshu=0;//词法分析没有结束
GetProgram（）;//把源程序装入数组a
charword[MaxiWordLength];//声明临时数组
while（（chr=GetChr（））!
='\0'）
{if（!
（Judge（chr）））
{break;}//跳过空格和回车取元素
x=0;word[x]='\0';//清空
if（IsLetter（chr））
{jieshu=1;
while（IsLetter（chr））
{Input（word,chr,x）;//是字符就将其装入数组word
chr=GetChr（）;}
if（chr=='>'||chr=='='||chr=='<'）
nLength=nLength-1;//指向算符
word[x]='\0';
Save（word,x）;//将关键字或标志符或算符装入Token
}
elseif（chr==">"|"<"|"="）//将>|<|=装入Token
{Input（word,chr,x）;
word[x]='\0';
Save（word,x）;}
Else出错}
if（jieshu==1）//词法分析结束
{Getcode（）;
for（intd=1;d{if（Token[d].ID==6）
{
strcpy（Token[d].b,"id"）;
}}
strcpy（Token[nTokenNumer].b,"#"）;
Token[nTokenNumer].ID=7;
}}
语法分析主要算法
intExpressionAnalyse（）//语法分析
{
strcpy（Ecode[Top++],"#"|"S"）;//将#和S压栈
intFLAG=1;//语法分析未结束标志
while（FLAG）
{intf1=0;
f1=panduanSEA（）;
分别把各个识别的符号压栈；
}
else{
intf2=0;
f2=EStrcmp（）;
if（f2==1）//识别出关键字
{Pop（）;
nID=nID+1;}
Else识别出"#"号结束此次分析
Else语法出错
return0;}}};}}
语义分析主要算法：
voidmain（）
{if（Wordanalyze（））//词法分析成功
{if（ExpressionAnalyse（））//语法分析也成功
{inti;
L[nL].add=nadd;
for（i=0;i{
if（strcmp（L[i].str,"while"）==0）
{输出三地址表达式}}}}}
具体执行函数：
Input函数：
执行将各个字符压栈的功能
Getprogram函数：
把输入的语句装入一数组，方便分析使用
ISletter函数：
判断是否为字母
Judge（char&chr）函数：
判断是否分析到句子结尾
panduanSEA（）函数：
识别非终结符
Pop（）函数：
用于执行出栈操作
Save（char*p,intx）函数：
把关键字或标识符装入指定数组
EStrcmp（）函数：
识别DOWHILE关键字
6软件的测试方法和测试结果
6.1测试方法
在visualc++6.0下调试并通过.输入不同的语句进行测试，测试的主要目的是看程序能否正确判断条件语句是否正确，赋值语句的格式有没有错误以及最后结果输出的三地址是否正确。
6.2测试结果
现用一下用例来测试本程序：
测试1：
输入一个最简单的dowhile循环语句，正确输入看能否得出正确结果，程序运行结果如下：
测试2：
输入一错误语句查看结果：
如下
程序不支持FOR语句的循环，所以显示输入错误。
7研制报告
7.1研制过程
本次课程设计要求我用LL
（1）分析法来翻译while循环语句，这就要求对编译原理语法分析方面有一定的了解，熟悉各种语法分析的方法，特别是本题中所要求的LL
（1）法，需要弄清楚LL
（1）法的概念，过程，需要注意的地方等。
另外还需要对编程语言联系，才能编出符合要求的程序。
看到题目以后，首先将编译原理书上相关知识仔细看了一遍，不清楚的地方搞清楚特别是关系程序设计的部分。
然后参阅了编译程序构造方面的书籍，对编译程序的实现有了一定的了解。
最后是从编程语言方面，根据编译原理方面的知识，找出实现课程设计要求的解决方式，然后编写程序来实现。
编好以后，对其测试，找出其中存在的问题，不过有些问题是因为本人水平有限，有些功能实现不了，根据课程设计要求检验程序，对程序进行相应的修改。
7.2本设计的缺点
由于时间较短,编程者对编译原理的理解有限，还有就是编程能力有限，导致对课程设计要求的功能的实现会有些问题，可能某些情况考虑不到，或者处理得不合适。
另外为了简化程序而对while循环做出了若干限制,比如while循环语句中可以嵌套while，为了降低难度，所以取消了while的嵌套，因此降低了程序的通用性,使得本程序并不是对所有的语句都能分析正确。
.
7.3设计的体会和收获
课程设计是对我们动手解决实际问题的一种方式，对于我们熟悉所学过的知识具有很大的帮助，在这次课程设计中，我有很多收获。
首先,巩固了编译原理的知识。
为了做好这次课程设计,要求我必须重新复习一遍编译的课本,特别是需要实现的那部分原理。
除此之外,还有上网查询一些编译资料，和一些实际问题实现的例子，通过看别人实现的过程，学习实现的一些基本思路。
通过这次设计,我对整个编译程序的工作过程有了一个更立体的理解,清楚的了解了编译工作的五个阶段时如何衔接成一个整体的。
这次编译原理课程设计的题目是用简单优先分析法进行DO-WHILE循环语句的语法分析,并输出三地址表达式.设计的特点是利用定义每个终极符和非终极符之间优先关系,来进行符号的移进与规约,如果栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。
这样使得程序简化,只需定义一个栈用来存放移进的字符,然后用栈顶指针指向它后与待移进字符比较优先级即可,设计简单.此设计的严重不足是只能进行一个固定句子的词法与语法分析,因为在定义优先关系时已固定了DO,和WHILE的每个字符之间的优先关系,且赋值表达式和条件式也已固定,所以只能进行本程序已约定好的语句.最大的收获是在提出一个难题以后，如果能比较顺手的解决的话，那是一件比较开心的事。
只是有些时候越想问题就会越多，也越难解决，那就得慢慢调试，慢慢推导了。
相信只要想得出，就能调得出，当然耐心是很重要的，花在上面的时间也是要多一点的。
其次,通过本次课程设计检验了我的数据结构的知识。
因为在语法分析中需要用到数据结构的一些知识,这就敦促我去重新温习数据结构中相关的知识。
再次,本次课程设计对我的编程能力、程序设计能力的提高有很大的帮助。
在设计的过程中我体会到了一些程序设计的技巧。
比如说,在语法分析的时候,由于要分析的符号很多,整个程序很复杂,在后期编译的时候无法发现是那个具体的位置出错,所以我给每个错误编了号,这样就可以很容易找到程序出错的位置，方便自己找到错误原因和改正。
另外在程序编写的过程中我们可以添加一些注释,不仅便于自己对程序结构的理解,而且当编译遇到错误时可以帮助我们找到出错的位置。
往往编写结束以后自己对整个程序也不是说完完全全了解，加注释是一个很好的习惯，增加程序的可读性。
还有一点就是,要注意程序实现的过程.在本次实验中,我并不是词法分析跟语法分析一起编写的,而是我先写了一个词法分析器,将它调试通过编译了,然后在写语法分析器,这样就可以避免词法分析和语法分析的结果混乱,影响最终结果。
8参考文献
（1）《编译原理》陈火旺、刘春林等著国防工业出版社2002.6
（2）《计算机编译原理—编译程序构造实践》张幸儿著科学出版社2005.7
（3）《C++Primer》StanleyB.Lippman,JoseeLajoie著；BarbaraE.Moo李师贤，蒋爱军
等人译。
升级会员 