编译原理之 LL1 语法分析器（Java）

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

LL1 语法分析器实验要求

PS：

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

测试用例

老师要求的测试用例：

我的测试用例：

//直接左递归
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.*;


public class FileUtil {


    
    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.*;


public class EliminateLeftRecursion {

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

    public boolean isHappenLeftRecursion() {
        return isHappenLeftRecursion;
    }

    public Map getNewFormula() {
        return newFormula;
    }

    public Map getOldFormula() {
        return oldFormula;
    }


    
    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);
            }
        }
    }

    
    public boolean eliminateDirectLeftRecursion(String leftFormula, String rightNonTerminal) {
        //右侧由|分隔的符号集
        List 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;
        }
    }

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

            //消除式子的直接左递归
            boolean flag = eliminateDirectLeftRecursion(formulaEntity.getLeft(), formulaEntity.getRight());
            //如果式子没有直接左递归，看看是否是间接左递归
            if (!flag){
                String string1 = "";
                //右侧由|分隔的符号集
                List 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
                            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 entry: newFormula.entrySet()){
                System.out.println(entry.getKey()+"——>"+entry.getValue());
            }
        }
    }
    
    public List returnRightFormulaStringList(String flagNonTerminal, String leftFormula, String rightFormula){
        List result = recursionSearch(flagNonTerminal, leftFormula);
        boolean flag = false;
        ListIterator listIterator = result.listIterator();
        while(listIterator.hasNext()){
            String string = listIterator.next();
            if (string.equals("ε") && rightFormula.length()!=0){
                List 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 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
                string1 = string1 + "|";
            }
        }
        return string1;
    }

    
    public void perform(String nonTerminal){
        for(Formula formulaEntity: param){
            if (formulaEntity.getLeft().equals(nonTerminal)){
                formulaEntity.setRecursionFlag(true);
            }
        }
    }


    
    public List recursionSearch(String nonTerminal, String targetCharacter){
        String rightFormula = oldFormula.get(nonTerminal);
        List 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 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();
    }
}

消除左递归主要有两点

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

E——>E+T|T
T——>T*F|F
F——>(E)|i
执行消除左递归后的结果：
E——>TE'
E'——>+TE'|ε
T——>FT'
T'——>*FT'|ε
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——>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.*;


public class FirstCollection {

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

    public Map> 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 formula = eliminateLeftRecursion.getNewFormula();
        for (Map.Entry entry: formula.entrySet()){
            String leftNonTerminal = entry.getKey();
            Set set = new HashSet<>();
            searchFirstCharacter(leftNonTerminal, set);
            firstCollectionMap.put(leftNonTerminal, set);
        }

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


    
    public void searchFirstCharacter(String nonTerminal, Set set){
        Map 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> entry: firstCollection.firstCollectionMap.entrySet()){
            System.out.println(entry.getKey() + "的FIRST集：" + entry.getValue().toString());
        }
    }
}

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

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

4、生成 Follow 集

FollowCollection.java

import java.util.*;


public class FollowCollection {

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

    public EliminateLeftRecursion getEliminateLeftRecursion() {
        return eliminateLeftRecursion;
    }

    public FirstCollection getFirstCollection() {
        return firstCollection;
    }

    public Map> getFollowCollectionMap() {
        return followCollectionMap;
    }

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


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

        for (Map.Entry> setMap: firstCollection.getFirstCollectionMap().entrySet()) {
            if (followCollectionMap.containsKey(setMap.getKey())){
                for (Map.Entry> entry2 : followCollectionMap.entrySet()) {
                    Set set = entry2.getValue();
                    ListIterator listIterator = new ArrayList<>(set).listIterator();
                    while(listIterator.hasNext()){
                        String string = listIterator.next();
                        if (map.containsKey(string)){
                            //删除原来在Follow集中的代表Follow集的非终结符符号
                            listIterator.remove();
                            Set targetList = map.get(string);
                            for (String str: targetList){
                                //往Follow集里面添加新的元素
                                listIterator.add(str);
                            }
                        }
                    }
                    Set 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 set = new HashSet<>();
                set.add("#");
                map.put(setMap.getKey(), set);
            }
        }
    }

    
    public void searchTargetNonTerminalCharacter(String leftNonTerminal){
        Map formula;
        //如果发生了左递归
        if (eliminateLeftRecursion.isHappenLeftRecursion()){
            formula = eliminateLeftRecursion.getNewFormula();
        }else{
            formula = eliminateLeftRecursion.getOldFormula();
        }
        String[]strings = formula.get(leftNonTerminal).split("\|");
        for (String string: strings){   //待查找的式子
            for (Map.Entry 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 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);
                            }
                        }
                    }
                }
            }
        }
    }

    
    public Set eliminateFirstCollectionEmptySet(String nonTerminal){
        Set set = firstCollection.getFirstCollectionMap().get(nonTerminal);
        Set result = new HashSet<>();
        //去除First集中的ε
        for (String character : set) {
            if (!character.equals("ε")) {
                result.add(character);
            }
        }
        return result;
    }

    
    public boolean isContainEmptySet(String nonTerminal){
        Set 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");
    }
}

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

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

