ANTLR 4解析树匹配和XPath

发表于 | 分类于 |

Since ANTLR 4.2

1 解析树匹配

使用访问器和监听器可以实现DOM访问和模拟SAX事件处理。

如，只关心Java方法声明，并且有一个Java.g4文件，可以在JavaBaseListener中覆盖方法。ParseTreeWalker可以在遍历树时调用覆盖后的方法。

这种机制是建立在节点粒度的。也就是说，对于子树中的节点也可能被调用。

常用于以下用途：

  • 收集在特定上下文（如嵌套方法）中收集方法声明。
  • 根据模式分组翻译。
  • 收集整个树中的变量赋值。

因为讨论的是解析树，而不是抽象语法树，因此可以使用更加具体的模式。

2 解析树模式

用于验证子树是否具有特定结构。

定义如下：

1
<ID> = <expr>;

其中，expr代表任意记号或规则。

使用如下：

1
2
3
4
ParseTree t = ...; // assume t is a statement
ParseTreePattern p = parser.compileParseTreePattern("<ID> = <expr>;", MyParser.RULE_statement);
ParseTreeMatch m = p.match(t);
if ( m.succeeded() ) {...}

如需要找出加0的记号：

1
2
3
ParseTree t = ...; // assume t is an expression
ParseTreePattern p = parser.compileParseTreePattern("<ID>+0", MyParser.RULE_expr);
ParseTreeMatch m = p.match(t);

输出匹配的子树，此处为记号：

1
String id = m.get("ID");

设置tag分割符？

1
2
ParseTreePatternMatcher m = new ParseTreePatternMatcher();
m.setDelimiters("<<", ">>", "$"); // $ is the escape character

This would allow pattern <<ID>> = <<expr>> ;$<< ick $>> to be interpreted as elements: ID, =, expr, and ;<< ick >>.

(1) 模式标签

get()和getAll()可用于获取匹配的子树。

其中get()只返回匹配的第一个子树。

可以使用标签标记记号或规则。匹配的结果将包含标签显式标记的记号或规则，以及标记和未标记的完整集合。

如对于标签foo，将返回：

  • <foo:anyRuleName>和<foo:AnyTokenName>
  • <anyLabel:foo>
  • <foo>

(2) 使用模式matcher创建解析树

ParseTreePattern.getPatternTree()

详见TestParseTreeMatch.java

3 使用XPath识别解析树节点集合

XPath path是代表节点或子树的字符串。

path通常有节点名称和以下分隔符组成：

Expression Description
nodename 标记或规则的节点名称
/ 根节点
// 所有匹配的节点
! 除此以外的节点

理解：路径匹配

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/prog/func, -> all funcs under prog at root
/prog/*, -> all children of prog at root
/*/func, -> all func kids of any root node
prog, -> prog must be root node
/prog, -> prog must be root node
/*, -> any root
*, -> any root
//ID, -> any ID in tree
//expr/primary/ID, -> any ID child of a primary under any expr
//body//ID, -> any ID under a body
//'return', -> any 'return' literal in tree
//primary/*, -> all kids of any primary
//func/*/stat, -> all stat nodes grandkids of any func node
/prog/func/'def', -> all def literal kids of func kid of prog
//stat/';', -> all ';' under any stat node
//expr/primary/!ID, -> anything but ID under primary under any expr node
//expr/!primary, -> anything but primary under any expr node
//!*, -> nothing anywhere
/!*, -> nothing at root

常见的遍历方法：

1
2
3
for (ParseTree t : XPath.findAll(tree, xpath, parser) ) {
    ... process t ...
}

示例：获取匹配规则或记号的名称

1
2
3
4
5
6
7
8
9
10
List<String> nodes = new ArrayList<String>();
for (ParseTree t : XPath.findAll(tree, xpath, parser) ) {
    if ( t instanceof RuleContext) {
        RuleContext r = (RuleContext)t;
        nodes.add(parser.getRuleNames()[r.getRuleIndex()]);    }      
    else { 
        TerminalNode token = (TerminalNode)t;
        nodes.add(token.getText());
    }      
}

4 结合XPath和树模式

详见TestXPath.java

1
2
3
4
5
6
7
8
9
// assume we are parsing Java
ParserRuleContext tree = parser.compilationUnit();
String xpath = "//blockStatement/*"; // get children of blockStatement
String treePattern = "int <Identifier> = <expression>;";
ParseTreePattern p =
    parser.compileParseTreePattern(treePattern,   
        ExprParser.RULE_localVariableDeclarationStatement);
List<ParseTreeMatch> matches = p.findAll(tree, xpath);
System.out.println(matches);

参考资料