编译原理课设5.docx

编译原理课设5.docx

《编译原理课设5.docx》由会员分享，可在线阅读，更多相关《编译原理课设5.docx（21页珍藏版）》请在冰点文库上搜索。

编译原理课设5

课程设计（论文）任务书

软件学院学　　院　　软件测试专　　业2013-2班

一、课程设计（论文）题目　LL

（1）分析过程模拟

二、课程设计（论文）工作自2016年6月20日起至2016年6月24日止。

三、课程设计（论文）地点:

软件学院实训中心

四、课程设计（论文）内容要求：

1．本课程设计的目的

进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编

译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，

强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识,熟

悉使用开发工具VC/JAVA/C#/.NET。

2．课程设计的任务及要求

1）课程设计任务：

（1）分析LL

（1）模块的工作原理；

（2）确定解决问题的方法；

（3）详细设计和编码；

（4）程序的调试和运行

（5）完成课程设计报告。

2）创新要求：

3）课程设计论文编写要求

（1）课程设计任务及要求

（2）设计思路--工作原理、功能规划

（3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注

释）、界面等。

（4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。

（5）设计体会与小结---设计遇到的问题及解决办法，通过设计学到了哪些新知识，

巩固了哪些知识，有哪些提高。

（6）报告按规定排版打印，要求装订平整，否则要求返工；

（7）课设报告的装订顺序如下：

封面---任务书---中文摘要---目录----正文---附录

（代码及相关图片）

（8）严禁抄袭，如有发现，按不及格处理。

4）课程设计评分标准：

（1）学习态度：

20分；

（2）系统设计：

20分；

（3）编程调试：

20分；

（4）回答问题：

20分；

（5）论文撰写：

20分。

5）参考文献：

（1）张素琴，吕映芝.编译原理[M].,清华大学出版社

（2）蒋立源、康慕宁等，编译原理（第2版）[M]，西安：

西北工业大学出版社

6）课程设计进度安排

1．准备阶段（4学时）：

选择设计题目、了解设计目的要求、查阅相关资料

2．程序模块设计分析阶段（4学时）：

程序总体设计、详细设计

3．代码编写调试阶段（8学时）：

程序模块代码编写、调试、测试

4．撰写论文阶段（4学时）：

总结课程设计任务和设计内容，撰写课程设计论文

学生签名：

2016年6月24日

课程设计（论文）评审意见

（1）学习态度（20分）：

优（　）、良（　）、中（　）、一般（　）、差（　）；

（2）系统设计（20分）：

优（）、良（　）、中（　）、一般（　）、差（　）；

（3）编程调试（20分）：

优（　）、良（　）、中（　）、一般（　）、差（　）；

（4）回答问题（20分）：

优（　）、良（　）、中（　）、一般（　）、差（　）；

（5）论文撰写（20分）：

优（　）、良（　）、中（　）、一般（　）、差（　）；

评阅人：

　　　职称：

副教授

2016年6月日

中文摘要

在LL

（1）文法中，第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。

LL

（1）文法既不是二义性的，也不含左递归，对LL

（1）文法的所有句子均可进行确定的自顶向下语法分析。

需要注意的是，并不是所有的语言都可以用LL

（1）文法来描述，而且不存在判定某语言是否是LL

（1）文法的算法。

也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL

（1）文法所产生的语言。

另外，在上述LL

（1）文法的条件中，要求：

ε∈FIRST（α1），ε∈FIRST（α2），…ε∈FIRST（αn）中至多有一个成立。

目　录

一、课程设计任务及要求1

二、需求分析2

三、设计思路3

四、详细设计4

五、运行调试与分析讨论5

六、设计体会与小结6

七、参考文献7

一、课程设计任务及要求

1.问题描述

设计一个给定LL

（1）分析表，输入一个句子，能由依据LL

（1）分析表输出与句子对应的语法树。

能对语法树生成过程进行模拟。

2.基本要求

动态模拟算法的基本功能是：

（1）输入LL

（1）分析表和一个句子；

（2）输出LL

