解析在java中找到给定语法的第一个和第二个集合

Question

我被赋予了要完成的问题，以及找到第一个和后续的算法，但我的问题是我无法找到一个数据结构来实现找到这些集合

import java.util.Stack;

public class FirstFollowSet {

private final String[] term_tokens = { "begin", "end", ";", "if", "then", "else", "fi", "i", "=", "+", "-", "*",
        "/", "(", ")", "const" };
private final static String[] non_term_tokens = { "Start", "Prog", "Block", "Body", "S", "E", "T", "F" };
private static RuleStack rules;
private Stack<String> firstSet;
private Stack<String> followSet;

private boolean is_terminal(String str) {
    boolean test = false;
    for (int i = 0; i < term_tokens.length; i++) {
        if (str.equals(term_tokens[i]))
            test = true;
    }

    return test;
}

private boolean is_non_term(String str){
    for(int i = 0; i < non_term_tokens.length; i++)
    {
        if(str.equals(non_term_tokens[i]))
        {
            return true;
        }

    }
    return false;
}

private class Rule{
    String def, token;

    public Rule()
    {
        def = "";
        token = "";
    }

    public Rule(String d, String t)
    {
        def = d;
        token = t;
    }

    public String getDef() {
        return def;
    }

    public String getToken() {
        return token;
    }

    public String toString()
    {
        String str = "";
        str+= token + " " + def + '\n';
        return str;
    }
}

public class RuleStack{
    Stack<Rule> rules;

    public RuleStack(String grammar)
    {
        if(grammar.equals("G1"));
        {
            rules = new Stack();
            Rule rule = new Rule("Prog", "Start");
            rules.push(rule);
            rule = new Rule("Block #", "Prog");
            rules.push(rule);
            rule = new Rule("begin Body end", "Block");
            rules.push(rule);
            rule = new Rule("begin S end", "Body");
            rules.push(rule);
            rule = new Rule("Body ; S", "Body");
            rules.push(rule);
            rule = new Rule("S", "Body");
            rules.push(rule);
            rule = new Rule("if E then S else S fi", "S");
            rules.push(rule);
            rule = new Rule("if E else S fi", "S");
            rules.push(rule);
            rule = new Rule("i = E", "S");
            rules.push(rule);
            rule = new Rule("Block", "S");
            rules.push(rule);
            rule = new Rule("E + T", "E");
            rules.push(rule);
            rule = new Rule("E * T", "E");
            rules.push(rule);
            rule = new Rule("T", "E");
            rules.push(rule);
            rule = new Rule("T * F", "T");
            rules.push(rule);
            rule = new Rule("T / F", "T");
            rules.push(rule);
            rule = new Rule("F", "T");
            rules.push(rule);
            rule = new Rule("const", "F");
            rules.push(rule);
            rule = new Rule("( E )", "F");
            rules.push(rule);
        }
    }

}

public FirstFollowSet()
{
    rules = new RuleStack("G1");
    firstSet = new Stack();
    followSet = new Stack();
}

public String FindFirstSet(String str, Stack<String> used)
{   
    if(used.contains(str))
    {
        return null;
    }
    String firstToken = "";
    String win = "";
    if(str.indexOf(" ") != -1)
        firstToken = str.substring(0, str.indexOf(" "));
    else
        firstToken = str;
    if(is_terminal(firstToken))
    {
        if(!(firstSet.contains(firstToken)))
            win = firstToken;
            if(win.equals("") != true)
                firstSet.push(win);
    }

    else if(is_non_term(firstToken) && !(used.contains(firstToken)))
    {
        used.push(firstToken);
        if(firstToken.equals("lambda"))
        {
            if(!(firstSet.contains(firstToken)))
            win = firstToken;
        }
        else
        {
            RuleStack rules = new RuleStack("G1");
            while(rules.rules.isEmpty() != true)
            {
                Rule winner = rules.rules.pop();
                if(winner.token.equals(firstToken))
                {
                    String test = FindFirstSet(winner.def, used);
                    if(!(test.equals("lambda")))
                    {
                        if(!(firstSet.contains(test)))
                        win = test;
                    }
                }
            }
        }
    }

    return win;
}

public String findFollowSet(String str)
{
    if(str.equals("S"))
    {
        followSet.push("$");
    }

    for(int i = 0; i < non_term_tokens.length; i++)
    {
        if(str.contains(non_term_tokens[i]))
        {
            int index = str.indexOf(non_term_tokens[i]);
            Stack<String> used = new Stack();
            FirstFollowSet test = new FirstFollowSet();
            if(index > 0 && index < str.length()-1)
            {
                test.FindFirstSet(str, used);
                while(test.firstSet.isEmpty() != true)
                {
                    String token = firstSet.pop();
                    if(!(token.equals("lambda")))
                        test.followSet.push(token);
                }
            }

            else if(index > 0 && index == str.length()-1)
            {

            }
        }
    }
}

public static void main(String[] args) {
    FirstFollowSet test = new FirstFollowSet();
    Stack<String> used = new Stack();
    test.FindFirstSet("S", used);
    while(test.firstSet.isEmpty() != true)
    {
        String str = test.firstSet.pop();
        System.out.println(str);
    }
}

}

这是到目前为止我所拥有的代码，find first set工作得很好，但是findfollowset方法我不太确定如何实现。我能想到的唯一想法似乎是为每个非终端符号做一个堆栈，应用算法，并将返回的每个终端符号添加到它所属的集合中。这种方法只是觉得它需要更多的工作

如果有人曾经解决过这个问题，或者看到了解决这个问题的方法，我只想知道使用了什么样的数据结构，以及算法是如何为该结构实现的

感谢您抽出时间阅读本文，感谢您的反馈

Answer 1

包装模型

导入java。util。ArrayList

/** * *@author celeste */ 公共类公理a{

public char getSimbolo() {
    return simbolo;
}

public void setSimbolo(char simbolo) {
    this.simbolo = simbolo;
}

public ArrayList<Character> getPrimeros() {
    return primeros;
}

public void setPrimeros(ArrayList<Character> primeros) {
    this.primeros = primeros;
}

public ArrayList<Character> getSiguientes() {
    return siguientes;
}

public void setSiguientes(ArrayList<Character> siguientes) {
    this.siguientes = siguientes;
}

public ArrayList<Character> getPredictivos() {
    return predictivos;
}

public void setPredictivos(ArrayList<Character> predictivos) {
    this.predictivos = predictivos;
}

public ArrayList<Character> getRegla() {
    return regla;
}

public void setRegla(ArrayList<Character> regla) {
    this.regla = regla;
}
private ArrayList<Character> primeros = new ArrayList<>();
private ArrayList<Character> siguientes = new ArrayList<>();
private ArrayList<Character> predictivos = new ArrayList<>();
private ArrayList<Character> regla = new ArrayList<>();
private char simbolo;

}