ANTLR парсер и древовидная грамматика для одного простого языка - PullRequest
Новая
       20

ANTLR парсер и древовидная грамматика для одного простого языка

1 голос
/ 01 мая 2011

Редактировать:

Вот обновленные грамматики дерева и синтаксического анализатора:

Грамматика синтаксического анализатора: 

    options {

language = CSharp2;

output=AST;


}
tokens {
UNARY_MINUS;
CALL;
}
program :   (function)* main_function

        ;



function:       'function' IDENTIFIER '(' (parameter (',' parameter)*)? ')' 'returns' TYPE declaration* statement* 'end' 'function'
        ->    ^('function' IDENTIFIER parameter* TYPE declaration* statement*)
    ;

main_function
    :   'function' 'main' '(' ')' 'returns' TYPE declaration* statement*  'end' 'function'
    ->    ^('function' 'main' TYPE declaration* statement*)   
    ;   

parameter
    :   'param' IDENTIFIER ':' TYPE
    ->    ^('param' IDENTIFIER TYPE)
    ;

declaration
    :       'variable' IDENTIFIER ( ',' IDENTIFIER)* ':' TYPE ';'
    ->    ^('variable' TYPE IDENTIFIER+ )
    |       'array' array  ':' TYPE ';'
    ->    ^('array' array TYPE)
    ;

statement 
    : ';'! | block | assignment | if_statement | switch_statement | while_do_statement | for_statement | call_statement | return_statement  
    ;

call_statement
    :   call ';'!
    ;

return_statement
    :   'return' expression ';'
    ->    ^('return' expression)
    ;

block   : 'begin' declaration* statement* 'end'
        -> ^('begin' declaration* statement*)
        |  '{' declaration* statement* '}'
        -> ^('{' declaration* statement*)
    ;

assignment 
    :   IDENTIFIER ':=' expression ';'
        ->      ^(':=' IDENTIFIER expression )
    |       array ':=' expression ';'
    ->     ^(':=' array expression) 
    ;

array   :   IDENTIFIER '[' expression (',' expression)* ']'
    ->  ^(IDENTIFIER expression+)
    ;

if_statement 
    :   'if' '(' expression ')' 'then' statement ('else' statement)? 'end' 'if'
    ->    ^('if' expression statement statement?)

    ;

switch_statement 
    :   'switch' '(' expression ')' case_part+ ('default' ':' statement)? 'end' 'switch'
    ->    ^('switch' expression case_part+ statement?)
    ; 

case_part
    :   'case' literal (',' literal)* ':' statement
    ->    ^('case' literal+ statement)
    ;

literal 
    :   INTEGER | FLOAT | BOOLEAN | STRING
    ; 

while_do_statement
    :   'while' '(' expression ')' 'do' statement 'end' ' while'
    ->    ^('while' expression statement)
    ;

for_statement 
    :       'for' '(' IDENTIFIER ':=' expression 'to' expression ')' 'do' statement 'end' 'for'
    ->   ^('for' IDENTIFIER expression expression statement)
    ;

expression
    :   conjuction ( 'or'^ conjuction)*
    ;

conjuction
    :       equality ('and'^ equality)* 
    ;

equality:   relation (('=' | '/=')^ relation)?
        ;

relation:   addition (('<' | '<=' | '>' | '>=')^ addition)?
    ;

addition:   multiplication (('+' | '-')^ multiplication)*   
    ;

multiplication
    :   unary_operation (('*' | '/' | '%')^ unary_operation)*
    ;
unary_operation
    :   '-' primary 
    ->   ^(UNARY_MINUS primary)
    |        'not' primary 
    ->   ^('not' primary)
    |     primary
    ;

primary :   IDENTIFIER 
        | array 
        |  literal 
        | '('! expression ')'!  
        | '(' TYPE ')'  '(' expression ')'
        -> ^(TYPE expression) 
        |  call
    ; 

call    :   IDENTIFIER '(' arguments ')'
        ->     ^(CALL IDENTIFIER arguments)
    ;

arguments
    :   (expression  (','! expression)*)? 
    ;

BOOLEAN :   'true' | 'false'
    ;   

T    YPE    : 'integer' | 'boolean' | 'float' | 'string' | 'array' | 'void'
    ;

IDENTIFIER  :   ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;

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

FLOAT
    :   ('0'..'9')+ '.' ('0'..'9')+ 
    ;

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

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

STRING
    :  '"' .* '"'
    ;

А вот обновленная грамматика дерева (я изменил выражения,и так далее ...): 

    options {
language = 'CSharp2';
//tokenVocab= token vocab needed
ASTLabelType=CommonTree; // what is Java type of nodes?

}
program :   (function)* main_function

        ;



function:     ^('function' IDENTIFIER parameter* TYPE declaration* statement*)
    ;

main_function
    :   ^('function' 'main' TYPE declaration* statement*)   
    ;   

