Как перевести LR(1) Parse в абстрактное синтаксическое дерево?

Question

Я закодировал анализатор LR(1), управляемый таблицей, и он работает очень хорошо, однако у меня возникли некоторые проблемы на этапе анализа синтаксического дерева / абстрактного синтаксического дерева. Это проект, которым я очень увлечен, но я просто зашел в тупик. Спасибо за вашу помощь заранее.

Редактировать: Кроме того, мой анализатор просто использует 2d-массив и объект действия, который сообщает ему, куда идти дальше или, если это сокращение, куда идти и сколько элементов выскочить. Я заметил, что многие люди используют шаблон посетителей. Я не уверен, как они знают, какой тип узла сделать.

Вот автомат для контекста

 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, а элементы, извлеченные из стека, соответствуют дочерним элементам этого внутреннего узла. Элемент, выдвигаемый для перехода, соответствует внутреннему узлу, тогда как элемент, выдвигаемый действиями сдвига, соответствует листьям (токенам) AST.

Собрав все это вместе, вы можете легко построить AST, создавая новый внутренний узел каждый раз, когда вы делаете сокращение, и соединяйте все вместе соответствующим образом.