一种简单语言的ANTLR解析器和树语法

本文关键字：ANTLR 树语法 语言 一种 简单 | 更新日期: 2023-09-27 17:53:52

编辑:

下面是更新后的树和解析器语法:

语法解析器:

    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

一种简单语言的ANTLR解析器和树语法

更新

除了引入假想的标记以确保您的树语法生成"唯一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，你不能在语法Y中正确导入语法X:语法X中的文字标记在语法Y中不可用。当您在解析器和词法分析器语法中拆分您的组合语法时，这些文字标记是不允许的。对于像您这样的小语法，这些最后的注释与您无关(您可以让语法保持原样)，但是在创建更大的语法时请记住它们。

祝你好运!

编辑

想象的标记不仅在没有真正的标记可以作为树的根时很方便。我看待想象符号的方式是，它们使你的树"独一无二"，因此树语法只能以一种可能的方式"遍历"你的树。以减法和一元减法为例。如果您不想创建一个名为UNARY_MINUS的虚拟令牌，而只是这样做:

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

那么你的树形语法中就会有这样的内容:

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

现在减法和一元减法都以相同的符号开始，这是树语法不喜欢的!这个-(减)的例子很容易看出，但也有一些不那么明显的棘手情况(即使是像你这样的小语法!)。因此，在重写为AST时，总是让解析器创建"唯一树"。

希望能澄清一点。

相关文章：