语法制导的应用-526互联

语法制导的实现可以有很多中，如后缀翻译方案，L属性定义的SDT，遍历语法分析树

这里选择使用语法分析树来实现，即

1.建立一棵语法分析树

2.按照从左到右的深度优先顺序执行动作

3.产生式体中的动作在它左边的所有文法符号都被匹配之后立刻执行

这样选择的理由是，非常通用任何SDT都可以实现

一、首先改造之前的语法分析，在分析过程中构造一个语法分析树，在分析完成后返回根节点

语法分析树是推导的图形表示形式，每个内部结点表示一个产生式的应用。

因此，只要在使用产生式进行规约时生成相应树结构就可以完成构造

public Node parseWithNode(Grammar grammar, List<Symbol> inputs, ParsingTable table) {
        LinkedList<Symbol> inputQueue = new LinkedList<>(inputs);
        inputQueue.addLast(Terminal.dollar);

        // 符号栈 （方便打印）
        Stack<Symbol> symbolStack = new Stack<>();
        final int initStateCode = 0;// 初始状态
        // 状态栈
        Stack<StateStackItem> stateStack = new Stack<>();
        stateStack.push(StateStackItem.of(initStateCode));

        while (true) {
            StateStackItem state = stateStack.peek();// 当前状态
            printStack(state, symbolStack, inputQueue);

            Symbol symbol = inputQueue.getFirst();
            Action action = table.getAction(state.getState(), symbol);
            if (action instanceof ShiftAction) {// 移入
                inputQueue.removeFirst();

                ShiftAction shiftAction = (ShiftAction) action;
                stateStack.push(StateStackItem.of(shiftAction.getToId()));
                symbolStack.push(symbol);

                LogUtil.print("移入:" + shiftAction.getToId());
                LogUtil.newline();
            } else if (action instanceof ReduceAction) {// 规约
                ReduceAction reduceAction = (ReduceAction) action;
                Production production = reduceAction.getProduction();

                Node node = Node.of(production.getHead());
                node.setProduction(production);
                for (Symbol bo : production.getBody()) {
                    if (bo.equals(Terminal.epsilon)) {// 形如 E -> ·ε，不需要弹出产生式的体，直接进行规约
                        continue;
                    }
                    StateStackItem item = stateStack.pop();
                    Symbol childSymbol = symbolStack.pop();
                    Node child;
                    if (item.getValue() == null) {// 终结符
                        child = Node.of(childSymbol);
                    } else {
                        child = (Node) item.getValue();
                    }
                    // 由于符号栈的顶端时产生式体的右边，将后面的节点添加到子节点列表的前面，即左边
                    node.addChildFirst(child);
                }
                symbolStack.push(production.getHead());

                state = stateStack.peek();
                Integer gotoState = table.gotoSet(state.getState(), production.getHead());
                StateStackItem item = StateStackItem.of(gotoState);
                item.setValue(node);
                stateStack.push(item);

                LogUtil.print("规约:" + production + " GOTO:" + gotoState);
                LogUtil.newline();

            } else if (action instanceof AcceptAction) {
                LogUtil.print("接受");
                LogUtil.newline();
                return (Node) stateStack.peek().getValue();
            } else {
                LogUtil.print("错误");
                LogUtil.newline();
                return null;
            }
        }
    }