|
2.LL(1)分析表的构造 LL(1)分析表：它是用来反映分析栈中的元素与输入串中元素的一种匹配关系。如果分析栈中的元素为A，输入元素为a，则其匹配关系记为LL(A,a) http://www.paper51.com LL(1)分析矩阵：一种用来反映这种匹配关系的矩阵表示，该矩阵称为LL(1)分析矩阵。首先进行介绍与LL(1)分析有关的3个操作约定： copyright paper51.com (1)N表示继续下一个符号； http://www.paper51.com (2)P表示重读当前符号，也即不读入下一符号； http://www.paper51.com (3)R(b)表示用b的逆串替换栈顶符号。 copyright paper51.com 构造LL(1)分析表的方法如下： 内容来自论文无忧网 www.paper51.com 1.对于A::=ab，(aÎVt)，则 内容来自www.paper51.com 令 LL(A,a)=R(b)/N paper51.com **R(b)/N：表示用b的逆串替换Ａ后，继续读入下一个符号。 copyright paper51.com
当b为e时，即：A::=a，有：LL(A,a)=R(e)/N 内容来自论文无忧网 www.paper51.com 2.对于A::=Db，(DÎVn)，且有 Select(A::=Db)={b1,b2,…,bn}， paper51.com 则LL(A,bi)=R(Db)/P，(i=1,2,…,n) 内容来自论文无忧网 www.paper51.com **R(Db)/P：表示用Db的逆串替换A后，重读当前符号 http://www.paper51.com 3.对于A::=e，且有 Select(A::=e)={b1,b2,…,bn} 内容来自www.paper51.com 则 LL(A,bi)=R(e)/P 内容来自www.paper51.com
4.对于每一个aÎVt，a不出现于规则右部的首部， copyright paper51.com 则令 LL(a,a)=R(e)/N 内容来自www.paper51.com 5.对于#，令LL(#,#)=acc 表示分析结束，输入串得到识别。 内容来自www.paper51.com 6.非上述5种情况，则置出错，分析表中用空白表示。 内容来自www.paper51.com 2 系统流程图2.1程序流程图 内容来自论文无忧网 www.paper51.com 项目的程序流程图如图3所示： 内容来自www.paper51.com
http://www.paper51.com 图3 程序流程图 copyright paper51.com
2.2 系统模块流程图 内容来自www.paper51.com
系统的模块流程图如图4所示： 内容来自论文无忧网 www.paper51.com
内容来自论文无忧网 www.paper51.com 图4系统模块流程图 内容来自论文无忧网 www.paper51.com 3 系统实施 内容来自www.paper51.com
《一个编译原理语法分析器的设计与实现》 内容来自www.paper51.com
主要分为四个模块： paper51.com 1．文件读取模块 copyright paper51.com 文件读取模块主要完成将记事本中的待分析文法读入到内存中的功能。其中包括了对可能出现的文法BNF表示法的判断以及对文法中是否存在直接左递归规则的判断。 http://www.paper51.com
2．算法分析模块 http://www.paper51.com 算法分析模块是《一个编译原理语法分析器的设计与实现》 copyright paper51.com 中的关键模块。本模块包含了LL（1）算法中的大部分重要数据和信息，其中包括获取输入文法的终结符集和非终结符集，对文法中每一条规则求select集（select集的求解又包括求first集或者follow集），以及对select集合法性的判断，即同一非终结符所对应的不同规则的select集中不能有相同的终结符。 paper51.com
3．分析表构造模块 内容来自论文无忧网 www.paper51.com 分析表构造模块的主要功能是将算法分析模块所求解出的符合LL（1）算法规则的文法的select集转化成文法分析表，以便下一模块的调用。 内容来自www.paper51.com 4．句子分析模块 copyright paper51.com 句子分析模块是整个《一个编译原理语法分析器的设计与实现》的主体演示模块，包括句子读取、句子合法性判断、句子分析等部分。其中句子合法性的判断又分为句子中是否有文法终结符以外的符号和句子是否符合文法规则的判断。下面将对以上四个模块的具体实现技术、数据结构及关键程序片段进行详细的说明。 内容来自www.paper51.com 3.1文件读取模块 内容来自www.paper51.com 本模块通过调用VB中CommonDialog控件的ShowOpen方法启动打开文件对话框，获取需要读取的文件的路径，再调用Open命令打开文件，将文件中保存的文法读入内存，用二维数组进行保存。 paper51.com 3.1.1文件读取使用的CommonDialog控件介绍 内容来自论文无忧网 www.paper51.com
CommonDialog 控件提供诸如打开和保存文件、设置打印选项、选择颜色和字体等操作的一组标准对话框。调用打开文件对话框的具体代码如下： 内容来自www.paper51.com Dim p_name AsString ' 文件路径 http://www.paper51.com Form1.CommonDialog1.CancelError= True paper51.com On Error GoTo err 内容来自论文无忧网 www.paper51.com
Form1.CommonDialog1.Filter= "Text(*.txt)|*.txt" 内容来自论文无忧网 www.paper51.com Form1.CommonDialog1.FilterIndex= 1 copyright paper51.com Form1.CommonDialog1.ShowOpen' 用 ShowOpen 方法显示对话框 copyright paper51.com p_name =Form1.CommonDialog1.FileName ' 用 FileName 属性获取选定文件的名称 内容来自www.paper51.com
3.1.2文法左递归的判断 copyright paper51.com 文法中使用递归规则以后，可以用有限的规则刻划无限语言，但不利的是对与具有左递归性的文法，不能采用自顶向下的分析算法。一般含有左递归规则的文法形式为U::=xUy， 内容来自www.paper51.com
若x=e, 则有U::=Uy，即为左递归规则。由于消除左递归算法的复杂性和毕业设计时间所限，所以本软件没有这项功能，只是对直接左递归进行错误判断。 paper51.com Do While WF(j, 0)<> Empty ' 判断文法是否有左递归 http://www.paper51.com If WF(j, 0) = WF(j, 1) Then 内容来自www.paper51.com MsgBox "！错误！文法有左递归存在，不符合LL(1)的要求", vbApplicationModal, "错误" http://www.paper51.com Exit Sub http://www.paper51.com End If paper51.com j = j + 1 内容来自论文无忧网 www.paper51.com Loop 内容来自www.paper51.com 3.2算法分析模块 copyright paper51.com 本模块首先获取文法的终结符集和非终结符集，分别用一维数组进行保存；然后在对文法的每一条规则求select集，并将select集保存到二维数组中；最后对select集做相关判断，以确定所读入的文法是否符合LL（1）文法的规则。程序中所用到的公有数据成员有： paper51.com Public hs As Integer ' 文法的行数 copyright paper51.com Public zj As Integer ' 终结符的个数 内容来自论文无忧网 www.paper51.com Public nz As Integer ' 非终结符的个数 内容来自论文无忧网 www.paper51.com Public SLT(50, 50) As String' select集 内容来自论文无忧网 www.paper51.com Dim F(50) As String ' 用与临时存放select集中元素的数组 http://www.paper51.com Public ZJF(50) As String ' 终结符集 http://www.paper51.com Public NZJ(250) As String ' 非终结符集 copyright paper51.com 3.2.1求select集 内容来自论文无忧网 www.paper51.com 设有文法G[S]，并有规则A::=b，则该规则的可选集为： copyright paper51.com
Select(A::=b)= http://www.paper51.com copyright paper51.com paper51.com |