用Java写LL1语法分析器

下面是一个简单的用Java实现LL1语法分析器的示例代码：

import java.util.*;

public class LL1Parser {
    private List<String> terminals;
    private List<String> nonTerminals;
    private Map<String, List<String>> productions;
    private Map<String, Set<String>> firstSets;
    private Map<String, Set<String>> followSets;
    private Map<String, Map<String, String>> parsingTable;

    public LL1Parser(List<String> terminals, List<String> nonTerminals, Map<String, List<String>> productions) {
        this.terminals = terminals;
        this.nonTerminals = nonTerminals;
        this.productions = productions;
        this.firstSets = new HashMap<>();
        this.followSets = new HashMap<>();
        this.parsingTable = new HashMap<>();
    }

    public void computeFirstSets() {
        for (String terminal : terminals) {
            firstSets.put(terminal, new HashSet<>(Arrays.asList(terminal)));
        }
        for (String nonTerminal : nonTerminals) {
            firstSets.put(nonTerminal, new HashSet<>());
        }
        boolean changed = true;
        while (changed) {
            changed = false;
            for (String nonTerminal : nonTerminals) {
                for (String production : productions.get(nonTerminal)) {
                    boolean allNullable = true;
                    for (int i = 0; i < production.length(); i++) {
                        String symbol = production.substring(i, i + 1);
                        if (terminals.contains(symbol)) {
                            if (!firstSets.get(nonTerminal).contains(symbol)) {
                                firstSets.get(nonTerminal).add(symbol);
                                changed = true;
                            }
                            allNullable = false;
                            break;
                        } else {
                            Set<String> firstSet = firstSets.get(symbol);
                            if (!firstSet.contains("")) {
                                allNullable = false;
                            }
                            for (String firstSymbol : firstSet) {
                                if (!firstSets.get(nonTerminal).contains(firstSymbol)) {
                                    firstSets.get(nonTerminal).add(firstSymbol);
                                    changed = true;
                                }
                            }
                            if (!allNullable) {
                                break;
                            }
                        }
                    }
                    if (allNullable && !firstSets.get(nonTerminal).contains("")) {
                        firstSets.get(nonTerminal).add("");
                        changed = true;
                    }
                }
            }
        }
    }

    public void computeFollowSets() {
        for (String nonTerminal : nonTerminals) {
            followSets.put(nonTerminal, new HashSet<>());
        }
        followSets.get(nonTerminals.get(0)).add("$");
        boolean changed = true;
        while (changed) {
            changed = false;
            for (String nonTerminal : nonTerminals) {
                for (String production : productions.get(nonTerminal)) {
                    for (int i = 0; i < production.length(); i++) {
                        String symbol = production.substring(i, i + 1);
                        if (terminals.contains(symbol)) {
                            continue;
                        }
                        Set<String> followSet = followSets.get(symbol);
                        boolean isLastSymbol = i == production.length() - 1;
                        if (!isLastSymbol) {
                            String nextSymbol = production.substring(i + 1, i + 2);
                            Set<String> firstSet = firstSets.get(nextSymbol);
                            boolean allNullable = true;
                            for (String firstSymbol : firstSet) {
                                if (!followSet.contains(firstSymbol)) {
                                    followSet.add(firstSymbol);
                                    changed = true;
                                }
                                if (!firstSymbol.equals("")) {
                                    allNullable = false;
                                }
                            }
                            if (allNullable) {
                                Set<String> followSetOfNonTerminal = followSets.get(nonTerminal);
                                for (String followSymbol : followSetOfNonTerminal) {
                                    if (!followSet.contains(followSymbol)) {
                                        followSet.add(followSymbol);
                                        changed = true;
                                    }
                                }
                            }
                        } else {
                            Set<String> followSetOfNonTerminal = followSets.get(nonTerminal);
                            for (String followSymbol : followSetOfNonTerminal) {
                                if (!followSet.contains(followSymbol)) {
                                    followSet.add(followSymbol);
                                    changed = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    public void buildParsingTable() {
        for (String nonTerminal : nonTerminals) {
            parsingTable.put(nonTerminal, new HashMap<>());
            for (String terminal : terminals) {
                parsingTable.get(nonTerminal).put(terminal, "");
            }
        }
        for (String nonTerminal : nonTerminals) {
            for (String production : productions.get(nonTerminal)) {
                Set<String> firstSet = computeFirstSet(production);
                for (String symbol : firstSet) {
                    if (!symbol.equals("")) {
                        parsingTable.get(nonTerminal).put(symbol, production);
                    } else {
                        Set<String> followSet = followSets.get(nonTerminal);
                        for (String followSymbol : followSet) {
                            parsingTable.get(nonTerminal).put(followSymbol, production);
                        }
                    }
                }
            }
        }
    }

    private Set<String> computeFirstSet(String production) {
        Set<String> firstSet = new HashSet<>();
        boolean allNullable = true;
        for (int i = 0; i < production.length(); i++) {
            String symbol = production.substring(i, i + 1);
            if (terminals.contains(symbol)) {
                firstSet.add(symbol);
                allNullable = false;
                break;
            } else {
                Set<String> symbolFirstSet = firstSets.get(symbol);
                firstSet.addAll(symbolFirstSet);
                if (!symbolFirstSet.contains("")) {
                    allNullable = false;
                    break;
                }
            }
        }
        if (allNullable) {
            firstSet.add("");
        }
        return firstSet;
    }

    public boolean parse(List<String> input) {
        Stack<String> stack = new Stack<>();
        stack.push("$");
        stack.push(nonTerminals.get(0));
        int inputIndex = 0;
        while (!stack.isEmpty()) {
            String top = stack.pop();
            if (terminals.contains(top)) {
                if (!top.equals(input.get(inputIndex))) {
                    return false;
                }
                inputIndex++;
            } else {
                String production = parsingTable.get(top).get(input.get(inputIndex));
                if (production.equals("")) {
                    return false;
                }
                for (int i = production.length() - 1; i >= 0; i--) {
                    String symbol = production.substring(i, i + 1);
                    if (!symbol.equals("")) {
                        stack.push(symbol);
                    }
                }
            }
        }
        return true;
    }
}

这个LL1语法分析器可以通过以下方式进行使用：

List<String> terminals = Arrays.asList("+", "*", "(", ")", "id", "$");
List<String> nonTerminals = Arrays.asList("E", "T", "F");
Map<String, List<String>> productions = new HashMap<>();
productions.put("E", Arrays.asList("T E'"));
productions.put("E'", Arrays.asList("+ T E'", ""));
productions.put("T", Arrays.asList("F T'"));
productions.put("T'", Arrays.asList("* F T'", ""));
productions.put("F", Arrays.asList("( E )", "id"));

LL1Parser parser = new LL1Parser(terminals, nonTerminals, productions);
parser.computeFirstSets();
parser.computeFollowSets();
parser.buildParsingTable();

List<String> input = Arrays.asList("id", "+", "id", "*", "id", "$");
boolean result = parser.parse(input);
System.out.println(result); // prints "true"

这个示例代码实现了一个LL1语法分析器，用来分析一个简单的四则运算表达式语言。它可以分析包含加、乘、括号和标识符的表达式，并检测语法错误。