编译原理LL1文法分析

LL(1)文法是一个自顶向下语法分析算法

基本流程

1.读取文法

​ 这里的终结符、非终结符是可以用字符串来表示，而不是单个字符，同时也要求了我们不同了的符号需要用一个空格来隔开，在输入文法时也要求间隔开来。例如：A -> A a | b

​ 对象声明：

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

​ 文法读取txt文件，具体txt文件以行读取，对每一行的"->“分割，”->“左边就是非终结符，若NT中不存则加入NT中，右边部分再以”|"分割，分割成多个产生式，将所有所有产生式加入到对应的NT的产生式production中；在所有文法读取完毕之后，对已经建立起来的产生式集进行扫描，若不在NT中字符串则将其加入到N中作为终结符。

    /**
     * 读取文法
     * 终结符非终结符
     *
     * @param fileName 路径
     */
    public void readGrammar(String fileName) {
        File file = new File(fileName);
        try {
            BufferedReader 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();
        }
    }
    /**
     * 添加非终结符
     */
    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);
    }

2.消除左递归

​ 消除左递归有立即消除和非立即消除，立即消除就是非终结符自己的产生式之间来进行替换，非立即消除则就是利用前（i-1）个非终极符的产生式来替换第 i 个中的产生式，然后再对于第 i 个产生式自己进行立即消除。因此下面实现了两个函数来作为这两种消除方式，同时包括以及辅助函数。

​ 辅助函数

    /**
     * 判断右部第一个字符是否为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();
    }	

​ 消除立即左递归，传入一个非终结符Ai，要知道能调用这个函数则证明会产生一个新的非终结符来存储一个新的产生式，然后扫描 Ai的所有产生式，若产生式中第一个字符串就是Ai的话，那么需要产生式中原来的Ai删除，将新的非终结符加入到末尾，这里用到的也就是replaceLast函数；若不包含就在原来的产生式后面加上新的非终结符来调用；最后需要在新的非终结符中加入$的产生来结束递归，更新到产生式集合中即可。

​ 非立即消除左递归，在第i个非终结符时，扫描所有产生式，若产生式第一个字符串就是前i-1个的非终结符中的一个，就需要将这个终结符替换成这个非终结符的所有产生式，若不是则保证原来的产生式即可，最后判断自己的产生式中第一个字符串是否为自身，若是则执行消除立即左递归函数，注意执行完之后需要跳过一个i ，将i增大一个数，因为消除立即左递归加入了一个新的非终结符到NT中，而这个非终结符就这个下一个i中，新的非终结符也不存在左递归的情况，所以需要直接跳过。

/**
     * 消除立即左递归
     *
     * @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);
    }

​ 执行示例：

我们输入：
A -> a B | B b
B -> A c | d

​ 执行结果如下：

3.提取左公共因子

​ 提取左公因子我们用一个新的对象 产生式树，也就是将我们现在的产生式建立一颗树，因为这样可用很好的找到我们公共最大前缀，这颗树其实就相当于我们熟悉的字典树， 找到公共最大前缀之后对其进行提取，提取之后同时也会产生新的非终结符加入到NT中即可。

​ 首先我们来建立这颗 产生式树，加入我们的新对象，对于每一个非终结符建立起一颗树，树根就是 我们的非终结符，productionTree利用HashMap存储可快速定义到我们需要的树。

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

​ 定义我们树的节点，树节点包含节点、很多孩子节点，同时每个树节点存在一个标识isLast，表示此节点是否为一个产生式的末尾，这对于后面的递归就很大的作用，因为有了这样的标识我们递归到此节点时就可以判断是否进行提取。

/**
 * @author zzj
 * @date 2021-12-6 03:42:55
 */
public class TreeNode {
    /**
     * 孩子节点
     */
    public Vector<TreeNode>childNodes =new Vector<>();
    /**
     * 是否为结束标志
     */
    public boolean isLast = false;
    /**
     * 节点的值
     */
    public String nodeVal;

    @Override
    public String toString() {
        return "TreeNode{" +
                "childNodes=" + childNodes +
                ", isLast=" + isLast +
                ", nodeVal='" + nodeVal + '\'' +
                '}';
    }
}

​ 首先我们利用递归来建立这些以非终结符为根的树。用到两个函数，buildProductionTree（）建立产生式树，对于每一个非终结符的所有产生式进行addProductionToTree（）函数。

​ buildProductionTree（）对于每一个非终结符建立起一个数根，然后这个非终结符所有的产生式，将产生以空格分割成字符串数组，从0层开始，进行addProductionToTree递归。

​ addProductionToTree（），参数为根节点，字符串数组，树的层数。字符串数组的大小也就表明了该产生式能走到树的层数，这也就是递归出口，出口对于产生式的字符串数组也就是走到的最后一层的节点，这里将isLast表识为true，证明此节点为一个产生式末尾。对于产生式就是一个$的情况，我们不需要对其建立节点，直接返回即可。结点建立的过程中，一些值的节点已经建立我们直接跳过进行下一步节点，若该节点不存在则建立节点加入到根节点之后再进行下一步递归。

    /**
     * 建立产生式树
     */
    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);
    }

​ 输入示例建立树：

A -> a a a a | a a b c | a a b d | a a
非终结符A的产生式如下图：
图示中标红的节点则表示为该节点为一个产生式的结尾

​ 有了上面这个图我们就能很清楚的两个产生式之间的最大公共前缀。下面我们根据这个树来提取我们最大公共前缀。

​ 辅助函数isPrefix（）来判断产生式中前缀是否为prefix

/**
     * 判断是否包含前缀
     *
     * @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;
    }

​ 提取左公共因子，下面对树节点采用后序遍历，也就是自底向上，自底向上能够很好的确定我们的最大公共因子，深入底部在此以上的父节点就是我们的公共因子。

​ leftFactoring后序遍历入口，对每个非终结符进行getLeftFactorProduction（）。

​ getLeftFactorProduction（）函数需要维护我们的前缀prefix，每到一个节点将其值加入到prefix中，返回值int也很重要，这决定我们是否提取。每到一个结点，递归其子节点，对其返回值用total相加，若total值大于2，则证明子节点下面有两个文法经过于此，调用updateProduction（）函数进行在产生式集中提取，为何这个节点能成为最大的公共前缀，因为每提取一次公共因子我们的total值都会变为1，想上传的最大值就为1，自底向上所以就能保证在下面的时候就进行提取公共因子。

​ updateProduction（）获取到最大公共前缀，我们就能在产生中进行提取合并，产生新的非终结符。因为这一步产生的新的非终结符可能很多，我们保证新产生的非终结符在NT中不存在，利用循环决定加入“ ‘ ” 的个数。得到的非终结符加入道NT中，然后遍历原来的非终结符的所有产生式，匹配我们的最大前缀成功匹配的就提取替换，不匹配保证原来的产生式即可。

    /**
     * 提取左公因子 获得新文法
     */
    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);
    }

