前言：编译原理实验要求做一个语法分析器，所以才有了这个项目

LL1 语法分析器

实验要求

PS：

1. 这里其实还可以选择算符优先分析法和SLR(1)分析法做的，但是由于我对预测分析法比较熟悉，所以…
2. 第五步的模拟分析过程这里我并没有实现…因为老师并没有要求实现这个模拟分析过程

测试用例

老师要求的测试用例：

我的测试用例：

//直接左递归
P——>Pa|b
V——>Eabc|bc|Vabc|c

E——>E+T|T
T——>T*F|F
F——>(E)|i

//间接左递归
S——>i|h|c|t|Qc
Q——>Rb|b
R——>Ba|a
B——>Cf|H
C——>Dd|d
D——>Se|e
H——>zy|x

//无左递归
S——>aSe|B
B——>bBe|C
C——>cCe|d

//不是LL1文法
S——>ABBA
A——>a|ε
B——>b|ε

S——>AB|bC
A——>b|ε
B——>aD|ε
C——>AD|b
D——>aS|c

S——>ABD|bC
A——>b|ε
B——>aD|ε
C——>AD|b
D——>aS|c

S——>aAS|b
A——>bA|ε

实验步骤

1、读取测试文件

• FileUtil.java

import java.io.*;

/**
 * @Author 小关同学
 * @Create 2022/5/2 23:30
 * 文件读取
 */
public class FileUtil {


    /**
     * 读取文件文本内容
     * @param fileName
     * @return
     */
    public static BufferedReader readFile(String fileName) {

        BufferedReader bufferedReader = null;
        try {
            File myFile = new File(fileName);//通过字符串创建File类型对象，指向该字符串路径下的文件

            if (myFile.isFile() && myFile.exists()) { //判断文件是否存在

                InputStreamReader Reader = new InputStreamReader(new FileInputStream(myFile), "UTF-8");
                //考虑到编码格式，new FileInputStream(myFile)文件字节输入流，以字节为单位对文件中的数据进行读取
                //new InputStreamReader(FileInputStream a, "编码类型")
                //将文件字节输入流转换为文件字符输入流并给定编码格式

                bufferedReader = new BufferedReader(Reader);
                //BufferedReader从字符输入流中读取文本，缓冲各个字符，从而实现字符、数组和行的高效读取。
                //通过BuffereReader包装实现高效读取

            } else {
                System.out.println("找不到指定的文件");
            }

        } catch (Exception e) {
            System.out.println("读取文件内容出错");
            e.printStackTrace();
        }

        return bufferedReader;

    }


}

2、消除式子中可能存在的左递归

• EliminateLeftRecursion.java

import entity.Formula;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;

/**
 * @Author 小关同学
 * @Create 2022/5/2 22:36
 * 消除左递归(直接左递归和简介左递归)
 */
public class EliminateLeftRecursion {

    //原始式子
    private Map<String,String> oldFormula = new HashMap<>();
    //消除左递归后的式子
    private Map<String,String> newFormula = new HashMap<>();
    //经过封装过的式子集合，主要作用是判断是否经历了间接左递归的递归查找过程
    private ArrayList<Formula> param = new ArrayList<>();
    //是否发生了左递归
    private boolean isHappenLeftRecursion;

    public boolean isHappenLeftRecursion() {
        return isHappenLeftRecursion;
    }

    public Map<String, String> getNewFormula() {
        return newFormula;
    }

    public Map<String, String> getOldFormula() {
        return oldFormula;
    }