（1）总控程序；

（3）输出依据句子构成的对应语法树的过程；

3.测试数据

输入句子：

i*i+i

输入LL

（1）分析表

二、需求分析

1.问题理解

用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。

并实现算法与生成过程的关联。

2.问题分析

求出First集和Follow集，是求出Select集的基础，因此本程序也做了些完善，功能扩展发面，在出First集和Follow集的基础上求Select集，判断是否为LL1文法，构造预测分析表。

判断是在LL1分析文法中通过Select集判断是否是LL1文法，求出预测分析表之后，实现了字符串，依据LL1分析表单步输出字符串的分析过程。

3.问题的解决

其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。

语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。

自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。

或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。

4.解决步骤

总体步骤

在自上而下的分析法中，主要是研究LL

（1）分析法。

它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL

（1）文法，这个文法应该满足：

无二义性，无左递归，无左公因子。

当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL

（1）分析表，最后利用分析表，根据LL

（1）语法分析构造一个分析器。

LL

（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。

FIRST集的确定

FIRST集使用以下四个步骤判定：

（1）若X∈VT,则FIRST（X）={X}

（2）若X∈VN,且有产生式X→a…，a∈VT。

则把a加入到FIRST（X）中，即a∈FIRST（X）

（3）若X∈VN,且有产生式X→$，

则把$也加到FIRST（X）中，即$∈FIRST（X）

（4）若X∈VN,Y1，Y2，…，Yi都∈VN，

且有产生式X→Y1Y2…Yn。

当Y1，..Yi-1=>$（1≤i≤n），则FIRST（Y1）-{$}，…，FIRST（Yi-1）-{$}，FIRST（Yi）都包含在FIRST（X）中，即：

FIRST（Yi-1）-{$}∈FIRST（X）

所有Y1,…Yn*=>$，则把$加到FIRST（X）中,即：

FIRST（Yi）∈FIRST（X）

FOLLOW集的确定

FOLLOW集使用以下三个步骤判定：

（1）如果X是开始符那么把#加入到FOLLOW（X）

（2）若Ａ=>αBβ是一个产生式,则把FIRST（β）－{$}加至FOLLOW（B）中

（3）若Ａ=>αB是一个产生式，或Ａ=>αBβ是一个产生式而β*=>$（即$∈FIRST（β）），则把FOLLOW（A）加至FOLLOW（B）中

FOLLOW集的求法与FIRST集类似，但有不同的地方。

FOLLOW集需要扫描每一个产生式。

而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。

FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。

碰到死循环使用FIRST集一样的方法处理就可以。

SELLECT集的确定

FIRST集＆FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：

A→αA∈VN，α∈V*，

（1）若α是终结符，那么SELLECT（A→α）={α}

（2）若α是$，则SELECT（A→α）=FOLLOW（A）

（3）若α是非终结符那么

若α*=>$，则SELECT（A→α）=（FIRST（α）-$）∪FOLLOW（A）

若α┐*=>$则SELECT（A→α）=FIRST（α）

LL

（1）文法的判定

当SELLECT集求出来后就可以判断是不是一个文法是不是LL

（1）文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相同元素则返回TRUE。

句子的判定

当一个文法确定是LL

（1）文法时就可以对输入的语句进行判定了。

首先要安装SELLECT集生成LL

（1）预测分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。

这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。

在实际分析时设置两个栈，把"#"压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。

三、设计思路

1、设计原理

（1）、LL

（1）文法的定义

LL

（1）分析法属于确定的自顶向下分析方法。

LL

（1）的含义是：

第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则）进行推导。

LL

（1）文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL

（1）文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。

即在LL

（1）分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。

LL

（1）分析方法要求文法满足如下条件：

对于任一非终极符A的两个不同产生式A,A，都要满足下面条件：

SELECT（A）∩SELECT（A）=

（2）、预测分析表构造

LL

（1）分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。

它的行对应文法的非终极符，列对应终极符，表中的值有两种：

一是产生式的右部的字符串，一是null。

若用M表示LL

（1）分析表，则M可表示如下：

