精华内容
下载资源
问答
  • 编译原理FOLLOW集

    千次阅读 2020-05-27 14:26:45
    follow集求法有两种,要么逐步推导,推导出所有式子求follow集合,这种方法简单但是容易遗漏 要么就按照步骤一步一步来求 文字定义:FOLLOW(A)集合是所有紧跟A之后的终结符或#所组成的集合(#是句尾的标志),称...
    follow集求法有两种,要么逐步推导,推导出所有式子求follow集合,这种方法简单但是容易遗漏
    要么就按照步骤一步一步来求
    
    文字定义:FOLLOW(A)集合是所有紧跟A之后的终结符或#所组成的集合(#是句尾的标志),称FOLLOW(A)是A的随符集
    

    下面直接介绍规范的求法(这个文法必须消除左递归和提取公共左因子)

    计算所有非终结符号A的follow(A)集合时,不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。
    注意:当A是最右部的时候,将$加入到follow(A)中

    (1)将 $ 放到follow(S)中,其中S是文法的开始符号。

    (2)如果存在一个产生式A→αBβ,那么first(β)中除ε之外的所有符号都在follow(B)中。 【 follow(B)是求跟在B后的终结符或$组成的集合,因此对于跟在B后的β,它的first集合就是follow(B)的子集 】

    (3)如果存在一个产生式A→αB,或存在产生式A→αBβ且first(β)包含ε,那么follow(A)中的所有符号都在follow(B)中。 【 对于A→αBβ,且β多步推导出ε ,那么可以用αB替换A, B后面紧跟的字符就是A后面紧跟的字符】


    下面举个例子来按照这种方法求FOLLOW

    文法如下:

    1. E -> TE’
    2. E’ -> +TE’ | ε
    3. T -> FT’
    4. T’ -> *FT’ | ε
    5. F -> (E) | id

    直接给出First集
    first(E) = first(T) = first(F) = { ( , id }
    first(E’) = {+, ε}
    first(T’) = {*, ε}

    FOLLOW E
    E是文法的开始符号,根据规则 (1) 将$加入到 follow(E), follow(E) = { $ }, 
    再根据规则(2)和产生式 5) 加入, 所以 follow(E) = {$, )}
    

    FOLLOW E’

    根据产生式 1 , E'是结尾符号,所以将$加入follow(E’), 根据规则 (3) 和产生式 1,可知,将
    follow(E) 加入到 follow(E‘)中 ,所以 follow(E') = {$, )}
    

    FOLLOW T

     根据产生式 1 和 规则(2) ,first(E') - {ε}加入到follow(T)中,follow(T) = {+} , 
     再根据产生式 1 和规则(3),follow(E)加入到follow(T)中,所以follow(T) = {+, ), $}
    

    FOLLOW T’

    根据产生式 3 因为T'出现在最右部,所以{$}加入follow(T‘)中,再根据规则(3)和产生式3,
    将follow(T)加入到follow(T’)中,所以follow(T') = {+, ), $}
    

    FOLLOW F

    ① 根据产生式 3 和规则 (2),first(T')-{ε}加入到follow(F)中,follow(F) = {*}
    ② 产生式 3 和 规则 (3) ,将follow(T)加入到follow(F)中,follow(F) = {*,+,),$}
    ③ 再根据产生式 4 和规则(3)follow(T')加入follow(F) follow(F) = {+, ), *, $}
    ④ 根据产生式 4 和规则2first(T')加入到follow(F)中, follow(F) = {+,),*,$}
    
    实际上,我们回顾规则开头,当没有新的终结符加入时,不必对所有的式子都应用
    式子进行计算。
    
    展开全文
  • 对文法中的非终结符,first集和follow集
  • 编译原理实验-LL1语法分析器(自动生成First、Follow)java 博主在做实验时,参考众多他人代码,发现bug众多,在[@moni_mm]代码基础上,与伙伴把能看到的BUG都做出修正,同时增添了一个GUI展示。再次我将代码做出...

    编译原理实验-LL1语法分析器(自动生成First、Follow)java

    博主在做实验时,参考众多他人代码,发现bug众多,在@moni_mm代码基础上,与伙伴把能看到的BUG都做出修正,同时增添了一个GUI展示。再次我将代码做出讲解。完整代码最下方贴出。

    一、数据结构

    下文程序运行的文法为:

    static String[] grammarStr = {"E->TG" ,"G->+TG|-TG" ,"G->ε" ,"T->FS" ,"S->*FS|/FS" ,"S->ε" ,"F->(E)" ,"F->i"};//相关文法
    

    处理的输入串为:

    static inStr="i+i*i#";//输入串
    

    -----首先要考虑FOLLOW、FIRST、终结符、非终结符、预测分析表、栈、各个产生式的存储的数据结构设计:

    static HashMap<Character, HashSet<Character>> FirstSet  = new HashMap<>();//构造FIRST集合
    static HashMap<String, HashSet<Character>> FirstSetX  = new HashMap<>();//生成任何符号串的first
    static HashMap<Character, HashSet<Character>> FollowSet = new HashMap<>();//构造FOLLOW集合
    static String[][] table;//预测分析表
    static HashSet<Character> VnSet = new HashSet<>();//非终结符Vn集合
    static HashSet<Character> VtSet = new HashSet<>();//终结符Vt集合
    static Stack<Character>   stack = new Stack<>();  //符号栈
    static HashMap<Character,ArrayList<String>> production = new HashMap<>();//产生式
    

    二、运行效果

    LL(1)预测分析的实现均在类LL1中得到实现,类GUI仅仅将结果在桌面程序得到展示,LL1也可单独运行,结果输出控制台:

    运行GUI(注释掉LL1的main即可,反之亦然):

    在这里插入图片描述

    运行LL1:在这里插入图片描述

    在这里插入图片描述

    三、类的设计

    • class: LL1(打印相关不与介绍)

        - dividechar()     将产生式填充进production,划分终结符(vt)与非终结符(vn)
        - First()          生成FIRST集(非终结符的)
        - getFirstX()      生成FIRST集(任意字符串的),Follow()需要调用
        - Follow()         生成FOLLOW集
        - insert()         将生成式插入表中
        - creatTable()     创建预测分析表
        - find(char X, char a)   寻找预测分析表中对应内容,X非终结符,a终结符
        - processLL1()     执行LL1栈分析
      
    • class:GUI(可专注于LL1即可,本处简略)
      - Gui(String title) 添加组件,创建面板
      - class Listener implements ActionListener 时间监听器(添加具体执行语句,展示LL1.stepList、LL1.FirstSet、LL1.FollowSet的数据)

    三、核心算法(求first\follow)

    • 求First集:
      first集叫做首终结符集下面是博主自己的理解,用的列子讲的。在博主自己学的时候,不会的时候,死磕概念是看不懂的。额,博主菜ji.
      基本就两种情况:(终结符的first即它本身)
      • 1.直接遇到终结符
        A->aBCd | ε
        若a,e为终结符,first(A)= {a,ε}。
      • 2.第一个为非终结符
        A->BC
        此时first(A)=first(B);值得注意的是,若first(B)包含空ε,需要继续求first(C )加入first(A)中。若first(c)仍旧包含空ε,将空字符ε加入first(A)。
    • 程序实现:
       /**
       * 生成非终结符的FIRST集的递归入口
       */
      static void First(){
          //遍历求每一个非终结符vn的first集
          for (Character vn: VnSet
               ) {
              getfisrst(vn);
          }
      }
      /**
       * 生成非终结符FIRST集的递归程序
       */
      static void getfisrst(Character ch){
          ArrayList<String> ch_production = production.get(ch);
          HashSet<Character> set = FirstSet.containsKey(ch) ? FirstSet.get(ch) : new HashSet<>();
          // 当ch为终结符vt
          if(VtSet.contains(ch)){
              set.add(ch);
              FirstSet.put(ch,set);
              return;
          }
          //ch为非终结符vn
          for (String str:ch_production
               ) {
                  int i = 0;
                  while (i < str.length()) {
                      char tn = str.charAt(i);
                      //递归
                      getfisrst(tn);
                      HashSet<Character> tvSet = FirstSet.get(tn);
                      // 将其first集加入左部
                      for (Character tmp : tvSet) {
                          if (tmp != 'ε')
                              set.add(tmp);
                      }
                      // 若包含空串 处理下一个符号
                      if (tvSet.contains('ε'))
                          i++;
                          // 否则退出 处理下一个产生式
                      else
                          break;
                  }
                  //此处处理产生式如A ->BC,B、C的first集都有ε
                  if(i==str.length())
                      set.add('ε');
          }
          FirstSet.put(ch,set);
      }
      
      • 求follow集:
        课本上规则如下:
    1. 将放到follow(S)中,其中S是开始符号,#将放到follow(S)中,其中S是开始符号,而#是输入右端的结束标记。

    2. 如果存在一个产生式A→αBβ,那么first(β)中除ε之外的所有符号都在follow(B)中。

    3. 如果存在一个产生式A→αB,或存在产生式A→αBβ(β可以是单个非终结符,或数个非终结符的组合,β或许是CD)且first(β)包含ε,那么follow(A)中的所有符号都在follow(B)中。

    举例说明:
    ①E→TE’
    ②E’→+TE’ | ε
    ③T→FT’
    ④T’→*FT’ | ε
    ⑤F→(E)| id
    各个规则的展现:
    规则一:E是文法的开始符号,第一步,follow(E).add(’#’)
    规则二:对于产生式①E→TE’,follow(T).add(first(E’))
    规则三:对于产生式①E→TE’,E’后面为空,故follow(E’).add(follow(E));又first(E’)包含空ε,follow(T).add(follow(E))

    对每条产生式套用上述规则,循环至各个follow集都不增加。
    因为:例如对于产生式①E→TE’,first(E’)包含空ε,follow(T).add(follow(E)),而此时follow(E)并未求完整。需要第二遍。

    • 程序实现:
      /**
         * 生成FOLLOW集
         */
        static void Follow(){
            //此处我多循环了几次,合理的方法应该是看每一个非终结符的follow集师傅增加,不增加即可停止循环。
            for (int i = 0; i <3 ; i++) {
                for (Character ch:VnSet
                ) {
                    getFollow(ch);
                }
    
            }
    
        }
      /**
         * 求单个字符的FOLLOW集
         */
        static void getFollow(char c){
            ArrayList<String> list = production.get(c);
                HashSet<Character> setA = FollowSet.containsKey(c) ? FollowSet.get(c) : new HashSet<Character>();
            //如果是开始符 添加 #
            if (c == start) {
                setA.add('#');
            }
            //查找输入的所有产生式,确定c的后跟 终结符
            for (Character ch : VnSet) {
                ArrayList<String> l = production.get(ch);
                for (String s : l)
                    for (int i = 0; i < s.length(); i++)
                        if (s.charAt(i) == c && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                            setA.add(s.charAt(i + 1));
            }
            FollowSet.put(c, setA);
            //处理c的每一条产生式,从右向左分析,A->aBβ,
            for (String s : list) {
                int i = s.length() - 1;
                while (i >= 0 ) {
                    char tn = s.charAt(i);
                    //只处理非终结符
                    if(VnSet.contains(tn)){
                        // 都按 A->αBβ  形式处理
                        //若β不存在   followA 加入 followB
                        //若β存在,把β的非空first集  加入followB
                        //若β存在  且 first(β)包含空串   followA 加入 followB
    
                        //若β存在
                        if (s.length() - i - 1 > 0) {
                            String right = s.substring(i + 1);
                            //非空first集 加入 followB
                            HashSet<Character> setF = null;
                            if( right.length() == 1){
                                if(!FirstSet.containsKey(right.charAt(0)))
                                    getfisrst(right.charAt(0));
                                setF = FirstSet.get(right.charAt(0));
                            }
                            else{
                                //先找出右部的first集
                                if(!FirstSetX.containsKey(right))
                                    getFirstX(right);
                                setF =FirstSetX.get(right);
                            }
                            HashSet<Character> setX = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                            for (Character var : setF)
                                if (var != 'ε')
                                    setX.add(var);
                            FollowSet.put(tn, setX);
    
                            // 若first(β)包含空串   followA 加入 followB
                            if(setF.contains('ε')){
                                if(tn != c){
                                    HashSet<Character> setB =FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                                    for (Character var : setA)
                                        setB.add(var);
                                    FollowSet.put(tn, setB);
                                }
                            }
                        }
                        //若β不存在   followA 加入 followB
                        else{
                            // A和B相同不添加
                            if(tn != c){
                                HashSet<Character> setB = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                                for (Character var : setA)
                                    setB.add(var);
                                FollowSet.put(tn, setB);
                            }
                        }
                        i--;
                    }
                    //如果是终结符往前看  如 A->aaaBCDaaaa  此时β为 CDaaaa
                    else i--;
                }
            }
        }
    

    四、完整代码

    IDEA 工程文件放在github上:https://github.com/mhl222/BiYiYuanLi_2
    大家可直接git clone下来运行

    import javax.swing.*;
    import javax.swing.table.DefaultTableModel;
    import java.awt.*;
    import java.awt.event.ActionEvent;
    import java.awt.event.ActionListener;
    import java.util.*;
    /**
    * class:
    * --LL1:
    *      实现LL(1)分析,构造分析预测程序(FIRST集-->FOLLOW集-->分析预测表-->stack预测分析)
    * --Gui:
    *      读取输入串,桌面程序展示分析预测步骤
    */
    
    public class LL1 {
       static String[] grammarStr = {"E->TG" ,"G->+TG|-TG" ,"G->ε" ,"T->FS" ,"S->*FS|/FS" ,"S->ε" ,"F->(E)" ,"F->i"};//相关文法
       static HashMap<Character,ArrayList<String>> production = new HashMap<>();//产生式
       static HashMap<Character, HashSet<Character>> FirstSet  = new HashMap<>();//构造FIRST集合
       static HashMap<String, HashSet<Character>> FirstSetX  = new HashMap<>();//生成任何符号串的first
       static HashMap<Character, HashSet<Character>> FollowSet = new HashMap<>();//构造FOLLOW集合
       static String[][] table;//预测分析表
       static HashSet<Character> VnSet = new HashSet<>();//非终结符Vn集合
       static HashSet<Character> VtSet = new HashSet<>();//终结符Vt集合
       static Stack<Character>   stack = new Stack<>();  //符号栈
       static String inStr="i+i*i#";//输入串
       static Character start = 'E';
       static int index = 0;//输入字符指针
       static String action ="";
       static ArrayList<Vector>  stepList = new ArrayList<>();//与LL(1)无关,可不关心,为GUI记录了stack每一步的变化
       public static void main(String[] args) {
           dividechar();
           First();
           for (Character c : VnSet) {
               ArrayList<String> l = production.get(c);
               for (String s : l)
                  getFirstX(s);
           }
           Follow();
           creatTable();
           ouput();
           processLL1();
    
       }
    
       /**
        * 生成产生式Map(production),划分终结符(vt)与非终结符(vn)
        */
       static void dividechar(){
           //生成产生式Map(production)
           for (String str:grammarStr
                ) {
               //将“|”相连的产生式分开
               String[] strings = str.split("->")[1].split("\\|");
               //非终结符
               char Vch = str.charAt(0);
               ArrayList<String> list = production.containsKey(Vch) ? production.get(Vch) : new ArrayList<String>();
               for (String S:strings
                    ) {
                   list.add(S);
               }
               production.put(str.charAt(0),list);
               VnSet.add(Vch);
           }
           //寻找终结符
           for (Character ch:VnSet
               ){
               for (String str : production.get(ch)
                    ) {
                   for (Character c: str.toCharArray()
                   ) {
                       if( !VnSet.contains(c) )
                           VtSet.add(c);
                   }
               }
    
           }
    
       }
       /**
        * 生成非终结符的FIRST集的递归入口
        */
       static void First(){
           //遍历求每一个非终结符vn的first集
           for (Character vn: VnSet
                ) {
               getfisrst(vn);
           }
       }
       /**
        * 生成非终结符FIRST集的递归程序
        */
       static void getfisrst(Character ch){
           ArrayList<String> ch_production = production.get(ch);
           HashSet<Character> set = FirstSet.containsKey(ch) ? FirstSet.get(ch) : new HashSet<>();
           // 当ch为终结符
           if(VtSet.contains(ch)){
               set.add(ch);
               FirstSet.put(ch,set);
               return;
           }
           //ch为vn
           for (String str:ch_production
                ) {
                   int i = 0;
                   while (i < str.length()) {
                       char tn = str.charAt(i);
                       //递归
                       getfisrst(tn);
                       HashSet<Character> tvSet = FirstSet.get(tn);
                       // 将其first集加入左部
                       for (Character tmp : tvSet) {
                           if (tmp != 'ε')
                               set.add(tmp);
                       }
                       // 若包含空串 处理下一个符号
                       if (tvSet.contains('ε'))
                           i++;
                           // 否则退出 处理下一个产生式
                       else
                           break;
                   }
                   if(i==str.length())
                       set.add('ε');
           }
           FirstSet.put(ch,set);
       }
       /**
        * 生成任何符号串的first
        */
       static void getFirstX(  String s) {
    
               HashSet<Character> set = (FirstSetX.containsKey(s))? FirstSetX.get(s) : new HashSet<Character>();
               // 从左往右扫描该式
               int i = 0;
               while (i < s.length()) {
                   char tn = s.charAt(i);
                   if(!FirstSet.containsKey(tn))
                       getfisrst(tn);
                   HashSet<Character> tvSet = FirstSet.get(tn);
                   // 将其非空 first集加入左部
                   for (Character tmp : tvSet)
                       if(tmp != 'ε')
                           set.add(tmp);
                   // 若包含空串 处理下一个符号
                   if (tvSet.contains('ε'))
                       i++;
                       // 否则结束
                   else
                       break;
                   // 到了尾部 即所有符号的first集都包含空串 把空串加入
                   if (i == s.length()) {
                       set.add('ε');
                   }
               }
               FirstSetX.put(s, set);
    
    
       }
       /**
        * 生成FOLLOW集
        */
       static void Follow(){
           //此处我多循环了几次,合理的方法应该是看每一个非终结符的follow集师傅增加,不增加即可停止循环。
           for (int i = 0; i <3 ; i++) {
               for (Character ch:VnSet
               ) {
                   getFollow(ch);
               }
    
           }
    
       }
       static void getFollow(char c){
           ArrayList<String> list = production.get(c);
               HashSet<Character> setA = FollowSet.containsKey(c) ? FollowSet.get(c) : new HashSet<Character>();
           //如果是开始符 添加 #
           if (c == start) {
               setA.add('#');
           }
           //查找输入的所有产生式,确定c的后跟 终结符
           for (Character ch : VnSet) {
               ArrayList<String> l = production.get(ch);
               for (String s : l)
                   for (int i = 0; i < s.length(); i++)
                       if (s.charAt(i) == c && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                           setA.add(s.charAt(i + 1));
           }
           FollowSet.put(c, setA);
           //处理c的每一条产生式
           for (String s : list) {
               int i = s.length() - 1;
               while (i >= 0 ) {
                   char tn = s.charAt(i);
                   //只处理非终结符
                   if(VnSet.contains(tn)){
                       // 都按 A->αBβ  形式处理
                       //若β不存在   followA 加入 followB
                       //若β存在,把β的非空first集  加入followB
                       //若β存在  且 first(β)包含空串   followA 加入 followB
    
                       //若β存在
                       if (s.length() - i - 1 > 0) {
                           String right = s.substring(i + 1);
                           //非空first集 加入 followB
                           HashSet<Character> setF = null;
                           if( right.length() == 1){
                               if(!FirstSet.containsKey(right.charAt(0)))
                                   getfisrst(right.charAt(0));
                               setF = FirstSet.get(right.charAt(0));
                           }
                           else{
                               //先找出右部的first集
                               if(!FirstSetX.containsKey(right))
                                   getFirstX(right);
                               setF =FirstSetX.get(right);
                           }
                           HashSet<Character> setX = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                           for (Character var : setF)
                               if (var != 'ε')
                                   setX.add(var);
                           FollowSet.put(tn, setX);
    
                           // 若first(β)包含空串   followA 加入 followB
                           if(setF.contains('ε')){
                               if(tn != c){
                                   HashSet<Character> setB =FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                                   for (Character var : setA)
                                       setB.add(var);
                                   FollowSet.put(tn, setB);
                               }
                           }
                       }
                       //若β不存在   followA 加入 followB
                       else{
                           // A和B相同不添加
                           if(tn != c){
                               HashSet<Character> setB = FollowSet.containsKey(tn) ? FollowSet.get(tn) : new HashSet<Character>();
                               for (Character var : setA)
                                   setB.add(var);
                               FollowSet.put(tn, setB);
                           }
                       }
                       i--;
                   }
                   //如果是终结符往前看  如 A->aaaBCDaaaa  此时β为 CDaaaa
                   else i--;
               }
           }
       }
       /**
        * 生成预测分析表
        */
       static void creatTable(){
           Object[] VtArray = VtSet.toArray();
           Object[] VnArray = VnSet.toArray();
           // 预测分析表初始化
           table = new String[VnArray.length + 1][VtArray.length + 1];
           table[0][0] = "Vn/Vt";
           //初始化首行首列
           for (int i = 0; i < VtArray.length; i++)
               table[0][i + 1] = (VtArray[i].toString().charAt(0) == 'ε') ? "#" : VtArray[i].toString();
           for (int i = 0; i < VnArray.length; i++)
               table[i + 1][0] = VnArray[i] + "";
           //全部置error
           for (int i = 0; i < VnArray.length; i++)
               for (int j = 0; j < VtArray.length; j++)
                   table[i + 1][j + 1] = "error";
    
           //插入生成式
           for (char A : VnSet) {
               ArrayList<String> l = production.get(A);
               for(String s : l){
                   HashSet<Character> set = FirstSetX.get(s);
                   for (char a : set)
                       insert(A, a, s);
                   if(set.contains('ε'))  {
                       HashSet<Character> setFollow = FollowSet.get(A);
                       if(setFollow.contains('#'))
                           insert(A, '#', s);
                       for (char b : setFollow)
                           insert(A, b, s);
                   }
               }
           }
       }
       /**
        * 将生成式插入表中
        */
       static void insert(char X, char a,String s) {
           if(a == 'ε') a = '#';
           for (int i = 0; i < VnSet.size() + 1; i++) {
               if (table[i][0].charAt(0) == X)
                   for (int j = 0; j < VtSet.size() + 1; j++) {
                       if (table[0][j].charAt(0) == a){
                           table[i][j] = s;
                           return;
                       }
                   }
           }
       }
    
       /**
        * 返回当前栈内容的字符串,与LL(1)无关,为GUI提供字符串
        *
        */
       static String getStack(){
           String str ="";
           for (Character ch : stack
                ) {
               str+=ch;
           }
           return str;
       }
    
       /**
        * 与LL(1)无关,为GUI的表格所需的setpList,提供一行数据
        */
       static void addRowToList(String production,String action){
           Vector v = new Vector();
           v.add(stepList.size()+1);
           v.add(getStack());
           v.add(inStr.substring(index));
           v.add(production);
           v.add(action);
           stepList.add(v);
       }
    
       /**
        * 执行LL1栈分析
        */
       static void processLL1(){
           System.out.println("****************LL分析过程**********");
           System.out.println("               Stack           Input     Action");
           stack.push('#');
           stack.push('E');
           addRowToList("","");//GUI数据,可不关心
           displayLL();
           char X = stack.peek();
           while (X != '#') {
               char a = inStr.charAt(index);
               if (X == a) {
                   action = "match " + stack.peek();
                   stack.pop();
                   index++;
                   addRowToList("","POP,GETNEXT(I)");//GUI数据,可不关心
    
               }
    //            }else if (VtSet.contains(X))
    //                return;
               else if (find(X, a).equals("error")){
                   boolean flag = false;
                   if(FirstSet.get(X).contains('ε')){
    
                       addRowToList(X+"->ε","POP");//GUI数据,可不关心
                       action = X+"->ε";
                       stack.pop();
                       flag = true;
                   }
                   if(!flag){
                       action="error";
                      addRowToList("","ERROR");//GUI数据,可不关心
                       displayLL();
                       return;
                   }
    
               }
               else if (find(X, a).equals("ε")) {
                   stack.pop();
                   action = X + "->ε";
                   addRowToList(action,"POP");//GUI数据,可不关心
               }
               else {
                   String str = find(X, a);
                   if (str != "") {
                       action = X + "->" + str;
                       stack.pop();
                       int len = str.length();
                       String pushStr="";
                       for (int i = len - 1; i >= 0; i--){
                           stack.push(str.charAt(i));
                           pushStr+=str.charAt(i);
                       }
                       addRowToList(action,"POP,PUSH("+pushStr+")");//GUI数据,可不关心
                   }
                   else {
                       System.out.println("error at '" + inStr.charAt(index) + " in " + index);
                       return;
                   }
               }
               X = stack.peek();
               displayLL();
           }
           System.out.println("analyze LL1 successfully");
           System.out.println("****************LL分析过程**********");
       }
    
       /**
        *
        * @param X 非终结符
        * @param a 终结符
        * @return  预测分析表中对应内容
        */
       static String find(char X, char a) {
           for (int i = 0; i < VnSet.size() + 1; i++) {
               if (table[i][0].charAt(0) == X)
                   for (int j = 0; j < VtSet.size() + 1; j++) {
                       if (table[0][j].charAt(0) == a)
                           return table[i][j];
                   }
           }
           return "";
       }
       static void displayLL() {
           // 输出 LL1单步处理
           Stack<Character> s = stack;
           System.out.printf("%23s", s);
           System.out.printf("%13s", inStr.substring(index));
           System.out.printf("%10s", action);
           System.out.println();
       }
       /**
        * 打印first.follow集,预测分析表
        */
       static void ouput() {
           System.out.println("*********first集********");
           for (Character c : VnSet) {
               HashSet<Character> set = FirstSet.get(c);
               System.out.printf("%10s",c + "  ->   ");
               for (Character var : set)
                   System.out.print(var);
               System.out.println();
           }
           System.out.println("**********first集**********");
    
           System.out.println("**********follow集*********");
    
           for (Character c : VnSet) {
               HashSet<Character> set =FollowSet.get(c);
               System.out.print("Follow " + c + ":");
               for (Character var : set)
                   System.out.print(var);
               System.out.println();
           }
           System.out.println("**********follow集**********");
    
           System.out.println("**********LL1预测分析表********");
    
           for (int i = 0; i < VnSet.size() + 1; i++) {
               for (int j = 0; j < VtSet.size() + 1; j++) {
                   System.out.printf("%6s", table[i][j] + " ");
               }
               System.out.println();
           }
           System.out.println("**********LL1预测分析表********");
       }
    }
    class Gui extends JFrame {
       static JButton btnLL1 = new JButton("LL(1)分析");
       static JTextField input = new JTextField("i+i*i#",8);
       static JLabel label = new JLabel("输入串:");
       static JLabel first = new JLabel("FIRST:");
       static JLabel follow = new JLabel("FOLLOW:");
       static JLabel tit = new JLabel("---------------      LL(1)单步     -------------");
       static JPanel contentPanel = new JPanel();
    
       static Vector row= new Vector();;
       static Vector row2= new Vector();
       static Vector row3= new Vector();
       static Vector columnNames2 = new Vector() ;
       static Vector columnNames1 = new Vector() ;
       static JTable table3;
       static JTable table2;
       static JTable table;
    
    //    public static void main(String[] args) {
    //        new Gui("LL1");
    //    }
       public Gui(String title) throws HeadlessException {
    
           super(title);
           setSize(550,500);
           setResizable(false);
    
           contentPanel.setLayout(null);
           columnNames1.add("步骤");
           columnNames1.add("分析栈");
           columnNames1.add( "剩余输入串");
           columnNames1.add("所用产生式");
           columnNames1.add("动作");
           table = new JTable(row,columnNames1);
           JScrollPane scrollPane1 = new JScrollPane(table);
    
    
    
           columnNames2.add("非终结符");
           columnNames2.add("结果");
           table2 = new JTable(row2,columnNames2);
           JScrollPane scrollPane2 = new JScrollPane(table2);
           table3 = new JTable(row3,columnNames2);
           JScrollPane scrollPane3 = new JScrollPane(table3);
           contentPanel.add(btnLL1);
           contentPanel.add(input);
           contentPanel.add(label);
           contentPanel.add(first);
           contentPanel.add(follow);
           contentPanel.add(scrollPane1);
           contentPanel.add(scrollPane2);
           contentPanel.add(scrollPane3);
           contentPanel.add(tit);
    
           label.setBounds(5,5,110,30);
           input.setBounds(70,8,100,25);
           btnLL1.setBounds(180,8,100,25);
           first.setBounds(5,40,110,30);
           follow.setBounds(280,40,110,30);
           tit.setBounds(150,180,300,30);
           scrollPane1.setBounds(5,220,520,200);
           scrollPane2.setBounds(5,70,250,100);
           scrollPane3.setBounds(280,70,250,100);
           btnLL1.addActionListener(new Listener());
    
           this.add(contentPanel);
           this.setVisible(true);
           this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    
       }
    
       class Listener implements ActionListener {
    
           @Override
           public void actionPerformed(ActionEvent actionEvent) {
    
               if(actionEvent.getSource()==btnLL1){
                   String in = input.getText();
                   LL1.inStr = in;
                   LL1.dividechar();
                   LL1.First();
    
                   for (Character ch:LL1.VnSet
                        ) {
                       HashSet<Character> firset = LL1.FirstSet.get(ch);
                       String token = "";
                       for (Character c:firset
                            ) {
                           token+=c;
                       }
                       Vector vc = new Vector();
                       vc.add(ch);
                       vc.add(token);
                       ((DefaultTableModel)Gui.table2.getModel()).addRow(vc);
                   }
                   for (Character c : LL1.VnSet) {
                       ArrayList<String> l = LL1.production.get(c);
                       for (String s : l)
                           LL1.getFirstX(s);
                   }
                   LL1.Follow();
                   for (Character chr:LL1.VnSet
                   ) {
                       HashSet<Character> firset = LL1.FollowSet.get(chr);
                       String token1 = "";
                       for (Character c:firset
                       ) {
                           token1+=c;
                       }
                       Vector vc1 = new Vector();
                       vc1.add(chr);
                       vc1.add(token1);
                       ((DefaultTableModel)Gui.table3.getModel()).addRow(vc1);
                   }
                   LL1.creatTable();
                   LL1.processLL1();
    
                   for (Vector vc2: LL1.stepList
                        ) {
                       ((DefaultTableModel)Gui.table.getModel()).addRow(vc2);
                   }
    
    
    
    
               }
           }
       }
    
    }
    
    展开全文
  • 编译原理FIRST集和FOLLOW集

    千次阅读 多人点赞 2019-06-18 17:16:41
    编译原理FIRST集和FOLLOW集法 由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了...

    编译原理FIRST集和FOLLOW集的求法

    由于最近要期末考试了,所以要从头到尾复习(预习)一遍了。陈意云老师写的课本比较抽象,看不太懂,最后又找了中科大的编译原理课,可能听的时候太困了没有集中精力,又跑去看了以前曾经看过的哈工大的公开课,应该是看懂了,所以就厚颜无耻的来捋一捋,欢迎交流,批评指正。

    废话不多说,直接看怎么计算的吧。
    首先看FIRST集,文字描述如下:

    1.FIRST(X):可以从X推导出的所有串首终结符构成的集合
    如果X=>*ε,那么ε∈FIRST(X)

    举个栗子

    表达式FIRST集FOLLOW集
    E -> TE’{}{}
    E’-> +TE’|ε{}{}
    T-> FT’{}{}
    T’->*FT’|ε{}{}
    F-> (E)|id{}{}

    我是这样做的,首先看有终结符的表达式F-> (E)|id可以得到FIRST(F)={(, id};
    再看有终结符的表达式T’->FT’|ε,得到FIRST(T’)={*, ε}
    再看E’-> +TE’|ε,得到FIRST(E’)={+ , ε},所得得到以下结果:

    表达式FIRST集FOLLOW集
    E -> TE’{}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’{}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    然后再从头看每个表达式可以得到FIRST(E)=FIRST(T),所以去求FIRST(T);
    所以来看表达式T-> FT’,得到FIRST(T)=FIRST(F),又因为F无法推导出ε,所以FIRST(T)=FIRST(F);
    同理可得FIRST(E)=FIRST(T)=FIRST(F)
    所以表就更新为以下结果:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    这时候,我们FIRST集就已经求完了,接下来看FOLLOW集:
    同样先来文字描述:

    FOLLOW(A):可能在某个句型中紧跟在A后边的终结符a的集合
    FOLLOW(A)={a| S=>*αAaβ, a∈VT, α,β∈(VT∪VN)*
    如果A是某个句型的最右符号,则将结束符“$”添加到FOLLOW(A)中。

    还是上面的栗子:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}{}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}{}
    F-> (E)|idFIRST(F)={(, id}{}

    我是首先找处在句子最右边的非终结符有哪些,由上面的表达式可以看出,分别有E’、T’所以首先把"$"填进去:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}{}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$}
    T-> FT’FIRST(T)={(, id}{}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$}
    F-> (E)|idFIRST(F)={(, id}{}

    然后从头开始看,首先看E,先直观的看E后面跟有哪些终结符;很容易可以看到有“)”;
    又因为E为开始符号,所以FOLLOW(E)中有“$”符
    再看T,T后面跟的是E’,所以FOLLW(T)要包含FIRST(E’);又由于E’可以推导出空串,所以T也可以是最右符号;
    再看T’,T’首先是最右符号,所以FOLLOW(T)包含结束符;
    最后看F,F后面跟的是T’,所以FOLLOW(F)包含FIRST(T’),又由于T’可以推导出空串,所以F也可以是最右符号
    所以得到以下列表:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $}

    接下来再看有表达式推导得到的FOLLOW集是否发生改变:
    又由于E->TE’,所以FOLLOW(E)=FOLLOW(E’);
    又因为T->FT’,所以FOLLOW(T)=FOLLOW(T’)
    所以有些FOLLOW集需要更新如下所示:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$, )}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$, +}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $}

    再看有些表达式能够推出空串,所以右边非终结符的FOLLW集合需包含左边非终结符的FOLLW集合,如E -> TE’,由于E’能够推导出空串,所以FOLLW(T)要包含FOLLW(E),根据这条规则,对FOLLW集做以下更新:

    表达式FIRST集FOLLOW集
    E -> TE’FIRST(E)={(, id}FOLLOW(E)={), $}
    E’-> +TE’|εFIRST(E’)={+ , ε}FOLLOW(E’)={$, )}
    T-> FT’FIRST(T)={(, id}FOLLOW(T)={+, $, )}
    T’->*FT’|εFIRST(T’)={*, ε}FOLLOW(T’)={$, +, )}
    F-> (E)|idFIRST(F)={(, id}FOLLOW(F)={*, $, +,)}

    总结

    FIRST集没什么问题,很好求,但是FOLLOW集合想对就比较麻烦,需要考虑的地方比较多,在做题目的时候千万不要遗漏!
    欢迎批评指正,交流。

    展开全文
  • 编译原理中Follow集

    万次阅读 多人点赞 2018-05-29 11:16:36
    首先引用龙书里面的一段较为公式化的follow集求法的话: 计算所有非终结符号A的follow(A)集合时,不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。 (1)将放到follow(S)中,...

    经过前阵子的各种百度以及对课本的反复研究,终于弄明白了follow集的求法,下面记录一下!

    首先引用龙书里面的一段较为公式化的follow集求法的话:

    计算所有非终结符号A的follow(A)集合时,不断应用下面的规则,直到再没有新的终结符号可以被加入到任意的follow集合中为止。

    (1)将放到follow(S)中,其中S是开始符号,而放到follow(S)中,其中S是开始符号,而是输入右端的结束标记。

    (2)如果存在一个产生式A→αBβ,那么first(β)中除ε之外的所有符号都在follow(B)中。

    (3)如果存在一个产生式A→αB,或存在产生式A→αBβ且first(β)包含ε,那么follow(A)中的所有符号都在follow(B)中。

    下面举个例子来说明下,假设有如下文法:

    ①E→TE’

    ②E’→+TE’ | ε

    ③T→FT’

    ④T’→*FT’ | ε

    ⑤F→(E)| id

    对于每个非终结符号,我们都可以求出其follow集:

    根据(1),首先将加入到follow(E)中,即follow(E)={加入到follow(E)中,即follow(E)={},由⑤可知,)也应该在follow(E)中,即follow(E)={$,)};

    对于E’,根据规则(3)以及产生式①,应该将follow(E)加入到follow(E‘)中,即follow(E’)={$,)};

    对于T,根据规则(2)以及产生式①,应该将first(E’)加入到follow(T)中,即follow(T)={+},根据规则(3),由于first(E’)包含ε,所以应该将follow(E)加入到follow(T)中,即follow(T)={+,$,)};

    对于T’,根据规则(3)以及产生式③,应该将follow(T)加入到follow(T‘)中,即follow(T’)={+,$,)};

    对于F,根据规则(2)以及产生式③,应该将first(T’)加入到follow(F)中,即follow(F)={},根据规则(3),由于first(T’)包含ε,所以应该将follow(T)加入到follow(F)中,即follow(F)={,+,$,)};

    展开全文
  • 求FOLLOW集例题详细步骤

    万次阅读 多人点赞 2019-06-22 19:49:48
    例如:对下面的文法G: E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’ F’→*F’|ε P→(E)|a|b|∧ ...求FOLLOW集的方法: (1)对文法的开始符号 S,置‘#’于FOLOOW(S)中; ...
  • 编译原理的FIRST集和FOLLOW集~~有兴趣的可以看一下,有漏了一个条件,不过注明出来了~~
  • First集和Follow集
  • ( 编译原理JAVAFirst集Follow集
  • 求Follow集:对每个非终结符,找出分别紧跟它们的所有第一个终结符或$组成的集合,例如 F --> ( E ) | id,E 后面紧跟了 ) ,所以它的Follow集里面一定有 ),Follow集最后一定要加上 $ 例如下面的文法 E --> T...
  • 编译原理 First集和Follow集

    千次阅读 2018-04-19 19:05:35
    自上而下分析:FIRST集求法 First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的...
  • 给定文法,构造FIRST集、FOLLOW集的构造的C代码和我个人的实验报告
  • 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合 输入任意的上下文无关文法,输出所输入的上下文无关文法一切非终结符的first集合和follow集合
  • 编译原理用C语言first集sellect集follow集,最后,判断给出的文法是否是LL(1)文
  • FIRST集求法参照篇①添加链接描述 本篇参考链接:添加链接描述 FOLLOW集 ① FOLLOW(A)可能在某个句型中紧跟在A后边的终结符的集合,若A是某句型的最右符号,则将结束符#添加到 FOLLOW(A)中。 ②若存在A→...
  • 复习 | First集和Follow集

    千次阅读 2020-12-22 17:53:56
    这篇文章记录First集和Follow集法。
  • 编译原理FIRST集、FOLLOW集和SELECT集

    万次阅读 多人点赞 2019-07-02 15:29:50
    觉得解释比较不错。 所有大写字母代表非终结符,小写字母代表终结符,省略号代表未知数目(可能为0)的不确定类型的文法符号。 First集合: First集合顾名思义就是一个文法符号串所...First集合可分如下几...
  • 一、FIRST FIRST(A)为A的开始符或者首符号。 1、定义: 设G=(VT,VN,S,P)是上下文无关文法 ,FIRST(α)={a|α能推导出aβ,a∈VT,α,β∈V*} 特别的,若α能推导出ε,则规定ε∈FIRST(α). 2、根据定义求解...
  • 如何First集与Follow集(超详细)

    千次阅读 多人点赞 2020-12-23 18:16:37
    如何First集与Follow集 已知文法如下,First集与Follow集 G[E]:E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣i G[E]: E{\rightarrow} TE' \\ {\quad\quad\quad\quad\quad}E'{\rightarrow}+TE'|\var...
  • 编译原理:First集和Follow集

    千次阅读 2018-10-25 22:16:04
    #输入文法First集和Follow集 #要求大写字母表示非终结符,小写字母表示终结符 #最后一个产生式以$结尾或者输入$表示输入结束 #默认第一个产生式的→左边为起始符号 def inputGrammer(): #接收文法输入的函数 ...
  • 编译原理FIRST集和FOLLOW集法以及构建LL(1)分析表

    万次阅读 多人点赞 2019-07-01 10:57:57
    文章目录FIRST集的FOLLOW集的计算生成预期分析表算法例题 FIRST集的法 FIRST集是一个文法符号串所可能推导出的符号串的第一个终结符的集合 对于文法G的任一符号串α\alphaα = x1x2…xnx_{1}x_{2} \ldots x_{n...
  • 博文链接:https://zpchen.iteye.com/blog/208947
  • 计算first集和follow集

    2012-06-04 19:53:51
    编译实验中一文法的first集和follow集
  • FIRST集和FOLLOW集法FIRST集步骤FOLLOW集步骤 FIRST集 步骤 若X->a…,则将终结符a加入FIRST(X)中; 若X->e ,则将终结符e加入FIRST(X)中(e表示空集); 若 X->BC…D,则将First(B)所有元素(除了空集...
  • 构造预测分析表 源程序 #include<stdlib.h> #include<stdio.h> #include<string.h> /*/ int count=0; /* 分解的产生式的个数 */ int number; /* 所有终结符和非终结符的总数 */ char start; /* 开始符号 */ char ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,100
精华内容 11,640
关键字:

follow集怎么求