Преобразование дерева разбора в AST

Позвольте мне сначала задать вопрос: могу ли я преобразовать дерево разбора, реализующее эту конкретную грамматику в AST тривиально.Преобразование дерева разбора в AST

Я получил эту грамматику, чтобы построить дерево разбора:

literal := INTEGER | FLOAT | TRUE | FALSE . 

designator := IDENTIFIER { "[" expression0 "]" } . 

op0 := ">=" | "<=" | "!=" | "==" | ">" | "<" . 
op1 := "+" | "-" | "or" . 
op2 := "*" | "/" | "and" . 

expression0 := expression1 [ op0 expression1 ] . 
expression1 := expression2 { op1 expression2 } . 
expression2 := expression3 { op2 expression3 } . 
expression3 := "not" expression3 
     | "(" expression0 ")" 
     | designator 
     | call-expression 
     | literal .

Для этого конкретного примера:

func main() : void { 
    let a = 1 + 2 + 3 + 4; 
}

Мой анализатор будет генерировать (часть) дерево разбора как таковой

  EXPRESSION1 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(1)(lineNum:2, charPos:10) 
       OP1 
        ADD(lineNum:2, charPos:12) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(2)(lineNum:2, charPos:14) 
       OP1 
        ADD(lineNum:2, charPos:16) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(3)(lineNum:2, charPos:18) 
       OP1 
        ADD(lineNum:2, charPos:20) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(4)(lineNum:2, charPos:22)

Просто обратите внимание, как эти ветви деревьев под EXPRESSION1 идут:

EXPRESSION2 + EXPRESSION2 + EXPRESSION2 + EXPRESSION2

который оператор + не соответствует его двум операндам. Так что мне кажется, что в преобразовании АСТ я не могу получить AST, который помогает генерировать 3-адресный IR-код, просто подтягивая оператора для замены нетерминального EXPRESSION1.

Для достижения этой цели, грамматика я бы написал для этого языка будет как этот вместо

expression1 := expression2 | expression1 + expression2 (1) 
expression2 := expression3 | expression2 * expression3 (2) 
expression3 := literal         (3)

, которые ветвь под ВЫРАЖЕНИЕ1 только

EXPRESSION1 + EXPRESSION2

Однако эта грамматика не LL (1), так как | FIRST (выражение2) | = | {literal, +} | > 1.

Он задает вопрос, что (1) что было бы самым элегантным и тривиальным способом преобразования этого дерева разбора? (2) является ли мое построение дерева разбора полной потерей времени для этой грамматики, что я должен был начать кодирование АСТ вместо этого?

источник

2017-02-23 Davis

Вы можете рассмотреть реальные различия между деревом синтаксического анализа и абстрактным деревом синтаксиса. См. Мой ответ: http://stackoverflow.com/questions/1888854/what-is-the-difference-between-an-abstract-syntax-tree-and-a-concrete-syntax-tre/1916687#1916687 –

Это похоже очень хорошо. Я слышал некоторые приятные свойства о GLR. Теперь для сжатия используется сжатый CST. Спасибо за информацию. – Davis

Ну, это какое-то школьное задание, которое я не смог выяснить до крайнего срока.Мне нужно следовать конкретному руководству. Я был слишком глуп, чтобы не осознавать, что проблема с грамматикой выражения заключается в том, что цель АСТ была не просто «упрощенной» версией КНТ. Древовидная структура отличается. Я просто немного разозлился. – Davis

Я считаю, что вы хотите, чтобы произвести AST как:

 ADD 
    /\ 
    1 ADD 
     /\ 
     2 ADD 
     /\ 
      3 4

Но, наверное, вы заметили, что ваш синтаксического дерева на самом деле плоский список не представляющий простой отправной точкой для групповых операторов и их операндов в один проход. В любом случае кодирование более продвинутого парсера, распознавание древовидной структуры и применение сокращений грамматики - не тривиальная задача.

Следовательно, прежде чем начинать делать это, вы можете рассмотреть некоторые существующие генераторы синтаксического анализатора, такие как yacc или ANTLR. Вероятно, вам нужно будет переписать свою грамматику, чтобы создать правила, ориентированные на операторов, вместо того, чтобы рассматривать их как утилиту рекурсии. Грамматика, не являющаяся классическим LL (1), может быть не большой проблемой, поскольку современные генераторы (например, ANTLR) могут обрабатывать грамматики LL (k) с более крупными искажениями, предикатами и т. Д. И просто обходить проблемы этого типа.

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

источник

2017-02-23 16:23:50 jszpilewski

Означает ли это, что придерживаться грамматики LL (1) является по своей природе плохой дизайн, поскольку он обрабатывает приоритет оператора, но терпит неудачу при ассоциативности операторов? – Davis

@Davis Targeting LL (1) хорош, но довольно часто непрактичен и не является абсолютно необходимым, когда вы можете использовать расширенный генератор парсеров LL (k), такой как ANTLR. – jszpilewski

Преобразование дерева разбора в AST

ответ

Смежные вопросы