编译原理LL1文法Follow集算法实现

import hjzgg.first.First;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class Follow {
    private Map<String, Set<Character>> first = null;
    private Map<String, Set<Character>> follow = new TreeMap<String, Set<Character>>();
    private Map<String, String[]> mp = null;
    public Follow(Map<String, String[]> mp, Map<String, Set<Character>> first) {
        super();
        this.first = first;
        this.mp = mp;
    }
    
    public Map<String, Set<Character>> getFollowSet(){
        return follow;
    }
    
    private void getFirstSet(Set<Character> st, String node, int k){
        if(k >= node.length()) return;
        if(node.charAt(k)=='\'') --k;
        String nextNode = "" + node.charAt(k);
        if(k+1<node.length() && node.charAt(k+1)=='\''){
            nextNode += '\'';
            ++k;
        }
        if(!mp.containsKey(nextNode)){//终结点
            st.add(nextNode.charAt(0));
        } else {
            st.addAll(first.get(nextNode));
            if(first.get(nextNode).contains('$'))
                getFirstSet(st, node, k+1);
        }
    }
    
    private void findFollow(String curNode){
        Set<Character> st = null;
        for(String leftNode : mp.keySet()){
            String rightNodes[] = mp.get(leftNode);
            for(int i=0; i<rightNodes.length; ++i){
                int index = rightNodes[i].indexOf(curNode, 0);
                while(index != -1){
                    int nextIndex = index + 1;
                    if(curNode.length()==1 && index+1<rightNodes[i].length() && rightNodes[i].charAt(index+1)=='\''){
                        index = rightNodes[i].indexOf(curNode, nextIndex);
                        continue;
                    }
                    index = index+curNode.length();
                    if(index == rightNodes[i].length()){//末尾的非终结点, A->@B
                        if(follow.get(leftNode) == null)
                            findFollow(leftNode);
                        if(follow.get(curNode) == null){
                            st = new TreeSet<Character>();
                            st.addAll(follow.get(leftNode));
                            follow.put(curNode, st);
                        }
                        else follow.get(curNode).addAll(follow.get(leftNode));
                    } else {
                        String nextNode = ""+rightNodes[i].charAt(index);
                        if(index+1 < rightNodes[i].length() && rightNodes[i].charAt(index+1)=='\''){
                            nextNode += '\'';
                            ++index;
                        }
                        if(mp.containsKey(nextNode)){//非终结符
                            if(first.get(nextNode).contains(new Character('$'))){//A->@B&, 而 &->$
                                if(follow.get(leftNode) == null)
                                    findFollow(leftNode);
                                if(follow.get(curNode) == null){
                                    st = new TreeSet<Character>();
                                    st.addAll(follow.get(leftNode));
                                    follow.put(curNode, st);
                                }
                                else follow.get(curNode).addAll(follow.get(leftNode));
                            } 
                            
                            //好特殊的情况啊....
                            {//A->@B&, First(&)^$ 放入follow(B)
                                Set<Character> tmpSt = new TreeSet<Character>();
                                getFirstSet(tmpSt, rightNodes[i], index);
                                tmpSt.remove('$');
                                if(follow.get(curNode) == null){
                                    st = new TreeSet<Character>();
                                    st.addAll(tmpSt);
                                    follow.put(curNode, st);
                                }
                                else follow.get(curNode).addAll(tmpSt);
                            }
                        } else {//终结符
                            if(follow.get(curNode) == null){
                                st = new TreeSet<Character>();
                                st.add(nextNode.charAt(0));
                                follow.put(curNode, st);
                            }
                            else follow.get(curNode).add(nextNode.charAt(0));
                        }
                    }
                    index = rightNodes[i].indexOf(curNode, nextIndex);
                }
            }
        }
    }
    
    public String followKernealCode(){
         String content = "";
         boolean flag = true;
         for(String leftNode : mp.keySet()){
             if(flag){
                 Set<Character> st = new TreeSet<Character>();
                 st.add('#');
                 follow.put(leftNode, st);
                 flag = false;
             }
             findFollow(leftNode);
         }
         //打印first集合
         System.out.println("Follow 集合如下:");
         for(Map.Entry<String, Set<Character>> entry : follow.entrySet()){
             content += entry.getKey() + "  :  " + entry.getValue() + "\n";
             System.out.println(entry.getKey() + "  :  " + entry.getValue());
         }
         return content;
    }
    
    public static void main(String[] args) {
        String[] rightLinearGrammar = {
            "E->TE\'",
            "E\'->+TE\'|$",
            "T->FT\'",
            "T\'->*FT\'|$",
            "F->(E)|i"
        };
        
//        String[] rightLinearGrammar = {
//                "S->ABc",
//                "A->a|$",
//                "B->b|$"
//        };
        
        Map<String, String[]> mp = new LinkedHashMap<String, String[]>();
        try{
            for(int i=0; i<rightLinearGrammar.length; ++i){
                String split1[] = rightLinearGrammar[i].split("->");
                String split2[] = split1[1].split("\\|");
                mp.put(split1[0], split2);
            }
            
        } catch(Exception e){
            e.printStackTrace();
            System.out.println("右线性文法错误!");
        }
        First first = new First(mp);
        first.firstKernealCode();
        new Follow(mp, first.getFirstSet()).followKernealCode();
    }

}

        

          
        
        
        

          

          AI 代码解读