LL1 first follow集

《LL1 first follow集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程名称:LL1文法的判别年级/专业/班:11级计算机类（二）班姓名:徐勇兵学号：E01114278一、背景资料如果一个文法具有以下两个特点：（1）每个产生式的右部都由终结符开始；（2）如果两个产生式有相同的左部，那么他们的右部则由不同的终结符开始。显然对于这样的文法，其推导过程完全可以根据当前的输入符号，决定选哪个产生式往下推导，分析过程是惟一确定的，可以采用不带回溯的自上而下的预测分析方法。如果两个产生式的左部相同，而右部都由非终结符开始，例如，存在A→α/β,α和β均以非终结符开始，那么就很难决定何时使用A→α选项，何时使用A→β选项。二、实验目的要求输入：

2、任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合和其空表以及对是否是LL1的判别。三、实验原理设文法G[S]＝（VN，VT，P，S），则首字符集为：FIRST（α）＝{a

3、αaβ，a∈VT，α,β∈V*}。若αε，ε∈FIRST（α）。由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设α＝x1x2…xn，FIRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1）若xi∈VT，则xi∈FIRST（α）；（2）若xi∈VN；①

4、若εFIRST（xi），则FIRST（xi）∈FIRST（α）；②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或i>n为止。当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法G[S]＝（VN，VT，P，S），则FOLLOW（A）＝{a

5、S

6、…Aa…，a∈VT}。若S…A，#∈FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V*，则FIRST（y）－{ε}∈FOLLOW（A）；（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；importjava.util.Vector;impor

7、tjavax.swing.JOptionPane;classTools{publicVectorprotection(Vectorvs){Vectornewvector=newVector();for(inti=0;i>doubleprotection(Vector>vs){Vector

8、ring>>newvector=newVector>();for(inti=0;iproduce=(Vector)vs.get(i);Vectortemp=newVector();for(intj=0;j

9、ments{Vectorend=newVector();//表示终结符Vectornoend=newVector();//表示非终结符Vector>produce=newVector>();//产生式publicvoidsetend(){//终结符元素添加while(true){Strings=JOptionPane.showInputDialog(null,"请输入终结符");if(s==null){return;}//ifend.add(

10、s);}/