ANTLR 复制一棵树 [英] ANTLR duplicate a tree
问题描述
我使用ANTLR构建了一棵树(CommonTree),就像follwing(语言:JAVA):
Parser.prog_return r = parser.prog();CommonTree t = (CommonTree) r.getTree();
现在,我需要将t"作为参数传递,并在不影响原始树的情况下进行一些更改.但是,使用 Java 的指针,这无法完成,因此我需要复制树.
我在网上搜索过,我能找到的最隐蔽的是ASTFactory类的dupTree()方法.
关于如何实现这一点的任何建议或建议将不胜感激!
编辑
@Bart Kiers,感谢您的回答,它绝对有效!
我看到您正在对树进行深度优先遍历,并为每个访问过的节点创建一个 CommonTree 对象.
我现在的问题是,CommonToken 和 CommonTree 之间的关系是什么,这些属性有什么作用:
cTok.setCharPositionInLine(oTok.getCharPositionInLine());cTok.setChannel(oTok.getChannel());cTok.setStartIndex(oTok.getStartIndex());cTok.setStopIndex(oTok.getStopIndex());cTok.setTokenIndex(oTok.getTokenIndex());
试试这个:
public static CommonTree copyTree(CommonTree original) {CommonTree copy = new CommonTree(original.getToken());copyTreeRecursive(copy, original);返回副本;}private static void copyTreeRecursive(CommonTree copy, CommonTree original) {if(original.getChildren() != null) {for(Object o : original.getChildren()) {CommonTree originalChild = (CommonTree)o;//从原始子节点获取tokenCommonToken oTok = (CommonToken)originalChild.getToken();//创建一个具有相同类型的新令牌 &文本为oTok"CommonToken cTok = new CommonToken(oTok.getType(), oTok.getText());//将所有属性从 'oTok' 复制到 'cTok'cTok.setLine(oTok.getLine());cTok.setCharPositionInLine(oTok.getCharPositionInLine());cTok.setChannel(oTok.getChannel());cTok.setStartIndex(oTok.getStartIndex());cTok.setStopIndex(oTok.getStopIndex());cTok.setTokenIndex(oTok.getTokenIndex());//创建一个新的树节点,以 'cTok' 作为标记CommonTree copyChild = new CommonTree(cTok);//设置子节点的父节点copyChild.setParent(copy);//将子节点添加到父节点copy.addChild(copyChild);//进行递归调用以进行更深的复制copyTreeRecursive(copyChild, originalChild);}}}...//获取原始树CommonTree 树 = (CommonTree)parser.parse().getTree();//创建树的副本CommonTree copy = copyTree(tree);//改变根的右节点的右节点的内容((CommonTree)tree.getChild(1).getChild(1)).getToken().setText("X");System.out.println(tree.toStringTree());System.out.println(copy.toStringTree());
会产生:
<前>(&& a (|| b X))(&& a (|| b c))对于输入a && (b || c)"
.即,tree
有 X
,但 copy
将具有原始内容:c
.
请注意,我选择了 CommonTree
和 CommonToken
对象,因为它们是默认的 Token
和 Tree
实现.如果您选择创建自己的 Token
和/或 Tree
,您可能会继承 CommonTree
和 CommonToken代码> 类,在这种情况下,我的建议不会中断.
一个CommonTree
只不过是一个CommonToken
的包装器,包含一些额外的信息:父节点和子节点.这就是为什么我还要从 CommonToken
对象中复制所有信息.
I use ANTLR to build a tree (CommonTree) like follwing (language: JAVA):
Parser.prog_return r = parser.prog();
CommonTree t = (CommonTree) r.getTree();
Now, I need to pass "t" as a parameter, and make some changes without affecting the original tree. However, with Java's pointer, this could not been done, so I need to duplicate the tree.
I have been search on the internet, the cloested thing I could find is the dupTree() method of ASTFactory class.
Any suggestion or advises on how to achive this would be appreciated!
EDIT
@Bart Kiers, Thanks for your answer, it absolutely works!
I see you are doing a depth first walk over the tree, and create a CommonTree object for each node that was visited.
My question is now, what is the relation between CommonToken and CommonTree, and what are these attributes do:
cTok.setCharPositionInLine(oTok.getCharPositionInLine());
cTok.setChannel(oTok.getChannel());
cTok.setStartIndex(oTok.getStartIndex());
cTok.setStopIndex(oTok.getStopIndex());
cTok.setTokenIndex(oTok.getTokenIndex());
Try something like this:
public static CommonTree copyTree(CommonTree original) {
CommonTree copy = new CommonTree(original.getToken());
copyTreeRecursive(copy, original);
return copy;
}
private static void copyTreeRecursive(CommonTree copy, CommonTree original) {
if(original.getChildren() != null) {
for(Object o : original.getChildren()) {
CommonTree originalChild = (CommonTree)o;
// get the token from the original child node
CommonToken oTok = (CommonToken)originalChild.getToken();
// create a new token with the same type & text as 'oTok'
CommonToken cTok = new CommonToken(oTok.getType(), oTok.getText());
// copy all attributes from 'oTok' to 'cTok'
cTok.setLine(oTok.getLine());
cTok.setCharPositionInLine(oTok.getCharPositionInLine());
cTok.setChannel(oTok.getChannel());
cTok.setStartIndex(oTok.getStartIndex());
cTok.setStopIndex(oTok.getStopIndex());
cTok.setTokenIndex(oTok.getTokenIndex());
// create a new tree node with the 'cTok' as token
CommonTree copyChild = new CommonTree(cTok);
// set the parent node of the child node
copyChild.setParent(copy);
// add the child to the parent node
copy.addChild(copyChild);
// make a recursive call to copy deeper
copyTreeRecursive(copyChild, originalChild);
}
}
}
...
// get the original tree
CommonTree tree = (CommonTree)parser.parse().getTree();
// create a copy of the tree
CommonTree copy = copyTree(tree);
// change the contents of the right node of the right node of the root
((CommonTree)tree.getChild(1).getChild(1)).getToken().setText("X");
System.out.println(tree.toStringTree());
System.out.println(copy.toStringTree());
which would produce:
(&& a (|| b X)) (&& a (|| b c))
for the input "a && (b || c)"
. I.e., the tree
has X
, but the copy
would will have the original contents: c
.
Note that I choose CommonTree
and CommonToken
objects because those are the default Token
and Tree
implementations. If you choose to create your own Token
and/or Tree
, chances are that you'll subclass the CommonTree
and CommonToken
classes, in which case my suggestion would not break.
A CommonTree
is nothing more than a wrapper around a CommonToken
, holding a bit of extra information: a parent node, and child nodes. That is why I also copy all the information from the CommonToken
objects.
这篇关于ANTLR 复制一棵树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!