    /**
     * 初始化数据
     * @param fileSrc
     */
    public EliminateLeftRecursion(String fileSrc) {
        BufferedReader bufferedReader = FileUtil.readFile(fileSrc);
        if (bufferedReader!=null){
            String lineText = null;
            while(true){
                try {
                    if ((lineText = bufferedReader.readLine()) == null){
                        break;
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                }
                assert lineText != null;
                String[]strings = lineText.split("——>");
                Formula formulaEntity = new Formula(strings[0], strings[1]);
                oldFormula.put(strings[0], strings[1]);
                param.add(formulaEntity);
            }
        }
    }

    /**
     * 消除直接左递归
     * @param leftFormula
     * @param rightNonTerminal
     * @return
     */
    public boolean eliminateDirectLeftRecursion(String leftFormula, String rightNonTerminal) {
        //右侧由|分隔的符号集
        List<String> splitByLine = new ArrayList<>(Arrays.asList(rightNonTerminal.split("\\|")));
        int index = -1;
        //右侧大P所在的首部的字符串
        String oldFlag = null;
        int oldFlagIndex = 0;
        for (String string : splitByLine) {
            index = string.indexOf(leftFormula);
            if (index == 0) {
                oldFlag = string;
                break;
            }
            oldFlagIndex++;
        }
        //如果有直接左递归，进行消除直接左递归的操作
        if (index == 0) {
            //P'
            String newFlag = leftFormula + "'";
            //P'——>aP'|ε
            String newFormula1 = newFlag + "——>" + oldFlag.replace(leftFormula, "") + newFlag + "|ε";
            //移除直接左递归项
            splitByLine.remove(oldFlagIndex);
            //P——>bP'
            String newFormula2 = leftFormula + "——>";
            for (int i = 0; i < splitByLine.size(); i++) {
                String str = splitByLine.get(i);
                if (!str.equals("ε")){
                    newFormula2 = newFormula2 + str + newFlag;
                }else{
                    newFormula2 = newFormula2 + str;
                }
                if (i + 1 < splitByLine.size()) {
                    newFormula2 = newFormula2 + "|";
                }
            }
            String[] newFormulas1 = newFormula1.split("——>");
            String[] newFormulas2 = newFormula2.split("——>");
            newFormula.put(newFormulas1[0], newFormulas1[1]);
            newFormula.put(newFormulas2[0], newFormulas2[1]);
            isHappenLeftRecursion = true;
            return true;
        }else {
            newFormula.put(leftFormula, rightNonTerminal);
            return false;
        }
    }

    /**
     * 消除左递归
     * @return
     */
    public void eliminateLeftRecursion(){
        for(Formula formulaEntity: param){
            //如果已经进行过间接消除左查询，就不再循环
            if (formulaEntity.isRecursionFlag()){
                continue;
            }

            //消除式子的直接左递归
            boolean flag = eliminateDirectLeftRecursion(formulaEntity.getLeft(), formulaEntity.getRight());
            //如果式子没有直接左递归，看看是否是间接左递归
            if (!flag){
                String string1 = "";
                //右侧由|分隔的符号集
                List<String> splitByLine = new ArrayList<>(Arrays.asList(formulaEntity.getRight().split("\\|")));
                //搜索是否有间接左递归
                for (int i = 0;i < splitByLine.size();i++){
                    String string = splitByLine.get(i);
                    String flagNonTerminal = ""+string.charAt(0);
                    //判断是否存在首项是非终结符的
                    if (oldFormula.containsKey(flagNonTerminal)){
                        string = string.replaceFirst(flagNonTerminal, "");
                        //生成右边的式子
                        string1 = createRightFormulaString(formulaEntity.getLeft(), flagNonTerminal, string, i);
                        //如果最后面的符号是|，且是循环的最后一个元素的话，则去掉|
                        if (string1.charAt(string1.length()-1)=='|' && i==splitByLine.size()-1){
                            string1 = string1.substring(0, string1.length()-1);
                        }
                    }else{//如果首项不是终结符
                        string1 = string1 + string;
                        if (i+1<splitByLine.size()){
                            string1 = string1 + "|";
                        }
                    }
                }
                //消除式子的直接左递归
                eliminateDirectLeftRecursion(formulaEntity.getLeft(), string1);
            }

            //清除已经递归了的元素中多余的式子
            for (Formula formulaEntity2: param){
                if (formulaEntity2.isRecursionFlag()){
                    if (newFormula.containsKey(formulaEntity2.getLeft())){
                        String[]strings = newFormula.get(formulaEntity2.getLeft()).split("\\|");
                        for (String string: strings){
                            if (string.indexOf(formulaEntity.getLeft())==0){
                                newFormula.remove(formulaEntity2.getLeft());
                                break;
                            }
                        }
                    }
                }
            }
        }

        //如果发生了消除左递归才进行打印
        if (isHappenLeftRecursion){
            System.out.println("消除左递归后的结果：");
            for (Map.Entry<String,String> entry: newFormula.entrySet()){
                System.out.println(entry.getKey()+"——>"+entry.getValue());
            }
        }
    }
    
    public List<String> returnRightFormulaStringList(String flagNonTerminal, String leftFormula, String rightFormula){
        List<String> result = recursionSearch(flagNonTerminal, leftFormula);
        boolean flag = false;
        ListIterator<String> listIterator = result.listIterator();
        while(listIterator.hasNext()){
            String string = listIterator.next();
            if (string.equals("ε") && rightFormula.length()!=0){
                List<String> list;
                if (rightFormula.length() > 1){
                    String str1 = "" + rightFormula.charAt(0);
                    String str2 = rightFormula.replaceFirst(str1, "");
                    list = returnRightFormulaStringList(str1, leftFormula, str2);
                }else{
                    String str1 = "" + rightFormula.charAt(0);
                    list = returnRightFormulaStringList(str1, leftFormula, "");
                }
                for (String s: list){
                    if (!s.equals("ε")){
                        listIterator.add(s+"ε");
                    }else{
                        if (rightFormula.length()<=1){//如果此时后面已经没有元素了且存在ε，则证明结果必有ε
                            //这里找一个特殊符号#代表ε，跟其他的多余的ε区分开来
                            listIterator.add("#"+"ε");
                        }
                    }
                }
                flag = true;
            }
        }
        if (flag){
            result.add("ε");
        }
        return result;
    }

    public String createRightFormulaString(String leftFormula, String flagNonTerminal, String string, int flag){
        List<String> result = returnRightFormulaStringList(flagNonTerminal, leftFormula, string);
        result.removeIf(str -> str.equals("ε"));
        String string1 = "";
        for (int j = 0;j < result.size();j++){
            String string2 = result.get(j);
            if (string2.indexOf(leftFormula) == 0){
                newFormula.remove(flagNonTerminal);
            }
            int num = 0;
            for (int x = 0;x < string2.length();x++){
                if (string2.charAt(x)=='ε'){
                    num++;
                }
            }
            string2 = string2.substring(0, string2.length()-num);
            if (!string2.equals("ε")){
                if (num == 0){
                    if (string2.equals("#")){
                        string1 = string1 + "ε";
                    }else{
                        string1 = string1 + string2 + string;
                    }
                }else{
                    String str = "";
                    if (num <= string.length()){
                        str = string.substring(num, string.length());
                    }
                    if (string2.equals("#")){
                        string1 = string1 + "ε";
                    }else{
                        string1 = string1 + string2 + str;
                    }
                    result.set(j, string2.substring(0, string2.length()-1));
                }
            }else{//如果是ε的话，后续得查看ε后面是否还有符号(终结符或非终结符)
                string1 = string1 + result.get(j);
            }
            //后面还有元素，且该元素不为ε，就继续添加|分隔
            if (j+1<result.size() || flag < string.length()){
                string1 = string1 + "|";
            }
        }
        return string1;
    }

    /**
     * 改变式子状态，如果进行过间接消除左递归的过程的，就设置recursionFlag为true
     * 即已经经过递归查找简介左递归的式子下次消除左递归就不用在遍历了
     * @param nonTerminal
     */
    public void perform(String nonTerminal){
        for(Formula formulaEntity: param){
            if (formulaEntity.getLeft().equals(nonTerminal)){
                formulaEntity.setRecursionFlag(true);
            }
        }
    }


    /**
     * 递归向下搜寻、合并间接左递归
     * @param nonTerminal 式子本身的左终结符
     * @param targetCharacter 待搜寻的目标终结符
     * @return
     */
    public List<String> recursionSearch(String nonTerminal, String targetCharacter){
        String rightFormula = oldFormula.get(nonTerminal);
        List<String> rightFormulaCollection = new ArrayList<>(Arrays.asList(rightFormula.split("\\|")));
        perform(nonTerminal);
        newFormula.put(nonTerminal, rightFormula);
        for (int i = 0;i < rightFormulaCollection.size();i++){
            int index = -1;
            String string = rightFormulaCollection.get(i);
            index = string.indexOf(targetCharacter);

            //如果第一位是目的终结符，说明出现了间接左递归
            if (index == 0){
                return rightFormulaCollection;
            }

            String flagNonTerminal = ""+string.charAt(0);
            if (oldFormula.containsKey(flagNonTerminal)){
                List<String> result = recursionSearch(flagNonTerminal, targetCharacter);
                String string1 = string.replace(flagNonTerminal,"");
                String string2 = "";
                for (int j = 0;j < result.size();j++){
                    string2 = result.get(j) + string1 + string2;
                    if (j+1 < result.size()){
                        string2 = "|" + string2;
                    }
                }
                String[]strings = string2.split("\\|");
                rightFormulaCollection.addAll(Arrays.asList(strings));
                rightFormulaCollection.remove(i);
                newFormula.put(nonTerminal, rightFormula.replace(string, string2));
            }
        }
        return rightFormulaCollection;
    }

    //测试
    public static void main(String[] args) {
        EliminateLeftRecursion eliminateLeftRecursion = new EliminateLeftRecursion("./src/input.txt");
        eliminateLeftRecursion.eliminateLeftRecursion();
    }
}

消除左递归主要有两点

1. 直接左递归
   直接左递归直接按照书本上的方法进行消除即可，如下：

E——>E+T|T
T——>T*F|F
F——>(E)|i
执行消除左递归后的结果：
E——>TE'
E'——>+TE'|ε
T——>FT'
T'——>*FT'|ε
F——>(E)|i

2. 间接左递归
   间接左递归这个就比较麻烦了，这个还得分情况，同样也是两种情况

• 首字符是非终结符，且该非终结符对应的式子元素中不含 ε
  则将该非终结符式子中的元素添加到上一个式子的前面（想说清楚挺麻烦的，看例子吧），如下：

S——>i|h|c|t|Qc
Q——>Rb|b
R——>Ba|a
B——>Cf|H
C——>Dd|d
D——>Se|e
H——>zy|x
执行消除左递归后的结果：
S——>bcS'|edfabcS'|dfabcS'|abcS'|xabcS'|zyabcS'
S'——>edfabcS'|ε
H——>zy|x

• 首字符是非终结符，且该非终结符下对应的式子元素中含有 ε
  这个就异常的麻烦了，因为如果存在 ε ，就意味着不能只看首字符，还得看下一个字符是不是有左递归，如下：

S——>AB|bC
A——>b|ε
B——>aD|ε
C——>AD|b
D——>aS|c
执行消除左递归后的结果：
A——>b|ε
B——>aD|ε
S——>bB|aD|ε|bC
C——>bD|aS|c|b
D——>aS|c

PS：上面这个例子中是不存在左递归的，但是为了让大家方便理解才拿出来举例

3、生成 First 集

FirstCollection.java

import java.util.*;

/**
 * @Author 小关同学
 * @Create 2022/5/2 22:37
 * 构建FIRST集
 */
public class FirstCollection {

    private EliminateLeftRecursion eliminateLeftRecursion;
    private Map<String, Set<String>> firstCollectionMap = new HashMap<>();

    public Map<String, Set<String>> getFirstCollectionMap() {
        return firstCollectionMap;
    }

    public EliminateLeftRecursion getEliminateLeftRecursion() {
        return eliminateLeftRecursion;
    }

    public FirstCollection(String fileSrc) {
        //消除左递归
        this.eliminateLeftRecursion = new EliminateLeftRecursion(fileSrc);
        eliminateLeftRecursion.eliminateLeftRecursion();
        //生成First集
        createFirstCollection();
    }