​ 输入示例执行结果：

A -> a a a a | a a b c | a a b d | a a

第二个新文法即为我们执行提取左公因子的结果

4.求FIRST集

​ 我们创建新的对象来存储我们FIRST集合

    /**
     * first集
     */
    private Map<String, HashSet<String>> FIRST = new HashMap<>();

​ 参照龙书上的描述来实现我们求FIRST程序。首先将所有非终结符以First（x)=x的形式存入FIRST对象中；依照描述我们的$字符也将加入到FIRST集合中。然后遍历所有的非终结符，对非终结符的所有文法进行扫描，获取文法的第一个字符，若该字符在FIRST集合中，则该字符的FIRST集合将加入到第一个字符的FIRST集合中；对于文法中第一个字符为$的情况，因为$的FIRST集合为$，则对于这个非终结符的FIRST集合中加入$。我们将上述描述多执行几遍来达到最终效果，因为第一次执行时，需要的非终结符FIRST集合还不存在，需要执行生成了再第二遍时使用。

​ 辅助函数：

    /**
     * 获取右部的第一个字符
     *
     * @param right
     * @return
     */
    public 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);
    }

5.求FOLLOW集

​ 创建我们的FOLLOW集合对象

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

​ 同样根据龙书描述，但我们的程序中字符KaTeX parse error: Expected 'EOF', got '#' at position 12: 表示为空，这里我们使用#̲表示结束标记。首先在FOLLO…，包含则执行我们3）规则。上述过程也执行多次来达到最终状态，与求FIRST集合同理。

​ 辅助函数：

    /**
     * 获取当前字符的下一个字符
     * @param right 右部
     * @param B 当前字符
     * @return 返回字符串
     */
    public 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包含
     */
    public 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
     */
    public 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);
    }

6.获取分析表

​ 在实现了FIRST和FOLLOW集后我们的分析表就能很快实现，根据龙书上提出的方法完成我们的分析表，创建分析表对象

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

​ 遍历所有的非终结符的产生式，提取产生式的第一个第一字符，判断其FIRST集合中是否包含$，若包含则在分析表中加入该非终结符的所有FOLLOW集合；反之不包含$，则将第一个字符的FIRST集合加入值分析表中。

    /**
     * 获得分析表
     */
    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);
    }

7.建立语法树

​ 首先输入字符串进行语法分析，根据龙书步骤,首先在输入字符后面加上结束标志#，同时在栈里面最先也加入结束标志#，两个结束表示用于匹配时结束程序。

​ 循环栈，查看栈顶元素，维护输入字符串下标，若栈顶元素与当前字符串下标的字符相等，弹出栈顶，字符串下标右移；当栈顶为终结符或在分析表中查询不到有值的情况跳过；最后一种情况就在分析表中查找的有值，我们取出分析表的值，将栈顶推出，然后将分析表的值倒置后加入栈中，同时要去除掉产生式是$字符。我们的语法树结点嵌套在最后一个情况，当从分析表中取出产生式时，我们利用栈将产生式记录下来，在后面用来建立我们的语法树。

​ 接下来建立语法书，根据我们存储的产生式的栈，循环栈直到空，每次取出栈顶的产生式，将其建立节点，符号->左边的为父节点，右边的全是其子节点，但子节点中只需要加入终结符的子节点，因为非终结符节点将以此创建；栈的好处是因为能模仿低估具有树结构的顺序，我们将每次建立其节点存储到新的节点栈中，每次加入这个节点栈时判断，当前要加入的节点的产生式中是否包含 已经在栈中的节点的非终结符，如果包含，取出节点栈栈顶节点，将其作为要加入节点的子节点，直到栈顶节点不包含为止 ，再将要加入的节点压入栈中。最后我们的节点栈中存储的一个节点就是我们的语法树的树根。

    /**
     * 语法分析
     * @param input 输入字符串
     */
    public void parser(String input)
    {
        //加入结束标志
        input +=" #";
        String[] inputs =input.trim().split(" ");
        int k = 0;
        Stack<String> analysis =new Stack<>();
        //加入结束标志
        analysis.add("#");
        analysis.add(S);
        while (!analysis.isEmpty())
        {
            //查看栈顶
            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();
            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("错误！！！！！！！！！！！！！！！");
        }
        root=stackNode.pop();
        System.out.println(root);
    }

LL（1）分析程序实验目的与要求

  编制一个能识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序），输出对输入符号串的分析过程。

实验内容

  对于这个实验，核心内容是Process类。该类是一个带有三个参数的构造函数。将初始分析栈，输入的句子，预测分析表作为参数注入该类，调用BeginAnalyze()函数进行分析，同时Process本身属性在函数的循环中发生迭代变化，其自身的属性代表了每一分析步骤的结果，打印即可。

实验步骤

• 主函数内容：先打印出给定文法，预测分析表，然后对用户输入，构造Process类，进行分析。
• 获取推导所用的产生式或匹配：GetProductionRule()
  需要调用GetRowIndex(StackTop)和 GetColIndex(Terminal)根据分析栈的栈顶元素与输入字符串首字符来获取预测分析表的内容。
• 反转字符串函数 Reverse(string s)：该函数用于将产生式元素逆序入栈

            private string Reverse(string s)
            {
                char[] cs= s.ToCharArray();
                Array.Reverse(cs);
                return new string(cs);
            }

  值得一提的是本程序并没有使用Stack数据结构来完成，而是使用了对字符串的操作来代替Stack。

using System;
using System.Collections.Generic;
using static System.Console;

namespace LL1
{

    class Program
    {
        /// <summary>
        /// 文法
        /// </summary>
        static List<string> Grammar = new List<string>()
        {
            "E->TB","B->+TB|ε",
            "T->FY","Y->*FY|ε",
            "F->i|(E)"
        };
        /// <summary>
        /// 预测分析表
        /// </summary>
        /// <param name="args"></param>
        static string[,] predictTab =
        {
            {"  ",   "i",     "+",    "*",    "(",    ")",    "#" },
            {"E"   ,   "TB",   "NULL", "NULL", "TB",  "NULL", "NULL" },
            {"B"  ,   "NULL",  "+TB", "NULL", "NULL", "ε",   "ε"},
            {"T"   ,   "FY",   "NULL", "NULL", "FY",  "NULL", "NULL" },
            {"Y"  ,   "NULL",  "ε",   "*FY", "NULL", "ε",   "ε" },
            {"F"   ,   "i",     "NULL", "NULL", "(E)",  "NULL", "NULL" }
        };

        static void Main(string[] args)
        {
            DisplayG();
            DisplayTab();
            WriteLine("请输入要分析的串：");
            string inputString = ReadLine();
            WriteLine("--------------------------------------------------------------------------");
            string symbolStack = "#E";
            Process process = new Process(symbolStack, inputString, predictTab);
            process.BeginAnalyze();
        }