5、判断是否是 LL1 文法

JudgeIsLL1.java

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


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文法");
        }
    }

    
    public boolean judgeIsLL1(){
        EliminateLeftRecursion eliminateLeftRecursion = followCollection.getEliminateLeftRecursion();
        boolean isHappenLeftRecursion = eliminateLeftRecursion.isHappenLeftRecursion();
        Map formula;
        //如果发生了消除左递归
        if (isHappenLeftRecursion){
            formula = eliminateLeftRecursion.getNewFormula();
            boolean flag = formulaLoop(formula);
            return flag;
        }else{
            formula = eliminateLeftRecursion.getOldFormula();
            boolean flag = formulaLoop(formula);
            return flag;
        }
    }

    
    public boolean formulaLoop(Map formula){
        for (Map.Entry 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;
    }

    
    public boolean judgeIsIntersect(String leftNonTerminal, String string1, String string2){
        Set set1 = new HashSet<>();
        Set set2 = new HashSet<>();
        searchFirstCharacter(string1, set1);
        searchFirstCharacter(string2, set2);
        Map> followCollectionMap = followCollection.getFollowCollectionMap();
        Map> 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;
    }

    
    public boolean compareFirstAndFollow(Set first, Set 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;
    }


    
    public void searchFirstCharacter(String nonTerminal, Set set){
        String string = "" + nonTerminal.charAt(0);
        Map> 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.*;


public class AnalyzeTable {
    private JudgeIsLL1 judgeIsLL1;
    private FollowCollection followCollection;
    private FirstCollection firstCollection;
    private EliminateLeftRecursion eliminateLeftRecursion;
    private String[][] table;
    private Map> formulaSplitted;

    //非终结符
    private Set nonTerminalSet;
    //终结符
    private Set 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> map = firstCollection.getFirstCollectionMap();
            for (Map.Entry> entry: map.entrySet()){
                nonTerminalSet.add(entry.getKey());
            }
            Map formula;
            //是否进行了消除左递归
            if (eliminateLeftRecursion.isHappenLeftRecursion()){
                formula = eliminateLeftRecursion.getNewFormula();
            }else{
                formula = eliminateLeftRecursion.getOldFormula();
            }
            for (Map.Entry 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 nonTerminalList = new ArrayList<>(nonTerminalSet);
        List 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
            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 formula;
        formulaSplitted = new HashMap<>();
        if (eliminateLeftRecursion.isHappenLeftRecursion()){
            formula = eliminateLeftRecursion.getNewFormula();
        }else{
            formula = eliminateLeftRecursion.getOldFormula();
        }
        for (Map.Entry entry: formula.entrySet()){
            String[]strings = entry.getValue().split("\|");
            List list = new ArrayList<>(Arrays.asList(strings));
            formulaSplitted.put(entry.getKey(), list);
        }
    }

    public String findFormula(String nonTerminal, String terminal){
        List strings = formulaSplitted.get(nonTerminal);
        Set follow = followCollection.getFollowCollectionMap().get(nonTerminal);
        Set 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 searchFirstFromFormula(String formula){
        Map> firstCollectionMap = firstCollection.getFirstCollectionMap();
        Set 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 类保存数据。以上就是设计的主要方案。


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：也可以到我的个人博客查看更多内容
个人博客地址：小关同学的博客

编译原理之 LL1 语法分析器（Java）

Java相关栏目本月热门文章