《编译原理课程设计》LL1文法判定.docx
《《编译原理课程设计》LL1文法判定.docx》由会员分享，可在线阅读，更多相关《《编译原理课程设计》LL1文法判定.docx（30页珍藏版）》请在冰点文库上搜索。
《编译原理课程设计》LL1文法判定
目录
1前言1
2需求分析1
3概要设计（特殊功能）1
4详细设计2
5源代码及调试2
6使用说明及测试结果11
7结论12
8总结与体会12
9参考文献12
1前言
1.1课题简介
试编写一个程序，用来计算给定文法的全部FIRST集及FOLLOW集，并判定所给文法是否LL
（1）文法，掌握消除左递归及消除回溯的方法，掌握LL
（1）分析器的基本结构及FIRST集、FOLLOW集、LL
（1）分析表的构造方法，能根据文法写出给定输入串的自下而上分析过程。
1.2方案及其论证
LL
（1）文法使用的是确定的自顶向下的分析技术。
LL
（1）的含义是：
第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则）进行推导。
LL
（1）文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL
（1）文法,最后再进行句子分析。
2需求分析
本次课程设计要求编写一个程序，用来计算给定文法的全部FIRST集及FOLLOW集，并判定所给文法是否LL
（1）文法。
首先要面临一个问题就是本次程序具体实现的是一个内部给定的正确文法，其次是依次计算FIRST集、FOLLOW集和SELLECT集，然后判断是否为LL
（1）文法,最后再进行句子分析。
终结符，非终结符，FIRST集，FOLLOW集，SELLECT集和LL
（1）分析表对于课程设计LL
（1）问题的解决是特别的重要，计算出FIRST集、FOLLOW集和SELLECT集后，后面LL
（1）分析表的构造以及判断文法是否为LL
（1）文法就很容易解决了。
3概要设计（特殊功能）
3.1系统结构图
3.2主要控制流程
改造文法
无
4详细设计
4.1词法分析程序的实现
由于本程序简单，所以依次扫描遇到的每一个字符即可确定哪些是终结符哪些是非终结符。
4.2语法分析程序的实现
4.2.1能推出$的非终结符
首先进行第一次扫描，把能够直接推出$的非终结符号记录到空串表，把不能直接推出$的符号依次记录下来，然后单个扫描每一个不能直接推出$的符号。
扫描这个符号能够直接推出的第一个非终结符记录到一个队列，接下来依次检查队列中每一个元素，把二次能够推出$的符号记录到空串表，把二次也推不出空串的继续送入到队列，然后再从队列取元素扫描，直到队列为空没能找到能够星推导出$的终结符，那么可以确定这个非终结符推导不出$，接下去扫描下一个非终结符。
4.2.2FIRST集的确定
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）
其中第1-3个方法都很好处理，关键是第四个方法判断时首先判断第一个字符为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，接下去依次扫描产生式右部每一个字符Yi，假如第i个字符可以推出空，那么就把这个字符的FIRST集去除$加入到产生式左部字符的FIRST集中，即FIRST（Yi）-{$}
FIRST（X）,假如Yi是终结符或者不可以推出$，那么就把这个字符的FIRST集直接加入到FIRST（X）中，即FIRST（Yi）
FIRST（X）同时置FLAG为FALSE不再向下扫描，假如Yi恰好是最后一个字符，那么不管它能不能星推导出空都直接把它的FIRST集加入到FIRST（X）中。
同时要设置一个队列和一组布尔型变量记录FIRST集是否完成，队列用来记录FIRST（X）用到了哪些其它非终结符的FIRST集。
第一遍扫描完成后就扫描队列，把FIRST集完成的非终结符的FIRST集加入到那些没有完成的非终结符的FIRST集中去，没有完成的非终结符再送回到队列，这时候可能出现死循环，比如FIRST（S）用到了FIRST（A）,而FIRST（A）用到了FIRST（B），FIRST（B）又用到了FIRST（S）,这时候S,A,B的FIRST标志均为FALSE，无限循环下去。
这时候可以记录一下，比如循环了100次，强行设置FIRST（S）的标志为TRUE，那么FIRST（A）,FIRST（B）也就依次可以求出了。
我们在实际计算时也是这样处理的，只是没有把标志写出来而是记录在心里的。
对于100次循环或许有些多了，那么到极限情况，可能就是循环总共产生式的个数次数时如果再循环就可以确定是进入死循环了。
4.2.3FOLLOW集的确定
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集一样的方法处理就可以。
4.2.4SELLECT集的确定
FIRST集＆FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：
A→αA∈VN，α∈V*，
（1）、若α是终结符，那么SELLECT（A→α）={α}；
（2）、若α是$，则SELECT（A→α）=FOLLOW（A）；
（3）、若α是非终结符，那么
若α*=>$，则SELECT（A→α）=（FIRST（α）-$）∪FOLLOW（A）；
若α┐*=>$则SELECT（A→α）=FIRST（α）。
4.2.5LL
（1）文法的判定
当SELLECT集求出来后就可以判断是不是一个文法是不是LL
（1）文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相同元素则返回TRUE。
4.3句子的判定
当一个文法确定是LL
（1）文法时就可以对输入的语句进行判定了。
首先要安装SELLECT集生成LL
（1）预测分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。
这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。
在实际分析时设置两个栈，把"#"压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。
5源代码及调试
frmMain.cs主要算法：
#region主要步骤
#region得到FIRST集
///
///得到FIRST集
///
///ArrayList
publicArrayListFirstSet（）
{
ArrayList[]lstFirst=newArrayList[LeftItem.Count];
ArrayListlstItems=newArrayList（）;
QueuequeueFirst=newQueue（）;
for（inti=0;i{
lstFirst[i]=newArrayList（）;
Productproduct=（Product）LeftItem[i];
//分成四步求FIRST集式SELECT集
//1.如果X属于VT则FIREST（X）={X}
if（SymbolSet.getInstance（）.IsInEndSet（product.LeftItem））
{
lstFirst[i].Add（product.LeftItem）;
}
else
{
lstFirst[i]=newArrayList（）;
//以此检测每一个右部
for（intj=0;j{
//2.如果X属于VN且有产生式X->a...,a属于VT,则a属于FIREST（X）
stringstrFirstLetter=product.StringRightItemAt（j）.Substring（0,1）;
if（SymbolSet.getInstance（）.IsInEndSet（strFirstLetter））
{
if（!
Tools.IsInList（strFirstLetter,lstFirst[i]））
lstFirst[i].Add（strFirstLetter）;
//Console.Write（strFirstLetter+"x"）;
}
//3.如果X推出$,则$属于FIRST（X）
if（Tools.IsInList（product.LeftItem,emptyList））
{
if（!
Tools.IsInList（"$",lstFirst[i]））
{
lstFirst[i].Add（"$"）;
//if（i==1）Console.WriteLine（"bbbbbbbbb"）;
//Console.Write（"$0"）;
}
}
//4.如果产生式的右部的每一个字符都是非终结符集
if（product.CheckRightItemAt（j））
{
stringstrRightTemp=product.StringRightItemAt（j）;
if（CheckEmptySymbol（strRightTemp.Substring（0,1）））
{
for（intl=0;l{
boolbNext=true;
if（CheckEmptySymbol（strRightTemp.Substring（l,1））&&bNext）
{
stringstrQueueElement="";
if（l==strRightTemp.Length-1）
{
strQueueElement=product.LeftItem+product.StringRightItemAt（j）.Substring（l,1）;
//Console
}
else
strQueueElement=product.LeftItem+product.StringRightItemAt（j）.Substring（l,1）+"$";
if（!
Tools.IsInQueue（strQueueElement,queueFirst））
{
queueFirst.Enqueue（strQueueElement）;
Console.WriteLine（strQueueElement+"\txp"）;
}
}
else
{
bNext=false;
stringstrQueueElement=product.LeftItem+product.StringRightItemAt（j）.Substring（l,1）;
if（!
Tools.IsInQueue（strQueueElement,queueFirst））
{
queueFirst.Enqueue（strQueueElement）;
Console.WriteLine（strQueueElement+"\txp"）;
}
}
}
}
else
{
stringstrQueueElement=product.LeftItem+product.StringRightItemAt（j）.Substring（0,1）;
if（!
Tools.IsInQueue（strQueueElement,queueFirst））queueFirst.Enqueue（strQueueElement）;
Console.WriteLine（strQueueElement+"\txp"）;
}
}
else
{
//假如产生式的右部并非都是非终结符
//那么取出第一个字符,假如是终结符,那么在上面的第2步里就已经计算过了,所以不用再计算
//假如是非终结符就假如到待取队列
if（SymbolSet.getInstance（）.IsInNotEndSet（product.StringRightItemAt（j）.Substring（0,1）））
{
stringstrQueueElement=product.LeftItem+product.StringRightItemAt（j）.Substring（0,1）;
if（!
Tools.IsInQueue（strQueueElement,queueFirst））queueFirst.Enqueue（strQueueElement）;
Console.WriteLine（strQueueElement+"\txp"）;
}
}
}//endforj
}//endifIsInEndSet（X）
}//endfori
lstItems=FinishFirst（lstFirst,queueFirst）;
returnlstItems;
}
#endregion
#region完成FIRST集计算,把未求出FIRST集的非终结符求出
publicArrayListFinishFirst（ArrayList[]FirstList,QueuequeueFirst）
{
//初始化标记数组
bool[]FirstFinished=newbool[FirstList.Length];
for（inti=0;i{
FirstFinished[i]=true;
}
//将队列中元素依次取出,将出现的元素标记为false,意为这个FIRST集未求出
for（inti=0;i{
stringstrQueue=queueFirst.Dequeue（）.ToString（）;
intiLeftIndex=getLeftIndex（strQueue.Substring（0,1））;
FirstFinished[iLeftIndex]=false;
queueFirst.Enqueue（strQueue）;
}
//防止死循环,最高循环100次强行退出
intiOutException=0;
while（queueFirst.Count>0&&iOutException!
=100）
{
iOutException++;
//首先取出队列中的一个元素
stringstrQueue=queueFirst.Dequeue（）.ToString（）;
//获取队列元素相关信息
intiPos1=getLeftIndex（strQueue.Substring（0,1））;
intiPos2=getLeftIndex（strQueue.Substring（1,1））;
//假如右部的FIRST集已经求出,那么就把右部的FIRST集加入到左部FIRST
if（FirstFinished[iPos2]）
{
ArrayListnextArray=FirstList[iPos2];
if（strQueue.Length==3）
{
FirstList[iPos2].Remove（"$"）;
}
FirstList[iPos1]=Tools.AddArrayList（FirstList[iPos1],FirstList[iPos2]）;
if（strQueue.Length==3&&this.CheckEmptySymbol（strQueue.Substring（1,1）））
{
FirstList[iPos2].Add（"$"）;
}
//假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出
if（Tools.IsQueueElement（strQueue,0,1,queueFirst）==false）
FirstFinished[iPos1]=true;
}
else
{
queueFirst.Enqueue（strQueue）;
}
}
ArrayListaryFirst=newArrayList（）;
foreach（ArrayListarylstinFirstList）
{
aryFirst.Add（arylst）;
}
returnaryFirst;
}
#endregion
#region得到FOLLOW集
///
///得到FOLLOW集
///
///需要把FIRST集传入
///ArrayList
publicArrayListFollowSet（ArrayListaryFirst）
{
if（LeftItem.Count==0）returnnull;
ArrayList[]lstFollow=newArrayList[LeftItem.Count];
ArrayList[]lstFirst=Tools.ConvertToArray（aryFirst）;
ArrayListlstItems=newArrayList（）;
Stack[]RemoveList=newStack[LeftItem.Count];
QueuequeueFollow=newQueue（）;
stringstrStartLetter=this.listboxProducts.Items[0].ToString（）.Substring（0,1）;
bool[]iFollowFinished=newbool[LeftItem.Count];
for（inti=0;i{
//初始化标记位
iFollowFinished[i]=true;
//初始化Follow集
lstFollow[i]=newArrayList（）;
RemoveList[i]=newStack（）;
}
//FOLLOW集的求法（规定第一个产生式的第一个字符式开始符）
//1.如果X是开始符那么把#加入到FOLLOW（X）
lstFollow[0].Add（"#"）;
//第一次进行扫描,把符合条件的符号和FIRST集,FOLLOW集全部加入
for（inti=0;i{
Productproduct=（Product）LeftItem[i];
lstFollow[i]=FollowLetter（product.LeftItem,lstFollow[i]）;
//扫描同时把能够替换FIRST集,FOLLOW集的先替换
intFollo
升级会员 