        /// <summary>
        /// 打印文法列表
        /// </summary>
        static void DisplayG()
        {
            WriteLine("文法列表  (将课件例题中的 E' 换成了 B , T' 换成了 Y)");
            foreach (string s in Grammar)
            {
                WriteLine(s);
            }
            WriteLine("--------------------------------------------------------------------------");
        }
        /// <summary>
        /// 打印预测分析表
        /// </summary>
        static void DisplayTab()
        {
            WriteLine("{0,35}", "预测分析表");
            for (int i = 0; i < predictTab.GetLength(0); i++)
            {
                for (int j = 0; j < predictTab.GetLength(1); j++)
                {
                    Write($"{predictTab[i, j],-10}");
                }
                WriteLine();
            }
            WriteLine("--------------------------------------------------------------------------");
        }

        class Process
        {
            public int index;//步骤
            public string symbolStack;//分析栈
            public string residueString;//剩余串
            public string productionRule;//产生式或匹配
            public string[,] predictTab;//预测表

            public Process(string symbolStack, string inputString, string[,] predictTab)
            {
                this.index = 1;
                this.symbolStack = symbolStack;
                this.residueString = inputString;
                this.predictTab = predictTab;
            }
            
            //当前输入符号
            public string Terminal
            {
                get
                {
                    return residueString.Substring(0, 1);
                }              
            }
            //分析栈栈顶元素
            public string StackTop
            {
                get
                {
                    return symbolStack.Substring(symbolStack.Length - 1, 1);
                }
            }
            //产生式首字符
            public string ruleTop
            {
                get
                {
                    return productionRule.Substring(0,1);
                }
            }
            /// <summary>
            /// LL(1) 分析
            /// </summary>
            public void BeginAnalyze()
            {                
                while (true)
                {
                    productionRule = GetProductionRule();
                    Display();
                    symbolStack = symbolStack.Substring(0, symbolStack.Length - 1);
                    if (productionRule== "ε")
                    {
                        index++;
                        continue;
                    }
                    if (ruleTop == Terminal)
                    {
                        if (residueString.Length == 1)
                        {
                            WriteLine("     分析完成，匹配成功！");
                            return;
                        }
                        else
                        {
                            residueString = residueString.Substring(1, residueString.Length-1);
                            if (productionRule.Length > 1)
                            {
                                symbolStack += Reverse(productionRule.Substring(1, productionRule.Length - 1));
                            }
                        }
                    }
                    else
                    {
                        residueString = residueString.Substring(0, residueString.Length);
                        symbolStack += Reverse(productionRule);
                    }
                    index++;
                }
            }

            /// <summary>
            /// 获取推导所用的产生式或匹配
            /// </summary>
            /// <returns></returns>
            private string GetProductionRule()
            {                
                int row = GetRowIndex(StackTop);
                int col = GetColIndex(Terminal);
                string rule = predictTab[row, col];
                if (rule == "NULL")
                {
                    Error();
                }               
                return rule;
            }

            /// <summary>
            /// 根据栈顶元素获取行号
            /// </summary>
            /// <param name="stackTop"></param>
            /// <returns></returns>
            private int GetRowIndex(string stackTop)
            {
                int index = -1;
                for(int i = 0; i < predictTab.GetLength(0); i++)
                {
                    if (predictTab[i, 0] == stackTop)
                    {
                        index = i;
                    }
                }
                if (index == -1)
                {
                    Error();
                }
                return index;
            }

            /// <summary>
            /// 根据当前终结符获取列号
            /// </summary>
            /// <param name="terminal"></param>
            /// <returns></returns>
            private int GetColIndex(string terminal)
            {
                int index = -1;
                for (int i = 0; i < predictTab.GetLength(1); i++)
                {
                    if (predictTab[0, i] == terminal)
                    {
                        index = i;
                    }
                }
                if (index == -1)
                {
                    Error();
                }
                return index;
            }

            /// <summary>
            /// 反转字符串
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            private string Reverse(string s)
            {
                char[] cs= s.ToCharArray();
                Array.Reverse(cs);
                return new string(cs);
            }
            
            /// <summary>
            /// 打印当前步骤
            /// </summary>
            private void Display()
            {
                WriteLine($"{index,-20}{symbolStack,-20}{residueString,-20}{productionRule,-20}");
            }

            /// <summary>
            /// 出错处理程序
            /// </summary>
            private void Error()
            {
                WriteLine("!!!!!!!!!!!!!!  语句非法  !!!!!!!!!!!!!!");
                Environment.Exit(0);
            }

        }
        
    }
}

LL(1)分析器 实验二

实验要求

简单要求：

至少做到对下列已知的文法，用LL（1）分析法对任意输入的符号串进行分析：

（1）E->TG

（2）G->+TG

（3）G->ε

（4）T->FS

（5）S->*FS

（6）S->ε

（7）F->(E)

（8）F->I

高要求：

1、手动输入文法

2、显示文法的非终结符的Follow集

3、显示规则的可选集合

3、构造预测分析表

4、对任意输入的符号串进行分析

记号和规定

• 空串：$
• 符号栈终止符：#
• 规定第一个产生式的左边那个非终结符就是开始符号

简单要求的固定文法（无左递归）

（1）E->TG

（2）G->+TG

（3）G->ε

（4）T->FS

（5）S->*FS

（6）S->ε

（7）F->(E)

（8）F->I

First Follow Select 集合

产生式对应的SELECT集

分析表

简单要求(固定文法递归的预测分析)

在主函数中构造一个RecursionSimple对象调用run方法即可运行

运行示例

[递归式固定文法]请输入需要分析的字符串：
I
[递归式固定文法]*****输入的字符串符合该文法*****success*****
[递归式固定文法]请输入需要分析的字符串：
***
[递归式固定文法]#####输入的字符串符不合该文法#####error#####
[递归式固定文法]请输入需要分析的字符串：
(I)
[递归式固定文法]*****输入的字符串符合该文法*****success*****

头文件 RecursionSimple.h

#pragma once

#include<iostream>
using namespace std;


//简单的递归版本 固定文法 
class RecursionSimple{
	public:
		static const string name;
		static enum over{Run,Error,Success};
		int isOver;
		char cur;
		int len;
		int pos;//当前指向的字符位置
		string text;//需要分析的文本

		//文法函数
		void E();
		void T();
		void G();
		void S();
		void F();

		//执行函数
		void run();
		//读入数据 在末尾插入#
		void cinData();
		//输入的字符串符合文法
		void success();
		//输入的内容不符合文法处理函数
		void error();
		//获取下一个字符 如果已经到了末尾则执行 error()
		void next();
		//输出结果
		void coutResult();


};

源文件 RecursionSimple.cpp

#include "RecursionSimple.h"

#define IS_OVER if(isOver!=Run)return;

