用java写控制台输入LR(0)文法并分析程序识别活前缀DFA构造并输出

首先，让我们来了解一下LR(0)文法和活前缀DFA。

LR(0)文法是一种用于语法分析的形式文法。它的特点是可以根据输入符号串的任意前缀在不需要回溯的情况下进行推导，即从左到右扫描输入符号串，同时从栈顶到栈底扫描LR(0)项集，直到找到一个可以进行规约的项集，或者发现输入符号串不符合文法。

活前缀DFA是一种用于确定LR(0)自动机状态的算法。它的特点是可以根据当前LR(0)项集中的活前缀（即尚未匹配完毕的输入符号）和规约符号（即待规约的非终结符）来确定下一个状态的编号。

接下来，我们可以开始编写Java代码了。首先，我们需要定义一个类来表示LR(0)项：

class LR0Item {
    private String left;  // 产生式左部
    private String right;  // 产生式右部
    private int dot;  // 点的位置

    public LR0Item(String left, String right, int dot) {
        this.left = left;
        this.right = right;
        this.dot = dot;
    }

    public String getLeft() {
        return left;
    }

    public String getRight() {
        return right;
    }

    public int getDot() {
        return dot;
    }

    public boolean isReduceItem() {
        return dot == right.length();
    }

    public String getNextSymbol() {
        return right.substring(dot, dot + 1);
    }

    public LR0Item advanceDot() {
        return new LR0Item(left, right, dot + 1);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof LR0Item) {
            LR0Item item = (LR0Item) obj;
            return left.equals(item.left) && right.equals(item.right) && dot == item.dot;
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return left.hashCode() * 31 + right.hashCode() * 17 + dot;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(left).append(" -> ");
        for (int i = 0; i < right.length(); i++) {
            if (i == dot) {
                builder.append("·");
            }
            builder.append(right.charAt(i));
        }
        if (dot == right.length()) {
            builder.append("·");
        }
        return builder.toString();
    }
}

LR0Item类包含了一个产生式的左部、右部和点的位置。它还提供了一些方便的方法，如判断是否为规约项、获取下一个符号、移动点等。equals()、hashCode()和toString()方法用于比较、哈希和输出。

接下来，我们需要定义一个类来表示LR(0)项集：

class LR0ItemSet {
    private Set<LR0Item> items = new HashSet<>();

    public void addItem(LR0Item item) {
        items.add(item);
    }

    public Set<LR0Item> getItems() {
        return items;
    }

    public Set<String> getLookaheads() {
        Set<String> lookaheads = new HashSet<>();
        for (LR0Item item : items) {
            if (item.isReduceItem()) {
                lookaheads.addAll(getLookaheads(item.getLeft()));
            }
        }
        return lookaheads;
    }

    private Set<String> getLookaheads(String symbol) {
        Set<String> lookaheads = new HashSet<>();
        for (LR0Item item : items) {
            if (item.getLeft().equals(symbol)) {
                lookaheads.add("$");
                String lookahead = item.getNextSymbol();
                if (!lookahead.equals("") && !lookahead.equals("$")) {
                    lookaheads.add(lookahead);
                } else {
                    lookaheads.addAll(getLookaheads(item.getLeft()));
                }
            }
        }
        return lookaheads;
    }

    public boolean containsItem(LR0Item item) {
        return items.contains(item);
    }

    public LR0ItemSet closure(Map<String, List<String>> grammar) {
        LR0ItemSet closure = new LR0ItemSet();
        closure.items.addAll(items);
        Queue<LR0Item> queue = new LinkedList<>(items);
        while (!queue.isEmpty()) {
            LR0Item item = queue.poll();
            String symbol = item.getNextSymbol();
            if (!symbol.equals("") && !item.isReduceItem()) {
                for (String right : grammar.getOrDefault(symbol, Collections.emptyList())) {
                    LR0Item newItem = new LR0Item(symbol, right, 0);
                    if (!closure.containsItem(newItem)) {
                        closure.addItem(newItem);
                        queue.offer(newItem);
                    }
                }
            }
        }
        return closure;
    }

    public LR0ItemSet goTo(String symbol, Map<String, List<String>> grammar) {
        LR0ItemSet next = new LR0ItemSet();
        for (LR0Item item : items) {
            if (!item.isReduceItem() && item.getNextSymbol().equals(symbol)) {
                next.addItem(item.advanceDot());
            }
        }
        return next.closure(grammar);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof LR0ItemSet) {
            LR0ItemSet set = (LR0ItemSet) obj;
            return items.equals(set.items);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return items.hashCode();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (LR0Item item : items) {
            builder.append(item).append("\n");
        }
        return builder.toString();
    }
}

