import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;

import javafx.util.Pair;

public class Ref {
    /**
     * 终结符
     */
    private Vector<String> T = new Vector<>();
    /**
     * 非终结符
     */
    private Vector<String> NT = new Vector<>();
    /**
     * 产生式
     */
    private HashMap<String, Vector<String>> production = new HashMap<>();



        /**
     * 读取文法
     * 终结符非终结符
     *
     * @param fileName 路径
     */
    public void readGrammar(String fileName) {
        File file = new File(fileName);
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(file));
            String line = null;
            while ((line = reader.readLine()) != null) {
                System.out.println("line: " + line);
                //添加文法
                String[] lr = line.split("->");
                String[] rs = lr[1].split("\\|");
                Vector<String> rights = new Vector<>();
                for (String right : rs) {
                    rights.add(right.trim());
                }
                production.put(lr[0].trim(), rights);
                addNt(lr[0].trim());
            }
            System.out.println("文法: " + production);
            System.out.println("非终结符：" + NT);
            addN();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    /**
     * 添加非终结符
     */
    private void addNt(String left) {
        if (!NT.contains(left)) {
            NT.add(left);
        }
    }
    /**
     * 添加终结符
     */
    private void addN() {
        for (String left : production.keySet()) {
            for (String right : production.get(left)) {
                String[] strs = right.split(" ");
                for (String str : strs) {
                    if (NT.contains(str) || T.contains(str)) {
                        continue;
                    } else {
                        T.add(str);
                    }
                }
            }
        }
        System.out.println("终结符：" + T);
    }


        /**
     * 判断右部第一个字符是否为Ai
     *
     * @param right 右部
     * @param Ai    字符
     * @return True包含 False不包含
     */
    private boolean isFirst(String right, String Ai) {
        String[] strs = right.trim().split(" ");
        return Ai.trim().equals(strs[0].trim());
    }
    /**
     * 字符替换
     *
     * @param right 右部
     * @param Ai    旧字符
     * @param newAi 新字符
     * @return 新字符串
     */
    private String replaceLast(String right, String Ai, String newAi) {
        String newRight = "";
        String[] strs = right.trim().split(" ");
        for (String str : strs) {
            if (str.equals(Ai) || " ".equals(str)) {
                continue;
            }
            newRight += str + " ";
        }
        newRight += newAi;
        return newRight.trim();
    }
    /**
     * 字符替换
     *
     * @param right 右部
     * @param Ai    旧字符
     * @param newAi 新字符
     * @return 新字符串
     */
    private String replace(String right, String Ai, String newAi) {
        String newRight = "";
        String[] strs = right.trim().split(" ");
        for (String str : strs) {
            if (str.equals(Ai)) {
                newRight += newAi + " ";
                continue;
            } else if (" ".equals(str)) {
                continue;
            }
            newRight += str + " ";
        }
        return newRight.trim();
    }	

/**
     * 消除立即左递归
     *
     * @param Ai 字符
     */
    private void eliminateImmediateLeftRecursion(String Ai) {
        String newAi = Ai + "'";
        NT.insertElementAt(newAi, NT.indexOf(Ai));
        Vector<String> rights1 = new Vector<>();
        Vector<String> rights2 = new Vector<>();
        for (String right : production.get(Ai)) {
            if (isFirst(right, Ai)) {
                String newRight = replaceLast(right, Ai, newAi);
                rights2.add(newRight);
            } else {
                String newRight = right.trim() + " " + newAi;
                rights1.add(newRight);
            }
        }
        rights2.add("$");
        production.replace(Ai, rights1);
        production.put(newAi, rights2);
    }
    /**
     * 消除左递归
     * 产生式 无环 和 $
     */
    public void eliminateLeftRecursion() {
        for (int i = 0; i < NT.size(); i++) {
            String Ai = NT.get(i);
            //新的右部
            Vector<String> newIrights = new Vector<>();
            for (String iRight : production.get(Ai)) {
                //iRight是否包含aj
                boolean flag = false;
                for (int j = 0; j < i; j++) {
                    String Aj = NT.get(j);
                    if (isFirst(iRight, Aj)) {
                        flag = true;
                        for (String jRight : production.get(Aj)) {
                            String newIright = replace(iRight, Aj, jRight);
                            newIrights.add(newIright);
                        }
                    }
                }
                //未替换 加入原来的右部
                if (!flag) {
                    newIrights.add(iRight);
                }
            }
            //i==0时，newIrights未维护
            if (i != 0) {
                production.replace(Ai, newIrights);
            }
            //消除直接左递归
            for (String iRight : production.get(Ai)) {
                if (isFirst(iRight, Ai)) {
                    eliminateImmediateLeftRecursion(Ai);
                    i++;
                    break;
                }
            }
        }
        System.out.println("新文法:" + production);
    }