    public void createFirstCollection(){
        Map<String,String> formula = eliminateLeftRecursion.getNewFormula();
        for (Map.Entry<String,String> entry: formula.entrySet()){
            String leftNonTerminal = entry.getKey();
            Set<String> set = new HashSet<>();
            searchFirstCharacter(leftNonTerminal, set);
            firstCollectionMap.put(leftNonTerminal, set);
        }

        System.out.println();
        for (Map.Entry<String, Set<String>> entry: firstCollectionMap.entrySet()){
            System.out.println(entry.getKey() + "的FIRST集：" + entry.getValue().toString());
        }
    }


    /**
     * 递归向下查找式子第一个开头的字符
     * @param nonTerminal 终结符
     */
    public void searchFirstCharacter(String nonTerminal, Set<String> set){
        Map<String,String> formula = eliminateLeftRecursion.getNewFormula();
        String[]strings = formula.get(nonTerminal).split("\\|");
        for (String string: strings){
            String firstCharacter = ""+string.charAt(0);
            //首字符是否是非终结符，若是则继续递归查找，若不是则直接添加进FIRST集合
            if (formula.containsKey(firstCharacter)){
                searchFirstCharacter(firstCharacter, set);
            }else{
                set.add(firstCharacter);
            }
        }
    }

    //测试
    public static void main(String[] args) {
        FirstCollection firstCollection = new FirstCollection("./src/input.txt");
        //进行消除左递归
        firstCollection.eliminateLeftRecursion.eliminateLeftRecursion();
        firstCollection.createFirstCollection();


        System.out.println();
        for (Map.Entry<String, Set<String>> entry: firstCollection.firstCollectionMap.entrySet()){
            System.out.println(entry.getKey() + "的FIRST集：" + entry.getValue().toString());
        }
    }
}

生成式子的 First 集这里就比较轻松了，只要对首字符进行分析就行了

1. 首字符是终结符
   直接将该终结符添加进 First 集里面

2. 首字符是非终结符
   其实这种情况是不会在我上面的代码中出现的，因为这里使用的式子是消除完左递归后的式子，理论上不会再出现首字符是非终结符的情况了…如果出现了这种情况，请参照前面消除左递归时的步骤来设计。

4、生成 Follow 集

• FollowCollection.java

import java.util.*;

/**
 * @Author 小关同学
 * @Create 2022/5/2 22:37
 * 构建FOLLOW集
 */
public class FollowCollection {

    private EliminateLeftRecursion eliminateLeftRecursion;
    private FirstCollection firstCollection;
    private Map<String, Set<String>> followCollectionMap = new HashMap<>();

    public EliminateLeftRecursion getEliminateLeftRecursion() {
        return eliminateLeftRecursion;
    }

    public FirstCollection getFirstCollection() {
        return firstCollection;
    }

    public Map<String, Set<String>> getFollowCollectionMap() {
        return followCollectionMap;
    }

    public FollowCollection(String fileSrc) {
        this.firstCollection = new FirstCollection(fileSrc);
        this.eliminateLeftRecursion = firstCollection.getEliminateLeftRecursion();
        createFollowCollection();
        System.out.println();
        for (Map.Entry<String, Set<String>> entry1 : followCollectionMap.entrySet()) {
            System.out.println(entry1.getKey() + "的FOLLOW集：" + entry1.getValue());
        }
    }


    public void createFollowCollection(){
        Map<String,String> formula = eliminateLeftRecursion.getNewFormula();
        for (Map.Entry<String,String> entry: formula.entrySet()){
            searchTargetNonTerminalCharacter(entry.getKey());
        }
        Map<String, Set<String>> map = followCollectionMap;

        for (Map.Entry<String, Set<String>> setMap: firstCollection.getFirstCollectionMap().entrySet()) {
            if (followCollectionMap.containsKey(setMap.getKey())){
                for (Map.Entry<String, Set<String>> entry2 : followCollectionMap.entrySet()) {
                    Set<String> set = entry2.getValue();
                    ListIterator<String> listIterator = new ArrayList<>(set).listIterator();
                    while(listIterator.hasNext()){
                        String string = listIterator.next();
                        if (map.containsKey(string)){
                            //删除原来在Follow集中的代表Follow集的非终结符符号
                            listIterator.remove();
                            Set<String> targetList = map.get(string);
                            for (String str: targetList){
                                //往Follow集里面添加新的元素
                                listIterator.add(str);
                            }
                        }
                    }
                    Set<String> stringSet = new HashSet<>();
                    while(listIterator.hasPrevious()){
                        String string = listIterator.previous();
                        if (!(string.length()==1 && string.charAt(0)>=65 && string.charAt(0)<=90)){
                            stringSet.add(string);
                        }
                    }
                    stringSet.add("#");
                    entry2.setValue(stringSet);
                }
            }else{
                Set<String> set = new HashSet<>();
                set.add("#");
                map.put(setMap.getKey(), set);
            }
        }
    }

    /**
     * 查找目标非终结符的末尾字符
     * 查找结果可能是终结符也可能是非终结符
     * @param leftNonTerminal
     */
    public void searchTargetNonTerminalCharacter(String leftNonTerminal){
        Map<String,String> formula;
        //如果发生了左递归
        if (eliminateLeftRecursion.isHappenLeftRecursion()){
            formula = eliminateLeftRecursion.getNewFormula();
        }else{
            formula = eliminateLeftRecursion.getOldFormula();
        }
        String[]strings = formula.get(leftNonTerminal).split("\\|");
        for (String string: strings){   //待查找的式子
            for (Map.Entry<String,String> entry: formula.entrySet()){
                //非终结符出现的位置
                int index = string.indexOf(entry.getKey());
                //搜索右边式子中是否有非终结符
                if (index!=-1){
                    for (int i = index;i < string.length();i++){
                        String flag = ""+string.charAt(i);
                        if (i+1 < string.length() && string.charAt(i+1)=='\''){
                            flag = flag + "'";
                        }
                        if (flag.equals(entry.getKey())){
                            //没有单引号的兄弟，避免混淆
                            if (entry.getKey().length()==1 && i+1 < string.length() && string.charAt(i+1)=='\''){
                                continue;
                            }
                            Set<String> set = new HashSet<>();
                            //如果非终结符出现在最末尾
                            if (i == (string.length()-entry.getKey().length())){
                                //如果该终结符的follow集还未出现，则存放对应的follow集标识，后面再补上
                                if(!followCollectionMap.containsKey(entry.getKey())){
                                    if (!leftNonTerminal.equals(entry.getKey())){
                                        set.add(leftNonTerminal);
                                        followCollectionMap.put(entry.getKey(), set);
                                    }
                                }else{//如果已经出现，则直接赋值给它(PS:不能直接赋值给它，因为有可能前面已出现的也只是个标识...)
                                    set = followCollectionMap.get(entry.getKey());
                                    if (!leftNonTerminal.equals(entry.getKey())){
                                        set.add(leftNonTerminal);
                                        followCollectionMap.put(entry.getKey(), set);
                                    }
                                }
                            }else{
                                if (followCollectionMap.containsKey(flag)){
                                    set = followCollectionMap.get(flag);
                                }
                                String nextCharacter = ""+string.charAt(i+1);
                                //得区分有单引号和没单引号的，真无语...
                                if (i+2 < string.length() && string.charAt(i+2)=='\''){
                                    nextCharacter = nextCharacter + string.charAt(i+2);
                                }
                                //如果后面的符号不是非终结符，则直接加入到follow集中
                                if (firstCollection.getFirstCollectionMap().containsKey(nextCharacter)){
                                    set.addAll(eliminateFirstCollectionEmptySet(nextCharacter));
                                    //查看后面的非终结符中是否存在ε空集，如果存在则要再添加follow集
                                    if (isContainEmptySet(nextCharacter)){
                                        set.add(leftNonTerminal);
                                    }
                                }else{
                                    set.add(nextCharacter);
                                }
                                followCollectionMap.put(entry.getKey(), set);
                            }
                        }
                    }
                }
            }
        }
    }

    /**
     * 消除First集中的ε
     * @param nonTerminal 目标非终结符对应的式子
     * @return 返回消除ε后的集合
     */
    public Set<String> eliminateFirstCollectionEmptySet(String nonTerminal){
        Set<String> set = firstCollection.getFirstCollectionMap().get(nonTerminal);
        Set<String> result = new HashSet<>();
        //去除First集中的ε
        for (String character : set) {
            if (!character.equals("ε")) {
                result.add(character);
            }
        }
        return result;
    }

