Как мне сделать TreeParser в ANTLR3? - PullRequest
Новая
       14

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

4 голосов
/ 14 января 2010

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

Я создал грамматику 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 не сохранилось: (

1 Ответ

9 голосов
/ 14 января 2010

Шаг 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!;

Имея это под своим поясом, теперь посмотрите на некоторые из учебных пособий .

...