Debian Codegraph @

www/doc/jjtreeintro.html

raw
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2 <html xmlns="http://www.w3.org/1999/xhtml">
3 <!--
4
5 Copyright (c) 2006, Sun Microsystems, Inc.
6 All rights reserved.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are met:
10
11 * Redistributions of source code must retain the above copyright notice,
12 this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16 * Neither the name of the Sun Microsystems, Inc. nor the names of its
17 contributors may be used to endorse or promote products derived from
18 this software without specific prior written permission.
19
20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
30 THE POSSIBILITY OF SUCH DAMAGE.
31
32 -->
33 <head>
34 <title>JavaCC: JJTree Introduction</title>
35 <!-- Changed by: Michael Van De Vanter, 14-Jan-2003 -->
36 </head>
37 <body bgcolor="#FFFFFF" >
38
39 <h1>JavaCC [tm]: JJTree Introduction</h1>
40
41 <pre>
42 JJTree is a preprocessor for JavaCC [tm] that inserts parse tree building actions
43 at various places in the JavaCC source. The output of JJTree is run through
44 JavaCC to create the parser. This document describes how to use JJTree, and
45 how you can interface your parser to it.
46
47 By default, JJTree generates code to construct parse tree nodes for each
48 nonterminal in the language. This behavior can be modified so that some
49 nonterminals do not have nodes generated, or so that a node is generated for a
50 part of a production's expansion.
51
52 JJTree defines a Java interface Node that all parse tree nodes must
53 implement. The interface provides methods for operations such as setting the
54 parent of the node, and for adding children and retrieving them.
55
56 JJTree operates in one of two modes, simple and multi (for want of better
57 terms). In simple mode, each parse tree node is of concrete type SimpleNode; in
58 multi mode, the type of the parse tree node is derived from the name of the
59 node. If you don't provide implementations for the node classes JJTree will
60 generate sample implementations based on SimpleNode for you. You can then
61 modify the implementations to suit.
62
63 Although JavaCC is a top-down parser, JJTree constructs the parse tree from
64 the bottom up. To do this it uses a stack where it pushes nodes after they
65 have been created. When it finds a parent for them, it pops the children from
66 the stack and adds them to the parent, and finally pushes the new parent node
67 itself. The stack is open, which means that you have access to it from within
68 grammar actions: you can push, pop and otherwise manipulate its contents
69 however you feel appropriate. See Node Scopes and User Actions below for more
70 important information.
71
72 JJTree provides decorations for two basic varieties of nodes, and some
73 syntactic shorthand to make their use convenient.
74 1.
75
76 A definite node is constructed with a specific number of
77 children. That many nodes are popped from the stack and made the
78 children of the new node, which is then pushed on the stack
79 itself. You notate a definite node like this:
80
81 #ADefiniteNode(INTEGER EXPRESSION)
82
83 A definite node descriptor expression can be any integer expression,
84 although literal integer constants are by far the most common
85 expressions.
86 2.
87
88 A conditional node is constructed with all of the children that were
89 pushed on the stack within its node scope if and only if its condition
90 evaluates to true. If it evaluates to false, the node is not
91 constructed, and all of the children remain on the node stack. You
92 notate a conditional node like this:
93
94 #ConditionalNode(BOOLEAN EXPRESSION)
95
96 A conditional node descriptor expression can be any boolean
97 expression. There are two common shorthands for conditional nodes:
98 1)
99
100 Indefinite nodes
101
102 #IndefiniteNode is short for #IndefiniteNode(true)
103 2)
104
105 Greater-than nodes
106
107 #GTNode(>1) is short for #GTNode(jjtree.arity() > 1)
108
109 The indefinite node shorthand (1) can lead to ambiguities in the
110 JJTree source when it is followed by a parenthesized expansion. In
111 those cases the shorthand must be replaced by the full expression. For
112 example:
113
114
115 ( ... ) #N ( a() )
116
117 is ambiguous; you have to use the explicit condition:
118
119 ( ... ) #N(true) ( a() )
120
121 WARNING: node descriptor expression should not have side-effects. JJTree
122 doesn't specify how many times the expression will be evaluated.
123
124 By default JJTree treats each nonterminal as an indefinite node and derives
125 the name of the node from the name of its production. You can give it a
126 different name with the following syntax:
127
128
129 void P1() #MyNode : { ... } { ... }
130
131 When the parser recognizes a P1 nonterminal it begins an indefinite node. It
132 marks the stack, so that any parse tree nodes created and pushed on the stack
133 by nonterminals in the expansion for P1 will be popped off and made children
134 of the node MyNode.
135
136 If you want to suppress the creation of a node for a production, you can use
137 the following syntax:
138
139
140 void P2() #void : { ... } { ... }
141
142 Now any parse tree nodes pushed by nonterminals in the expansion of P2 will
143 remain on the stack, to be popped and made children of a production further up
144 the tree. You can make this the default behavior for non-decorated nodes by
145 using the NODE_DEFAULT_VOID option.
146
147
148 void P3() : {}
149 {
150 P4() ( P5() )+ P6()
151 }
152
153 In this example, an indefinite node P3 is begun, marking the stack, and then a
154 P4 node, one or more P5 nodes and a P6 node are parsed. Any nodes that they
155 push are popped and made the children of P3. You can further customize the
156 generated tree:
157
158
159 void P3() : {}
160 {
161 P4() ( P5() )+ #ListOfP5s P6()
162 }
163
164 Now the P3 node will have a P4 node, a ListOfP5s node and a P6 node as
165 children. The #Name construct acts as a postfix operator, and its scope is the
166 immediately preceding expansion unit.
167
168 Node Scopes and User Actions
169
170 Each node is associated with a node scope. User actions within this scope can
171 access the node under construction by using the special identifier jjtThis to
172 refer to the node. This identifier is implicitly declared to be of the correct
173 type for the node, so any fields and methods that the node has can be easily
174 accessed.
175
176 A scope is the expansion unit immediately preceding the node decoration. This
177 can be a parenthesized expression. When the production signature is decorated
178 (perhaps implicitly with the default node), the scope is the entire right hand
179 side of the production including its declaration block.
180
181 You can also use an expression involving jjtThis on the left hand side of an
182 expansion reference. For example:
183
184
185 ... ( jjtThis.my_foo = foo() ) #Baz ...
186
187 Here jjtThis refers to a Baz node, which has a field called my_foo. The result
188 of parsing the production foo() is assigned to that my_foo.
189
190 The final user action in a node scope is different from all the others. When
191 the code within it executes, the node's children have already been popped from
192 the stack and added to the node, which has itself been pushed onto the
193 stack. The children can now be accessed via the node's methods such as
194 jjtGetChild().
195
196 User actions other than the final one can only access the children on the
197 stack. They have not yet been added to the node, so they aren't available via
198 the node's methods.
199
200 A conditional node that has a node descriptor expression that evaluates to
201 false will not get added to the stack, nor have children added to it. The
202 final user action within a conditional node scope can determine whether the
203 node was created or not by calling the nodeCreated() method. This returns true
204 if the node's condition was satisfied and the node was created and pushed on
205 the node stack, and false otherwise.
206
207 Exception handling
208
209 An exception thrown by an expansion within a node scope that is not caught
210 within the node scope is caught by JJTree itself. When this occurs, any nodes
211 that have been pushed on to the node stack within the node scope are popped
212 and thrown away. Then the exception is rethrown.
213
214 The intention is to make it possible for parsers to implement error recovery
215 and continue with the node stack in a known state.
216
217 WARNING: JJTree currently cannot detect whether exceptions are thrown from
218 user actions within a node scope. Such an exception will probably be handled
219 incorrectly.
220
221 Node Scope Hooks
222
223 If the NODE_SCOPE_HOOK option is set to true, JJTree generates calls to two
224 user-defined parser methods on the entry and exit of every node scope. The
225 methods must have the following signatures:
226
227
228 void jjtreeOpenNodeScope(Node n)
229 void jjtreeCloseNodeScope(Node n)
230
231 If the parser is STATIC then these methods will have to be declared as static
232 as well. They are both called with the current node as a parameter.
233
234 One use for these functions is to store the node's first and last tokens so
235 that the input can be easily reproduced again. For example:
236
237
238 void jjtreeOpenNodeScope(Node n)
239 {
240 ((MySimpleNode)n).first_token = getToken(1);
241 }
242
243 void jjtreeCloseNodeScope(Node n)
244 {
245 ((MySimpleNode)n).last_token = getToken(0);
246 }
247
248 where MySimpleNode is based on SimpleNode and has the following additional
249 fields:
250
251
252 Token first_token, last_token;
253
254 Another use might be to store the parser object itself in the node so that
255 state that should be shared by all nodes produced by that parser can be
256 provided. For example, the parser might maintain a symbol table.
257
258 The Life Cycle of a Node
259
260 A node goes through a well determined sequence of steps as it is built. The
261 following
262 is that sequence viewed from the perspective of the node itself:
263 1. the node's constructor is called with a unique integer parameter. This
264 parameter identifies the kind of node and is especially useful in
265 simple mode. JJTree automatically generates a file called
266 parserTreeConstants.java and declares Java constants for the node
267 identifiers. It also declares an array of Strings called jjtNodeName[]
268 which maps the identifier integers to the names of the nodes.
269 2. the node's jjtOpen() method is called.
270 3. if the option NODE_SCOPE_HOOK is set, the user-defined parser method
271 openNodeScope() is called and passed the node as its parameter. This
272 method can initialize fields in the node or call its methods. For
273 example, it might store the node's first token in the node.
274 4. if an unhandled exception is thrown while the node is being parsed
275 then the node is abandoned. JJTree will never refer to it again. It
276 will not be closed, and the user-defined node scope hook
277 closeNodeHook() will not be called with it as a parameter.
278 5. otherwise, if the node is conditional and its conditional expression
279 evaluates to false then the node is abandoned. It will not be closed,
280 although the user-defined node scope hook closeNodeHook() might be
281 called with it as a parameter.
282 6. otherwise, all of the children of the node as specified by the integer
283 expression of a definite node, or all the nodes that were pushed on
284 the stack within a conditional node scope are added to the node. The
285 order they are added is not specified.
286 7. the node's jjtClose() method is called.
287 8. the node is pushed on the stack.
288 9. if the option NODE_SCOPE_HOOK is set, the user-defined parser method
289 closenNodeScope() is called and passed the node as its parameter.
290 10. if the node is not the root node, it is added as a child of another
291 node and its jjtSetParent() method is called.
292
293 Visitor Support
294
295 JJTree provides some basic support for the visitor design pattern. If the
296 VISITOR option is set to true, JJTree will insert an jjtAccept() method into
297 all of the node classes it generates, and also generate a visitor interface
298 that can be implemented and passed to the nodes to accept.
299
300 The name of the visitor interface is constructed by appending Visitor to the
301 name of the parser. The interface is regenerated every time that JJTree is
302 run, so that it accurately represents the set of nodes used by the
303 parser. This will cause compile time errors if the implementation class has
304 not been updated for the new nodes. This is a feature.
305
306 Options
307
308 JJTree 0.3pre4 supports the following options on the command line and in the
309 JavaCC options statement:
310
311 BUILD_NODE_FILES (default: true)
312 Generate sample implementations for SimpleNode and any other nodes used
313 in the grammar.
314
315 MULTI (default: false)
316 Generate a multi mode parse tree. The default for this is false,
317 generating a simple mode parse tree.
318
319 NODE_DEFAULT_VOID (default: false)
320 Instead of making each non-decorated production an indefinite node, make
321 it void instead.
322
323 NODE_CLASS (default: "")
324 If set defines the name of a user-supplied class that will extend
325 SimpleNode. Any tree nodes created will then be subclasses of NODE_CLASS.
326
327 NODE_FACTORY (default: "")
328 Specify a class containing a factory method with following signature
329 to construct nodes:
330 public static Node jjtCreate(int id)
331 For backwards compatibility, the value "false" may also be specified,
332 meaning that SimpleNode will be used as the factory class.
333
334 NODE_PACKAGE (default: "")
335 The package to generate the node classes into. The default for this is
336 the parser package.
337
338 NODE_EXTENDS (default: "") (DEPRECATED)
339 The superclass for the SimpleNode class. By providing a custom
340 superclass you may be able to avoid the need to edit the generated
341 SimpleNode.java. See the examples/Interpreter for an example usage.
342
343 NODE_PREFIX (default: "AST")
344 The prefix used to construct node class names from node identifiers in
345 multi mode. The default for this is AST.
346
347 NODE_SCOPE_HOOK (default: false)
348 Insert calls to user-defined parser methods on entry and exit of every
349 node scope. See Node Scope Hooks above.
350
351 NODE_USES_PARSER (default: false)
352 JJTree will use an alternate form of the node construction routines
353 where it passes the parser object in. For example,
354
355 public static Node MyNode.jjtCreate(MyParser p, int id);
356 MyNode(MyParser p, int id);
357
358 TRACK_TOKENS (default: false)
359 Insert jjtGetFirstToken(), jjtSetFirstToken(), jjtGetLastToken() and
360 jjtSetLastToken() methods in SimpleNode. The firstToken is automatically
361 set up on entry to a node scope; the endToken is automatically set
362 up on exit from a node scope.
363
364 STATIC (default: true)
365 Generate code for a static parser. The default for this is true. This
366 must be used consistently with the equivalent JavaCC options. The value
367 of this option is emitted in the JavaCC source.
368
369 VISITOR (default: false)
370 Insert a jjtAccept() method in the node classes, and generate a visitor
371 implementation with an entry for every node type used in the grammar.
372
373 VISITOR_DATA_TYPE (default: "Object")
374 If this option is set, it is used in the signature of the
375 generated jjtAccept() methods and the visit() methods as the type of the
376 "data" argument.
377
378 VISITOR_RETURN_TYPE (default: "Object")
379 If this option is set, it is used in the signature of the generated
380 jjtAccept() methods and the visit() methods as the return type of the
381 method.
382
383 VISITOR_EXCEPTION (default: "")
384 If this option is set, it is used in the signature of the generated
385 jjtAccept() methods and the visit() methods.
386
387 JJTree state
388
389 JJTree keeps its state in a parser class field called jjtree. You can use
390 methods in this member to manipulate the node stack.
391
392
393 final class JJTreeState {
394 /* Call this to reinitialize the node stack. */
395 void reset();
396
397 /* Return the root node of the AST. */
398 Node rootNode();
399
400 /* Determine whether the current node was actually closed and
401 pushed */
402 boolean nodeCreated();
403
404 /* Return the number of nodes currently pushed on the node
405 stack in the current node scope. */
406 int arity();
407
408 /* Push a node on to the stack. */
409 void pushNode(Node n);
410
411 /* Return the node on the top of the stack, and remove it from the
412 stack. */
413 Node popNode();
414
415 /* Return the node currently on the top of the stack. */
416 Node peekNode();
417 }
418
419 Node Objects
420
421
422 /* All AST nodes must implement this interface. It provides basic
423 machinery for constructing the parent and child relationships
424 between nodes. */
425
426 public interface Node {
427 /** This method is called after the node has been made the current
428 node. It indicates that child nodes can now be added to it. */
429 public void jjtOpen();
430
431 /** This method is called after all the child nodes have been
432 added. */
433 public void jjtClose();
434
435 /** This pair of methods are used to inform the node of its
436 parent. */
437 public void jjtSetParent(Node n);
438 public Node jjtGetParent();
439
440 /** This method tells the node to add its argument to the node's
441 list of children. */
442 public void jjtAddChild(Node n, int i);
443
444 /** This method returns a child node. The children are numbered
445 from zero, left to right. */
446 public Node jjtGetChild(int i);
447
448 /** Return the number of children the node has. */
449 int jjtGetNumChildren();
450 }
451
452 The class SimpleNode implements the Node interface, and is automatically
453 generated by JJTree if it doesn't already exist. You can use this class as a
454 template or superclass for your node implementations, or you can modify it to
455 suit. SimpleNode additionally provides a rudimentary mechanism for recursively
456 dumping the node and its children. You might use this is in action like this:
457
458
459 {
460 ((SimpleNode)jjtree.rootNode()).dump(">");
461 }
462
463 The String parameter to dump() is used as padding to indicate the tree
464 hierarchy.
465
466 Another utility method is generated if the VISITOR options is set:
467
468
469 {
470 public void childrenAccept(MyParserVisitor visitor);
471 }
472
473 This walks over the node's children in turn, asking them to accept the
474 visitor. This can be useful when implementing preorder and postorder
475 traversals.
476
477 More Documentation
478
479 Jocelyn Paine has contributed a very nice introduction to JJTree where he
480 describes how he has used it to develop an extension to HTML for interactive
481 web pages: http://users.ox.ac.uk/~popx/jjtree.html
482
483 Examples
484
485 JJTree 0.3pre3 is distributed with some simple examples containing a grammar
486 that parses arithmetic expressions. See the file
487 examples/JJTreeExamples/README for further details.
488
489 There is also an interpreter for a simple language that uses JJTree to build
490 the program representation. See the file examples/Interpreter/README for more
491 information.
492
493 A grammar for HTML 3.2 is also included in the distribution. See
494 examples/HTMLGrammars/RobsHTML/README to find out more.
495
496 Information about an example using the visitor support is in
497 examples/VTransformer/README.
498 </pre>
499
500 </body>
501 </html>