antlr - 如何在 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 步是使树看起来像您张贴的小图。现在，您没有任何树构造运算符，因此您最终会得到一个平面列表。

见 tree construction在 antlr.org 网站上。

您可以使用 ANTLRWorks看看你从解析树和 AST 中得到了什么。开始添加树构造运算符并观察情况如何变化。

编辑/附加信息:

您可以按照以下流程大致了解如何操作:

下载 ANTLRWorks 并使用它的绘图工具。您肯定希望在进行更改之前和之后查看解析树和 AST。一旦你了解了一切是如何工作的，那么你就可以使用任何你想要的 IDE 或编辑器。

树构造有两个基本运算符 - 感叹号 !它告诉编译器不要将节点放置在 AST 中，并且胡萝卜 ^ ，它告诉 ANTLR 使某些东西成为根节点。首先检查每个非终结符规则并决定哪些元素不需要在 AST 中。例如，您不需要逗号或括号。获得所有信息后，您可以填充提供所有信息的结构(或创建您自己的 AST 结构)。逗号不再有用，所以添加 !给他们。例如:
function: ID (OPEN_BRACKET! (attribute (COMMA!? attribute)*)? CLOSE_BRACKET!)? (OPEN_BRACE! function* CLOSE_BRACE!)?;

看看之前和之后的 ANTLRWorks 中的 AST。相比。

现在决定哪个元素应该是根节点。看起来你想要 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!;

有了它，现在去看看一些 tutorials .