const string RecursionSimple::name = "[递归式固定文法]";

void RecursionSimple::E(){
	IS_OVER
	T();
	G();
}

void RecursionSimple::T(){
	IS_OVER
	F();
	S();
}

void RecursionSimple::G(){
	IS_OVER
	if(cur == '+'){
		next();
		T();
		G();
	} else if(cur != '+' && cur != ')' && cur != '#')error();
}

void RecursionSimple::S(){
	IS_OVER
	if(cur == '*'){
		next();
		F();
		S();
	} else if(cur != '+' && cur != ')' && cur != '#')error();
}

void RecursionSimple::F(){
	IS_OVER
	if(cur == '('){
		next();
		E();
		if(cur == ')')next(); else error();

	} else if(cur == 'I'){
		next();
	} else error();
}

void RecursionSimple::run(){
	cout << "文法：\n" << "E->TG\n" << "G->+TG\n" << "G->ε\n" << "T->FS\n" << "S->*FS\n" << "S->ε\n" << "F->(E)\n" << "F->I\n";
	cinData();//读入数据 并初始化
	next();//获取第一个字符
	E();//分析开始（首个非终结符函数）
	if(cur == '#')success();
	else error();
	coutResult();//输出结果
}

void RecursionSimple::cinData(){
	cout << name << "请输入需要分析的字符串：" << endl;
	cin >> text;
	text += '#';
	pos = 0;
	isOver = false;
	len = text.length();
}

void RecursionSimple::success(){
	isOver = Success;
}

void RecursionSimple::error(){
	isOver = Error;
}

void RecursionSimple::next(){
	if(pos < len){
		cur = text[pos++];
		return;
	}
	error();
}

void RecursionSimple::coutResult(){
	if(isOver==Success)	cout << name << "*****输入的字符串符合该文法*****success*****" << endl;
	else cout << name << "#####输入的字符串符不合该文法#####error#####" << endl;
}

高要求(任意文法非递归的预测分析)

1. 读入文法
2. 确定终结符与非终结符
3. 去除左递归
4. First集 Follow集
5. 判断是否为LL(1)文法(First与Follow元素不相交)
6. Select集
7. 预测分析表
8. 分析

解析

