如何将LR（1）解析转换为抽象语法树？ [英] How do I translate LR(1) Parse into a Abstract syntax tree?

问题描述

我已经编码了一个表驱动的LR（1）解析器，但是它工作得很好，但是在解析语法树/抽象语法树的阶段，我有些脱节。这是一个我非常热衷的项目，但是我真的在这里陷入了僵局。提前谢谢你的帮助。

I have coded a table driven LR(1) parser and it is working very well however I am having a bit of a disconnect on the stage of turing a parse into a syntax tree/abstract syntax tree. This is a project that I m very passionate about but I have really just hit a dead end here. Thank you for your help in advance.

编辑：同样，我的解析器仅使用一个2d数组和一个动作对象，该对象告诉它接下来要去哪里，或者它减少了哪里去以及弹出了多少项目。我注意到许多人使用访客模式。我不确定他们如何知道要制作哪种类型的节点。

Also my parser just uses a 2d array and an action object that tells it where to go next or if its a reduction where to go and how many items to pop. I noticed that many people use the visitor pattern. Im not sure how they know what type of node to make.

这是上下文的下推自动机

Here is the pushdown automata for context

 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;
        }

推荐答案

LR解析中的每个缩减进程对应于解析树中的内部节点。减少的规则是内部AST节点，并且从堆栈中弹出的项目对应于该内部节点的子代。推送到goto的项对应于内部节点，而通过shift动作推动的项对应于AST的叶子（令牌）。

Each reduction in the LR parsing process corresponds to an internal node in the parse tree. The rule being reduced is the internal AST node, and the items popped off the stack correspond to the children of that internal node. The item pushed for the goto corresponds to the internal node, while those pushed by shift actions correspond to leaves (tokens) of the AST.

将所有内容放在一起，您可以每次进行精简并适当地将所有连线正确连接在一起时，只需创建一个新的内部节点即可轻松构建AST。

Putting all that together, you can easily build an AST by createing a new internal node every time you do a reduction and wiring everything together appropriately.

这篇关于如何将LR（1）解析转换为抽象语法树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！