M:

VN×VTP∪{Error}

M（A,t）=Aα，当tselect（Aα），否则

M（A,t）=Error

其中P表示所有产生式的集合。

（3）、语法分析程序构造

LL

（1）分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括号即输入串的括号。

分析表用一个二位数组M表示，数组元素M[A，a]中的下标A表示非终结符，a为终结符或句子括号‘#’，二维数组中存放的是一条关于A的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。

LL

（1）分析过程主要包括以下四个动作：

替换：

当XVN时选相应产生式的右部去替换X。

此时X出栈，逆序入栈。

匹配：

当XVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。

接受：

当格局为（#，空#）时报告分析成功。

报错：

出错后，停止分析。

并给出相应的错误提示信息。

驱动程序框图如：

2、预测分析表具体构造

此语法程序的实现采用手工操作输入构造LL

（1）分析表。

LL

（1）分析表用一个二维矩阵表示，其中每个非终极符对应一行，每个终级符对应一列，一个非终极符和一个终极符可以确定矩阵中的一个元素，元素的值表示该非终极符和该终极符对应的产生式。

每个矩阵元素都是一个字符串，所有元素初始化为null；构造LL

（1）表时，根据给出的测试数据中相应的分析表LL

（1）分析表的内容。

其中输入产生式为空用&表示，产生式不存在则进行出错处理，在数组中出错用NULL或者null表示。

在根据LL

（1）分析表选择产生式进行推导时，若查到的产生式为NULL或者null表示无相应的产生式可选，不匹配错误；否则根据编号得到相应的产生式进行推导。

a.控制程序是依据分析表和分析栈联合控制输入字符串的识别和分析，它在任何时候都是依据当前分析栈的栈顶符号和当前输入字符来执行控制功能。

对不同文法，控制程序是相同的。

b.输入缓冲器用来存放被分析的符号串，符号串后跟以标志符号#。

c.栈中存放一系列文法符号，符号#存在于栈的底部，分析开始时，栈底先放好#，然后放进文法开始符号。

d.分析表是一个二维数组M[A,a]，其中A是非终结符号，a是终结符号或是符号#，M[A,a]内容为一条关于A的产生式或出错标志，不同语言使用内容不同的分析表。

e.输出流是在分析中不断产生的输出序列。

3、主要算法思想

（1）、分析开始时，首先将标志符号#和文法开始符号E依次压入符号栈；输入流指针指向分析串的第一个输入符号，即由符号栈和输入流构成的初始格局为：

（#E,a1a2...an#）

然后，反复执行第2步所列的工作。

（2）、设在分析的某一步，符号栈及剩余的输入流处于如下的格局：

（#A12...Am-1Am,aiai+1...an#）

其中，A1A2...Am-1Am为分析栈中的文法符号，此时，可视栈顶符号Xm的不同情况，分别作如下动作：

若AmVN，则以Am及ai组成的符号对（Am，ai）查分析表M。

设M（Am，ai）为一产生式，假设是AmUVW，此时将Am从分析栈中弹出，并将UVW逆序压入栈中，从而得到新的格局：

（#A1A2...Am-1WVU,aiai+1...an#）

但若T（Am，ai）=NULL或null，则调用出错处理程序进行处理；

若Am=ai#，则表明栈顶符号已经与当前扫描的输入符号得到匹配，此时应将Am（即ai）从栈中退出，并将输入流指针向前移动一个位置。

若Xm=ai=#，则表明输入串已经完全得到匹配，此时即可宣告分析成功而结束分析。

其它情形，转到错误处理程序。

四、详细设计

1.总体思路分析及流程图

给定一个正规文法G，在LL

（1）预测分析中，必须先求出First集和Follow集，然后求出Select集，通过Select集判断是否是LL1文法，如果是的话，构造预测分析表。

求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。

功能模块分解图

（1）主程序流程图

（2）核心算法流程图