    /**
     * 产生式树
     */
    private HashMap<String, TreeNode> productionTree = new HashMap<>();


    /**
     * 建立产生式树
     */
    public void buildProductionTree() {
        for (String left : production.keySet()) {
            TreeNode root = new TreeNode();
            for (String right : production.get(left)) {
                String[] strs = right.split(" ");
                addProductionToTree(root, strs, 0);
            }
            productionTree.put(left, root);
        }
        System.out.println("产生式树：" + productionTree);
    }
    /**
     * 添加产生式到树结点
     *
     * @param root  树结点
     * @param right 产生式
     * @param i     产生式位置
     */
    private void addProductionToTree(TreeNode root, String[] right, int i) {
        if (right[0].equals("$")) {
            return;
        }
        if (i == right.length) {
            root.isLast = true;
            return;
        }
        for (TreeNode childNode : root.childNodes) {
            if (childNode.nodeVal.equals(right[i])) {
                addProductionToTree(childNode, right, i + 1);
                return;
            }
        }
        TreeNode newChildNode = new TreeNode();
        newChildNode.nodeVal = right[i];
        root.childNodes.add(newChildNode);
        addProductionToTree(newChildNode, right, i + 1);
    }


/**
     * 判断是否包含前缀
     *
     * @param right
     * @param prefix
     * @return
     */
    private boolean isPrefix(String right, String prefix) {
        String[] str1 = right.trim().split(" ");
        String[] str2 = prefix.trim().split(" ");
        if(str2.length>str1.length)
        {
            return false;
        }
        for (int i = 0; i < str2.length; i++) {
            if (!str1[i].equals(str2[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 提取左公因子 获得新文法
     */
    public void leftFactoring() {
        for (int i = 0; i < NT.size(); i++) {
            String left = NT.elementAt(i);
            if (productionTree.containsKey(left)) {
                getLeftFactorProduction(left, productionTree.get(left), "");
            }
        }
        System.out.println("新文法：" + production);
    }
    /**
     * 获取产生式最大公共前缀
     *
     * @param left   非终结符
     * @param root   树节点
     * @param prefix 前缀
     * @return 占有公共前缀结点数量
     */
    private int getLeftFactorProduction(String left, TreeNode root, String prefix) {
        int total = 0;
        for (TreeNode childNode : root.childNodes) {
            total += getLeftFactorProduction(left, childNode, prefix.trim() + " " + childNode.nodeVal);
        }
        if (root.isLast) {
            total++;
        }
        if (total >= 2) {
            total = 1;
            if (!prefix.equals("")) {
                updateProduction(left, prefix);
            }
        }
        return total;
    }
    /**
     * 更新产生式
     *
     * @param left   非终结符
     * @param prefix 前缀
     */
    private void updateProduction(String left, String prefix) {
        String newLeft = left + "'";
        while (NT.contains(newLeft)) {
            newLeft += "'";
        }
        NT.insertElementAt(newLeft, NT.indexOf(left) + 1);
        Vector<String> rights1 = new Vector<>();
        Vector<String> rights2 = new Vector<>();
        for (String right : production.get(left)) {
            //匹配到前缀
            if (isPrefix(right, prefix)) {
                String newRight = prefix.trim() + " " + newLeft;
                if (!rights1.contains(newRight)) {
                    rights1.add(newRight.trim());
                }
                String tmp = right.replaceFirst(prefix.trim(), "").trim();
                rights2.add("".equals(tmp) ?"$":tmp);
            } else {
                rights1.add(right.trim());
            }
        }
        production.replace(left, rights1);
        production.put(newLeft, rights2);
    }

    /**
     * first集
     */
    private HashMap<String, HashSet<String>> FIRST = new HashMap<>();
    
    /**
     * 获取右部的第一个字符
     *
     * @param right
     * @return
     */
    private String getFirstStr(String right) {
        String[] strs = right.trim().split(" ");
        return strs[0];
    }

     /**
     * 获取FIRST集合
     */
    public void getFirst() {
        FIRST.clear();
        //将所有终结符加入到FIRST集合
        for (String t : T) {
            HashSet<String> firsts = new HashSet<String>();
            firsts.add(t);
            FIRST.put(t, firsts);
        }
        HashSet<String> tmp = new HashSet<String>();
        tmp.add("$");
        FIRST.put("$", tmp);
        //非终结符
        int k = 0;
        while (k < 5) {
            for (String Ai:NT) {
                //所有文法
                for (String right : production.get(Ai)) {
                    //是否需要加入$
                    boolean flag = true;
                    //第一个token
                    String first = getFirstStr(right);
                    //终结符  非终结符就是自己  $  //&& !FIRST.get(first).isEmpty()
                    if (FIRST.containsKey(first) ) {
                        for (String firstNext : FIRST.get(first)) {
                            if (firstNext.equals("$")) {
                                continue;
                            } else {
                                flag = false;
                                if (!FIRST.containsKey(Ai)) {
                                    HashSet<String> firsts = new HashSet<>();
                                    firsts.add(firstNext);
                                    FIRST.put(Ai, firsts);
                                } else {
                                    FIRST.get(Ai).add(firstNext);
                                }
                            }
                        }
                        if (flag) {
                            if (!FIRST.containsKey(Ai)) {
                                HashSet<String> firsts = new HashSet<>();
                                firsts.add("$");
                                FIRST.put(Ai, firsts);
                            } else {
                                FIRST.get(Ai).add("$");
                            }
                        }
                    }
                }
            }
            k++;
        }
        System.out.println("First集:" + FIRST);
    }

    /**
     * follow
     */
    private HashMap<String, HashSet<String>> FOLLOW = new HashMap<>();

    /**
     * 获取当前字符的下一个字符
     * @param right 右部
     * @param B 当前字符
     * @return 返回字符串
     */
    private String getNextStr(String right,String B)
    {
        String strs[] = right.trim().split(" ");
        for (int i =0;i<strs.length;i++)
        {
            if(strs[i].equals(B)&&i+1<strs.length)
            {
                return strs[i+1];
            }
        }
        return " ";
    }
    /**
     * 判断右部是否包含 B
     * @param right 右部
     * @param B 字符
     * @return true包含
     */
    private boolean isContain(String right,String B)
    {
        String strs[] = right.trim().split(" ");
        for (String str:strs)
        {
            if(str.equals(B))
            {
                return true;
            }
        }
        return false;
    }

    /**
     * 添加follow
     * @param left
     * @param hs
     */
    private void addFollow(String left,HashSet<String> hs)
    {
        if(FOLLOW.containsKey(left))
        {
            FOLLOW.get(left).addAll(hs);
        }
        else{
            FOLLOW.put(left,hs);
        }
    }

     /**
     * 获取Follow集
     */
    public void getFollow() {
        FOLLOW.clear();
        HashSet<String> follows = new HashSet<String>();
        follows.add("#");
        FOLLOW.put(NT.elementAt(0), follows);

        //若A->αBβ是一个产生式，则把First(β)-{$}加入到Follow(B)中
        //若A->αB是一个产生式，或者A->αBβ是一个产生式且β->$，则把Follow(A)加入到Follow(B)中
        int k = 0;
        while (k < 5) {
            for (String A:NT)
            {
                for (String right:production.get(A))
                {
                    if(right.equals("$"))
                    {
                        continue;
                    }
                    for (String B:NT)
                    {
                        if(A.equals(B))
                        {
                            continue;
                        }
                        if(isContain(right,B))
                        {
                            //B后面的字符
                            String b = getNextStr(right,B);
                            if(!" ".equals(b))
                            {
                                addFollow(B, (HashSet<String>) FIRST.get(b).clone());
                                FOLLOW.get(B).remove("$");
                                if(FIRST.get(b).contains("$")&&FOLLOW.containsKey(A))
                                {
                                    addFollow(B, FOLLOW.get(A));
                                }
                            }
                            else
                            {
                                //B后无字符
                                if(FOLLOW.containsKey(A))
                                {
                                    addFollow(B, FOLLOW.get(A));
                                }
                            }

                        }
                    }
                }
            }
            k++;
        }
        System.out.println("Follow集: "+FOLLOW);
    }

    /**
     * 分析表
     */
    private HashMap<Pair<String, String>, String> Table = new HashMap<>();

    /**
     * 获得分析表
     */
    public void getTable()
    {
        for (String A:NT)
        {
            for (String right:production.get(A))
            {
                String first = getFirstStr(right);
                right = A + "->" + right;
                if(FIRST.get(first).contains("$"))
                {
                    for (String a:FOLLOW.get(A))
                    {
                        Pair<String,String> symbol =new Pair<>(A,a);
                        Table.put(symbol,right);
                    }
                }
                else
                {
                    for (String a:FIRST.get(first))
                    {
                        Pair<String,String> symbol =new Pair<>(A,a);
                        Table.put(symbol,right);
                    }
                }
            }
        }
        System.out.println("分析表："+Table);
    }

    private Stack<String> stack = new Stack<>();

    /**
     * 语法分析
     * @param input 输入字符串
     */
    public void parser(String input)
    {
        int step = 1;
        System.out.println("步骤\t分析栈\t\t剩余输入串\t\t推导所用产生式或匹配");
        stack.push("#");
        //加入结束标志
        input +=" #";
        String[] inputs = input.trim().split(" "); 
        int k = 0;
        Stack<String> analysis = new Stack<>();
        //加入结束标志
        analysis.add("#");
        analysis.add("E");
        while (!analysis.isEmpty())
        {
            // 输出分析栈, 剩余输入串
            System.out.print(step++ + "\t" + analysis + "\t\t");
            for(int j = k; j < inputs.length; j++) {
                System.out.print(inputs[j]);
            }
            System.out.print("\t");
            //查看栈顶
            String top = analysis.peek();
            if(top.equals(inputs[k]))
            {
                //栈顶与输入匹配
                String tmp =  analysis.pop();
                System.out.println("匹配:" + tmp);
                k++;
            }
            else if(T.contains(top))
            {
                //终结符包含top
			   break;
            }
            else if(!Table.containsKey(new Pair<>(top,inputs[k])))
            {
                //分析表中不存在
                break;
            }
            else
            {
                //分析表中取出产生式
                String str = Table.get(new Pair<>(top,inputs[k]));
                analysis.pop();
                System.out.println("使用:"+str);
                //加入语法栈
                stack.add(str);
                String []strs =str.split("->");
                String []strss = strs[1].split(" ");
                Collections.swap(Arrays.asList(strss),0,strss.length-1);
                analysis.addAll(Arrays.asList(strss));
                analysis.remove("$");
            }
        }
    }

    /**
     * 根据产生式创建节点
     * @param str   文法
     * @return 节点
     */
    public TreeNode createNode(String str)
    {
        String[] strs = str.trim().split("->");
        TreeNode root = new TreeNode(strs[0]);
        String[] strss = strs[1].trim().split(" ");
        for (String tmp:strss)
        {
            if(T.contains(tmp)||tmp.equals("$"))
            {
                TreeNode tmpNode = new TreeNode(tmp);
                root.childNodes.add(tmpNode);
            }
        }
        return root;
    }

    /**
     * 建立语法树
     */
    public void buildTree()
    {
        //节点栈
        Stack<TreeNode> stackNode =new Stack<>();
        while (!stack.isEmpty())
        {
            //文法
            String str = stack.pop();
            if(!str.equals("#")) {
                TreeNode newNode = createNode(str);
                //在栈中寻找子节点  栈顶是否子节点
                while (!stackNode.isEmpty()&&isContain(str.trim().split("->")[1],stackNode.peek().nodeVal))
                {
                    TreeNode childNode = stackNode.pop();
                    newNode.childNodes.add(childNode);
                }
                stackNode.add(newNode);
            }
        }
        if(stackNode.size() != 1)
        {
            System.out.println("错误！！！！！！！！！！！！！！！");
        }
        TreeNode root = stackNode.pop();
        System.out.println(root);
    }



    public void run(String filename) {
        // 1) 读取文法
        this.readGrammar("grammar.txt");
        // 2.消除左递归
        this.eliminateLeftRecursion();
        // 3.构间产生式树
        this.buildProductionTree();
        // 3.提取左公共因子
        this.leftFactoring();
        // 计算FIRST集
        this.getFirst();
        // 5.计算FOLLOW集
        this.getFollow();
        // 6.获取分析表
        this.getTable();
        // // 7.建立语法树
        this.parser("i + i * i");
        this.buildTree();
    }

    public static void main(String[] args) {
        Ref ref = new Ref();
        ref.run("grammer.txt");
    }

}