1. 读入文法: A -> @B a | c | $

   • 先输入左边 (在这里输入含有 # 的会结束文法输入)
   • 再输入右边 (同时输入各种可能 用 | 隔开 非终结符要在前面加@ ,#号结束本次右边输入)
   • 不可以包含下划线
   • 包含$的将自动转换为$单个字符

2. 确定终结符与非终结符

3. 去除左递归

   • 先将间接左递归转换为直接左递归
   • 将所有直接左递归消除
   • 删除所有不可达的产生式

4. First集 Follow集

   • First集：
     • 遍历每一个左部为x的产生式
     • 如果产生式右部第一个字符为终结符，则将其计入左部非终结符的First集
     • 如果产生式右部第一个字符为非终结符
     • 求该非终结符的First集
     • 将该非终结符的去掉$的First集计入左部的First集
     • 若存在$，继续往后遍历右部
     • 若不存在$，则停止遍历该产生式，进入下一个产生式
     • 若已经到达产生式的最右部的非终结符（即右部的First集都含有空串），则将$加入左部的First集
     • 处理数组中重复的First集中的终结符
   • Follow集：
     • 如果x为起始符，x的Follow集添加#
     • 遍历每一个右部包含非终结符x的产生式
     • 如果x的下一个字符是终结符，添加进x的Follow集
     • 如果x的下一个字符是非终结符，把该字符的First集加入x的Follow集（不能加入空串）
     • 如果下一字符的First集有空串并且该产生式的左部不是x，则把左部的Follow集加入x的Follow集
     • 如果x已经是产生式的末尾，则把左部的Follow集添加到x的Follow集里

5. 判断是否为LL(1)文法：First与Follow元素不相交

6. Select集： First集(除去ε) [+ Follow集(如果First集存在ε)]

7. 预测分析表

   • 遍历每一个左部为x的产生式
   • 如果x右边首字符串为 空串 则添加x的Follow集
   • 如果x右边首字符串为 终结符 则添加该终结符
   • 如果x右边首字符串为 非终结符 则添加x的First集

8. 分析

   • 分析栈放入 S# (S为起始非终结符) 文本栈放入 文本#
   • 获取分析栈顶l与文本栈顶m
   • l如果为空串则直接出栈l
   • l如果为终结符 看l是否等于m 相等则匹配（一起出栈） 否则报错
   • l如果为非终结符 看l的分析表是否有m 有则一起出栈 否则报错
   • 分析栈与文本栈都全部出栈 则分析成功！

运行示例

示例一 固定文法

[郭坤 软工一班 20192758]
欢迎使用LL1文法分析器，输入1使用固定文法，否则自定义文法:1
*****固定文法*****
E->TG
G->+TG|$
T->FS
S->*FS|$
F->(E)|I


First集
E:{ ( I }
F:{ ( I }
G:{ $ + }
S:{ $ * }
T:{ ( I }

Follow集
E:{ # ) }
F:{ # ) * + }
G:{ # ) }
S:{ # ) + }
T:{ # ) + }

是否为LL1文法：是

Select集
E:{ ( I }
F:{ ( I }
G:{ # ) + }
S:{ # ) * + }
T:{ ( I }

预测分析表
                   #         (         )         *         +         I
         E    @empty        TG    @empty    @empty    @empty        TG
         F    @empty       (E)    @empty    @empty    @empty         I
         G         $    @empty         $    @empty       +TG    @empty
         S         $    @empty         $       *FS         $    @empty
         T    @empty        FS    @empty    @empty    @empty        FS

请输入待识别的符号串(空格分割，直到遇到#截止)
( I ) #

              分析栈                    剩余输入串              推导式
                  E#                          (I)#               E->TG
                 TG#                          (I)#               T->FS
                FSG#                          (I)#              F->(E)
              (E)SG#                          (I)#              ( 匹配
               E)SG#                           I)#               E->TG
              TG)SG#                           I)#               T->FS
             FSG)SG#                           I)#                F->I
             ISG)SG#                           I)#              I 匹配
              SG)SG#                            )#          S 空串出栈
               G)SG#                            )#          G 空串出栈
                )SG#                            )#              ) 匹配
                 SG#                             #          S 空串出栈
                  G#                             #          G 空串出栈
                   #                             #            @Accept!

示例二 任意文法

[郭坤 软工一班 20192758]
欢迎使用LL1文法分析器，输入1使用固定文法，否则自定义文法:0
输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
左边的非终结符:A @B c | d # B @A | f # #
右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割！非终结符前加@):
*****结束右边的输入*****
A->Bc|d
输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
左边的非终结符:右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割！非终结符前加@):
*****结束右边的输入*****
B->A|f
输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
左边的非终结符:*****结束文法输入*****
*****输入的文法如下*****
A->Bc|d
B->A|f

*****消除间接左递归*****
A->d|Ac|fc
B->A|f

*****消除直接左递归*****
A->dA_|fcA_
B->A|f
A_->$|cA_

*****删除不可达的文法*****
A->dA_|fcA_
A_->$|cA_


First集
A:{ d f }
A_:{ $ c }

Follow集
A:{ # }
A_:{ # }

是否为LL1文法：是

Select集
A:{ d f }
A_:{ # c }

预测分析表
                   #         B         c         d         f
         A    @empty    @empty    @empty       dA_      fcA_
        A_         $    @empty       cA_    @empty    @empty

请输入待识别的符号串(空格分割，直到遇到#截止)
f c c c #

              分析栈                    剩余输入串              推导式
                  A#                         fccc#            A_->fcA_
               fcA_#                         fccc#              f 匹配
                cA_#                          ccc#              c 匹配
                 A_#                           cc#             A_->cA_
                cA_#                           cc#              c 匹配
                 A_#                            c#             A_->cA_
                cA_#                            c#              c 匹配
                 A_#                             #         A_ 空串出栈
                   #                             #            @Accept!

代码

类头文件 ArbitraryGrammar.h

#pragma once
#include<iostream>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#include<iomanip>
#include<string>
using namespace std;

/*
- 空串：$
- 符号栈终止符：#
*/

//产生式
struct Production{
	string left;    //产生式左边 非终结符
	vector<vector<string>> right;   //产生式右边

    Production(string l,vector<vector<string>>r){ left = l;right = r; }
    Production(string l){ left = l; }

    string getRightString(int i){//获得右边所有元素联合的串
        string s = "";
        for(auto r : right[i])s += r;
        return s;
    }
    void insert(vector<string> temp){
        right.push_back(temp);
    }
    void insert(string temp){
        vector<string>v;
        v.push_back(temp);
        right.push_back(v);
    }
    string toString(){
        string str = left + "->";
        for(auto s : right[0])str += s;
        int len = right.size();
        for(int i = 1;i < len;i++){
            str += "|";
            for(auto s : right[i])str += s;
        }
        return str;
    }
};

//任意文法的LL(1)分析类
class ArbitraryGrammar{
public:
    ArbitraryGrammar();         //构造函数
    void run();                 //运行程序
    void displayGrammarHint(string s);  //打印系统提示语句 中间夹杂当前文法
    void displayGrammar();      //打印当前的文法
    void displayResultTable();  //打印分析结果表
    void displayAnalyzedTable();//打印预测分析表
    bool isNonTer(string x);    //判断是否是 非终结符
    bool isTer(string x);       //判断是否是 终结符
    void inputText();           //待分析的字符串输入 输入#号结束
    void display();             //打印First集,Follow集,Select集
protected:



    int  getNonTerPos(string x);//获取非终结符下标
    int  getTerPos(string x);   //获取终结符下标
    void init();                //初始化
    void load();                //加载数据 调用其他方法
    void inputGrammar();        //输入文法 输出#号结束

    bool isLL1Grammar;          //是否为LL1文法
    bool isLoad;                //是否加载了数据
    bool isAnalyzed;            //是否已经分析了输入的字符串
    string Start;               //起始符


    //文本是否已经分析完毕
    vector<Production> prod;    //产生式集合
    vector<string>text;         //拆分后的 待分析文本
    vector<vector<string>>resultTable;//分析后生成的结果分析表 0 分析栈 1 剩余输出串 2 推导式
    vector<bool>used;          //dfs看看哪些文法是访问了的

    vector<set<string>> first;  //First集
    vector<set<string>> follow; //Follow集
    vector<set<string>> select; //select集

    map<string,int> terAndEnd;  //终结符与#
    map<string,int> ter;        //终结符
    map<string,int> nonTer;     //非终结符 string为非终结符 int为对应编号


    vector<vector<int>> table;  //分析表[非终结符][终结符]-> 存储的是产生式prod的下标 

    void judgeLL1Grammar();     //判断文法是否为LL(1)文法 First与Follow不相交
    void getFirst(string x);    //获取某个非终结符的First集
    void getAllFirst();         //获取所有非终结符的First集
    void getFollow(string x);   //获取某个非终结符的Follow集
    void getAllFollow();        //获取所有非终结符的Follow集
    void getAllSelect();        //获取产生式的Select集
    void getAnalyzTable();      //获取预测分析表
    string getTableE(int prodPos,int rightPos);    //获取预测分析表中的元素 -1 empty -2 synch 
    void getResultTable();      //获取分析后的结果表
    string getVectorString(vector<string> v);//将字符串集合整合为一个字符串
    string getListString(list<string> li);//将字符串集合整合为一个字符串
    void dfs(int x);
    void simplify();
    void removeDirectly(int i);
    void removeIndirect(int i,int len);//消除间接做递归 产生式下标i 产生式数len
    void removeAllDirectly();
    void removeAllIndirect();
    void removeLeftRecursion(); //消除左递归
    void resize(int len);       //更新容器大小
};

类源文件 ArbitraryGrammar.cpp

#include "ArbitraryGrammar.h"

ArbitraryGrammar::ArbitraryGrammar(){
    //init();
}

bool ArbitraryGrammar::isNonTer(string x){
    return nonTer.find(x) != nonTer.end();
}

bool ArbitraryGrammar::isTer(string x){
    return terAndEnd.find(x)!=terAndEnd.end();
}

int ArbitraryGrammar::getNonTerPos(string x){
    return nonTer.at(x);
}

int ArbitraryGrammar::getTerPos(string x){
    return terAndEnd.at(x);
}

void ArbitraryGrammar::init(){
    /*产生式
    （1）E->TG
    （2）G->+TG
    （3）G->ε
    （4）T->FS
    （5）S->*FS
    （6）S->ε
    （7）F->(E)
    （8）F->I
    */

    

    for(auto t : ter)terAndEnd.insert(t);
    int ii = terAndEnd.size();
    terAndEnd["#"] = ii;



    Start = prod[0].left;

    int size = nonTer.size();
    
    resize(size);

    isLoad = false;
}

void ArbitraryGrammar::inputText(){
    //待分析的字符串输入 输入#号结束
    cout << endl;
    cout << "请输入待识别的符号串(空格分割，直到遇到#截止)" << endl;
    vector<string>().swap(text);
    string sin;cin >> sin;
    while(sin.find('#') == string::npos){
        text.push_back(sin);
        cin >> sin;
    }
    isAnalyzed = false;//输入了新的文本 设置为没有被分析
}

void ArbitraryGrammar::inputGrammar(){
    //输入所有非终结符
    string s,ss;
    set<string>st;
    vector<Production>P;
    
    while(1){
        cout << "输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]" << endl;
        cout << "左边的非终结符:";
        cin >> s;
        if(s.find('#') != string::npos){
            cout << "*****结束文法输入*****" << endl;
            break;
        }
        if(s.find('@') != string::npos || s.find('_') != string::npos || s.find('$') != string::npos){
            cout << "*****输入不合法 不能含有 @ 下划线 $ *****" << endl;
            continue;
        }
        int pos;
        if(isNonTer(s)){
            pos = getNonTerPos(s);
        } else{
            int pos = nonTer.size();
            nonTer[s] = pos;
        }
        st.erase(s);//消除未使用的非终结符
        cout << "右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割！非终结符前加@):" << endl;
        vector<vector<string>>V;
        vector<string>v;
        bool flag = 0;
        while(1){
            cin >> ss;
            if(ss.find('#') != string::npos){
                if(v.empty()){
                    cout << "*****产生式为空,不计入*****" << endl;
                    flag = 2;
                    break;
                }
                cout << "*****结束右边的输入*****" << endl;
                V.push_back(v);
                v.clear();
                break;
            }
            if(ss.find('_') != string::npos){
                cout << "*****输入不合法 不能含有下划线*****" << endl;
                flag = 1;
                break;
            }
            if(ss.find('$') != string::npos){
                v.push_back("$");
                continue;
            }
            if(ss.find('@') != string::npos){
                if(ss[0] != '@'){
                    cout << "*****输入不合法 @不在字符串首*****" << endl;
                    flag = 1;
                    break;
                }
                if(ss.size() == 1){
                    cout << "*****输入不合法 @后面没有非终结符串*****" << endl;
                    flag = 1;
                    break;
                }
                for(int i=1;i<ss.size();i++)
                    if(ss[i] == '@'){
                        cout << "*****输入不合法 一个非终结符存在多个@ *****" << endl;
                        flag = 1;
                        break;
                    }
                string nt = ss.substr(1);
                if(!isNonTer(nt))st.insert(nt);//计入非终结符序列
                v.push_back(nt);
                continue;
            }
            if(ss == "|" && !v.empty()){
                V.push_back(v);
                v.clear();
                continue;
            }
            v.push_back(ss);
        }
        if(flag)continue;
        //成功输入一组文法
        Production pr = Production(s,V);
        for(auto vv : V){
            for(auto x : vv){
                if(!isNonTer(x) && x != "$"){
                    int ii = ter.size();
                    ter[x] = ii;
                }
            }
        }
        P.push_back(pr);
        cout << pr.toString() << endl;
    }

    displayGrammarHint("输入的文法如下");

    if(!st.empty()){
        cout << "存在终结符没有对应的产生式！--> ";
        for(auto x : st)cout << x << " ";
        cout << endl << "请重新输入文法！" << endl;
        nonTer.clear();
        ter.clear();
        prod.clear();
        inputGrammar();
    }

    //更新prod
    prod.swap(P);

}

void ArbitraryGrammar::run(){

    

    cout << "[郭坤 软工一班 20192758]" << endl;
    cout << "欢迎使用LL1文法分析器，输入1使用固定文法，否则自定义文法:";
    string sin;
    getline(cin,sin);
    if(sin == "1"){
        prod.push_back(Production("E",{{"T","G"}}));
        prod.push_back(Production("G",{{"+","T","G"},{"$"}}));
        prod.push_back(Production("T",{{"F","S"}}));
        prod.push_back(Production("S",{{"*","F","S"},{"$"}}));
        prod.push_back(Production("F",{{"(","E",")"},{"I"}}));


        ter["+"] = 0;
        ter["*"] = 1;
        ter["("] = 2;
        ter[")"] = 3;
        ter["I"] = 4;

        nonTer["E"] = 0;
        nonTer["G"] = 1;
        nonTer["T"] = 2;
        nonTer["S"] = 3;
        nonTer["F"] = 4;

        init();
        displayGrammarHint("固定文法");

    } else{
        inputGrammar();
        init();
        removeLeftRecursion();
    }

    load();
}

void ArbitraryGrammar::load(){

    isLoad = true;

    getAllFirst();
    getAllFollow();

    judgeLL1Grammar();

    getAllSelect();

    display();

    if(isLL1Grammar){
        getAnalyzTable();
        displayAnalyzedTable();

        while(true){
            inputText();
            getResultTable();
            displayResultTable();
            cout << endl << "是否继续分析一组文本? y|Y" << endl;
            string s;
            cin >> s;
            if(s[0] != 'y' && s[1] != 'Y')break;

        }

    }
}

void ArbitraryGrammar::display(){
    if(isLoad){
        cout << endl;
        cout << "First集" << endl;
        for(auto x : nonTer){
            cout << x.first << ":{ ";
            for(auto f : first[x.second]){
                cout << f << " ";
            }
            cout << "}" << endl;
        }

        cout << endl;
        cout << "Follow集" << endl;
        for(auto x : nonTer){
            cout << x.first << ":{ ";
            for(auto f : follow[x.second]){
                cout << f << " ";
            }
            cout << "}" << endl;
        }

        cout << endl;
        cout << "是否为LL1文法：" << ( isLL1Grammar ? "是" : "不是" ) << endl;

        cout << endl;
        cout << "Select集" << endl;
        for(auto x : nonTer){
            cout << x.first << ":{ ";
            for(auto f : select[x.second]){
                cout << f << " ";
            }
            cout << "}" << endl;
        }
    }


}

void ArbitraryGrammar::displayResultTable(){
    if(isLL1Grammar){

        if(!isAnalyzed)getResultTable();//如果没有分析 则进行分析

        //分析表结果表输出
        int w0 = 20,w1 = 30,w2 = 20;
        cout << endl;
        cout << setw(w0) << "分析栈" << setw(w1) << "剩余输入串" << setw(w2) << "推导式" << endl;
        for(int i = 0;i < resultTable[0].size();i++){
            cout << setw(w0) << resultTable[0][i] << setw(w1) << resultTable[1][i] << setw(w2) << resultTable[2][i] << endl;
        }
    } else{
        cout << "当前文法不合法LL(1)规范，不可以打印LL(1)结果分析表" << endl;
    }
}

void ArbitraryGrammar::displayGrammar(){
    for(auto & p : prod)cout << p.toString() << endl;
}

void ArbitraryGrammar::displayGrammarHint(string s){
    cout << "*****" << s << "*****" << endl;
    displayGrammar();
    cout << endl;
}

void ArbitraryGrammar::displayAnalyzedTable(){
    if(isLL1Grammar){
        int width = 10;
        cout << endl;
        cout << "预测分析表" << endl;

        //打印终结符
        cout << setw(width) << "";
        for(auto s : terAndEnd){
            cout << setw(width) << s.first;
        }

        cout << endl;
        //打印预测的产生式
        for(auto nt : nonTer){
            cout << setw(width) << nt.first;
            int pos = getNonTerPos(nt.first);
            for(auto t : terAndEnd){
                int i = table[nt.second][t.second];
                cout << setw(width) << getTableE(pos,i);
            }
            cout << endl;
        }
    }
}

void ArbitraryGrammar::judgeLL1Grammar(){
    //First与Follow都不相交的才属于LL1文法
    int len = nonTer.size();
    for(int i = 0;i < len;i++){
        set<string>tmp;
        set_intersection(first[i].begin(),first[i].end(),follow[i].begin(),follow[i].end(),inserter(tmp,tmp.begin()));
        if(!tmp.empty()){
            isLL1Grammar = false;
            return;
        }
    }
    isLL1Grammar = true;
}

void ArbitraryGrammar::getFirst(string x){
    bool flag = 0;  //记录非终结符的First集是否有空串 
    int tot = 0;    //记录一个非终结符产生式含有空串的产生式
    int pos = getNonTerPos(x);//该非终结符对应的下标
    

    for(auto v : prod[pos].right){
        //如果右部的第一个字符是终结符 
        if(isTer(v[0])){
            first[pos].insert(v[0]);
        }
        //如果是非终结符
        else{
            //从左到右遍历右部 
            for(int j = 0;j < v.size();j++){
                //如果遇到终结符，直接将该终结符放入first集 并结束
                if(isTer(v[j])){
                    first[pos].insert(v[j]);
                    break;
                }
                //遇到空串
                if(v[j][0] == '$'){
                    //是最后一个符号 则加入first中
                    if(j == v.size() - 1){
                        first[pos].insert("$");
                        break;
                    }
                    //不是最后一个符号 ---其实可以去除它！
                    continue;
                }
                //不是终结符，求该非终结符的First集
                getFirst(v[j]);
                for(string it : first[getNonTerPos(v[j])]){
                    if(it[0] == '$'){//查看是否有空串在该非终结符的first中
                        flag = 1;
                    } else{//将该非终结符的first的非空串元素添加到first集中
                        first[pos].insert(it);
                    }
                }
                //没有空串就不必再找下去了 
                if(flag == 0)break;
                else{//有空串 则继续循环
                    flag = 0;//更新状态
                    tot++;
                }
            }
            //如果右部所有符号的First集都有空串] = 则符号x的First集也有空串 
            if(tot == v.size()){
                first[pos].insert("$");
            }
        }
    }
    
    
}

void ArbitraryGrammar::getAllFirst(){
    //getFirst
    for(auto i : nonTer)getFirst(i.first);
}

void ArbitraryGrammar::getAllFollow(){
    //起始非终结符的follow放入#
    follow[0].insert("#");
    //getFollow
    for(auto i : nonTer)getFollow(i.first);
}

void ArbitraryGrammar::getFollow(string x){
    int pos = getNonTerPos(x);


    //找到非终结符x出现的位置
    for(int i = 0;i < prod.size();i++){
        for(auto v : prod[i].right){
            int index = -1;
            int len = v.size();
            for(int j = 0;j < len;j++){
                if(v[j] == x){
                    index = j;
                    break;
                }
            }
            if(index == -1)continue;//没有包含x结束本次循环
            //如果找到了x] = 并且它不是最后一个字符 
            if(index < len - 1){
                //如果下一个字符是终结符，添加进x的Follow集 
                string next = v[index + 1];
                if(isTer(next))follow[pos].insert(next);
                else{
                //如果下一个字符是非终结符 
                    bool flag = 0;
                    //遍历下一个字符的First集
                    for(string it : first[getNonTerPos(next)]){
                        if(it[0] == '$')flag = 1;
                        else follow[pos].insert(it);
                    }
                    //如果有空串并且左部不是它本身(防止陷入死循环)] = 当前非终结符的Follow集是x的Follow集
                    string l = prod[i].left;
                    if(flag && l != x){
                        getFollow(l);
                        for(string it : follow[getNonTerPos(l)]){
                            follow[pos].insert(it);
                        }
                    }
                }
            } else if(index == len - 1 && x != prod[i].left){
                //如果x在产生式的末尾，则产生式左部的Follow集应该添加到x的Follow集里 
                string l = prod[i].left;
                getFollow(l);
                for(string it : follow[getNonTerPos(l)]){
                    follow[pos].insert(it);
                }
            }
        }
    }
}


void ArbitraryGrammar::getAllSelect(){
    //Slect集 = First集(除去ε) [+ Follow集(如果First集存在ε)]
    for(auto m : nonTer){
        string x = m.first;
        int pos = m.second;
        if(first[pos].find("$") != first[pos].end()){
            //First存在空串 
            set_union(first[pos].begin(),first[pos].end(),follow[pos].begin(),follow[pos].end(),inserter(select[pos],select[pos].begin()));
            //取出select中的空串 $
            select[pos].erase("$");
        } else{//不存在空串
            for(auto s : first[pos])select[pos].insert(s);
        }
    }
}

void ArbitraryGrammar::getAnalyzTable(){
    
    for(int i = 0;i < prod.size();i++){
        for(int j = 0;j < prod[i].right.size();j++){
            string tmp = prod[i].right[j][0];
            int pos = getNonTerPos(prod[i].left);
            //如果产生式右部的第一个字符串是终结符
            if(isTer(tmp) || tmp[0] == '$'){
                //该终结符是空串，遍历左部的follow集，更新table
                if(tmp[0] == '$'){
                    for(auto f : follow[pos])table[pos][getTerPos(f)] = j;
                } else{//该终结符不是空串，更新table
                    table[pos][getTerPos(tmp)] = j;
                }
            } else{
                //如果产生式右部的第一个字符是非终结符，遍历它的First集，更新table
                int tmpPos = getNonTerPos(tmp);
                for(auto f : first[tmpPos]){//添加 除空串$ 以外的所有元素
                    if(f[0] != '$')table[pos][getTerPos(f)] = j;
                }
                //如果有空串，遍历左部的follow集，更新table  
                if(first[tmpPos].find("$") != first[tmpPos].end()){
                    for(auto f : follow[pos])table[pos][getTerPos(f)] = j;
                }
            }
        }
    }
}

string ArbitraryGrammar::getTableE(int prodPos,int rightPos){
    if(rightPos == -1)return "@empty";
    //if(1 == -2)return "@synch";
    return prod[prodPos].getRightString(rightPos);
}

void ArbitraryGrammar::getResultTable(){
    if(isAnalyzed)return;//分析过就不需要再分析了

    isAnalyzed = true;

    auto rs = &resultTable;
    //重置结果表
    vector<vector<string>>().swap(*rs);
    rs->resize(3);
    list<string>a,b;//a-->分析栈 b->剩余输出串栈
    auto A = &rs->at(0),B = &rs->at(1),C = &rs->at(2);
    //把开始符和#push进分析栈
    a.push_back(Start);
    a.push_back("#");
    //把整个串push进剩余符号vector
    for(auto i : text)b.push_back(i);
    b.push_back("#");
    //如果剩余输入串长度不为0，就一直循环
    while(b.size() > 0){
        //输出分析栈内容
        A->push_back(getListString(a));
        //输出剩余输入串内容
        B->push_back(getListString(b));
        
        //获取分析栈首元素与剩余输入串首元素
        string sa = a.front(),sb = b.front();
        int pa;

        if(sa == sb){
            if(sa == "#"){//如果可以匹配，并且都为# 
                C->push_back("@Accept!");//输入串符合文法！
                return;
            } else{//如果可以匹配，并且都为终结符 
                a.pop_front();
                b.pop_front();
                C->push_back(sb + " 匹配");
            }
        }else if(isNonTer(sa)&& isTer(sb) &&table[pa = getNonTerPos(sa)][getTerPos(sb)] > -1){
            //如果在预测分析表中有值
            int index = table[pa][getTerPos(sb)];
            a.pop_front();
            if(getTableE(pa,index) != "$"){
                //E#->TG# 倒叙插入
                for(int i = prod[pa].right[index].size() - 1;i >= 0;i--){
                    a.push_front(prod[pa].right[index][i]);
                }
                C->push_back(prod[pa].left + "->" + getVectorString(prod[pa].right[index]));
            } else{//空串出栈
                C->push_back(sa + " 空串出栈");
            }
        } else{
            C->push_back("@Error!");
            return;
        }
    }
}

string ArbitraryGrammar::getVectorString(vector<string> v){
    string tmp = "";
    for(auto i : v)tmp += i;
    return tmp;
}

string ArbitraryGrammar::getListString(list<string> li){
    string tmp = "";
    for(auto i : li)tmp += i;
    return tmp;
}

//消除间接左递归
void ArbitraryGrammar::removeIndirect(int pa,int len){



    for(int pb = pa; pb < len; pb++){
             //相互循环遍历 一层层的消除间接左递归
        bool flag = false;
        vector<vector<string>> tmp;
        vector<vector<string>> & Ar = prod[pa].right;//检查的产生式右边Ar
        vector<vector<string>> & Br = prod[pb].right;//搜寻的产生式右边Br
        string Bl = prod[pb].left;//搜寻的产生式 左边
        //A->Bc B->Cd => A->Cdc
        for(auto & a : Ar)
            if(a[0] == Bl){//Ar中发现有以Bl开头的式子 
                //将B中非终结符式子Cd筛选出来
                for(auto & b : Br)
                    if(b[0]!=Bl&&b[0]!="$")
                        tmp.push_back(b);
                //找到Bl开头元素
                flag = true;
                break;
            }
        if(flag){
            //使用n--反向读取方式 避免因为删除导致的数组下标错误
            int n = Ar.size();
            while(n--){
                if(Ar[n][0] == Bl){//Ar中发现有以Bl开头的式子 
                    //取出tmp中的元素Cd加上a中的c 然后放入Ar中  Cdc
                    for(auto t : tmp){
                        int nn = Ar[n].size();
                        for(int k = 1;k < nn;k++)
                            t.push_back(Ar[n][k]);
                        //放入Ar中 A->CDc
                        Ar.push_back(t);
                    }
                    //删除A->Bc项
                    Ar.erase(Ar.begin() + n);
                }
            }
        }
    }
}

void ArbitraryGrammar::removeAllDirectly(){
    //固定了原本产生式数量 即使后续增加不会改变 因此之后遍历原有的产生式
    int len = prod.size();
    for(int i = 0;i < len;i++)removeDirectly(i);

    //扩容
    len = prod.size();//获取扩容后的大小
    resize(len);


    displayGrammarHint("消除直接左递归");
}

void ArbitraryGrammar::removeAllIndirect(){
    int len = prod.size();
    for(int i = 0;i < len;i++)removeIndirect(i,len);

    displayGrammarHint("消除间接左递归");
}

void ArbitraryGrammar::removeLeftRecursion(){
    //先消除所有间接左递归 再消除所有 直接左递归
    removeAllIndirect();
    removeAllDirectly();
    simplify();
}

void ArbitraryGrammar::resize(int len){
    first.resize(len);
    follow.resize(len);
    select.resize(len);
    table.resize(len);
    for(auto & i : table){
        i.resize(terAndEnd.size());
        for(auto & x : i)x = -1;//设置为-1 empty
    }
}

//消除直接左递归 
void ArbitraryGrammar::removeDirectly(int pos){
    string l = prod[pos].left;//获取左边
    //遍历看看有没有左递归元素
    bool isLeftRecursion = false;
    for(auto & i : prod[pos].right){
        if(i[0] == l){
            isLeftRecursion = true;
            break;
        }
    }
        
    if(!isLeftRecursion)return;

    //创建A_并放入prod中
    string l_ = l + '_';
    auto A_ = Production(l_);

    //nonTer 添加A_
    nonTer[l_] = prod.size();

    prod.push_back(A_);

    //----这里不知道为什么 不能放在前面声明r（会导致到下面循环时 r变空 只能放在这里了）
    auto & r_ = prod[prod.size() - 1].right;
    //添加空串到A_中
    r_.push_back({"$"});
    auto &r = prod[pos].right;

    //遍历A右边 寻找递归左元素
    for(int x = 0;x < r.size();x++){
        if(r[x][0] == "$")continue;//跳过空串
        if(r[x][0] == l){//A->Ab => A_->bA_
            vector<string>v;
            for(int i = 1;i < r[x].size();i++)
                v.push_back(r[x][i]);//b
            v.push_back(l_);//bA_
            r_.push_back(v);//添加A_->nA_
            r.erase(r.begin()+x);//删掉A->Ab
            x--;//回退一格
        } else{//A->c => A->cA_
            r[x].push_back(l_);//cA_
        }
    }
}


void ArbitraryGrammar::dfs(int x){
    if(used[x]) return;
    used[x] = 1;
    for(vector<string> &v : prod[x].right)
        for(string &s:v)
            if(isNonTer(s))
                dfs(getNonTerPos(s));
}

//化简 没有使用的文法扔掉
void ArbitraryGrammar::simplify(){
    //还没做好
    vector<bool>().swap(used);
    used.resize(prod.size());
    
    dfs(0);

    vector<Production> res;
    for(int i = 0; i < prod.size(); i++)
        if(used[i])
            res.push_back(prod[i]);

    prod.swap(res);

    resize(prod.size());

    nonTer.clear();
    for(int p = 0;p < prod.size();p++)
        nonTer[prod[p].left] = p;


    displayGrammarHint("删除不可达的文法");
}

主函数 main.cpp

#include <iostream>
#include <cmath>
#include "ArbitraryGrammar.h"
using namespace std;

int main(){
	
	ArbitraryGrammar ag = ArbitraryGrammar();
	ag.run();

}