1.计算非终结符的First集的算法及流程：

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是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，First（Yj）都含有ε（即Y1…Yi-1*ε），则把First（Yj）中的所有非ε-元素都加到First（X）中；特别是，若所有的First（Yj）均含有ε，j=1,2,…，k，则把ε加到First（X）中。

连续使用上面的规则，直至每个集合First不再增大为止。

2.计算非终结符的Follow集：

Follow集合的具体构造算法如下：

（1）对于文法的开始符号S，置#于Follow（S）中；

（2）若A→αBβ是一个产生式，则把First（β）|{ε}加至Follow（B）中；

（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈First（β）），则把Follow（A）加至Follow（B）中。

连续使用上面的规则，直至每个集合Follow不再增大为止。

3.预测分析控制程序的算法流程

2.关键代码

（1）计算非终结符的First集：

voidfirst（edgeni,edge*n,intx）//ni为一个产生式，n为整个文法

{inti,j;

for（j=0;j

{if（ni.getlf（）==n[j].getlf（））

{

if（NODE.find（n[j].getro（））

{for（i=0;i

if（n[i].getlf（）==n[j].getro（））

first（n[i],n,x）;

}

elsen[x].newfirst（n[j].getro（））;//终结符的情况

}

}

}

（2）计算非终结符的Follow集：

voidfollow（edgeni,edge*n,intx）//计算follow

{inti,j,k,s;

stringstr;

for（i=0;i

{s=NODE.find（ni.getrg（）[i]）;

if（s-1）//是非终结符

if（i

for（j=0;j

if（n[j].getlf（）.find（ni.getrg（）[i]）==0）

{if（NODE.find（ni.getrg（）[i+1]）

{for（k=0;k

{

n[j].newfollow（n[k].getfirst（））;if（n[k].getfirst（）.find（"*"）

n[j].newfollow（ni.getfollow（））;

}

}

else

{str.erase（）;

str+=ni.getrg（）[i+1];

n[j].newfollow（str）;

}

}

}

}

（3）输出预测分析表的主要代码：

voidoutgraph（edge*n,string（*yc）[50]）

{inti,j,k;

boolflag;

for（i=0;i

{if（ENODE[i]!

='*'）

{outfu（10,""）;

cout<

}

}outfu（10,""）;

cout<<"#"<

intx;

for（i=0;i

{outfu（4,""）;

cout<

outfu（5,""）;

for（k=0;k

{flag=1;

for（j=0;j

{if（NODE[i]==n[j].getlf（）[0]）

{x=n[j].getselect（）.find（ENODE[k]）;

if（x-1）

{cout<<"->"<

yc[i][k]=n[j].getrg（）;

outfu（9-n[j].getrlen（）,""）;

flag=0;//

}

x=n[j].getselect（）.find（'#'）;if（k==ENODE.length（）-1&&x-1）

{cout<<"->"<

yc[i][j]=n[j].getrg（）;

}

}

}

if（flag&&ENODE[k]!

='*'）

outfu（11,""）;

}

cout<

}

}

五、运行调试与分析讨论

六、设计体会与小结

在这次编译原理课程设计中，我学到了许多。

首先，对课程设计任务的难度把握不好。

仅仅是看书是不够的，理论知识比较容易理解，但是在实际环境中实践一下才能发现更多问题。

这导致我对任务的难度有所低估，编码时才发现许多细节没有考虑清楚。

其次，对自身编码能力有了提升。

编译原理作为难度比较高的课程，对我们学生的编码能力也是一个不小的挑战。

很久没有使用C/C++编程，对语言的各个特性有所生疏，给我的编码过程带来了或多或少的障碍，很多时候都需要翻书才能完成编码。

总之，通过这次课程设计，使我对LL

（1）词法分析原理有了更透彻的了解，通过将理论付诸实践的过程中，不但对课本知识有了更深的理解，掌握，同时对编程能力也有很大的巩固，,希望为自己以后的学习打下基础，以便将来自己学得更好、做得更好。

七、参考文献

[1]《编译原理》吕映芝张素琴蒋维杜主编清华大学出版社

[2]《编译原理及编译程序构造》高仲仪北京航天航空大学出版社