parameter
    :   ^('param' IDENTIFIER TYPE)
    ;

declaration
    :     ^('variable' TYPE IDENTIFIER+)
        |     ^('array' array TYPE  )
    ;

statement 
    : block | assignment | if_statement | switch_statement | while_do_statement | for_statement | call_statement | return_statement 
    ;

call_statement
    :   call 
    ;

return_statement
    :   ^('return' expression)
    ;

block   : ^('begin' declaration* statement*)
        |  ^('{' declaration* statement*)
    ;

assignment 
    :   ^(':=' IDENTIFIER expression )
    |      ^(':=' array expression) 
    ;

array   :   ^(IDENTIFIER expression+)
    ;

if_statement 
    :   ^('if' expression statement statement?)

    ;

switch_statement 
    :   ^('switch' expression case_part+ statement?)
    ; 

case_part
    :   ^('case' literal+ statement)
    ;

literal 
    :   INTEGER | FLOAT | BOOLEAN | STRING
    ; 

while_do_statement
    :   ^('while' expression statement)
    ;

for_statement 
    :    ^('for' IDENTIFIER expression expression statement)
    ;

expression
    :   ^('or' expression expression)
    |      ^('and' expression expression)
    |      ^('=' expression expression)   
    |      ^('/=' expression expression)
    |       ^('<' expression expression)
    |       ^('<=' expression expression)
    |       ^('>' expression expression)
    |       ^('>=' expression expression)
    |       ^('+' expression expression)
    |       ^('-' expression expression)
    |      ^(UNARY_MINUS expression)
    |      ^('not' expression)
    |      IDENTIFIER
    |      array
    |       literal 
        |      ^(TYPE expression) 
        |      call
    ;

call    :   ^(CALL IDENTIFIER arguments)
    ;

arguments
    :   (expression  (expression)*)? 
    ;

Я успешно сгенерировал древовидный граф с классами DOTTreeGenerator и StringTemplate, поэтому кажется, что все работает в данный момент.Но любые предложения (о вредных привычках или что-то еще в этой грамматике) приветствуются, поскольку у меня нет большого опыта работы с ANTLR или распознаванием языка.

См. Обновления на http://vladimir -radojicic.blogspot.com

1 Ответ

1 голос
/ 01 мая 2011

Единственное, что я собирался предложить, помимо введения воображаемых токенов, чтобы убедиться, что ваша древовидная грамматика производит «уникальный AST», и упрощение expression в дереве -граммы, которую вы оба ужесделал (опять же: хорошо сделано!), это то, что вы не должны использовать буквенные токены внутри грамматики вашего синтаксического анализатора.Особенно, если они не могут быть сопоставлены с другими правилами лексера.Например, все ваши зарезервированные слова (например, for, while, end и т. Д.) Также могут соответствовать правилу лексера IDENTIFIER.Лучше создавать явные токены внутри лексера (и поместить эти правила перед правилом IDENTIFIER!): 

...

FOR   : 'for'; 
WHILE : 'while'; 
END   : 'end';

...

IDENTIFIER  
  :  ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
  ;

...

В идеале, грамматика дерева не содержит никаких токенов в кавычках.AFAIK, вы не можете импортировать грамматику X внутри грамматики Y правильно: буквенные маркеры внутри грамматики X тогда недоступны в грамматике Y.И когда вы разбиваете свою объединенную грамматику на грамматику синтаксического анализатора и лексера, эти буквальные токены не допускаются.С такими маленькими грамматиками, как ваша, эти последние замечания вас не касаются (и вы можете оставить свою грамматику «как есть»), но помните их, когда создаете большие грамматики.

Удачи!

РЕДАКТИРОВАТЬ

Воображаемые токены полезны не только тогда, когда нет настоящего токена, который можно сделать корнем дерева.То, как я смотрю на воображаемые токены, состоит в том, что они делают ваше дерево «уникальным», так что грамматика дерева может «ходить» по вашему дереву только одним возможным способом.Возьмите к примеру вычитание и унарный минус.Если бы вы не создали воображаемый токен с именем UNARY_MINUS, а просто сделали это: 

unary_operation
  :  '-' primary   -> ^('-' primary)
  |  'not' primary -> ^('not' primary)
  |  primary
  ;

, то в вашей грамматике дерева было бы что-то вроде этого: 

expression
  :  ^('-' expression expression)
  |  ...
  |  ^('-' expression)
  |  ...
  ;

Теперь и вычитание, и унарный минус начинаются с одинаковых токенов, которые древовидная грамматика не любит!Это легко увидеть на этом примере - (минус), но могут быть довольно сложные случаи (даже с такими маленькими грамматиками, как ваша!), Которые не так очевидны.Поэтому всегда разрешайте анализатору создавать «уникальные деревья» при переписывании в AST.

Надеюсь, что это проясняет (немного).

...