3

我正在尝试编写一个声明性语法，其中声明和其他语句的顺序并不重要。但是，对于解析，我想让语法以有序的方式输出一棵树。假设语言由声明 ( decl) 和赋值 ( assign) 组成。一个例子可能是：

decl x
assign y 2
assign x 1
decl y

我想让程序由一棵树表示，所有声明都在一个子树中，所有分配都在另一个子树中。对于上面的示例，类似于：

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

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

4

2 回答 2

3

我认为这里有一个比另一个更简单的答案：

token { DECLS; ASSIGNS; }

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

...

当然，它可以适应尽可能多的规则。

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

吉姆

于 2012-12-11T06:49:07.397 回答
2

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

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

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

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

声明式.g

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保存，对于每个节点也是如此。statementdeclsassign

方法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)))
于 2012-12-11T05:48:38.093 回答