LR0ItemSet类包含了一个LR(0)项的集合。它提供了一些方便的方法，如获取向前看符号、计算闭包、计算转移等。equals()、hashCode()和toString()方法用于比较、哈希和输出。

接下来，我们需要定义一个类来表示活前缀DFA：

class LR0DFA {
    private Map<LR0ItemSet, Integer> states = new HashMap<>();
    private Map<Integer, Map<String, Integer>> transitions = new HashMap<>();

    public void addState(LR0ItemSet state) {
        if (!states.containsKey(state)) {
            states.put(state, states.size());
        }
    }

    public int getStateCount() {
        return states.size();
    }

    public int getStateId(LR0ItemSet state) {
        return states.get(state);
    }

    public LR0ItemSet getState(int id) {
        for (Map.Entry<LR0ItemSet, Integer> entry : states.entrySet()) {
            if (entry.getValue() == id) {
                return entry.getKey();
            }
        }
        return null;
    }

    public void addTransition(int from, String symbol, int to) {
        transitions.computeIfAbsent(from, k -> new HashMap<>()).put(symbol, to);
    }

    public int getTransition(int from, String symbol) {
        return transitions.getOrDefault(from, Collections.emptyMap()).getOrDefault(symbol, -1);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (Map.Entry<LR0ItemSet, Integer> entry : states.entrySet()) {
            builder.append("State ").append(entry.getValue()).append(":\n");
            builder.append(entry.getKey()).append("\n");
            for (Map.Entry<String, Integer> transition : transitions.getOrDefault(entry.getValue(), Collections.emptyMap()).entrySet()) {
                builder.append("  ").append(transition.getKey()).append(" -> ").append(transition.getValue()).append("\n");
            }
        }
        return builder.toString();
    }
}

LR0DFA类包含了一个状态编号到LR(0)项集的映射和一个转移函数。它提供了一些方便的方法，如添加状态、获取状态数量、获取状态编号、添加转移、获取转移等。toString()方法用于输出。

最后，我们可以编写主程序来实现控制台输入LR(0)文法并分析程序识别活前缀DFA构造并输出：

import java.util.*;

public class LR0Parser {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Map<String, List<String>> grammar = new HashMap<>();
        while (true) {
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) {
                break;
            }
            String[] parts = line.split("\\s*->\\s*");
            String left = parts[0];
            String[] right = parts[1].split("\\s*\\|\\s*");
            grammar.computeIfAbsent(left, k -> new ArrayList<>()).addAll(Arrays.asList(right));
        }
        LR0DFA dfa = buildLR0DFA(grammar);
        System.out.println(dfa);
    }

    private static LR0DFA buildLR0DFA(Map<String, List<String>> grammar) {
        LR0ItemSet initial = new LR0ItemSet();
        initial.addItem(new LR0Item("_S", "S", 0));
        LR0DFA dfa = new LR0DFA();
        dfa.addState(initial);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(dfa.getStateId(initial));
        while (!queue.isEmpty()) {
            int from = queue.poll();
            LR0ItemSet fromSet = dfa.getState(from);
            Set<String> symbols = new HashSet<>();
            for (LR0Item item : fromSet.getItems()) {
                symbols.add(item.getNextSymbol());
            }
            for (String symbol : symbols) {
                LR0ItemSet toSet = fromSet.goTo(symbol, grammar);
                if (!toSet.getItems().isEmpty()) {
                    dfa.addState(toSet);
                    int to = dfa.getStateId(toSet);
                    dfa.addTransition(from, symbol, to);
                    if (!queue.contains(to)) {
                        queue.offer(to);
                    }
                }
            }
        }
        return dfa;
    }
}

主程序首先从标准输入读取LR(0)文法，并将其转换为产生式的左部和右部。接着，它调用buildLR0DFA()方法来构造LR(0)自动机的状态和转移函数，并输出结果。

buildLR0DFA()方法使用广度优先搜索算法来遍历所有可能的LR(0)项集。它首先创建一个初始项集，然后加入自动机的状态中。接着，它从状态队列中取出一个状态，并根据每个可能的终结符计算下一个状态。如果下一个状态非空且还未加入自动机的状态中，则将其加入自动机的状态中，并记录转移函数。最后，它将下一个状态加入状态队列中，以便继续搜索。

这样，我们就成功地用Java实现了控制台输入LR(0)文法并分析程序识别活前缀DFA构造并输出。