ANTLR-树构造中的孙节点

Question

我正试图编写一种声明性语法，其中声明和其他语句的顺序并不重要。然而，对于解析，我希望语法以有序的方式输出一个树。假设该语言由声明(decl)和赋值(assign)组成。例如：

decl x
assign y 2
assign x 1
decl y

我希望用一个树来表示程序，其中所有声明都在一个子树中，所有赋值都在另一个子树上。对于上面的例子，类似于：

(PROGRAM
(DECLARATIONS x y)
(ASSIGNMENTS
(y 2)
(x 1)))

我可以在树构造期间执行此重排吗？还是应该编写树语法？

Answer 1

我认为这里有一个比其他答案更容易的答案：

token { DECLS; ASSIGNS; }
prog: (d+=decl | a+=assign)* EOF -> ^(DECLS $d*) ^(ASSIGNS $a*) ;
...

当然，它可以根据你喜欢的规则进行调整。

但是，你确定你需要这样做吗？为什么不在解析器中构建DECL指令的符号表，然后只构建ASSIGN的AST，您可以在树遍历中检查它。

Jim

Answer 2

我可以在树构造期间执行此重排吗，还是应该编写树语法？

两者都可以，但我建议在令牌解析期间对节点进行分组。

我对我写的任何树重写语法都不满意，因为这些语法必须重新发现每个可分组节点的位置——因此需要分组。令牌解析器在常规处理期间接触所有这些数据，树语法最终遍历这些节点的树，就像令牌解析器已经遍历其令牌输入一样。如果只是进行分组，我认为树解析器不值得麻烦。

无论如何，在解析器中管理分组可以归结为在生成decl和assign节点后保存它们，然后在它们的分组级别出现时再次将它们推出。下面是一个简单的例子。

声明性

grammar Declarative;
options { 
output = AST;
}
tokens { 
PROGRAM; DECLARATIONS; ASSIGNMENTS;
} 
@parser::header { 
import java.util.ArrayList;
}
@members {
private ArrayList<Object> assigns = new ArrayList<Object>(); 
private ArrayList<Object> decls = new ArrayList<Object>();

private Object createTree(int ttype,  ArrayList<Object> children) {
Object tree = adaptor.create(ttype, tokenNames[ttype]);
for (Object child : children){
adaptor.addChild(tree, child);
}

return tree; 
}
}
compilationUnit     : statement* EOF -> ^(PROGRAM {createTree(DECLARATIONS, decls)} {createTree(ASSIGNMENTS, assigns)}); 
statement           : decl {decls.add($decl.tree);}
| assign {assigns.add($assign.tree);}
;

decl                : DECL^ ID;
assign              : ASSIGN^ ID INT;

DECL    : 'decl';
ASSIGN  : 'assign';
ID      : ('a'..'z'|'A'..'Z')('a'..'z'|'A'..'Z')*;
INT     : ('0'..'9')+;                  
WS      : (' '|'t'|'f'|'n'|'r'){skip();};

每个decl节点由decls列表中的statement规则保存，对于每个assign节点也是类似的。

方法createTree使用解析器的TreeAdaptor来构建组节点并填充它们。

CommonTree tree = (CommonTree) adaptor.create(ttype, tokenNames[ttype]);
for (Object child : children){
adaptor.addChild(tree, child);
}
return tree; 

compilationUnit的产品是^(PROGRAM {createTree(DECLARATIONS, decls)} {createTree(ASSIGNMENTS, assigns)})，它将分组节点添加到PROGRAM。方法createTree用于一次性构建分组节点及其子节点。

可能有一种棘手的方法可以让ANTLR为您整合所有内容，但这是有效的，而且是不言自明的。

因此，考虑到这些输入。。。

decl x
assign y 2
assign x 1
decl y

为上述语法生成的令牌解析器生成以下树作为输出：

(PROGRAM 
(DECLARATIONS 
(decl x) 
(decl y)) 
(ASSIGNMENTS 
(assign y 2) 
(assign x 1)))