编译原理LL1文法分析表算法实现

简介:

import hjzgg.first.First;
import hjzgg.follow.Follow;
import hjzgg.tablenode.TableNode;
import hjzgg.treenode.TreeNode;

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

public class AnalysisTable {
    private final int noFinalCharacterCount = 100;
    private Map<String, Integer>stringToInt = new TreeMap<String, Integer>();//分析表行 列 字母映射到数字
    private Map<Integer, String>tableRow = new TreeMap<Integer, String>();//分析表 行列 数字 映射到字母
    private Map<Integer, String>tableCol = new TreeMap<Integer, String>();
    private String[][] table = new String[noFinalCharacterCount][];//分析表
    private Set<Character>terminalCharacters = new TreeSet<Character>();//终结符集合
    private Map<String, Set<Character>> first = null;
    private Map<String, Set<Character>> follow = null;
    private Map<String, String[]> mp = null;
    private int nodeCntRow = 0, nodeCntCol=0;
    
    public static final int treeNodeCnt = 200;//树最多节点的个数
    private int cntTreeNode = 0;
    private ArrayList<String> usedProduction = new ArrayList<String>();//预测分析中所用到的产生式
    private int fatherNode;//treeGraphic搜素是的开始节点
    private TreeNode[] treeGraphic = new TreeNode[treeNodeCnt];
    
    private String[] analysisStack = null;
    public String[] getAnalysisStack(){
        return analysisStack;
    }
    
    public Map<String, Integer> getStringToInt(){
        return stringToInt;
    }
    public Set<Character> getTerminalCharacters(){
        return terminalCharacters;
    }
    
    public int getFatherNode(){
        return fatherNode;
    }
    
    public TreeNode[] getTreeGraphic(){
        return treeGraphic;
    }
    
    public AnalysisTable(Map<String, Set<Character>> first,
            Map<String, Set<Character>> follow, Map<String, String[]> mp) {
        super();
        this.first = first;
        this.follow = follow;
        this.mp = mp;
        init();
    }
    
    private void init(){
        for(String leftNode : mp.keySet()){
            stringToInt.put(leftNode, ++nodeCntRow);
            tableRow.put(nodeCntRow, leftNode);
            String[] rightNodes = mp.get(leftNode);
            for(int i=0; i<rightNodes.length; ++i){//枚举每一个产生式
                for(int j=0; j<rightNodes[i].length(); ++j)
                    if(!mp.containsKey(""+rightNodes[i].charAt(j)) && rightNodes[i].charAt(j)!='\'' && rightNodes[i].charAt(j)!='$'){//每一个终结符
                        if(!stringToInt.containsKey(""+rightNodes[i].charAt(j))){
                            stringToInt.put(""+rightNodes[i].charAt(j), ++nodeCntCol);
                            terminalCharacters.add(rightNodes[i].charAt(j));
                            tableCol.put(nodeCntCol, ""+rightNodes[i].charAt(j));
                        }
                    }
            }
        }
        stringToInt.put("#", ++nodeCntCol);
        tableCol.put(nodeCntCol, "#");
        terminalCharacters.add('#');
    }
    
    public ArrayList<TableNode> analysisTableKernealCode(){
        for(String leftNode : mp.keySet()){
            String[] rightNodes = mp.get(leftNode);
            for(int i=0; i<rightNodes.length; ++i){//枚举每一个产生式
                for(Character terminal : terminalCharacters){//每一个终结符
                        char finalCharacter = terminal;
                        Set<Character> productionFirstSet = new TreeSet<Character>();//产生式对应first集
                        for(int k=0; k<rightNodes[i].length(); ++k){
                            String node = ""+rightNodes[i].charAt(k);
                            if(k+1 < rightNodes[i].length() && rightNodes[i].charAt(k+1)=='\''){
                                node += '\'';
                                ++k;
                            }
                            if(mp.containsKey(node)){//非终结符
                                productionFirstSet.addAll(first.get(node));
                                if(!first.get(node).contains('$')) break;
                            } else {//终结符
                                productionFirstSet.add(node.charAt(0));
                                break;
                            }
                        }
                        
                        if(productionFirstSet.contains(finalCharacter)){//A->@ 对于每一个终结符 a属于FIRST(@),加入M[A, a]
                            int col = stringToInt.get(""+finalCharacter);
                            int row = stringToInt.get(leftNode);
                            if(table[row]==null)
                                table[row] = new String[nodeCntCol+1];
                            table[row][col] = leftNode + "->" + rightNodes[i];
                        }
                        
                        /***********************************************************************/
                        else if(productionFirstSet.contains('$')){//A->@ 对于$属于First(@),对任何b属于Follow(A)则把A->@加入
                            if(follow.get(leftNode).contains(finalCharacter)){
                                int col = stringToInt.get(""+finalCharacter);
                                int row = stringToInt.get(leftNode);
                                if(table[row]==null)
                                    table[row] = new String[nodeCntCol+1];
                                table[row][col] = leftNode + "->" + rightNodes[i];
                            }
                        }
                }
            }
        }
        return printTalbe();
    }
    
    public ArrayList<TableNode> printTalbe(){
        ArrayList<TableNode> tableNodeAl = new ArrayList<TableNode>();
        System.out.println("分析表如下:");
        for(int i=1; i<=nodeCntRow; ++i){
            for(int j=1; j<=nodeCntCol; ++j)
                if(table[i]!=null && table[i][j]!=null){
                    tableNodeAl.add(new TableNode(i, j, table[i][j]));
                    System.out.println(tableRow.get(i) + ":" + tableCol.get(j) + "   " + table[i][j]);
                }
        }
        return tableNodeAl;
    }
    
