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

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

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