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

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 麻烦各位可否在看代码的时候顺手给一颗星 ^ _ ^，举手之劳感激不尽。