计算文法的firstvt集和lastvt集

《计算文法的firstvt集和lastvt集》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、renwairen369@yahoo.com.cn计算文法的FIRSTVT集和LASTVT集1.问题分析本题目和第三题都属于自下而上语法分析中算符优先分析算法相关的程序。计算非终结符的FIRSTVT集和LASTVT集是构造算符优先分析表的基础，而算符优先分析表的构造又是算符优先分析算法的基础。因此，本程序的实现可以说是算符优先分析算法实现的基础。FIRSTVT集和LASTVT集的定义如下：FIRSTVT(B)={b

2、Bb…或BCb…}LASTVT(B)={a

3、B…a或B…aC}2.基本算法构造集合FIRSTVT(P)的算法按FIRSTVT(P)的定义，可以用如下两条归则来构造：(1)

4、若有产生式Pàa…或àQa…，则a∈FIRSTVT(P)(2)若a∈FIRSTVT(Q)，且有产生式PàQ…，则a∈FIRSTVT(P)构造算法：建立一个二维布尔数组F[P,a]，使得F[P,a]为真的条件适当且仅当a∈FIRSTVT(P);构造算法再用一个栈STACK，把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放到栈中；算法如下：(1)将布尔矩阵各元素置假；栈置空；(2)按照归则(1)查看产生式，对于Pàa…或PàQa..，置相应F[P,a]为真，符号对(P,a)入栈；(3)按规则(2)，对栈施加如下操作：弹出栈定符号对记作(Q,a)，查看所有产生式是否有形如PàQ

5、…产生式，若有，且a∈FIRSTVT(P)，则将F[P,a]置为真，并把(P,a)入栈；(4)重复(3)，直到栈空为止。用类似的方法来构造LASTVT(P)可根据LASTVT(P)的定义来构造，两条规则：(1)若有产生式Pà…a或à…aQ，则a∈LASTVT(P)(2)若a∈LASTVT(P)，且有产生式Pà…Q，则a∈LASTVT(P)构造算法同FIRSTVT(P)的构造算法3.基本数据结构在程序中，用两个字符数组vn[M]和vt[N]分别用来存储所有的非终结字符集与终结字符集。为了记录非终结符的FIRSTVT集和LASTVT集，为此建立两个布尔数组By张焕人renwairen36

6、9@yahoo.com.cnF[M][N]和L[M][N]，分别记录非终结符的FIRSTVT集和LASTVT集。比如，F[i][j]=true表示vt[j]属于FIRSTVT(vn[i])，L[i][j]=true表示vt[j]属于LASTVT(vn[i])，值为false表示相应的终结符不属于非终结符的FIRSTVT集和LASTVT集。为了简便起见，程序中又构造了两个两维布尔数组first[M][M+N]和last[M][M+N]来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代表终结符。以first数组为例，fist[i][M+j]

7、代表非终结符vn[i]=P与非终结符vt[j]=a有推导关系Pàa…；fist[i][j]代表非终结符vn[i]=P与非终结符vt[j]=Q有推导关系或PàQa..。相关的数据结构定义如下：charvn[M],vt[N];//非终结字符与终结字符数组boolfirst[M][M+N],last[M][M+N];//以布尔数组形式定义推导关系charvn[M],vt[N];//非终结字符与终结字符数组intstp;//堆栈栈顶指针符号栈的数据结构：structrelation//结构体用来说明终结符vt与非终结符vn之间的关系，若关系存在说明vt属于FIRSTVT(vn)或LASTVT

8、(vn){intvn;intvt;};1.语法定义本程序中采用如下语法进行分析：E->E+T

9、TT->T*F

10、FF->P^F

11、PP->(E)

12、i在进行求解之前，首先要进行如下的初始化：vt[0]='+';vt[1]='*';vt[2]='^';vt[3]='(';vt[4]=')';vt[5]='i';vn[0]='E';vn[1]='T';vn[2]='F';vn[3]='P';first[0][1]=true;//vn[1]为vn[0]推导出的第一个非终结字符first[0][M]=true;//vt[0]为vn[0]推导出的第一个终结字符first[1][2]=true;//v

13、n[2]为vn[1]推导出的第一个非终结字符first[1][M+1]=true;//vt[1]为vn[1]推导出的第一个终结字符first[2][3]=true;//vn[3]为vn[2]推导出的第一个非终结字符first[2][M+2]=true;//vt[2]为vn[2]推导出的第一个终结字符first[3][M+3]=true;//vn[3]为vn[3]推导出的第一个终结字符first[3][M+5]=true;//vn[5]为vn[3]推导出的第