Debian Codegraph @

www/doc/JJTree.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 Reference</title>
35 <!-- Changed by: Michael Van De Vanter, 14-Jan-2003 -->
36 </head>
37 <body bgcolor="#FFFFFF">
38
39 <h1>JavaCC [tm]: JJTree Reference Documentation</h1>
40
41 <h3>Introduction</h3>
42
43 <p>JJTree is a preprocessor for JavaCC [tm] that inserts parse tree
44 building actions at various places in the JavaCC source. The
45 output of JJTree is run through JavaCC to create the parser.
46 This document describes how to use JJTree, and how you can
47 interface your parser to it.</p>
48
49 <p>By default JJTree generates code to construct parse tree nodes
50 for each nonterminal in the language. This behavior can be
51 modified so that some nonterminals do not have nodes generated,
52 or so that a node is generated for a part of a production's
53 expansion.</p>
54
55 <p>JJTree defines a Java interface Node that all parse tree nodes
56 must implement. The interface provides methods for operations
57 such as setting the parent of the node, and for adding children
58 and retrieving them.</p>
59
60 <p>JJTree operates in one of two modes, simple and multi (for want
61 of better terms). In simple mode each parse tree node is of
62 concrete type SimpleNode; in multi mode the type of the parse
63 tree node is derived from the name of the node. If you don't
64 provide implementations for the node classes JJTree will
65 generate sample implementations based on SimpleNode for you.
66 You can then modify the implementations to suit.</p>
67
68 <p>Although JavaCC is a top-down parser, JJTree constructs the
69 parse tree from the bottom up. To do this it uses a stack where
70 it pushes nodes after they have been created. When it finds a
71 parent for them, it pops the children from the stack and adds
72 them to the parent, and finally pushes the new parent node
73 itself. The stack is open, which means that you have access to
74 it from within grammar actions: you can push, pop and otherwise
75 manipulate its contents however you feel appropriate. See <a
76 href="#scopes">Node Scopes and User Actions</a> below for more
77 important information.</p>
78
79 <p>JJTree provides decorations for two basic varieties of nodes,
80 and some syntactic shorthand to make their use convenient.</p>
81
82 <ol>
83 <li>
84 <p>A definite node is constructed with a specific number of
85 children. That many nodes are popped from the stack and
86 made the children of the new node, which is then pushed on
87 the stack itself. You notate a definite node like this:</p>
88 <p><code>#ADefiniteNode(INTEGER EXPRESSION)</code></p> <p>A
89 definite node descriptor expression can be any integer
90 expression, although literal integer constants are by far
91 the most common expressions.</p>
92 </li>
93
94 <li>
95 <p>A conditional node is constructed with all of the children
96 that were pushed on the stack within its node scope if and
97 only if its condition evaluates to true. If it evaluates to
98 false, the node is not constructed, and all of the children
99 remain on the node stack. You notate a conditional node
100 like this:</p> <p><code>#ConditionalNode(BOOLEAN
101 EXPRESSION)</code></p> <p>A conditional node descriptor
102 expression can be any boolean expression. There are two
103 common shorthands for conditional nodes:</p>
104
105 <ol>
106 <li>
107 <p>Indefinite nodes</p> <p><code>#IndefiniteNode</code> is
108 short for <code>#IndefiniteNode(true)</code></p>
109 </li>
110
111 <li>
112 <p>Greater-than nodes</p> <p><code>#GTNode(>1)</code> is
113 short for <code>#GTNode(jjtree.arity() > 1)</code></p>
114 </li>
115
116 </ol>
117 <p>The indefinite node shorthand (1) can lead to
118 ambiguities in the JJTree source when it is followed by a
119 parenthesized expansion. In those cases the shorthand must
120 be replaced by the full expression. For example:</p> <pre>
121 ( ... ) #N ( a() ) </pre> <p>is ambiguous; you have to
122 use the explicit condition:</p> <pre> ( ... ) #N(true) ( a()
123 ) </pre>
124
125 </li>
126 </ol>
127
128 <p>WARNING: node descriptor expressions should not have
129 side-effects. JJTree doesn't specify how many times the
130 expression will be evaluated.</p>
131
132 <p>By default JJTree treats each nonterminal as an indefinite node
133 and derives the name of the node from the name of its
134 production. You can give it a different name with the following
135 syntax:</p>
136 <pre>
137 void P1() #MyNode : { ... } { ... }
138 </pre>
139
140 <p>When the parser recognizes a <code>P1</code> nonterminal it
141 begins an indefinite node. It marks the stack, so that any
142 parse tree nodes created and pushed on the stack by nonterminals
143 in the expansion for <code>P1</code> will be popped off and made
144 children of the node <code>MyNode</code>.</p>
145
146 <p>If you want to suppress the creation of a node for a production
147 you can use the following syntax:</p>
148 <pre>
149 void P2() #void : { ... } { ... }
150 </pre>
151
152 <p>Now any parse tree nodes pushed by nonterminals in the
153 expansion of <code>P2</code> will remain on the stack, to be
154 popped and made children of a production further up the tree.
155 You can make this the default behavior for non-decorated nodes
156 by using the <code>NODE_DEFAULT_VOID</code> option.</p>
157
158
159 <pre>
160 void P3() : {}
161 {
162 P4() ( P5() )+ P6()
163 }
164 </pre>
165
166 <p>In this example, an indefinite node <code>P3</code> is begun,
167 marking the stack, and then a <code>P4</code> node, one or more
168 <code>P5</code> nodes and a <code>P6</code> node are parsed.
169 Any nodes that they push are popped and made the children of
170 <code>P3</code>. You can further customize the generated
171 tree:</p>
172
173 <pre>
174 void P3() : {}
175 {
176 P4() ( P5() )+ #ListOfP5s P6()
177 }
178 </pre>
179
180 <p>Now the <code>P3</code> node will have a <code>P4</code> node,
181 a <code>ListOfP5s</code> node and a <code>P6</code> node as
182 children. The <code>#Name</code> construct acts as a postfix
183 operator, and its scope is the immediately preceding expansion
184 unit.</p>
185
186
187 <h3><a name="scopes">Node Scopes and User Actions</a></h3>
188
189 <p>Each node is associated with a node scope. User actions within
190 this scope can access the node under construction by using the
191 special identifier <code>jjtThis</code> to refer to the node.
192 This identifier is implicitly declared to be of the correct type
193 for the node, so any fields and methods that the node has can be
194 easily accessed.</p>
195
196 <p>A scope is the expansion unit immediately preceding the node
197 decoration. This can be a parenthesized expression. When the
198 production signature is decorated (perhaps implicitly with the
199 default node), the scope is the entire right hand side of the
200 production including its declaration block.</p>
201
202 <p>You can also use an expression involving <code>jjtThis</code>
203 on the left hand side of an expansion reference. For
204 example:</p>
205 <pre>
206 ... ( jjtThis.my_foo = foo() ) #Baz ...
207 </pre>
208
209 <p>Here <code>jjtThis</code> refers to a <code>Baz</code> node,
210 which has a field called <code>my_foo</code>. The result of
211 parsing the production <code>foo()</code> is assigned to that
212 <code>my_foo</code>.</p>
213
214 <p>The final user action in a node scope is different from all the
215 others. When the code within it executes, the node's children
216 have already been popped from the stack and added to the node,
217 which has itself been pushed onto the stack. The children can
218 now be accessed via the node's methods such as
219 <code>jjtGetChild()</code>.</p>
220
221 <p>User actions other than the final one can only access the
222 children on the stack. They have not yet been added to the
223 node, so they aren't available via the node's methods.</p>
224
225 <p>A conditional node that has a node descriptor expression that
226 evaluates to false will not get added to the stack, nor have
227 children added to it. The final user action within a
228 conditional node scope can determine whether the node was
229 created or not by calling the <code>nodeCreated()</code> method.
230 This returns true if the node's condition was satisfied and the
231 node was created and pushed on the node stack, and false
232 otherwise.</p>
233
234 <h3>Exception handling</h3>
235
236 <p>An exception thrown by an expansion within a node scope that is
237 not caught within the node scope is caught by JJTree itself.
238 When this occurs, any nodes that have been pushed on to the node
239 stack within the node scope are popped and thrown away. Then
240 the exception is rethrown.</p>
241
242 <p>The intention is to make it possible for parsers to implement
243 error recovery and continue with the node stack in a known
244 state.</p>
245
246 <p>WARNING: JJTree currently cannot detect whether exceptions are
247 thrown from user actions within a node scope. Such an exception
248 will probably be handled incorrectly.</p>
249
250
251 <h3><a name="hooks">Node Scope Hooks</a></h3>
252
253 <p>If the <code>NODE_SCOPE_HOOK</code> option is set to true,
254 JJTree generates calls to two user-defined parser methods on the
255 entry and exit of every node scope. The methods must have the
256 following signatures:</p>
257
258 <pre>
259 void jjtreeOpenNodeScope(Node n)
260 void jjtreeCloseNodeScope(Node n)
261 </pre>
262
263 <p>If the parser is <code>STATIC</code> then these methods will
264 have to be declared as static as well. They are both called
265 with the current node as a parameter.</p>
266
267 <p>One use might be to store the parser object itself in the
268 node so that state that should be shared by all nodes produced
269 by that parser can be provided. For example, the parser might
270 maintain a symbol table.</p>
271
272
273 <pre>
274 void jjtreeOpenNodeScope(Node n)
275 {
276 ((SimpleNode)n).jjtSetValue(getSymbolTable());
277 }
278
279 void jjtreeCloseNodeScope(Node n)
280 {
281 }
282 </pre>
283
284 <p>Where <code>getSymbolTable()</code> is a user-defined method to
285 return a symbol table structure for the node.</p>
286
287 <h3><a name="hooks">Tracking Tokens</a></h3>
288
289 <p>It is often useful to keep track of each node's first and last
290 token so that input can be easily reproduced again. By
291 setting the <code>TRACK_TOKENS</code> option the generated
292 <code>SimpleNode</code> class will contain 4 extra methods:</p>
293
294 <pre>
295 public Token jjtGetFirstToken()
296 public void jjtSetFirstToken(Token token)
297 public Token jjtGetLastToken()
298 public void jjtSetLastToken(Token token)
299 </pre>
300
301 <p>The first and last token for each node will be set
302 up automatically when the parser is run. </p>
303
304 <h3>The Life Cycle of a Node</h3>
305
306 <p>A node goes through a well determined sequence of steps as it
307 is built. This is that sequence viewed from the perspective of
308 the node itself:</p>
309
310 <ol>
311 <li>the node's constructor is called with a unique integer
312 parameter. This parameter identifies the kind of node and is
313 especially useful in simple mode. JJTree automatically
314 generates a file called <i>parser</i>TreeConstants.java that
315 declares valid constants. The names of constants are derived
316 by prepending JJT to the uppercase names of nodes, with dot
317 symbols (&quot;.&quot;) replaced by underscore symbols
318 (&quot;_&quot;). For convenience, an array of <code>String</code>s
319 called <code>jjtNodeName[]</code> that maps the constants to the
320 unmodified names of nodes is maintained in the same file.</li>
321
322 <li>the node's <code>jjtOpen()</code> method is called.</li>
323
324 <li>if the option <code>NODE_SCOPE_HOOK</code> is set, the
325 user-defined parser method <code>openNodeScope()</code> is
326 called and passed the node as its parameter. This method can
327 initialize fields in the node or call its methods. For
328 example, it might store the node's first token in the
329 node.</li>
330
331 <li>if an unhandled exception is thrown while the node is being
332 parsed then the node is abandoned. JJTree will never refer to
333 it again. It will not be closed, and the user-defined node
334 scope hook <code>closeNodeHook()</code> will not be called
335 with it as a parameter.</li>
336
337 <li>otherwise, if the node is conditional and its conditional
338 expression evaluates to false then the node is abandoned. It
339 will not be closed, although the user-defined node scope hook
340 <code>closeNodeHook()</code> might be called with it as a
341 parameter.</li>
342
343 <li>otherwise, all of the children of the node as specified by
344 the integer expression of a definite node, or all the nodes
345 that were pushed on the stack within a conditional node scope
346 are added to the node. The order they are added is not
347 specified.</li>
348
349 <li>the node's <code>jjtClose()</code> method is called.</li>
350
351 <li>the node is pushed on the stack.</li>
352
353 <li>if the option <code>NODE_SCOPE_HOOK</code> is set, the
354 user-defined parser method <code>closeNodeScope()</code> is
355 called and passed the node as its parameter.</li>
356
357 <li>if the node is not the root node, it is added as a child of
358 another node and its <code>jjtSetParent()</code> method is
359 called.</li>
360 </ol>
361
362 <h3>Visitor Support</h3>
363
364 <p>JJTree provides some basic support for the visitor design
365 pattern. If the <code>VISITOR</code> option is set to true
366 JJTree will insert an <code>jjtAccept()</code> method into all
367 of the node classes it generates, and also generate a visitor
368 interface that can be implemented and passed to the nodes to
369 accept.</p>
370
371 <p>The name of the visitor interface is constructed by appending
372 <code>Visitor</code> to the name of the parser. The interface
373 is regenerated every time that JJTree is run, so that it
374 accurately represents the set of nodes used by the parser. This
375 will cause compile time errors if the implementation class has
376 not been updated for the new nodes. This is a feature.</p>
377
378
379 <h3>Options</h3>
380
381 <p>JJTree supports the following options on the command
382 line and in the JavaCC options statement:</p>
383
384 <dl>
385 <dt><code>BUILD_NODE_FILES</code> (default:
386 <code>true</code>)</dt>
387 <dd>Generate sample implementations for SimpleNode and any other
388 nodes used in the grammar.</dd>
389
390 <dt><code>MULTI</code> (default: <code>false</code>)</dt>
391 <dd> Generate a multi mode parse tree. The default for this is
392 false, generating a simple mode parse tree.</dd>
393
394 <dt><code>NODE_DEFAULT_VOID</code> (default:
395 <code>false</code>)</dt>
396 <dd>Instead of making each non-decorated production an
397 indefinite node, make it void instead.</dd>
398
399 <dt><code>NODE_CLASS</code> (default: <code>""</code>)</dt>
400 <dd>If set defines the name of a user-supplied class that will
401 extend <code>SimpleNode</code>. Any tree nodes created will
402 then be subclasses of NODE_CLASS.</dd>
403
404 <dt><code>NODE_FACTORY</code> (default: <code>""</code>)</dt>
405 <dd>Specify a class containing a factory method with following
406 signature to construct nodes:
407
408 <br /><code>public static Node jjtCreate(int id)</code>
409 <br />For backwards compatibility, the value <code>false</code>
410 may also be specified, meaning that <code>SimpleNode</code>
411 will be used as the factory class.
412 </dd>
413
414 <dt><code>NODE_PACKAGE</code> (default: <code>""</code>)</dt>
415
416 <dd> The package to generate the node classes into. The default
417 for this is the parser package.</dd>
418
419 <dt><code>NODE_EXTENDS</code> (default: <code>""</code>) <em>Deprecated</em></dt>
420
421 <dd>The superclass for the SimpleNode class.
422 By providing a custom superclass you may be able to avoid
423 the need to edit the generated SimpleNode.java.
424 See the examples/Interpreter for an example
425 usage.</dd>
426
427 <dt><code>NODE_PREFIX</code> (default: <code>"AST"</code>)</dt>
428
429 <dd>The prefix used to construct node class names from node
430 identifiers in multi mode. The default for this is AST.</dd>
431
432 <dt><code>NODE_SCOPE_HOOK</code> (default:
433 <code>false</code>)</dt>
434
435 <dd>Insert calls to user-defined parser methods on entry and
436 exit of every node scope. See <a href="#hooks">Node Scope
437 Hooks above</a>.</dd>
438
439 <dt><code>NODE_USES_PARSER</code> (default:
440 <code>false</code>)</dt>
441
442 <dd>JJTree will use an alternate form of the node construction
443 routines where it passes the parser object in. For example,
444 <pre> public static Node MyNode.jjtCreate(MyParser p, int id);
445 MyNode(MyParser p, int id); </pre>
446 </dd>
447
448 <dt><code>TRACK_TOKENS</code> (default:
449 <code>false</code)</dt>
450
451 <dd>Insert <code>jjtGetFirstToken(), jjtSetFirstToken(), getLastToken(),
452 </code> and <code>jjtSetLastToken()</code> methods in SimpleNode. The
453 <code>FirstToken</code> is automatically set up on entry to a node
454 scope; the <code>LastToken</code> is automatically set up on exit
455 from a node scope.
456 </dd>
457
458 <dt><code>STATIC</code> (default: <code>true</code>)</dt>
459
460 <dd>Generate code for a static parser. The default for this is
461 true. This must be used consistently with the equivalent
462 JavaCC options. The value of this option is emitted in the
463 JavaCC source.</dd>
464
465 <dt><code>VISITOR</code> (default: <code>false</code>)</dt>
466
467 <dd>Insert a <code>jjtAccept()</code> method in the node
468 classes, and generate a visitor implementation with an entry
469 for every node type used in the grammar.</dd>
470
471 <dt><code>VISITOR_DATA_TYPE</code> (default:
472 <code>"Object"</code>)</dt>
473
474 <dd>If this option is set, it is used in the signature of the
475 generated <code>jjtAccept()</code> methods and the visit()
476 methods as the type of the <code>data</code>
477 argument.
478 </dd>
479
480 <dt><code>VISITOR_RETURN_TYPE</code> (default:
481 <code>"Object"</code>)</dt>
482
483 <dd>If this option is set, it is used in the signature of the
484 generated <code>jjtAccept()</code> methods and the visit()
485 methods as the return type of the method.
486 </dd>
487
488 <dt><code>VISITOR_EXCEPTION</code> (default:
489 <code>""</code>)</dt>
490
491 <dd>If this option is set, it is used in the signature of the
492 generated <code>jjtAccept()</code> methods and the visit()
493 methods.</dd>
494
495 <dt><code>JJTREE_OUTPUT_DIRECTORY</code> (default:
496 use value of <code>OUTPUT_DIRECTORY</code>)</dt>
497
498 <dd>By default, JJTree generates its output in the directory
499 specified in the global <code>OUTPUT_DIRECTORY</code> setting.
500 Explicitly setting this option allows the user to separate the
501 parser from the tree files.</dd>
502 </dl>
503
504
505 <h3>JJTree state</h3>
506
507 <p>JJTree keeps its state in a parser class field called
508 <code>jjtree</code>. You can use methods in this member to
509 manipulate the node stack.</p>
510
511 <pre>
512 final class JJTreeState {
513 /* Call this to reinitialize the node stack. */
514 void reset();
515
516 /* Return the root node of the AST. */
517 Node rootNode();
518
519 /* Determine whether the current node was actually closed and
520 pushed */
521 boolean nodeCreated();
522
523 /* Return the number of nodes currently pushed on the node
524 stack in the current node scope. */
525 int arity();
526
527 /* Push a node on to the stack. */
528 void pushNode(Node n);
529
530 /* Return the node on the top of the stack, and remove it from the
531 stack. */
532 Node popNode();
533
534 /* Return the node currently on the top of the stack. */
535 Node peekNode();
536 }
537 </pre>
538
539
540 <h3>Node Objects</h3>
541
542 <pre>
543 /* All AST nodes must implement this interface. It provides basic
544 machinery for constructing the parent and child relationships
545 between nodes. */
546
547 public interface Node {
548 /** This method is called after the node has been made the current
549 node. It indicates that child nodes can now be added to it. */
550 public void jjtOpen();
551
552 /** This method is called after all the child nodes have been
553 added. */
554 public void jjtClose();
555
556 /** This pair of methods are used to inform the node of its
557 parent. */
558 public void jjtSetParent(Node n);
559 public Node jjtGetParent();
560
561 /** This method tells the node to add its argument to the node's
562 list of children. */
563 public void jjtAddChild(Node n, int i);
564
565 /** This method returns a child node. The children are numbered
566 from zero, left to right. */
567 public Node jjtGetChild(int i);
568
569 /** Return the number of children the node has. */
570 int jjtGetNumChildren();
571 }
572 </pre>
573
574 <p>The class <code>SimpleNode</code> implements the
575 <code>Node</code> interface, and is automatically generated by
576 JJTree if it doesn't already exist. You can use this class as a
577 template or superclass for your node implementations, or you can
578 modify it to suit. <code>SimpleNode</code> additionally
579 provides a rudimentary mechanism for recursively dumping the
580 node and its children. You might use this is in action like
581 this:</p>
582
583 <pre>
584 {
585 ((SimpleNode)jjtree.rootNode()).dump(">");
586 }
587
588 </pre>
589
590 <p>The <code>String</code> parameter to <code>dump()</code> is
591 used as padding to indicate the tree hierarchy.</p>
592
593 <p>Another utility method is generated if the VISITOR options is set:</p>
594 <pre>
595 {
596 public void childrenAccept(MyParserVisitor visitor);
597 }
598 </pre>
599
600 <p>This walks over the node's children in turn, asking them to
601 accept the visitor. This can be useful when implementing
602 preorder and postorder traversals.</p>
603
604 <h3>Examples</h3>
605
606 <p>JJTree is distributed with some simple examples
607 containing a grammar that parses arithmetic expressions. See
608 the file <code>examples/JJTreeExamples/README</code> for further
609 details.</p>
610
611 <p>There is also an interpreter for a simple language that uses
612 JJTree to build the program representation. See the file
613 <code>examples/Interpreter/README</code> for more
614 information.</p>
615
616 <p>Information about an example using the visitor support is in
617 <code>examples/VTransformer/README</code>.</p>
618
619 </body>
620 </html>