如何在ANTLR3中创建TreeParser？

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中,而carot ^告诉ANTLR使某些节点成为根节点.首先浏览每个非终端规则并确定哪些元素不需要在AST中.例如,您不需要逗号或括号.获得所有信息后,您可以填充提供所有信息的结构(或创建自己的AST结构).逗号不再帮助了,所以添加一个!.例如:

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

3. 在之前和之后看一下ANTLRWorks中的AST.相比.

4. 现在决定哪个元素应该是根节点.看起来你想ID成为根节点,所以在ANTLRWorks中添加一个^after ID和compare.

这里有一些变化使它更接近我的想法:

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!;

有了这个,现在去看看一些教程.