    /**
     * 查看相应First集中是否存在ε
     * @param nonTerminal 目标非终结符对应的式子
     * @return 存在则是true，否则是false
     */
    public boolean isContainEmptySet(String nonTerminal){
        Set<String> set = firstCollection.getFirstCollectionMap().get(nonTerminal);
        for (String string: set){
            if (string.equals("ε")){
                return true;
            }
        }
        return false;
    }

    //测试
    public static void main(String[] args) {
        FollowCollection followCollection = new FollowCollection("./src/input.txt");
    }
}

首先，在右侧式子中寻找在非终结符集中存在的非终结符，找到非终结符后，判断非终结符后面是否有元素

1. 如果非终结符后面没有元素或者后面元素是非终结符且该非终结符有ε，直接将该式子的Follow集直接添加进所找非终结符的Follow集中
2. 如果非终结符后面有元素，判断该元素是否是非终结符，如果是终结符的话，则直接往Follow集里面添加，如果是非终结符的话就往下递归查找该非终结符的里面的元素

5、判断是否是 LL1 文法

• JudgeIsLL1.java

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author 小关同学
 * @Create 2022/5/10 11:12
 * 判断是不是LL1文法
 */
public class JudgeIsLL1 {

    private FollowCollection followCollection;
    private FirstCollection firstCollection;
    //是否是LL1文法
    private boolean isLL1;

    public boolean isLL1() {
        return isLL1;
    }

    public FollowCollection getFollowCollection() {
        return followCollection;
    }

    public FirstCollection getFirstCollection() {
        return firstCollection;
    }

    public JudgeIsLL1(String fileSrc) {
        this.followCollection = new FollowCollection(fileSrc);
        this.firstCollection = followCollection.getFirstCollection();
        this.isLL1 = judgeIsLL1();
        System.out.println();
        if (isLL1){
            System.out.println("该文法是LL1文法");
        }else{
            System.out.println("该文法不是LL1文法");
        }
    }

    /**
     * 判断是否是LL1文法
     * @return
     */
    public boolean judgeIsLL1(){
        EliminateLeftRecursion eliminateLeftRecursion = followCollection.getEliminateLeftRecursion();
        boolean isHappenLeftRecursion = eliminateLeftRecursion.isHappenLeftRecursion();
        Map<String,String> formula;
        //如果发生了消除左递归
        if (isHappenLeftRecursion){
            formula = eliminateLeftRecursion.getNewFormula();
            boolean flag = formulaLoop(formula);
            return flag;
        }else{
            formula = eliminateLeftRecursion.getOldFormula();
            boolean flag = formulaLoop(formula);
            return flag;
        }
    }

