LL1 first follow集.docVIP

 课 程 名 称: LL1文法的判别 年级/专业/班: 11级计算机类（二）班 姓 名: 徐勇兵 学 号： 一、α / β, α 和β均以非终结符开始，那么就很难决定何时使用A→α 选项，何时使用A→β选项。 二、实验 三、实验aβ，a∈VT，α,β∈V *}。 若αε，ε∈FIRST（α）。 由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。 设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1； 若xi∈VT，则xi∈FIRST（α）； 若xi∈VN； ① 若εFIRST（xi），则FIRST（xi）∈FIRST（α）； ② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）； i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若εFIRST（xi）或in为止。 当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。 设文法G[S]＝（VN，VT，P，S），则 FOLLOW（A）＝{a | S… Aa …，a∈VT}。 若S…A，#∈FOLLOW（A）。 由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。 FOLLOW集可按下列方法求得： 对于文法G[S]的开始符号S，有#∈FOLLOW（S）； 若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）； 若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）； import java.util.Vector; import javax.swing.JOptionPane; class Tools{ public VectorString protection(VectorString vs){ VectorString newvector=new VectorString(); for(int i=0;ivs.size();i++) newvector.add(vs.get(i)); return newvector; } public VectorVectorString doubleprotection(VectorVectorString vs){ VectorVectorString newvector=new VectorVectorString(); for(int i=0;ivs.size();i++){ VectorString produce=(VectorString)vs.get(i); VectorString temp=new VectorString(); for(int j=0;jproduce.size();j++){ temp.add((String)produce.get(j)); }//for j newvector.add(temp); }//for i return newvector; } } class Elements{ VectorString end=new VectorString();//表示终结符 VectorString noend=new VectorString();//表示非终结符 VectorVectorString produce=new VectorVectorString();//产生式 public void setend(){//终结符元素添加 while(true) { String s=JOptionPane.showInputDialog(null,请输入终结符); if(s==null) { return; }//if end.add(s); }//while }//public void addend(){//元素添加 public void setnoend(){//非终结符元素添加 while(true) {