Debian Codegraph @

doc/tree-matching.md

raw
1 # Parse Tree Matching and XPath
2
3 *Since ANTLR 4.2*
4
5 ANTLR 4 introduced a visitor and listener mechanism that lets you implement DOM visiting or SAX-analogous event processing of tree nodes. This works great. For example, if all you care about is looking at Java method declarations, grab the `Java.g4` file and then override methodDeclaration in `JavaBaseListener`. From there, a `ParseTreeWalker` can trigger calls to your overridden method as it walks the tree. Easy things are easy.
6
7 This mechanism works more or less on a node-level basis. In other words, for every method declaration subtree root, your `methodDeclaration()` would get called. There are many situations where we care more about subtrees not just nodes. We might want to:
8
9 * Collect method declarations within a particular context (i.e., nested within another method) or methods with specific structure or specific types (e.g., `void <ID>() { }`). We'll combine `XPath` and tree pattern matching for this.
10 * Group translation operations by patterns in the tree rather than spreading operations across listener event methods.
11 * Get a list of all assignments anywhere in the tree. It's much easier to say *go find me all "... = ... ;" subtrees* rather than creating a class just to get a listener method for rule assignment and then passing the listener to the parse tree walker.
12
13 The other important idea here is that, since we're talking about parse trees not abstract syntax trees, we can use concrete patterns instead of tree syntax. For example, we can say `x = 0;` instead of AST `(= x 0)` where the `;` would probably stripped before it went into the AST.
14
15 ## Parse tree patterns
16
17 To test a subtree to see if it has a particular structure, we use a tree pattern. We also often want to extract descendents from the subtree based upon the structure. A very simple example is checking to see if a subtree matches an assignment statement. The pattern might look like the following in your language:
18
19 ```
20 <ID> = <expr>;
21 ```
22
23 where "tags" in angle brackets represent either token or rule references in the associated grammar. ANTLR converts that string to a parse tree with special nodes that represent any token `ID` and rule `expr` subtree. To create this parse tree, the pattern matching compiler needs to know which rule in the grammar the pattern conforms to. In this case it might be statement. Here is how we could test a tree, `t`, to see if it matches that pattern:
24
25 ```java
26 ParseTree t = ...; // assume t is a statement
27 ParseTreePattern p = parser.compileParseTreePattern("<ID> = <expr>;", MyParser.RULE_statement);
28 ParseTreeMatch m = p.match(t);
29 if ( m.succeeded() ) {...}
30 ```
31
32 We can also test for specific expressions or token values. For example, the following checks to see if `t` is an expression consisting of an identifier added to 0:
33
34 ```java
35 ParseTree t = ...; // assume t is an expression
36 ParseTreePattern p = parser.compileParseTreePattern("<ID>+0", MyParser.RULE_expr);
37 ParseTreeMatch m = p.match(t);
38 ```
39
40 We can also ask the `ParseTreeMatch` result to pull out the token matched to the `<ID>` tag:
41
42 ```java
43 String id = m.get("ID");
44 ```
45
46 You can change the tag delimiters using a method on the pattern matcher:
47
48 ```java
49 ParseTreePatternMatcher m = new ParseTreePatternMatcher();
50 m.setDelimiters("<<", ">>", "$"); // $ is the escape character
51 ```
52
53 This would allow pattern `<<ID>> = <<expr>> ;$<< ick $>>` to be interpreted as elements: `ID`, ` = `, `expr`, and ` ;<< ick >>`.
54
55 ### Pattern labels
56
57 The tree pattern matcher tracks the nodes in the tree at matches against the tags in a tree pattern. That way we can use the `get()` and `getAll()` methods to retrieve components of the matched subtree. For example, for pattern `<ID>`, `get("ID")` returns the node matched for that `ID`. If more than one node matched the specified token or rule tag, only the first match is returned. If there is no node associated with the label, this returns null.
58
59 You can also label the tags with identifiers. If the label is the name of a parser rule or token in the grammar, the resulting list from `getAll()` (or node from `get()`) will contain both the parse trees matching rule or tags explicitly labeled with the label and the complete set of parse trees matching the labeled and unlabeled tags in the pattern for the parser rule or token. For example, if label is `foo`, the result will contain all of the following.
60
61 * Parse tree nodes matching tags of the form `<foo:anyRuleName>` and `<foo:AnyTokenName>`.
62 * Parse tree nodes matching tags of the form `<anyLabel:foo>`.
63 * Parse tree nodes matching tags of the form `<foo>`.
64
65 ### Creating parse trees with the pattern matcher
66
67 You can use the parse tree pattern compiler to create parse trees for partial input fragments. Just use method `ParseTreePattern.getPatternTree()`.
68
69 See [TestParseTreeMatch.java](https://github.com/antlr/antlr4/blob/master/tool-testsuite/test/org/antlr/v4/test/tool/TestParseTreeMatcher.java).
70
71 ## Using XPath to identify parse tree node sets
72
73 XPath paths are strings representing nodes or subtrees you would like to select within a parse tree. It's useful to collect subsets of the parse tree to process. For example you might want to know where all assignments are in a method or all variable declarations that are initialized.
74
75 A path is a series of node names with the following separators.
76
77 | Expression |Description|
78 |---------|-----------|
79 |nodename| Nodes with the token or rule name nodename
80 |/| The root node but `/X` is the same as `X` since the tree you pass to xpath is assumed to be the root. Because it looks better, start all of your patterns with `/` (or `//` below).|
81 |//| All nodes in the tree that match the next element in the path. E.g., `//ID` finds all `ID` token nodes in the tree.|
82 |!| Any node except for the next element in the path. E.g., `/classdef/!field` should find all children of `classdef` root node that are not `field` subtrees.|
83
84 Examples:
85
86 ```
87 /prog/func, -> all funcs under prog at root
88 /prog/*, -> all children of prog at root
89 /*/func, -> all func kids of any root node
90 prog, -> prog must be root node
91 /prog, -> prog must be root node
92 /*, -> any root
93 *, -> any root
94 //ID, -> any ID in tree
95 //expr/primary/ID, -> any ID child of a primary under any expr
96 //body//ID, -> any ID under a body
97 //'return', -> any 'return' literal in tree
98 //primary/*, -> all kids of any primary
99 //func/*/stat, -> all stat nodes grandkids of any func node
100 /prog/func/'def', -> all def literal kids of func kid of prog
101 //stat/';', -> all ';' under any stat node
102 //expr/primary/!ID, -> anything but ID under primary under any expr node
103 //expr/!primary, -> anything but primary under any expr node
104 //!*, -> nothing anywhere
105 /!*, -> nothing at root
106 ```
107
108 Given a parse tree, the typical mechanism for visiting those nodes is the following loop:
109
110 ```java
111 for (ParseTree t : XPath.findAll(tree, xpath, parser) ) {
112 ... process t ...
113 }
114 ```
115
116 E.g., here is a general formula for making a list of the text associated with every node identified by a path specification:
117
118 ```java
119 List<String> nodes = new ArrayList<String>();
120 for (ParseTree t : XPath.findAll(tree, xpath, parser) ) {
121 if ( t instanceof RuleContext) {
122 RuleContext r = (RuleContext)t;
123 nodes.add(parser.getRuleNames()[r.getRuleIndex()]); }
124 else {
125 TerminalNode token = (TerminalNode)t;
126 nodes.add(token.getText());
127 }
128 }
129 ```
130
131 ## Combining XPath and tree pattern matching
132
133 Naturally you can combine the use of XPath to find a set of root nodes and then use tree pattern matching to identify a certain subset of those and extract component nodes.
134
135 ```java
136 // assume we are parsing Java
137 ParserRuleContext tree = parser.compilationUnit();
138 String xpath = "//blockStatement/*"; // get children of blockStatement
139 String treePattern = "int <Identifier> = <expression>;";
140 ParseTreePattern p =
141 parser.compileParseTreePattern(treePattern,
142 ExprParser.RULE_localVariableDeclarationStatement);
143 List<ParseTreeMatch> matches = p.findAll(tree, xpath);
144 System.out.println(matches);
145 ```
146
147 See [TestXPath.java](https://github.com/antlr/antlr4/blob/master/tool-testsuite/test/org/antlr/v4/test/tool/TestXPath.java).