java ll1文法实现

LL(1)文法是一种特殊的上下文无关文法，它可以用于构建预测分析器，从而对输入的字符串进行语法分析。以下是一个Java LL(1)文法的实现示例：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class LL1Grammar {
    private static final String EPSILON = "";
    private static final String DOLLAR = "$";
    private Set<String> terminals;
    private Set<String> nonTerminals;
    private String startSymbol;
    private String[][] parsingTable;
    private GrammarProduction[] productions;

    public LL1Grammar(String startSymbol, GrammarProduction[] productions) {
        this.startSymbol = startSymbol;
        this.productions = productions;
        this.terminals = new HashSet<>();
        this.nonTerminals = new HashSet<>();
        for (GrammarProduction production : productions) {
            nonTerminals.add(production.getLhs());
            String[] rhs = production.getRhs();
            for (String symbol : rhs) {
                if (!nonTerminals.contains(symbol) && !symbol.equals(EPSILON)) {
                    terminals.add(symbol);
                }
            }
        }
        terminals.add(DOLLAR);
        nonTerminals.add(startSymbol);
        buildParsingTable();
    }

    public boolean parse(String input) {
        Stack<String> stack = new Stack<>();
        stack.push(DOLLAR);
        stack.push(startSymbol);
        int inputPointer = 0;
        while (!stack.isEmpty()) {
            String topSymbol = stack.peek();
            String inputSymbol = inputPointer < input.length() ? String.valueOf(input.charAt(inputPointer)) : DOLLAR;
            if (topSymbol.equals(inputSymbol)) {
                stack.pop();
                inputPointer++;
            } else if (terminals.contains(topSymbol)) {
                return false;
            } else {
                int row = getNonTerminalIndex(topSymbol);
                int col = getTerminalIndex(inputSymbol);
                String[] productionRhs = parsingTable[row][col].split(" ");
                if (productionRhs[0].equals(EPSILON)) {
                    stack.pop();
                } else {
                    stack.pop();
                    for (int i = productionRhs.length - 1; i >= 0; i--) {
                        stack.push(productionRhs[i]);
                    }
                }
            }
        }
        return true;
    }

    private void buildParsingTable() {
        int numNonTerminals = nonTerminals.size();
        int numTerminals = terminals.size();
        parsingTable = new String[numNonTerminals][numTerminals];
        for (int i = 0; i < numNonTerminals; i++) {
            Arrays.fill(parsingTable[i], "");
        }
        for (int i = 0; i < productions.length; i++) {
            String lhs = productions[i].getLhs();
            String[] rhs = productions[i].getRhs();
            int row = getNonTerminalIndex(lhs);
            for (String symbol : first(rhs)) {
                if (!symbol.equals(EPSILON)) {
                    int col = getTerminalIndex(symbol);
                    if (!parsingTable[row][col].equals("")) {
                        throw new RuntimeException("Grammar is not LL(1)!");
                    }
                    parsingTable[row][col] = i + "";
                } else {
                    for (String followSymbol : follow(lhs)) {
                        int col = getTerminalIndex(followSymbol);
                        if (!parsingTable[row][col].equals("")) {
                            throw new RuntimeException("Grammar is not LL(1)!");
                        }
                        parsingTable[row][col] = i + "";
                    }
                }
            }
        }
    }

    private Set<String> first(String[] symbols) {
        Set<String> result = new HashSet<>();
        for (String symbol : symbols) {
            if (terminals.contains(symbol)) {
                result.add(symbol);
                break;
            } else {
                int index = getNonTerminalIndex(symbol);
                String[] rhs = productions[index].getRhs();
                Set<String> first = first(rhs);
                result.addAll(first);
                if (!first.contains(EPSILON)) {
                    break;
                }
            }
        }
        return result;
    }

    private Set<String> follow(String symbol) {
        Set<String> result = new HashSet<>();
        if (symbol.equals(startSymbol)) {
            result.add(DOLLAR);
        }
        for (GrammarProduction production : productions) {
            String[] rhs = production.getRhs();
            for (int i = 0; i < rhs.length; i++) {
                if (rhs[i].equals(symbol)) {
                    if (i == rhs.length - 1) {
                        if (!production.getLhs().equals(symbol)) {
                            result.addAll(follow(production.getLhs()));
                        }
                    } else {
                        Set<String> first = first(Arrays.copyOfRange(rhs, i + 1, rhs.length));
                        result.addAll(first);
                        if (first.contains(EPSILON)) {
                            result.addAll(follow(production.getLhs()));
                        }
                    }
                }
            }
        }
        return result;
    }

    private int getNonTerminalIndex(String symbol) {
        int index = 0;
        for (String nonTerminal : nonTerminals) {
            if (nonTerminal.equals(symbol)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    private int getTerminalIndex(String symbol) {
        int index = 0;
        for (String terminal : terminals) {
            if (terminal.equals(symbol)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    private static class GrammarProduction {
        private String lhs;
        private String[] rhs;

        public GrammarProduction(String lhs, String[] rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
        }

        public String getLhs() {
            return lhs;
        }

        public String[] getRhs() {
            return rhs;
        }
    }
}

这个示例实现了一个LL(1)文法类，包括了构建预测分析表和使用分析表进行语法分析的方法。你可以使用该类来定义自己的文法，并使用parse()方法对输入的字符串进行语法分析。