    public boolean predictiveAnalysis(String formula){
        ArrayList<String>stringStack = new ArrayList<String>();
        System.out.println("开始进行预测分析,分析栈如下:");
        Stack<String> stack = new Stack<String>(); 
        stack.push("#");
        stack.push(tableRow.get(1));
        int formulaIndex = 0;
        char a = formula.charAt(formulaIndex++);
        boolean flag = false;
        while(true){
            if(stack.size() == 0){
                //error
                break;
            }
            stringStack.add(stack.toString());
            System.out.println(stack);
            String x = stack.pop();
            if(!mp.containsKey(x)){//终结符
                if(x.charAt(0)==a){
                    if(a=='#'){
                        flag = true;
                        break;
                    }
                    a = formula.charAt(formulaIndex++);
                } else {
                    //error
                }
            } else {//非终结符
                if(table[stringToInt.get(x)] != null){
                    String production = table[stringToInt.get(x)][stringToInt.get(""+a)];
                    if(production != null){
                        usedProduction.add(production);
                        if(!production.contains("$")){//X->X1X2X3....Xk 中 Xk....X3X2X1压入栈中
                            for(int i=production.length()-1; i>=0; --i){
                                if(production.charAt(i)=='>') break;
                                if(production.charAt(i)=='\''){
                                    stack.push(""+production.charAt(i-1)+production.charAt(i));
                                    --i;
                                } else{
                                    stack.push(""+production.charAt(i));
                                }
                            }
                        }
                    } else {
                        //error
                    }
                } else {
                    //error
                }
            }
        }
        analysisStack = stringStack.toArray(new String[stringStack.size()]);
        return flag;
    }
    
    private int produceAnalysisTree(int curRow, String preNode){
        String curProduction = usedProduction.get(curRow);
        String splits[] = curProduction.split("->");
        if(preNode != null && !preNode.equals(splits[0])) 
            return produceAnalysisTree(curRow+1, preNode);
        TreeNode treeNode = new TreeNode();
        treeNode.content = splits[0];
        for(int i=0; i<splits[1].length(); ++i){//右部的产生式
            String node = "" + splits[1].charAt(i);
            if(i+1<splits[1].length() && splits[1].charAt(i+1)=='\''){
                node += '\'';
                ++i;
            }
            if(!mp.containsKey(node)){//不是 非终结点
                TreeNode tmpTreeNode = new TreeNode();
                tmpTreeNode.content = node;
                treeNode.child.add(cntTreeNode);//加入孩子节点
                treeGraphic[cntTreeNode++] = tmpTreeNode;
            } else {//非终结点
                int childNodeCnt = produceAnalysisTree(curRow+1, node);//得到这个孩子的节点
                treeNode.child.add(childNodeCnt);
            }
        }
        treeGraphic[cntTreeNode] = treeNode;
        return cntTreeNode++;
    }
    
    private void printAnalysisTree(int curNode){
        System.out.print(" " + treeGraphic[curNode].content);
        for(int i=0; i<treeGraphic[curNode].child.size(); ++i)
            printAnalysisTree(treeGraphic[curNode].child.get(i));
    }
    
    public void AnalysisTree(){
        fatherNode = produceAnalysisTree(0, null);
        System.out.println("分析树的先序遍历如下:");
        printAnalysisTree(fatherNode);
    }
    
    public static void main(String[] args) {
        
//        String[] rightLinearGrammar ={
//                "S->iCtSA|a",
//                "A->$|eS", 
//                "C->b"
//        };
        
        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();
            Follow follow = new Follow(mp, first.getFirstSet());
            follow.followKernealCode();
            AnalysisTable analysisTable = new AnalysisTable(first.getFirstSet(), follow.getFollowSet(), mp);
            analysisTable.analysisTableKernealCode();
            
            analysisTable.predictiveAnalysis("i+i#");
            analysisTable.AnalysisTree();
    }

}

目录
相关文章
|
6月前
|
网络安全
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
411 1
|
6月前
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
116 0
|
6月前
编译原理——构造预测分析表(判断某字符串是否是文法G(E)的句子)
编译原理——构造预测分析表(判断某字符串是否是文法G(E)的句子)
60 0
编译原理实验:NFA转化为DFA
编译原理实验:NFA转化为DFA
174 0
|
6月前
|
存储 编译器 测试技术
【编译原理】LL(1)分析法:C/C++实现
【编译原理】LL(1)分析法:C/C++实现
524 0
|
6月前
|
存储 算法 Python
Python 数据结构和算法: 解释动态规划的概念,并提供一个实际应用的例子。
Python 数据结构和算法: 解释动态规划的概念,并提供一个实际应用的例子。
43 0
|
机器学习/深度学习 算法 搜索推荐
【数据结构】时间复杂度(详细解释,例子分析,易错分析,图文并茂)
【数据结构】时间复杂度(详细解释,例子分析,易错分析,图文并茂)
409 0
|
存储 Go C语言
编译原理,C语言实现LR(0)分析(扩展文法的生成、项目集规范簇的生成、ACTION GOTO表的生成、句子的分析)
注:代码生成的项目集规范簇、ACTION GOTO表的顺序可能和课本、教材、参考答案的顺序不同,但这并不影响分析过程的正确性,毕竟机器是按规律办事的😄
475 0
编译原理,C语言实现LR(0)分析(扩展文法的生成、项目集规范簇的生成、ACTION GOTO表的生成、句子的分析)
|
存储 算法
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成)
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成)
815 0
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成)