Как мне сделать TreeParser в ANTLR3?

Question

Я пытаюсь изучать разбор языка для удовольствия...

Я создал грамматику ANTLR, которая, я считаю, будет соответствовать простому языку, который я надеюсь реализовать. Он будет иметь следующий синтаксис:

<FunctionName> ( <OptionalArguments>+) {
     <OptionalChildFunctions>+
 }

Фактический пример:

ForEach(in:[1,2,3,4,5] as:"nextNumber") {
   Print(message:{nextNumber})
}

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

Во-первых, я должен признать, что не совсем уверен, КАК это дерево должно выглядеть. Во-вторых, я совершенно не понимаю, как это сделать в моей грамматике Antlr... Я пытался без особого успеха в течение нескольких часов.

Это текущая идея для дерева:

                   FunctionName
                  /          \
           Attributes         \
               / \          /  \ 
            ID    /\    ChildFunctions
           / \   ID etc
          /   \
  Attribute  AttributeValue
        Type

Это мой текущий файл грамматики Antlr:

grammar Test;

options {output=AST;ASTLabelType=CommonTree;}

program : function ;
function : ID (OPEN_BRACKET (attribute (COMMA? attribute)*)? CLOSE_BRACKET)? (OPEN_BRACE function* CLOSE_BRACE)?;

attribute : ID COLON datatype;

datatype : NUMBER | STRING | BOOLEAN | array | lookup ;
array  :  OPEN_BOX (datatype (COMMA datatype)* )? CLOSE_BOX ;
lookup  : OPEN_BRACE (ID (PERIOD ID)*) CLOSE_BRACE;

NUMBER
 : ('+' | '-')? (INTEGER | FLOAT)
 ;

STRING
    :  '"' ( ESC_SEQ | ~('\\'|'"') )* '"'
    ;

BOOLEAN
 : 'true' | 'TRUE' | 'false' | 'FALSE'
 ;

ID  : (LETTER|'_') (LETTER | INTEGER |'_')*
    ;

COMMENT
    :   '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    |   '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
    ;

WHITESPACE : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;

COLON : ':' ;
COMMA : ',' ;
PERIOD  :  '.' ;

OPEN_BRACKET : '(' ;
CLOSE_BRACKET : ')' ;

OPEN_BRACE : '{' ; 
CLOSE_BRACE : '}' ;

OPEN_BOX : '[' ;
CLOSE_BOX : ']' ;

fragment
LETTER
 : 'a'..'z' | 'A'..'Z' 
 ;

fragment
INTEGER
 : '0'..'9'+
 ;

fragment
FLOAT
 : INTEGER+ '.' INTEGER*
 ;

fragment
ESC_SEQ
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    ;

ЛЮБАЯ помощь / совет будут великолепны. Я пробовал читать десятки учебных пособий, и, похоже, ничего о поколении AST не осталось:(

Answer 1

Шаг 1 - сделать дерево похожим на маленький график, который вы разместили. Прямо сейчас у вас нет операторов построения дерева, поэтому вы получите плоский список.

Смотрите конструкцию дерева на сайте antlr.org.

Вы можете использовать ANTLRWorks, чтобы увидеть, что вы получаете за дерево разбора и AST. Начните добавлять операторов построения дерева и смотрите, как все меняется.

РЕДАКТИРОВАТЬ / Дополнительная информация:

Вот процесс, которым вы можете следовать, чтобы дать вам общее представление о том, как это сделать:

1. Скачайте ANTLRWorks и используйте его графические средства. Вы обязательно захотите увидеть дерево разбора и AST до и после внесения изменений. Как только вы поймете, как все работает, вы можете использовать любую IDE или редактор, который захотите.

2. Есть два основных оператора для построения дерева - восклицательный знак ! который говорит компилятору не размещать узел в AST, а карот ^, который говорит ANTLR сделать что-то корневым узлом. Начните с изучения каждого нетерминального правила и решите, какие элементы не обязательно должны быть в AST. Например, вам не нужны запятые или скобки. Когда у вас есть вся информация, вы можете заполнить структуру (или создать собственную структуру AST), которая предоставляет всю информацию. Запятые больше не помогают, поэтому добавьте ! им. Например:

   function: ID (OPEN_BRACKET! (attribute (COMMA!? attribute)*)? CLOSE_BRACKET!)? (OPEN_BRACE! function* CLOSE_BRACE!)?;

3. Посмотрите на AST в ANTLRWorks до и после. Сравните.

4. Теперь решите, какой элемент должен быть корневым узлом. Похоже, вы хотите ID быть корневым узлом, поэтому добавьте ^ после ID и сравните в ANTLRWorks.

Вот несколько изменений, которые приближают его к тому, что, я думаю, вы хотите:

program : function ;
function : ID^ (OPEN_BRACKET! attributeList? CLOSE_BRACKET!)? (OPEN_BRACE! function* CLOSE_BRACE!)?;
attributeList:  (attribute (COMMA!? attribute)*);
attribute : ID COLON! datatype;
datatype : NUMBER | STRING | BOOLEAN | array | lookup ;
array  :  OPEN_BOX! (datatype^ (COMMA! datatype)* )? CLOSE_BOX!;
lookup  : OPEN_BRACE! (ID (PERIOD! ID)*) CLOSE_BRACE!;

С этим под вашим поясом, теперь посмотрите на некоторые учебные пособия.