011_一个编译原理语法分析器

系统流程图
2.1程序流程图
项目的程序流程图如图3所示：

图3 程序流程图
2.2 系统模块流程图
系统的模块流程图如图4所示：

图4系统模块流程图

think58

[版权所有：http://think58.com]

[来源：http://think58.com]

3 系统实施
《一个编译原理语法分析器的设计与实现》
主要分为四个模块：
1．文件读取模块
文件读取模块主要完成将记事本中的待分析文法读入到内存中的功能。其中包括了对可能出现的文法BNF表示法的判断以及对文法中是否存在直接左递归规则的判断。
2．算法分析模块
算法分析模块是《一个编译原理语法分析器的设计与实现》
中的关键模块。本模块包含了LL（1）算法中的大部分重要数据和信息，其中包括获取输入文法的终结符集和非终结符集，对文法中每一条规则求select集（select集的求解又包括求first集或者follow集），以及对select集合法性的判断，即同一非终结符所对应的不同规则的select集中不能有相同的终结符。
3．分析表构造模块
分析表构造模块的主要功能是将算法分析模块所求解出的符合LL（1）算法规则的文法的select集转化成文法分析表，以便下一模块的调用。
4．句子分析模块
句子分析模块是整个《一个编译原理语法分析器的设计与实现》的主体演示模块，包括句子读取、句子合法性判断、句子分析等部分。其中句子合法性的判断又分为句子中是否有文法终结符以外的符号和句子是否符合文法规则的判断。下面将对以上四个模块的具体实现技术、数据结构及关键程序片段进行详细的说明。

copyright think58 [资料来源：http://www.THINK58.com]

3.1文件读取模块
本模块通过调用VB中CommonDialog控件的ShowOpen方法启动打开文件对话框，获取需要读取的文件的路径，再调用Open命令打开文件，将文件中保存的文法读入内存，用二维数组进行保存。
3.1.1文件读取使用的CommonDialog控件介绍
CommonDialog 控件提供诸如打开和保存文件、设置打印选项、选择颜色和字体等操作的一组标准对话框。调用打开文件对话框的具体代码如下：
Dim p_name As String ' 文件路径
Form1.CommonDialog1.CancelError = True
On Error GoTo err
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，即为左递归规则。由于消除左递归算法的复杂性和毕业设计时间所限，所以本软件没有这项功能，只是对直接左递归进行错误判断。 本文来自think58 [资料来源：http://www.THINK58.com]
Do While WF(j, 0) <> Empty ' 判断文法是否有左递归
If WF(j, 0) = WF(j, 1) Then
MsgBox "！错误！文法有左递归存在，不符合LL(1)的要求", vbApplicationModal, "错误"
Exit Sub
End If
j = j + 1
Loop
3.2算法分析模块
本模块首先获取文法的终结符集和非终结符集，分别用一维数组进行保存；然后在对文法的每一条规则求select集，并将select集保存到二维数组中；最后对select集做相关判断，以确定所读入的文法是否符合LL（1）文法的规则。程序中所用到的公有数据成员有：
Public hs As Integer ' 文法的行数
Public zj As Integer ' 终结符的个数
Public nz As Integer ' 非终结符的个数
Public SLT(50, 50) As String ' select集
Dim F(50) As String ' 用与临时存放select集中元素的数组
Public ZJF(50) As String ' 终结符集
Public NZJ(250) As String ' 非终结符集
3.2.1求select集
设有文法G[S]，并有规则A::=b，则该规则的可选集为：

[资料来源：http://www.THINK58.com]

Select(A::=b)=

具体实现代码如下：
If WF(a, 0) = Empty Then
Exit For
ElseIf WF(a, 1) = "ε" Then 'ε为空字符串
Call follow(a, fo)
i = 0
Do While F(i) <> Empty
SLT(a, i) = F(i)
F(i) = Empty
i = i + 1
SLT(a, i) = Empty
Loop
Else
Call first(a, fo)
3.2.2求first集
首符号集既求解文法每条规则右边的第一个符号并且必须是终结符，因为文法使用数组存放，所以既求文法每行规则的第2个字符既可；如果规则左边第一个字符为非终结符，则通过循环对该非终结符再求首符号集。
For i = 0 To zj
If WF(a, 1) = ZJF(i) Then '判断第a条规则右边的首符号是否是终结符
For p = 0 To fo '判断WF(i,j+1)在F()中是否已经存在
If WF(a, 1) = F(p) Then
b = 1
Exit For
End If
Next p
If b = 1 Then
b = 0
Else
F(fo) = WF(a, 1)
fo = fo + 1
F(fo) = Empty
End If
3.2.3求follow集
求向前看集主要分两种情况，一种是可以直接循环推导出终结符；第二种是推出的还是非终结符的，如果推出的还是非终结符的就循环对该非终结符再求向前看集；第三种情况是不能对该非终结符求向前看集，但是可以通过对该非终结符推导出的第二个非终结符求向前看集的方法求出终结符。 think58

c = 0: b = 0
If WF(a, 0) = WF(0, 0) Then '判断是不是对文法起始符求follow集
For p = 0 To fo '判断WF(i,j+1)在F()中是否已经存在
If F(p) = "#" Then
b = 1
Exit For
End If
Next p
If b = 1 Then
b = 0
Else
F(fo) = "#"
fo = fo + 1
F(fo) = Empty
End If
End If
For i = 0 To hs
j = 1
Do While WF(i, j) <> Empty
If WF(a, 0) = WF(i, j) Then
If WF(i, j + 1) = Empty And a <> i Then
Call follow(i, fo)
Else
For m = 0 To zj '判断WF(i,j+1)是不是终结符
If WF(i, j + 1) = ZJF(m) Then
For p = 0 To fo '判断WF(i,j+1)在F()中是否已经存在
If WF(i, j + 1) = F(p) Then
b = 1
Exit For
End If
Next p
If b = 1 Then
b = 0
Else
F(fo) = WF(i, j + 1)
fo = fo + 1
F(fo) = Empty
End If
c = 1
Exit For
End If
Next m
If c = 1 Then
c = 0
Else
For n = 0 To hs '查找WF(i,j+1)对应的非终结符在文法的第几行 [资料来源：http://www.THINK58.com]
If WF(i, j + 1) = WF(n, 0) Then
Call first(n, fo)
3.3分析表构造模块
在已经得到文法select集的前提下，以次为依据，对文法的三种类型的规则：A::=aβ型、A::=Dβ型、A::=ε型分别构造分析表，并用一个三维数组保存。形如FXB（y，x，z），其中，y表示分析表的第y行，x表示第x列，z表示第y行第x列所对应的格子中的第z个数据。
3.3.1构造文法分析表
在求解Select集完成后，结果按照非终结符放入分析表Y轴，没有出现在对应规则右部首部的终结符放入分析表Y轴，终结符放入分析表X轴等规则放置。如图5。

内容来自think58

[资料来源：THINK58.com]

[资料来源：http://THINK58.com]

think58

[资料来源：www.THINK58.com]

[资料来源：http://THINK58.com]

think58.com

[版权所有：http://think58.com]

本文来自think58 [资料来源：http://www.THINK58.com]

copyright think58 [资料来源：www.THINK58.com]

[版权所有：http://think58.com]

图5 分析表构造流程
3.3.2A::=aβ规则
对于A::=ab，(aÎVt)，则
令 LL(A,a)=R(b)/N
**R(b)/N：表示用b的逆串替换Ａ后，继续读入下一个符号。
当b为e时，即：A::=a，有：LL(A,a)=R(e)/N
3.3.3A::=Dβ规则
对于A::=Db，(DÎVn)，且有 Select(A::=Db)={b1,b2,…,bn} ，
则 LL(A,bi)=RDb)/P，(i=1,2,…,n)
**R(Db)/P：表示用Db的(逆串替换A后，重读当前符号
3.3.4A::=ε规则
对于A::=e，且有 Select(A::=e)= {b1,b2,…,bn}
则 LL(A, bi)=R(e)/P
3.4句子分析模块
本部分主要通过VB中的InputBox对话框读入待分析句子，并与分析表进行对照，逐步分析所输入的句子是否符合文法。分析过程均用一维数组进行保存。
相关程序片段如下：
程序中所用到的公有数据成员有：
Dim FXZ(50) As String '存放句子分析过程中的分析栈
Dim FHZ(50) As String '存放句子分析过程中的输入符号栈
3.4.1读取句子
Public Sub juzi_read(str As String) '读取句子
FHZ(0) = Empty
i = 0
a = Mid(str, 1, 1)
Do While a <> Empty 内容来自think58

[版权所有：http://think58.com]

FHZ(i) = a
a = Mid(str, i + 2, 1)
i = i + 1
FHZ(i) = Empty
Loop
If FHZ(0) = Empty Then
Exit Sub
End If
FHZ(i) = "#"
FHZ(i + 1) = Empty
Call fenxi_chr
End Sub
3.4.2分析句子
现在我们把句型的右端部分逆向放入一分析堆栈中，使x1成为栈顶，利用分析栈，当栈顶符号与输入串当前符号相匹配时，则从栈顶删除该符号。然后再把相应的规则逆向压入栈顶，替换原栈顶的非终结符。
Do While fenxibiao.FXB(i, j, k) <> Empty
Select Case fenxibiao.FXB(i, j, k)
Case "acc"
Exit Sub
Case "ε"
FXZ(a) = Empty
Case "/N"
FHZ(b) = " "
b = b + 1
a = a - 1
Exit For
Case "/P"
a = a - 1
Exit For
Case Else
FXZ(a) = fenxibiao.FXB(i, j, k)
a = a + 1
FXZ(a) = Empty
End Select
k = k + 1
Loop

[版权所有：http://think58.com]