    /**
     * 式子进行循环
     * @param formula
     * @return
     */
    public boolean formulaLoop(Map<String,String> formula){
        for (Map.Entry<String, String> entry: formula.entrySet()){
            String rightFormula = entry.getValue();
            String[]strings = rightFormula.split("\\|");
            for (int i = 0;i < strings.length;i++){
                for (int j = i;j < strings.length;j++){
                    if (i != j){
                        boolean flag = judgeIsIntersect(entry.getKey(), strings[i], strings[j]);
                        if (!flag){
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    /**
     * 判断式子是否是交集
     * @param leftNonTerminal
     * @param string1
     * @param string2
     * @return
     */
    public boolean judgeIsIntersect(String leftNonTerminal, String string1, String string2){
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();
        searchFirstCharacter(string1, set1);
        searchFirstCharacter(string2, set2);
        Map<String, Set<String>> followCollectionMap = followCollection.getFollowCollectionMap();
        Map<String, Set<String>> firstCollectionMap = firstCollection.getFirstCollectionMap();
        //如果存在ε的话
        if (set1.contains("ε") || set2.contains("ε")){
            boolean flag = compareFirstAndFollow(firstCollectionMap.get(leftNonTerminal), followCollectionMap.get(leftNonTerminal));
            if (!flag){
                return false;
            }
        }
        //不论存在不存在ε都要判断这个，两个条件不是互斥的，都得进行判断
        for (String stingX: set1){
            for (String stringY: set2){
                if (stingX.equals(stringY)){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 比较First集和Follow集是否有交集
     * @param first
     * @param follow
     * @return
     */
    public boolean compareFirstAndFollow(Set<String> first, Set<String> follow){
        if (follow==null || follow.size()==0){
            return true;
        }
        for (String sting1: first){
            for (String string2: follow){
                if (sting1.equals(string2)){
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 查找右边式子中的First集
     * @param nonTerminal
     * @param set
     */
    public void searchFirstCharacter(String nonTerminal, Set<String> set){
        String string = "" + nonTerminal.charAt(0);
        Map<String, Set<String>> firstCollectionMap = firstCollection.getFirstCollectionMap();
        if (firstCollectionMap.containsKey(string)){
            set.addAll(firstCollectionMap.get(string));
        }else{
            set.add(string);
        }
    }

    public static void main(String[] args) {
        JudgeIsLL1 judgeIsLL1 = new JudgeIsLL1("./src/input.txt");
    }

}

判断过程：遍历右侧的每个式子，判断它们每个式子的First集是否有交集，并判断式子是否存在ε，如果存在ε，则判断Follow集和First集是否有交集。

6、构建预测分析表

• AnalyzeTable.java

import java.util.*;

/**
 * @Author 小关同学
 * @Create 2022/5/2 22:37
 * 预测分析表
 */
public class AnalyzeTable {
    private JudgeIsLL1 judgeIsLL1;
    private FollowCollection followCollection;
    private FirstCollection firstCollection;
    private EliminateLeftRecursion eliminateLeftRecursion;
    private String[][] table;
    private Map<String,List<String>> formulaSplitted;

    //非终结符
    private Set<String> nonTerminalSet;
    //终结符
    private Set<String> terminalSet;

    public AnalyzeTable(String fileSrc) {
        this.judgeIsLL1 = new JudgeIsLL1(fileSrc);
        this.followCollection = judgeIsLL1.getFollowCollection();
        this.firstCollection = followCollection.getFirstCollection();
        this.eliminateLeftRecursion = firstCollection.getEliminateLeftRecursion();
    }

    public void init(){
        //判断是否是LL1文法
        if (judgeIsLL1.judgeIsLL1()){
            nonTerminalSet = new HashSet<>();
            terminalSet = new HashSet<>();
            Map<String, Set<String>> map = firstCollection.getFirstCollectionMap();
            for (Map.Entry<String, Set<String>> entry: map.entrySet()){
                nonTerminalSet.add(entry.getKey());
            }
            Map<String, String> formula;
            //是否进行了消除左递归
            if (eliminateLeftRecursion.isHappenLeftRecursion()){
                formula = eliminateLeftRecursion.getNewFormula();
            }else{
                formula = eliminateLeftRecursion.getOldFormula();
            }
            for (Map.Entry<String,String> entry: formula.entrySet()){
                String string = entry.getValue();
                for (int i = 0;i < string.length();i++){
                    String character = "" + string.charAt(i);
                    if (!nonTerminalSet.contains(character) && !character.equals("|") && !character.equals("'")){
                        if (!character.equals("ε")){
                            terminalSet.add(character);
                        }
                    }
                }
            }
            terminalSet.add("#");
            System.out.println("非终结符：" + nonTerminalSet);
            System.out.println("终结符：" + terminalSet);
        }
    }

    public void createTable(){
        List<String> nonTerminalList = new ArrayList<>(nonTerminalSet);
        List<String> terminalList = new ArrayList<>(terminalSet);
        table = new String[nonTerminalList.size()][terminalList.size()];
        for (int i = 0;i < nonTerminalList.size();i++){
            for (int j = 0;j < terminalList.size();j++){
                table[i][j] = findFormula(nonTerminalList.get(i), terminalList.get(j));
            }
        }

        System.out.printf("%-5s","");
        for (int i = 0;i<terminalList.size();i++){
            System.out.printf("%-13s",terminalList.get(i));
        }
        System.out.println();
        for (int i = 0;i < nonTerminalList.size();i++){
            System.out.printf("%-5s",nonTerminalList.get(i));
            for (int j = 0;j < terminalList.size();j++){
                System.out.printf("%-13s",table[i][j]);
            }
            System.out.println();
        }
    }

    public void splitFormula(){
        Map<String, String> formula;
        formulaSplitted = new HashMap<>();
        if (eliminateLeftRecursion.isHappenLeftRecursion()){
            formula = eliminateLeftRecursion.getNewFormula();
        }else{
            formula = eliminateLeftRecursion.getOldFormula();
        }
        for (Map.Entry<String,String> entry: formula.entrySet()){
            String[]strings = entry.getValue().split("\\|");
            List<String> list = new ArrayList<>(Arrays.asList(strings));
            formulaSplitted.put(entry.getKey(), list);
        }
    }

    public String findFormula(String nonTerminal, String terminal){
        List<String> strings = formulaSplitted.get(nonTerminal);
        Set<String> follow = followCollection.getFollowCollectionMap().get(nonTerminal);
        Set<String> first;
        for (String string: strings){
            first = searchFirstFromFormula(string);
            if (first.contains(terminal)){
                return nonTerminal+"——>"+string;
            }
            if (first.contains("ε") || string.equals("ε")){
                if (follow.contains(terminal)){
                    return nonTerminal+"——>ε";
                }
            }
        }
        return "ERROR";
    }

    public Set<String> searchFirstFromFormula(String formula){
        Map<String, Set<String>> firstCollectionMap = firstCollection.getFirstCollectionMap();
        Set<String> set = new HashSet<>();
        String character = ""+formula.charAt(0);
        if (firstCollectionMap.containsKey(character)){
            set = firstCollectionMap.get(character);
        }else{
            set.add(character);
        }
        return set;
    }


    public static void main(String[] args) {
        AnalyzeTable analyzeTable = new AnalyzeTable("./src/input.txt");
        analyzeTable.init();
        //如果不是LL1算法就不用构造预测分析表
        if (analyzeTable.judgeIsLL1.judgeIsLL1()){
            analyzeTable.splitFormula();
            System.out.println();
            System.out.println("预测分析表为：");
            analyzeTable.createTable();
        }
    }

}

初始化数据，比较右侧每个式子 First 集，如果该 First 集包含目标的终结符，则将该式子添加到该位置，如果该 First 集包含ε且待查找的终结符在 Follow 集里面，然后就添加非终结符+箭头+ ε 的式子

为了完成以上的任务，还需要创建一个 Formula 类保存数据。以上就是设计的主要方案。

/**
 * @Author 小关同学
 * @Create 2022/5/3 23:55
 */
public class Formula {
    //右侧式子
    private String right;
    //左侧非终结符
    private String left;
    //是否已经进行过间接消除左递归
    private boolean recursionFlag;

    public Formula() {
    }

    public Formula(String left, String right) {
        this.right = right;
        this.left = left;
    }

    public String getRight() {
        return right;
    }

    public void setRight(String right) {
        this.right = right;
    }

    public String getLeft() {
        return left;
    }

    public void setLeft(String left) {
        this.left = left;
    }

    public boolean isRecursionFlag() {
        return recursionFlag;
    }

    public void setRecursionFlag(boolean recursionFlag) {
        this.recursionFlag = recursionFlag;
    }

    @Override
    public String toString() {
        return right + "——>" + left;
    }
}

实验结果

最后

项目地址如下：
Github 地址：https://github.com/guanchanglong/GrammaticalAnalysis.git
麻烦各位可否在看代码的时候顺手给一颗星 ^ _ ^，举手之劳感激不尽。

PS：也可以到我的个人博客查看更多内容
个人博客地址：小关同学的博客

实验内容要求

一、实验目的 加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够 采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段 进行语法翻译。

二、实验内容 用预测分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工 具。

三、实验要求： 1. 对语法规则有明确的定义； 2. 编写的分析程序能够对测试用例进行正确的语法分析； 3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺 利完成语法分析过程； 4. 实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作 过程，说明错误处理的实现。

四、实验步骤 1. 定义目标语言的语法规则； 2. 求解预测分析方法需要的符号集和分析表； 3. 依次读入测试用例，根据预测分析的方法进行语法分析，直到源程序结束； 4. 对遇到的语法错误做出错误处理。

实验步骤

设计一个主类用来进行文件的输入，和结果的输出；然后按照四步走的策略来创建相对于的类操作。
第一步：创建LeftRecursion类来消除左递归，获取原始的产生式、终结符、非终结符；消除左递归之后的产生式、终结符和非终结符。然后简化产生式，每一个产生式只包含一个候选式。
第二步：创建FirstAndFollow类来求FIRST集和FOLLOW集。
第三步：创建AnalyzeTable类来获取分析表。
第四步：创建LL1Stack类来对测试用例进行入栈操作求解结果。
为了完成以上的任务，还需要创建一个Grammar类保存数据。以上就是设计的主要方案。

• LL1 .java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

/*
* 实验的主要方法：
* 1、消除左递归
*       1.1构造出终结符集、非终结符集
*       1.2把消除左递归得到的产生式进行简化，即一条产生式里面只有一个候选式
* 2、构造FIRST集和FOLLOW集
* 3、构造预测分析表
* 4、构造符号栈和输入串栈进行测试实例分析
* */

public class LL1 {

    //原始的产生式
    static ArrayList<String> expression;
    //语法器
    static Grammar grammar;

    public static void main(String []args) throws FileNotFoundException {

        grammar=new Grammar();
        expression=new ArrayList<>();

        //采用文件读入的方式
        File file=new File("E:\\code\\bytest\\test11\\test4.txt");
        try(Scanner input=new Scanner(file)) {
            while (input.hasNextLine()){
                String line=input.nextLine();
                if (line.equals("")){//采用空一行这种方式，下一行就是测试用例
                    grammar.setTestEx(input.nextLine());
                    break;
                }else {
                    expression.add(line);
                }
            }
        }

        //消除左递归
        LeftRecursion leftRecursion=new LeftRecursion();
        leftRecursion.setExpression(expression);
        leftRecursion.work();

        //分别给语法器开始设置非终结符集、终结符集、文法开始符号、简化之后的产生式
        grammar.setNa(leftRecursion.getNa());
        grammar.setNt(leftRecursion.getNt());
        grammar.setStart(leftRecursion.getStart());
        grammar.setSimpleExpression(leftRecursion.getSimpleExpression());

        System.out.println();
        System.out.println("--------------------------------------------------");
        System.out.println("消除左递归");
        System.out.println();

        System.out.println("产生式");
        for(Map.Entry<Character, ArrayList<String>> entry : grammar.getSimpleExpression().entrySet()){
            for (String s:entry.getValue()){
                System.out.println(entry.getKey()+"->"+s);
            }
        }

        System.out.println("--------------------------------------------------");
        System.out.println("非终结符");
        for (Character na:grammar.getNa().keySet()){
            System.out.printf("%-10c",na);
        }
        System.out.println();

        System.out.println("--------------------------------------------------");
        System.out.println("终结符");
        for (Character nt:grammar.getNt().keySet()){
            System.out.printf("%-10c",nt);
        }
        System.out.println();
        System.out.println("--------------------------------------------------");
        System.out.println("读取测试用例");
        System.out.println(grammar.getTestEx());

        //开始构造FIRST集和FOLLOW集
        FirstAndFollow firstAndFollow=new FirstAndFollow(grammar);
        firstAndFollow.work();
        grammar.setFirst(firstAndFollow.getFirst());
        grammar.setFollow(firstAndFollow.getFollow());

        System.out.println("--------------------------------------------------");
        System.out.println("FIRST集");
        for (Character na:grammar.getNa().keySet()){
            String FirstSet=grammar.getFirst().get(na).toString().replace("[","");
            FirstSet=FirstSet.replace("]","");
            System.out.println("FIRST("+na+")={"+FirstSet+"}");
        }
        System.out.println("--------------------------------------------------");
        System.out.println("FOLLOW集");
        for (Character na:grammar.getNa().keySet()){
            String FollowSet=grammar.getFollow().get(na).toString().replace("[","");
            FollowSet=FollowSet.replace("]","");
            System.out.println("FOLLOW("+na+")={"+FollowSet+"}");
        }

        //构造预测分析表
        AnalyzeTable analyzeTable=new AnalyzeTable(grammar);
        analyzeTable.work();
        grammar.setAnalyzeTable(analyzeTable.getAnalyzeTable());
        System.out.println("--------------------------------------------------");
        System.out.println("预测分析表");
        System.out.printf("%-11s","");
        for (Character nt:grammar.getNt().keySet()){
            if (nt!='ε') {
                System.out.printf("%-10s", nt);
            }
        }
        System.out.println();
        for (Character na:grammar.getNa().keySet()){
            System.out.printf("%-10s",na);
            for (int i=1;i<=grammar.getNt().size();i++){
                if(grammar.getAnalyzeTable()[grammar.getNa().get(na)][i]!=null){
                    System.out.printf("%-10s",na+"->"+ grammar.getAnalyzeTable()[grammar.getNa().get(na)][i]);
                }else{
                    System.out.printf("%-10s","");
                }
            }
            System.out.println("");
        }
        System.out.println("--------------------------------------------------");
        System.out.println("预测分析步骤");
        System.out.println();

        //利用LL1开始测试测试用例
        LL1Stack stack=new LL1Stack(grammar);
        stack.work();
    }
}

• Grammar.java

import java.util.*;

public class Grammar {
    //非终结符
    /*
    * 这里解释一下为什么要采用Map，而不是采用Set，因为我觉得采用map方便生成预测分析表，可以利用键对应的值，找到产生式在
    * 分析表中的位置。如 E->FA.要找到它在分析表中的位置，先要确定E在哪一行，直接判断FIRST(E)对应的符号所在哪一列，才可
    * 以确定表达式的位置，这样也有利于最后的测试用例测试。
    * */
    private Map<Character,Integer> Na;
    //终结符
    private Map<Character,Integer> Nt;
    //原始的产生式
    private ArrayList<String> expression;
    //简化之后的产生式
    private Map<Character,ArrayList<String>> simpleExpression;
    //开始符
    private Character start;
    //测试实例
    private String testEx;
    //分析表
    private String[][] analyzeTable;


    //first集
    private Map<Character, HashSet<Character>> First;
    //Follow集
    private Map<Character, HashSet<Character>> Follow;

    public Grammar() {
        Na=new LinkedHashMap<>();
        Nt=new LinkedHashMap<>();
        simpleExpression=new LinkedHashMap<>();
        Follow=new HashMap<>();
        First=new HashMap<>();
    }

    public Map<Character, Integer> getNa() {
        return Na;
    }

    public void setNa(Map<Character, Integer> na) {
        Na = na;
    }

    public Map<Character, Integer> getNt() {
        return Nt;
    }

    public void setNt(Map<Character, Integer> nt) {
        Nt = nt;
    }

    public ArrayList<String> getExpression() {
        return expression;
    }

    public void setExpression(ArrayList<String> expression) {
        this.expression = expression;
    }

    public Map<Character, ArrayList<String>> getSimpleExpression() {
        return simpleExpression;
    }

    public void setSimpleExpression(Map<Character, ArrayList<String>> simpleExpression) {
        this.simpleExpression = simpleExpression;
    }

    public Character getStart() {
        return start;
    }

    public void setStart(Character start) {
        this.start = start;
    }

    public Map<Character, HashSet<Character>> getFirst() {
        return First;
    }

    public void setFirst(Map<Character, HashSet<Character>> first) {
        First = first;
    }

    public Map<Character, HashSet<Character>> getFollow() {
        return Follow;
    }

    public void setFollow(Map<Character, HashSet<Character>> follow) {
        Follow = follow;
    }

    public String getTestEx() {
        return testEx;
    }

    public void setTestEx(String testEx) {
        this.testEx = testEx;
    }

    public String[][] getAnalyzeTable() {
        return analyzeTable;
    }

    public void setAnalyzeTable(String[][] analyzeTable) {
        this.analyzeTable = analyzeTable;
    }
}

• LeftRecursion.java

import java.util.*;

public class LeftRecursion {
    //非终结符
    private Map<Character,Integer> Na;
    //终结符
    private Map<Character,Integer> Nt;
    //原始的产生式
    private ArrayList<String> expression;
    //简化之后的产生式
    private Map<Character,ArrayList<String>> simpleExpression;
    //开始符
    private Character start;

    private int countNa;//非终结符的数量
    private int countNt;//终结符的数量

    public Map<Character, Integer> getNa() {
        return Na;
    }

    public void setNa(Map<Character, Integer> na) {
        Na = na;
    }

    public Map<Character, Integer> getNt() {
        return Nt;
    }

    public void setNt(Map<Character, Integer> nt) {
        Nt = nt;
    }

    public ArrayList<String> getExpression() {
        return expression;
    }

    public void setExpression(ArrayList<String> expression) {
        this.expression = expression;
    }

    public Map<Character, ArrayList<String>> getSimpleExpression() {
        return simpleExpression;
    }

    public void setSimpleExpression(Map<Character, ArrayList<String>> simpleExpression) {
        this.simpleExpression = simpleExpression;
    }

    public Character getStart() {
        return start;
    }

    public void setStart(Character start) {
        this.start = start;
    }

    public LeftRecursion(){
        Na=new LinkedHashMap<>();
        Nt=new LinkedHashMap<>();
        simpleExpression=new LinkedHashMap<>();
    };

    public LeftRecursion(Map<Character, Integer> na, Map<Character, Integer> nt, ArrayList<String> expression, Character start) {
        Na = na;
        Nt = nt;
        this.expression = expression;
        this.start = start;
    }

    //初始化得到初始的终结符和非终结符
    public void  init(){
        boolean hasKong=false;
        countNa=1;
        countNt=1;
        start=expression.get(0).charAt(0);
        for (String str:expression){
            String []term=str.split("->");
            if (!Na.containsKey(term[0].charAt(0))) {
                Na.put(term[0].charAt(0), countNa);
                countNa++;
            }
        }
        //输出初始的非终结符
        System.out.println("--------------------------------------------------");
        System.out.println("非终结符");
        for (Character na:Na.keySet()){
            System.out.printf("%-10c",na);
        }
        System.out.println();
        for (String str:expression){
            String []term=str.split("->");
            String []candidate=term[1].split("\\|");
            for (String s:candidate){
                for (int i=0;i<s.length();i++){
                    if (!Na.containsKey(s.charAt(i))&&!Nt.containsKey(s.charAt(i))){
                        if (s.charAt(i)!='ε') {
                            Nt.put(s.charAt(i), countNt);
                            countNt++;
                        }else{
                            hasKong=true;
                        }
                    }
                }
            }
        }


        if (!Nt.containsKey('#')) {
            Nt.put('#', countNt++);
        }

        if (hasKong){
            Nt.put('ε', countNt++);
        }
        //输出初始的终结符
        System.out.println("--------------------------------------------------");
        System.out.println("终结符");
        for (Character nt:Nt.keySet()){
            System.out.printf("%-10c",nt);
        }
    }

    //输出原始的产生式
    private void printOrigin(){
        System.out.println("原始产生式");
        for (String ex:expression){
            Character na=ex.charAt(0);
            String []parts=ex.split("->");
            String []candidates=parts[1].split("\\|");
            for (String s:candidates){
                System.out.println(na+"->"+s);
            }
        }
    }


    /*
    *完全消除左递归
    *
    * 如果文法G不含回路，也不含ε产生式，则下列算法可消除左递归（完全）
    * 1、把G的非终结符按任意顺序排列成P1,…,Pn
    * 2、for i:=1 to n do
    *            for j:=1 to i-1 do
    *               把形如 Pi  → P j γ  的规则改写成 P i  →  δ1 | ...   | δk γ,  其中 P i  → δ1 γ | ...   | δk γ ；
    *               消除关于Pi的直接左递归
    * 3、化简由2得到的文法（取消无用非终结符产生式）
    *
    * */
    private void allLeftTest(){
        for (int i=0;i<expression.size();i++){
            String []str=expression.get(i).split("->");
            String []candidate=str[1].split("\\|");
            String newExpression=str[1];
            Character c=str[0].charAt(0);
            ArrayList<String>notNeedChange=new ArrayList<>();
            notNeedChange.addAll(Arrays.asList(candidate));
            boolean hasLeft=false;
            for (int j=0;j<=i-1;j++){
                candidate=newExpression.split("\\|");
                newExpression="";
                for (int k=0;k<candidate.length;k++){
                    if (candidate[k].charAt(0)==expression.get(j).charAt(0)){
                        String []toReplace=expression.get(j).split("->");
                        if (expression.get(j).contains("|")){
                            candidate[k]=toReplace[1].replaceAll("\\|",candidate[k].substring(1)+"|")+candidate[k].substring(1);
                        }else {
                            candidate[k] = toReplace[1] + candidate[k].substring(1);
                        }
                    }
                    if (candidate[k].charAt(0)==c)
                        hasLeft = true;
                    newExpression+=candidate[k];
                    if (k!=candidate.length-1)
                        newExpression+="|";
                }
                candidate=newExpression.split("\\|");
            }
            if (i==0) {
                for (int j = 0; j < candidate.length; j++) {
                    if (candidate[j].charAt(0) == c) {
                        hasLeft = true;
                        break;
                    }
                }
            }

            if (hasLeft){
                disLeft(i,c,candidate);
                if (!Nt.containsKey('ε')) {
                    Nt.put('ε', countNt);
                }
            }else{
                ArrayList<String> right=new ArrayList<>();
                if (simpleExpression.get(c)!=null) {
                    right.addAll(simpleExpression.get(c));
                }
                right.addAll(notNeedChange);
                simpleExpression.put(c,right);
            }
        }
    }

    private void disLeft(int index,Character c,String []test){

        //出现左递归的话需要做出改变的候选式子，即带左递归的式子
        ArrayList<String>needChange=new ArrayList<>();
        //不带左递归的候选式
        ArrayList<String>notNeedChange=new ArrayList<>();
        //先找到一个合适的非终结符，来替代
        char reCh = 'A';
        for (int i='A'-'A';i<26;i++){
            reCh= (char) ('A'+i);
            if (!Na.containsKey(reCh)&&!Nt.containsKey(reCh)){
                break;
            }
        }
        //找到造成左递归的候选式
        for (String s:test){
            if (s.charAt(0)==c){
                needChange.add(s);
            }else{
                notNeedChange.add(s);
            }
        }

        //增加到非终结符集
        Na.put(reCh,countNa++);

        ArrayList<String> right=new ArrayList<>();
        //获取原来已经简化的产生式
        if (simpleExpression.get(c)!=null) {
            right.addAll(simpleExpression.get(c));
        }
        //消除左递归
        for (int i=0;i<notNeedChange.size();i++){
            right.add(notNeedChange.get(i)+reCh);
        }
        simpleExpression.put(c,right);

        //新的产生式
        ArrayList<String> right2=new ArrayList<>();
        for (String string:needChange){
            string=string.substring(1)+reCh;
            right2.add(string);
        }
        right2.add("ε");
        simpleExpression.put(reCh,right2);

    }

    //直接消除左递归。这个方法不能完全消除左递归
    public void testLeftRecur(){
        for (String str:expression){
            //判断有没有左递归
            boolean hasLeft=false;
            String []term=str.split("->");
            String []candidate=term[1].split("\\|");
            //出现左递归的话需要做出改变的候选式子，即带左递归的式子
            ArrayList<String>needChange=new ArrayList<>();
            //不带左递归的候选式
            ArrayList<String>notNeedChange=new ArrayList<>();

            //逐个查看候选式，以确定那些需要修改
            for (String s:candidate){
                //出现左递归吗
                if (s.charAt(0)==term[0].charAt(0)) {
                    needChange.add(s);
                    hasLeft=true;
                }
                else
                    notNeedChange.add(s);
            }



            //出现左递归了
            if (hasLeft){
                //先找到一个合适的非终结符，来替代
                char reCh = 'A';
                for (int i=0;i<26;i++){
                    reCh= (char) ('A'+i);
                    if (!Na.containsKey(reCh)&&!Nt.containsKey(reCh)){
                        break;
                    }
                }
                //增加到非终结符集
                Na.put(reCh,countNa++);
                ArrayList<String> right=new ArrayList<>();
                //获取原来已经简化的产生式
                if (simpleExpression.get(term[0].charAt(0))!=null) {
                    right.addAll(simpleExpression.get(term[0].charAt(0)));
                }
                //消除左递归
                for (String string:notNeedChange){
                    right.add(string+reCh);
                }
                simpleExpression.put(term[0].charAt(0),right);
                ArrayList<String> right2=new ArrayList<>();
                for (String string:needChange){
                    string=string.substring(1)+reCh;
                    right2.add(string);
                }
                right2.add("ε");
                simpleExpression.put(reCh,right2);
                Nt.put('ε',countNt);
            }else {
                ArrayList<String> right=new ArrayList<>();
                if (simpleExpression.get(term[0].charAt(0))!=null) {
                    right.addAll(simpleExpression.get(term[0].charAt(0)));
                }
                right.addAll(notNeedChange);
                simpleExpression.put(term[0].charAt(0),right);
            }
        }
    }

    public void work(){
        printOrigin();
        init();
        allLeftTest();
//        testLeftRecur();
    }

}

• FirstAndFollow.java

import java.util.*;

public class FirstAndFollow {
    private Map<Character, HashSet<Character>> First;
    private Map<Character, HashSet<Character>> Follow;
    private Grammar grammar;

    public FirstAndFollow(Grammar grammar) {
        this.grammar = grammar;
        First=new HashMap<>();
        Follow=new HashMap<>();
    }

    public Map<Character, HashSet<Character>> getFirst() {
        return First;
    }

    public void setFirst(Map<Character, HashSet<Character>> first) {
        First = first;
    }

    public Map<Character, HashSet<Character>> getFollow() {
        return Follow;
    }

    public void setFollow(Map<Character, HashSet<Character>> follow) {
        Follow = follow;
    }

    public Grammar getGrammar() {
        return grammar;
    }

    public void setGrammar(Grammar grammar) {
        this.grammar = grammar;
    }

    //求FIRST集
    private void getFirstSet(){
        for (Character character:grammar.getNa().keySet()){
                First.put(character, getNaFirstSet(character));
        }
    }


    /*
    * 具体方法：
    * 1.若X ∈VT，则FIRST(X)={X}
    * 2.若X∈VN，且有产生式X→a…，则把a加入到FIRST(X)中；若X→ɛ也是一条 产生式，则把 ɛ 也加到FIRST(X)中。
    * 3.若X→Y…是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ɛ元素都加到 FIRST(X)中；
    * 若X → Y1Y2…YK 是一个产生式，Y1,Y2,…,Y(i-1)都是非终结符， 而且，对于任何j,1≤j ≤i-1, FIRST(Yj)都
    * 含有ɛ (即Y1..Y(i-1)=>ɛ)，则把 FIRST(Yj)中的所有非ɛ元素都加到FIRST(X)中；
    * 特别是，若所有的FIRST(Yj , j=1,2,…,K)均含有ɛ，则把 ɛ 加到FRIST(X)中。
    * */

    private HashSet<Character> getNaFirstSet(Character character){
        HashSet<Character> term=new HashSet<>();
        for (String ex:grammar.getSimpleExpression().get(character)){
            //第一个字符是终结符
            if (grammar.getNt().containsKey(ex.charAt(0))){
                term.add(ex.charAt(0));
            }
            //第一个字符是非终结符
            else{
                if (First.get(ex.charAt(0))!=null){
                    term.addAll(First.get(ex.charAt(0)));
                }else {
                    term.addAll(getNaFirstSet(ex.charAt(0)));
                }
            }
        }
        return term;
    }

    //求FOLLOW集
    private void getFollowSet(){
        for (Character character:grammar.getNa().keySet()){
            Follow.put(character, getNaFollowSet(character));
        }
    }

    /*
    * 1、对于文法的开始符号S，置#于FOLLOW(S) 中；
    * 2、若A→α B β是一个产生式，则把FIRST(β)\{ɛ}加至FOLLOW(B)中；
    * 3、若A→α B是一个产生式，或A→ αBβ是 一个产生式而β可以推导出ɛ (即 ɛ FIRST(β))， 则把FOLLOW(A)加至FOLLOW(B)中。
     * */
    private HashSet<Character> getNaFollowSet(Character c){
        HashSet<Character> term=new HashSet<>();
        if (c==grammar.getStart()){
            term.add('#');
        }
        for (Map.Entry<Character, ArrayList<String>> entry : grammar.getSimpleExpression().entrySet()){
            for (String s:entry.getValue()){
//                System.out.println(entry.getKey()+"->"+s);
                if (s.indexOf(c)!=-1){
                    if (s.indexOf(c)==s.length()-1){
                        if (entry.getKey()!=c) {
                            if (Follow.get(entry.getKey()) != null) {
                                term.addAll(Follow.get(entry.getKey()));
                            } else {
                                term.addAll(getNaFollowSet(entry.getKey()));
                            }
                        }
                    }else{
                        //所求非终结符后的第一个字符
                        Character last=s.charAt(s.indexOf(c)+1);
                        //如果是终结符
                        if (grammar.getNt().containsKey(last)){
                            term.add(last);
                        }
                        //如果是非终结符
                        else{
                            HashSet<Character> firstToAdd=new HashSet<>(First.get(last));
                            firstToAdd.remove('ε');
                            term.addAll(firstToAdd);
                            if (grammar.getSimpleExpression().get(entry.getKey()).contains("ε")&&entry.getKey()!=c){
                                if (Follow.get(entry.getKey())!=null){
                                    term.addAll(Follow.get(entry.getKey()));
                                }
                                else {
                                    term.addAll(getNaFollowSet(entry.getKey()));
                                }
                            }
                        }
                    }
                }
            }
        }
        return term;
    }

    public void work(){
        getFirstSet();
        getFollowSet();
    }
}

• AnalyzeTable.java

public class AnalyzeTable {

    //分析表
    private String[][] analyzeTable;
    private Grammar grammar;

    public AnalyzeTable(Grammar grammar) {
        this.grammar=grammar;
        analyzeTable=new String[grammar.getNa().size()+1][grammar.getNt().size()+1];
    }

    public String[][] getAnalyzeTable() {
        return analyzeTable;
    }

    public void setAnalyzeTable(String[][] analyzeTable) {
        this.analyzeTable = analyzeTable;
    }

    public Grammar getGrammar() {
        return grammar;
    }

    public void setGrammar(Grammar grammar) {
        this.grammar = grammar;
    }


    /*
    *预测分析表的构造方法
    * 1、对文法G的每个产生式A→α执行第2步 和第3步；
    * 2、对每个终结符a∈FIRST(α)，把A→α加至M[A,a]中，
    * 3、若ɛ∈FIRST(α)，则对任何b∈FOLLOW(A) ， 把A→α加至M[A,b]中，
    * 4、把所有无定义的M[A,a]标上“出错标志”。
     * */

    private void genTable(){
        for (Character Na:grammar.getNa().keySet()){
            int row=grammar.getNa().get(Na);
            for (Character Nt:grammar.getFirst().get(Na)){
                //第3步的情况
                if (Nt=='ε'){
                    for (Character follow:grammar.getFollow().get(Na)){
                        analyzeTable[row][grammar.getNt().get(follow)]="ε";
                    }
                }else {
                    //执行第1步
                    for (String s:grammar.getSimpleExpression().get(Na)) {
                        //这里还需要进一步判断是因为一个非终结符有可能对应多个产生式，我们需要寻找出遇到这个终结符时对应的产生式

                        //如果这个产生式的第一个符号是终结符且等于当前遇到的终结符
                        if (grammar.getNt().containsKey(s.charAt(0))){
                            if (Nt==s.charAt(0)){
                                analyzeTable[row][grammar.getNt().get(Nt)]=s;
                                break;
                            }
                        }else{
                            if (grammar.getFirst().get(s.charAt(0)).contains(Nt)){
                                analyzeTable[row][grammar.getNt().get(Nt)]=s;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    public void work(){
        genTable();
    }



}

• LL1Stack.java

import java.util.Stack;

public class LL1Stack {
    private Grammar grammar;
    //这个是符号栈
    private Stack<Character> analyzeStack;
    //这个是输入串栈
    private Stack<Character> remain;

    public LL1Stack(Grammar grammar) {
        this.grammar = grammar;
        analyzeStack=new Stack<>();
        remain=new Stack<>();
        remain.push('#');
        //将输入串反向压栈
        for (int i=grammar.getTestEx().length()-1;i>=0;i--){
            remain.push(grammar.getTestEx().charAt(i));
        }
        analyzeStack.push('#');
        analyzeStack.push(grammar.getStart());
    }

    public Grammar getGrammar() {
        return grammar;
    }

    public void setGrammar(Grammar grammar) {
        this.grammar = grammar;
    }

    public Stack<Character> getAnalyzeStack() {
        return analyzeStack;
    }

    public void setAnalyzeStack(Stack<Character> analyzeStack) {
        this.analyzeStack = analyzeStack;
    }

    public Stack<Character> getRemain() {
        return remain;
    }

    public void setRemain(Stack<Character> remain) {
        this.remain = remain;
    }

    /*
    * LL1分析器工作步骤：
    * 1、如果X=a='#，分析成功退出
    * 2、如果X=a!='#，X推出，a指向写一个输入符号
    * 3、X为非终结符，查找分析表。M[x,a]是候选式反序压栈；M[x,a]=空串,弹栈什么都不压；M[x,a]为空白，出错
    * 4、然后x!=a,出错
    * */
    private void analyze(){
        System.out.printf("%-21s%-24s%-20s%-20s\n","步骤","符号栈","输入串","所用产生式");
        System.out.printf("%-25d%-25s%-25s%-25s\n",0,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"");
        int step=1;
        while (!remain.empty()){
            if (analyzeStack.peek()==remain.peek()&&remain.peek()=='#'){
                System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"分析成功，输入合法");
                break;
            }
            else if (analyzeStack.peek()==remain.peek()&&remain.peek()!='#'){
                analyzeStack.pop();
                remain.pop();
                System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"");
                step++;
            }
            else if (grammar.getNa().containsKey(analyzeStack.peek())){
                if (grammar.getAnalyzeTable()[grammar.getNa().get(analyzeStack.peek())][grammar.getNt().get(remain.peek())]==null){
                    System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"这里出错了，不存在M["+analyzeStack.peek()+","+remain.peek()+"]");
                    break;
                }
                else if (grammar.getAnalyzeTable()[grammar.getNa().get(analyzeStack.peek())][grammar.getNt().get(remain.peek())].equals("ε")){
                    Character na=analyzeStack.pop();
                    System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),na+"->"+"ε");
                    step++;
                }else {
                    String ex=grammar.getAnalyzeTable()[grammar.getNa().get(analyzeStack.peek())][grammar.getNt().get(remain.peek())];
                    Character na=analyzeStack.pop();
                    for (int i=ex.length()-1;i>=0;i--){
                        analyzeStack.push(ex.charAt(i));
                    }
                    System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),na+"->"+ex);
                    step++;
                }

            }else{
                System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"这里出错了，"+analyzeStack.peek()+"!="+remain.peek());
                break;
            }
        }
    }

    //不会正则表达式的蒟蒻只能这样子写了
    private String printStack(String s){
        s=s.replace(", ","");
        s=s.replace("[","");
        s=s.replace("]","");
        return s;
    }

    public void work(){
        analyze();
    }

}

实验结果

1、输入数据：
E->E+T|T
T->T*F|F
F->(E)|i

i*i+i
输出结果：i*i+i是合法的





2、输入数据
E->E+T|T
T->T*F|F
F->(E)|i

i*ii
输出结果：i*ii是不合法的