如何将 LR(1) Parse 翻译成抽象语法树？

Question

我已经编写了一个 table 驱动的 LR(1) 解析器，它工作得很好，但是我在将解析转换为语法的阶段有点断开连接 tree/abstract语法树。这是一个我非常热衷的项目，但我真的只是在这里走进了死胡同。提前谢谢你的帮助。

编辑：另外，我的解析器只使用一个二维数组和一个动作对象，告诉它下一步去哪里，或者如果它减少去哪里以及弹出多少项目。我注意到很多人使用访客模式。我不确定他们怎么知道要制作什么类型的节点。

这是上下文的下推自动机

 while (lexer.hasNext() || parseStack.size() > 0) {
        Action topOfStack = parseStack.peek();
        token = parseStack.size() > 0 ? lexer.nextToken() : new Token(TokenType.EOF, "EOF");
        topOfStack.setToken(token);

        int row = topOfStack.getTransitionIndex();
        int column = getTerminalIndex(token.getLexeme());

        column = token.getType() == TokenType.IDENTIFIER
                && !terminalsContain(token.getLexeme()) ? 0 : column;

        Action action = actionTable[row][column];

        if (action instanceof Accept) {
            System.out.println("valid parse!!!!!!");
        } else if (action instanceof Reduction) {
            Reduction reduction = (Reduction) action;

            popStack(parseStack, reduction.getNumberOfItemsToPop());
            column = reduction.getTransitionIndex();
            row = parseStack.peek().getTransitionIndex();

            parseStack.push(new Action(gotoTable[row][column]));
            lexer.backupTokenStream();
        } else if (action != null) {
            parseStack.push(actionTable[row][column]);
        } else {
            System.out.println("Parse error");
            System.out.println("On token: " + token.getLexeme());
            break;
        }

Answer 1

LR解析过程中的每一次归约都对应解析树中的一个内部节点。被减少的规则是内部 AST 节点，从堆栈中弹出的项目对应于该内部节点的子节点。 goto推送的item对应内部节点，shift动作推送的item对应AST的叶子（token）

将所有这些放在一起，您可以通过在每次进行归约时创建一个新的内部节点并将所有内容适当地连接在一起来轻松构建 AST。

如何将 LR(1) Parse 翻译成抽象语法树？

How do I translate LR(1) Parse into a Abstract syntax tree?

abstract-syntax-tree

lr1

semantic-analysis

concrete-syntax-tree

lr