论文简单的编译原理语法分析Word格式文档下载.doc
《论文简单的编译原理语法分析Word格式文档下载.doc》由会员分享，可在线阅读，更多相关《论文简单的编译原理语法分析Word格式文档下载.doc（22页珍藏版）》请在冰点文库上搜索。
3.3分析表构造模块 12
3.3.1构造文法分析表 12
3.3.2A:
:
=aβ规则 13
3.3.3A:
=Dβ规则 13
3.3.4A:
=ε规则 13
3.4句子分析模块 13
3.4.1读取句子 14
3.4.2分析句子 14
4特殊问题及解决方法 14
4.1Select集的求解 15
4.1.1问题描述 15
4.1.2解决方案 15
4.1.3解决结果 15
4.2为ListBox添加水平滚动条 15
4.2.1问题描述 15
4.2.2解决方案 15
4.2.3解决结果 16
5结果测试 16
5.1测试正确文法 16
5.2测试错误文法 19
结论 20
参考文献 20
1引言
1.1项目背景
编译原理是计算机专业中最难的一门课程,在理论上它要求学生掌握有关形势语言和自动机的抽象概念,在技术上要求学生能够熟练地利用各种数据结构进行编程。
编译程序是现代计算机系统的基本组成部分之一。
在编译原理的教学过程中，语法和语义分析阶段关于算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等。
这些过程往往需要占用大量时间来分析、制表等。
教学主要是对这些过程的讲解和分析，没有必要花这么多的时间来做这些工作。
本软件的主要任务就是利用程序来完成算法的上述相关过程，节约教学时间。
1.2目标
《一个编译原理语法分析器的设计与实现》
1.主要通过文本方式获取相关文法，并实现以下相关操作：
2.判断文法是否符合LL
（1）的要求
3.获取文法的终结符和非终结符
4.求文法的select集（其中包括first集和follow集的求解）并判断select集是否符合LL
（1）算法的要求
5.根据文法和select集构造文法分析表
6.根据文法分析表判断输入的句子是否符合文法
1.3名词解释
语法分析：
逐一分析词法分析所得的属性字，检查其中的语法错误，如果没有发现语法错误，则给出正确的语法结构。
句子的分析：
句子的分析实际就是分析源程序中的语句是否符合给定的文法。
文法：
对语言结构的定义和描述，即在形式上用于描述和规定语言结构。
由若干条规则组成。
规则：
为一个二元组，通常格式为U：
：
=x或U→x；
其中U为规则的左部，是一个符号；
x是规则的右部，是一贯有穷字符串。
规则又称为产生式。
BNF表示法：
即巴科斯范式表示法，它引进了符号“|”，符号“|”表示“或”。
运用符号“|”把相同左部的规则缩写在一起，这样显得文法更为紧凑。
文法G[Z]：
规则的非空有穷集合，其中Z为文法的识别符号或开始符号，它至少要在一条规则的左部出现。
字汇表：
在文法中，由全部规则的左部和右部中的所有符号组成的符号集。
非终结符：
文法中出现在规则左部的符号，它们组成的集合称为非终结符集。
终结符：
文法中凡不属于非终结符集的符号，它们组成的集合称为终结符集。
递归：
同一操作或一组操作的连续重复，其实质上是处理过程的性质，在这种过程的每一步都要用到它自身的上一步或上几步的结果。
递归定义：
在定义某种事物时又用到其本身。
直接左递归规则：
型如U：
=Uy的规则称为直接左递归规则。
First集：
首符号集。
Follow集：
向前看集。
Select集：
可选集。
LL
（1）文法：
对于文法G（S），其每个非终结符的不同规则具有不相交的Select集，则称该文法为LL
（1）文法。
1.4算法简介
1.4.1自顶向下分析
对于文法G[Z]，给顶一个待分析的句子（字符串），自顶向下分析的基本思想是从识别符号Z开始，根据文法试着建立一个推导序列，若得到所给的句子，则句子得到识别，表明其结构符合文法，如果经过各种推导都不能得到所分析的句子，则该符号串不符合文法。
或者说，从根结点出发，自上而下地建立一颗语法树，其未端结点按从左到右的顺序连接起来，构成给定的符号串，则符号串得到识别。
例：
设有文法G[N]和符号串25N
D
N
N:
=D|ND
D:
=0|1|2|…|9
根据文法有：
5
NÞ
NDÞ
DDÞ
2DÞ
25；
因此我们说25符合此文法
2
图1G[N]过程分析
自顶向下分析的难点及解决办法：
1.自顶向下分析的难点
对于形如:
U:
=x1|x2|…|xn的规则,可能需要对所有的规则都要试探。
2.难点的解决办法
该解决办法是把文法中每个非终结符号A的右部称为A的候选式，对候选式的选择，则根据当前输入符号来决定。
方法：
首先对文法的每个规则A:
=b求可选集Select（A:
=b）。
当e¹
b时，则对于当前输入的符号a，若有aÎ
First（b），则可以选用规则A:
=b进行推导。
若对于某非终止符号有n条规则（即有n个候选式）的处理方法：
1.首符号集不相同的解决办法
对于文法，有A:
=x1|x2|…|xn，其右部的n个候选式的首符号集均不相同:
即First（xi）∩First（xj）=Æ
（i¹
j），对于待分析的符号串，如果最左的非终结符号为A，若其句子中对应的下一个符号（当前输入符号）为a，且有aÎ
First（xk），则选择规则A:
=xk来作为推导的候选式。
设有文法G[Z]，和句子bbabaax
Z:
=aV|bZ
V:
=baZ|x
Select（Z:
=aV）={a};
=bZ）={b};
Select（V:
=baZ）={b};
=x）={x};
ZÞ
bZÞ
bbZÞ
bbaVÞ
bbabaZÞ
bbabaaVÞ
bbabaax
（babaax）（abaax）（baax）（ax）（x）
2.首符号相同的解决办法
=x1|x2|…|xn，若有First（xi）∩First（xj）Æ
¹
（i¹
j），采用试探法：
即从首字符中有输入符号的多个候选式中任选一个来试探，如果不成功，就换另一个接着试。
试探法有可能形成回溯现象。
对于回溯现象，可以通过“左提因子方法”对文法进行修改来消除。
1.4.2递归子程序
递归子程序方法：
这里讲的递归子程序方法是一种自顶向下的编译方法，其思想是通过对源程序的每个语法成分编制一个处理子程序，通过子程序调用来对源程序进行语法和语义分析。
递归子程序及其调用：
常用的子程序的种类有3种：
1、简单子程序，2、嵌套子程序，3、递归子程序。
三种子程序的返回地址保护方法：
1.所有简单子程序可以公用一个返回地址保护单元。
2.嵌套子程序各自有各自的返回地址保护单元，不得随意公用。
3.对于递归子程序，由于返回地址保护单元数目不明确，一般采用堆栈形式。
方法是在内存中开辟一个保护栈，每次进入递归子程序时，就把当前返回地址送入保护栈，相应地，每次退出递归子程序时，就取栈顶的返回地址作为其返回地址。
同时入栈和出栈的还有相应的递归子程序中需要保护的工作单元。
递归子程序调用时，入口与出口的工作：
（1）递归入口工作：
①当前返回地址送保护栈；
②递归子程序中（调用程序）不允许被破坏的工作单元内容送保护栈。
（2）递归出口工作：
①恢复保护在栈顶中的工作单元的原来内容，并上退保护栈；
②取保护在栈顶中的返回地址进行返回，并退保护栈。
1.4.3LL（K）分析方法
LL（K）分析方法是一种自顶向下的分析技术。
这种分析方法从左到右扫描源程序（输入串），同时从识别符号开始生成句子的最左推导（规范推导），向前看K个符号，便能确定当前应选择怎样的规则。
当K=1时，既是LL
（1）分析方法。
1.4.4LL
（1）分析方法
1.LL
（1）方法的思想：
根据输入串的当前输入符号，确定用某规则进行推导，当推导的第一个符号与输入串的当前符号匹配时，就把输入串的下一个字符作为当前输入字符，直到推导出输入串。
根据输入串向前的1个符号来确定推导规则时，就是LL
（1）方法。
2.LL
（1）分析方法的逻辑结构
第18页共22页
＃ a1a2a3…ai…am#
x1
分析表
控制器
……..
Xn-1
图2LL
（1）分析方法的逻辑结构
1.4.5LL
（1）分析表
LL
（1）分析表是分析方法的核心,它确定了推导所使用的规则。
1.LL
（1）分析过程
假设分析过程中当前句型的右端部分为：
x1x2…xm，（xiÎ
V）
输入流（待分析串）的右端部分为：
y1y2…yn，（yiÎ
Vt）
此时有以下3种情况：
（1）当x1Î
Vn，则根据当前输入符号y1选择相应的规则去替换x1;
（2）当x1Î
Vt时，则查看x1与y1是否相同，若x1与y1相同，则分别删去x1和y1，然后继续向前分析；
不相同表示不相配，为出错。
（3）若上述两个字符串均为空，则表示全部匹配，输入串被识别。
现在我们把句型的右端部分逆向放入一分析堆栈中，使x1成为栈顶，利用分析栈，当栈顶符号与输入串当前符号相匹配时，则从栈顶删除该符号。
然后再把相应的规则逆向压入栈顶，替换原栈顶的非终结符。
2.LL
（1）分析表的构造
LL
（1）分析表：
它是用来反映分析栈中的元素与输入串中元素的一种匹配关系。
如果分析栈中的元素为A，输入元素为a，则其匹配关系记为LL（A,a）
LL
（1）分析矩阵：
一种用来反映这种匹配关系的矩阵表示，该矩阵称为LL
（1）分析矩阵。
首先进行介绍与LL
（1）分析有关的3个操作约定：
（1）N表示继续下一个符号；
（2）P表示重读当前符号，也即不读入下一符号；
（3）R（b）表示用b的逆串替换栈顶符号。
构造LL
（1）分析表的方法如下：
1.对于A:
=ab，（aÎ
Vt），则
令LL（A,a）=R（b）/N
**R（b）/N：
表示用b的逆串替换Ａ后，继续读入下一个符号。
当b为e时，即：
A:
=a，有：
LL（A,a）=R（e）/N
2.对于A:
=Db，（DÎ
Vn），且有Select（A:
=Db）={b1,b2,…,bn}，
则LL（A,bi）=R（Db）/P，（i=1,2,…,n）
**R（Db）/P：
表示用Db的逆串替换A后，重读当前符号
3.对于A:
=e，且有Select（A:
=e）={b1,b2,…,bn}
则LL（A,bi）=R（e）/P
4.对于每一个aÎ
Vt，a不出现于规则右部的首部，
则令LL（a,a）=R（e）/N
5.对于#，令LL（#,#）=acc表示分析结束，输入串得到识别。
6.非上述5种情况，则置出错，分析表中用空白表示。
2系统流程图
2.1程序流程图
项目的程序流程图如图3所示：
程序开始
调用打开对话框输入文法
优化输入的文法并判断文法合法性
获取文法的终结符和非终结符
对文法求select集并判断select集合法性
构造文法分析表
输入并分析句子
结束
图3程序流程图
2.2系统模块流程图
系统的模块流程图如图4所示：
LL
（1）算法
演示系统
文法输入
文法分析
句子输入
与分析
文法分析表
构造
获取终结符和非终结符
求文法的select集
判断select集的合法性
求first集
求follow集
图4系统模块流程图
3系统实施
主要分为四个模块：
1．文件读取模块
文件读取模块主要完成将记事本中的待分析文法读入到内存中的功能。
其中包括了对可能出现的文法BNF表示法的判断以及对文法中是否存在直接左递归规则的判断。
2．算法分析模块
算法分析模块是《一个编译原理语法分析器的设计与实现》
中的关键模块。
本模块包含了LL
（1）算法中的大部分重要数据和信息，其中包括获取输入文法的终结符集和非终结符集，对文法中每一条规则求select集（select集的求解又包括求first集或者follow集），以及对select集合法性的判断，即同一非终结符所对应的不同规则的select集中不能有相同的终结符。
3．分析表构造模块
分析表构造模块的主要功能是将算法分析模块所求解出的符合LL
（1）算法规则的文法的select集转化成文法分析表，以便下一模块的调用。
4．句子分析模块
句子分析模块是整个《一个编译原理语法分析器的设计与实现》的主体演示模块，包括句子读取、句子合法性判断、句子分析等部分。
其中句子合法性的判断又分为句子中是否有文法终结符以外的符号和句子是否符合文法规则的判断。
下面将对以上四个模块的具体实现技术、数据结构及关键程序片段进行详细的说明。
3.1文件读取模块
本模块通过调用VB中CommonDialog控件的ShowOpen方法启动打开文件对话框，获取需要读取的文件的路径，再调用Open命令打开文件，将文件中保存的文法读入内存，用二维数组进行保存。
3.1.1文件读取使用的CommonDialog控件介绍
CommonDialog控件提供诸如打开和保存文件、设置打印选项、选择颜色和字体等操作的一组标准对话框。
调用打开文件对话框的具体代码如下：
Dimp_nameAsString'
文件路径
Form1.CommonDialog1.CancelError=True
OnErrorGoToerr
Form1.CommonDialog1.Filter="
Text（*.txt）|*.txt"
Form1.CommonDialog1.FilterIndex=1
Form1.CommonDialog1.ShowOpen'
用ShowOpen方法显示对话框
p_name=Form1.CommonDialog1.FileName'
用FileName属性获取选定文件的名称
3.1.2文法左递归的判断
文法中使用递归规则以后，可以用有限的规则刻划无限语言，但不利的是对与具有左递归性的文法，不能采用自顶向下的分析算法。
一般含有左递归规则的文法形式为U:
=xUy，
若x=e,则有U:
=Uy，即为左递归规则。
由于消除左递归算法的复杂性和毕业设计时间所限，所以本软件没有这项功能，只是对直接左递归进行错误判断。
DoWhileWF（j,0）<
>
Empty'
判断文法是否有左递归
IfWF（j,0）=WF（j,1）Then
MsgBox"
！
错误！
文法有左递归存在，不符合LL
（1）的要求"
vbApplicationModal,"
错误"
ExitSub
EndIf
j=j+1
Loop
3.2算法分析模块
本模块首先获取文法的终结符集和非终结符集，分别用一维数组进行保存；
然后在对文法的每一条规则求select集，并将select集保存到二维数组中；
最后对select集做相关判断，以确定所读入的文法是否符合LL
（1）文法的规则。
程序中所用到的公有数据成员有：
PublichsAsInteger'
文法的行数
PubliczjAsInteger'
终结符的个数
PublicnzAsInteger'
非终结符的个数
PublicSLT（50,50）AsString'
select集
DimF（50）AsString'
用与临时存放select集中元素的数组
PublicZJF（50）AsString'
终结符集
PublicNZJ（250）AsString'
非终结符集
3.2.1求select集
设有文法G[S]，并有规则A:
=b，则该规则的可选集为：
Select（A:
=b）=
具体实现代码如下：
IfWF（a,0）=EmptyThen
ExitFor
ElseIfWF（a,1）="
ε"
Then'
ε为空字符串
Callfollow（a,fo）
i=0
DoWhileF（i）<
Empty
SLT（a,i）=F（i）
F（i）=Empty
i=i+1
SLT（a,i）=Empty
Loop
Else
Callfirst（a,fo）
3.2.2求first集
首符号集既求解文法每条规则右边的第一个符号并且必须是终结符，因为文法使用数组存放，所以既求文法每行规则的第2个字符既可；
如果规则左边第一个字符为非终结符，则通过循环对该非终结符再求首符号集。
Fori=0Tozj
IfWF（a,1）=ZJF（i）Then'
判断第a条规则右边的首符号是否是终结符
Forp=0Tofo'
判断WF（i,j+1）在F（）中是否已经存在
IfWF（a,1）=F（p）Then
b=1
ExitFor
EndIf
Nextp
Ifb=1Then
b=0
Else
F（fo）=WF（a,1）
fo=fo+1
F（fo）=Empty
EndIf
3.2.3求follow集
求向前看集主要分两种情况，一种是可以直接循环推导出终结符；
第二种是推出的还是非终结符的，如果推出的还是非终结符的就循环对该非终结符再求向前看集；
第三种情况是不能对该非终结符
升级会员 