/usr/share/doc/javacc4/doc/JJTree.html

<HTML>
<!--

Copyright © 2002 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
California 95054, U.S.A. All rights reserved.  Sun Microsystems, Inc. has
intellectual property rights relating to technology embodied in the product
that is described in this document. In particular, and without limitation,
these intellectual property rights may include one or more of the U.S.
patents listed at http://www.sun.com/patents and one or more additional
patents or pending patent applications in the U.S. and in other countries.
U.S. Government Rights - Commercial software. Government users are subject
to the Sun Microsystems, Inc. standard license agreement and applicable
provisions of the FAR and its supplements.  Use is subject to license terms.
Sun,  Sun Microsystems,  the Sun logo and  Java are trademarks or registered
trademarks of Sun Microsystems, Inc. in the U.S. and other countries.  This
product is covered and controlled by U.S. Export Control laws and may be
subject to the export or import laws in other countries.  Nuclear, missile,
chemical biological weapons or nuclear maritime end uses or end users, whether
direct or indirect, are strictly prohibited.  Export or reexport to countries
subject to U.S. embargo or to entities identified on U.S. export exclusion
lists, including, but not limited to, the denied persons and specially
designated nationals lists is strictly prohibited.

-->
<HEAD>
<title>JavaCC:  JJTree Reference</title>
<!-- Changed by: Michael Van De Vanter, 14-Jan-2003 -->
</HEAD>
<BODY bgcolor="#FFFFFF">

<H1>JavaCC [tm]: JJTree Reference Documentation</H1>

    <h3>Introduction</h3>

    <p>JJTree is a preprocessor for JavaCC [tm] that inserts parse tree
      building actions at various places in the JavaCC source.  The
      output of JJTree is run through JavaCC to create the parser.
      This document describes how to use JJTree, and how you can
      interface your parser to it.</p>

    <p>By default JJTree generates code to construct parse tree nodes
      for each nonterminal in the language.  This behavior can be
      modified so that some nonterminals do not have nodes generated,
      or so that a node is generated for a part of a production's
      expansion.</p>

    <p>JJTree defines a Java interface Node that all parse tree nodes
      must implement.  The interface provides methods for operations
      such as setting the parent of the node, and for adding children
      and retrieving them.</p>

    <p>JJTree operates in one of two modes, simple and multi (for want
      of better terms).  In simple mode each parse tree node is of
      concrete type SimpleNode; in multi mode the type of the parse
      tree node is derived from the name of the node.  If you don't
      provide implementations for the node classes JJTree will
      generate sample implementations based on SimpleNode for you.
      You can then modify the implementations to suit.</p>

    <p>Although JavaCC is a top-down parser, JJTree constructs the
      parse tree from the bottom up.  To do this it uses a stack where
      it pushes nodes after they have been created.  When it finds a
      parent for them, it pops the children from the stack and adds
      them to the parent, and finally pushes the new parent node
      itself.  The stack is open, which means that you have access to
      it from within grammar actions: you can push, pop and otherwise
      manipulate its contents however you feel appropriate.  See <a
      href="#scopes">Node Scopes and User Actions</a> below for more
      important information.</p>

    <p>JJTree provides decorations for two basic varieties of nodes,
      and some syntactic shorthand to make their use convenient.</p>

    <ol>
      <li>
	<p>A definite node is constructed with a specific number of
	  children.  That many nodes are popped from the stack and
	  made the children of the new node, which is then pushed on
	  the stack itself.  You notate a definite node like this:</p>
	<p><code>#ADefiniteNode(INTEGER EXPRESSION)</code></p> <p>A
	  definite node descriptor expression can be any integer
	  expression, although literal integer constants are by far
	  the most common expressions.</p>
      </li>

      <li>
	<p>A conditional node is constructed with all of the children
	  that were pushed on the stack within its node scope if and
	  only if its condition evaluates to true.  If it evaluates to
	  false, the node is not constructed, and all of the children
	  remain on the node stack.  You notate a conditional node
	  like this:</p> <p><code>#ConditionalNode(BOOLEAN
	    EXPRESSION)</code></p> <p>A conditional node descriptor
	  expression can be any boolean expression.  There are two
	  common shorthands for conditional nodes:</p>

	<ol>
	  <li>
	    <p>Indefinite nodes</p> <p><code>#IndefiniteNode</code> is
	      short for <code>#IndefiniteNode(true)</code></p>
	  </li>
	  
	  <li>
	    <p>Greater-than nodes</p> <p><code>#GTNode(>1)</code> is
	      short for <code>#GTNode(jjtree.arity() > 1)</code></p>
	  </li>
	  
	</ol> <p>The indefinite node shorthand (1) can lead to
	  ambiguities in the JJTree source when it is followed by a
	  parenthesized expansion.  In those cases the shorthand must
	  be replaced by the full expression.  For example:</p> <pre>
	  ( ... ) #N ( a() ) </pre>	 <p>is ambiguous; you have to
	  use the explicit condition:</p> <pre> ( ... ) #N(true) ( a()
	  ) </pre>

	    </li>
    </ol>

    <p>WARNING: node descriptor expression should not have
      side-effects.  JJTree doesn't specify how many times the
      expression will be evaluated.</p>

    <p>By default JJTree treats each nonterminal as an indefinite node
      and derives the name of the node from the name of its
      production.  You can give it a different name with the following
      syntax:</p>
	  <pre>
    void P1() #MyNode : { ... } { ... }
	  </pre>

    <p>When the parser recognizes a <code>P1</code> nonterminal it
      begins an indefinite node.  It marks the stack, so that any
      parse tree nodes created and pushed on the stack by nonterminals
      in the expansion for <code>P1</code> will be popped off and made
      children of the node <code>MyNode</code>.</p>

    <p>If you want to suppress the creation of a node for a production
      you can use the following syntax:</p>
	  <pre>
    void P2() #void : { ... } { ... }
	  </pre>

    <p>Now any parse tree nodes pushed by nonterminals in the
      expansion of <code>P2</code> will remain on the stack, to be
      popped and made children of a production further up the tree.
      You can make this the default behavior for non-decorated nodes
      by using the <code>NODE_DEFAULT_VOID</code> option.</p>


    <pre>    
    void P3() : {}
    {
        P4() ( P5() )+ P6()
    }
    </pre>

    <p>In this example, an indefinite node <code>P3</code> is begun,
      marking the stack, and then a <code>P4</code> node, one or more
      <code>P5</code> nodes and a <code>P6</code> node are parsed.
      Any nodes that they push are popped and made the children of
      <code>P3</code>.  You can further customize the generated
      tree:</p>

    <pre>
    void P3() : {}
    {
        P4() ( P5() )+ #ListOfP5s P6()
    }
    </pre>

    <p>Now the <code>P3</code> node will have a <code>P4</code> node,
      a <code>ListOfP5s</code> node and a <code>P6</code> node as
      children.  The <code>#Name</code> construct acts as a postfix
      operator, and its scope is the immediately preceding expansion
      unit.</p>


    <h3><a name="scopes">Node Scopes and User Actions</a></h3>

    <p>Each node is associated with a node scope.  User actions within
      this scope can access the node under construction by using the
      special identifier <code>jjtThis</code> to refer to the node.
      This identifier is implicitly declared to be of the correct type
      for the node, so any fields and methods that the node has can be
      easily accessed.</p>

    <p>A scope is the expansion unit immediately preceding the node
      decoration.  This can be a parenthesized expression.  When the
      production signature is decorated (perhaps implicitly with the
      default node), the scope is the entire right hand side of the
      production including its declaration block.</p>

    <p>You can also use an expression involving <code>jjtThis</code>
      on the left hand side of an expansion reference.  For
      example:</p>
	  <pre>
    ... ( jjtThis.my_foo = foo() ) #Baz ...
	  </pre>

    <p>Here <code>jjtThis</code> refers to a <code>Baz</code> node,
      which has a field called <code>my_foo</code>.  The result of
      parsing the production <code>foo()</code> is assigned to that
      <code>my_foo</code>.</p>

    <p>The final user action in a node scope is different from all the
      others.  When the code within it executes, the node's children
      have already been popped from the stack and added to the node,
      which has itself been pushed onto the stack.  The children can
      now be accessed via the node's methods such as
      <code>jjtGetChild()</code>.</p>

    <p>User actions other than the final one can only access the
      children on the stack.  They have not yet been added to the
      node, so they aren't available via the node's methods.</p>

    <p>A conditional node that has a node descriptor expression that
      evaluates to false will not get added to the stack, nor have
      children added to it.  The final user action within a
      conditional node scope can determine whether the node was
      created or not by calling the <code>nodeCreated()</code> method.
      This returns true if the node's condition was satisfied and the
      node was created and pushed on the node stack, and false
      otherwise.</p>

    <h3>Exception handling</h3>

    <p>An exception thrown by an expansion within a node scope that is
      not caught within the node scope is caught by JJTree itself.
      When this occurs, any nodes that have been pushed on to the node
      stack within the node scope are popped and thrown away.  Then
      the exception is rethrown.</p>

    <p>The intention is to make it possible for parsers to implement
      error recovery and continue with the node stack in a known
      state.</p>

    <p>WARNING: JJTree currently cannot detect whether exceptions are
      thrown from user actions within a node scope.  Such an exception
      will probably be handled incorrectly.</p>


    <h3><a name="hooks">Node Scope Hooks</a></h3>

    <p>If the <code>NODE_SCOPE_HOOK</code> option is set to true,
      JJTree generates calls to two user-defined parser methods on the
      entry and exit of every node scope.  The methods must have the
      following signatures:</p>

    <pre>
    void jjtreeOpenNodeScope(Node n)
    void jjtreeCloseNodeScope(Node n)
    </pre>

    <p>If the parser is <code>STATIC</code> then these methods will
      have to be declared as static as well.  They are both called
      with the current node as a parameter.</p>

    <p>One use for these functions is to store the node's first and
      last tokens so that the input can be easily reproduced again.
      For example:</p>

    
    <pre>
    void jjtreeOpenNodeScope(Node n)
    {
      ((MySimpleNode)n).first_token = getToken(1);
    }

    void jjtreeCloseNodeScope(Node n)
    {
      ((MySimpleNode)n).last_token = getToken(0);
    }
    </pre>

    <p>where <code>MySimpleNode</code> is based on
      <code>SimpleNode</code> and has the following additional
      fields:</p>

    <pre>
    Token first_token, last_token;
    </pre>

    <p>Another use might be to store the parser object itself in the
      node so that state that should be shared by all nodes produced
      by that parser can be provided.  For example, the parser might
      maintain a symbol table.</p>

    <h3>The Life Cycle of a Node</h3>

    <p>A node goes through a well determined sequence of steps as it
      is built.  This is that sequence viewed from the perspective of
      the node itself:</p>

    <ol>
      <li>the node's constructor is called with a unique integer
	parameter.  This parameter identifies the kind of node and is
	especially useful in simple mode.  JJTree automatically
	generates a file called <i>parser</i>TreeConstants.java that 
	declares valid constants.  The names of constants are derived
	by prepending JJT to the uppercase names of nodes, with dot 
	symbols (&quot;.&quot;) replaced by underscore symbols 
	(&quot;_&quot;).  For convenience, an array of <code>String</code>s 
	called <code>jjtNodeName[]</code> that maps the constants to the 
	unmodified names of nodes is maintained in the same file.</li>

      <li>the node's <code>jjtOpen()</code> method is called.</li>

      <li>if the option <code>NODE_SCOPE_HOOK</code> is set, the
	user-defined parser method <code>openNodeScope()</code> is
	called and passed the node as its parameter.  This method can
	initialize fields in the node or call its methods.  For
	example, it might store the node's first token in the
	node.</li>

      <li>if an unhandled exception is thrown while the node is being
	parsed then the node is abandoned.  JJTree will never refer to
	it again.  It will not be closed, and the user-defined node
	scope hook <code>closeNodeHook()</code> will not be called
	with it as a parameter.</li>

      <li>otherwise, if the node is conditional and its conditional
	expression evaluates to false then the node is abandoned.  It
	will not be closed, although the user-defined node scope hook
	<code>closeNodeHook()</code> might be called with it as a
	parameter.</li>

      <li>otherwise, all of the children of the node as specified by
	the integer expression of a definite node, or all the nodes
	that were pushed on the stack within a conditional node scope
	are added to the node.  The order they are added is not
	specified.</li>

      <li>the node's <code>jjtClose()</code> method is called.</li>

      <li>the node is pushed on the stack.</li>

      <li>if the option <code>NODE_SCOPE_HOOK</code> is set, the
	user-defined parser method <code>closenNodeScope()</code> is
	called and passed the node as its parameter.</li>

      <li>if the node is not the root node, it is added as a child of
	another node and its <code>jjtSetParent()</code> method is
	called.</li>
    </ol>

    <h3>Visitor Support</h3>

    <p>JJTree provides some basic support for the visitor design
      pattern.  If the <code>VISITOR</code> option is set to true
      JJTree will insert an <code>jjtAccept()</code> method into all
      of the node classes it generates, and also generate a visitor
      interface that can be implemented and passed to the nodes to
      accept.</p>

    <p>The name of the visitor interface is constructed by appending
      <code>Visitor</code> to the name of the parser.  The interface
      is regenerated every time that JJTree is run, so that it
      accurately represents the set of nodes used by the parser.  This
      will cause compile time errors if the implementation class has
      not been updated for the new nodes.  This is a feature.</p>


    <h3>Options</h3>

    <p>JJTree supports the following options on the command
      line and in the JavaCC options statement:</p>

    <dl>
      <dt><code>BUILD_NODE_FILES</code> (default:
	<code>true</code>)</dt>
      <dd>Generate sample implementations for SimpleNode and any other
	nodes used in the grammar.</dd>

      <dt><code>MULTI</code> (default: <code>false</code>)</dt>
      <dd> Generate a multi mode parse tree.  The default for this is
	false, generating a simple mode parse tree.</dd>

      <dt><code>NODE_DEFAULT_VOID</code> (default:
	<code>false</code>)</dt>
      <dd>Instead of making each non-decorated production an
	indefinite node, make it void instead.</dd>

      <dt><code>NODE_FACTORY</code> (default: <code>false</code>)</dt>

      <dd>Use a factory method with following signature to construct
	nodes:

	<br><code>public static Node jjtCreate(int id)</code>
      </dd>

      <dt><code>NODE_PACKAGE</code> (default: <code>""</code>)</dt>

      <dd> The package to generate the node classes into.  The default
	for this is the parser package.</dd>

      <dt><code>NODE_PREFIX</code> (default: <code>"AST"</code>)</dt>

      <dd>The prefix used to construct node class names from node
	identifiers in multi mode.  The default for this is AST.</dd>

      <dt><code>NODE_SCOPE_HOOK</code> (default:
	<code>false</code>)</dt>

      <dd>Insert calls to user-defined parser methods on entry and
	exit of every node scope.  See <a href="#hooks">Node Scope
	  Hooks above</a>.</dd>
      
      <dt><code>NODE_USES_PARSER</code> (default:
	<code>false</code>)</dt>

      <dd>JJTree will use an alternate form of the node construction
	routines where it passes the parser object in.  For example,
	<pre> public static Node MyNode.jjtCreate(MyParser p, int id);
	  MyNode(MyParser p, int id); </pre>
      </dd>

      <dt><code>STATIC</code> (default: <code>true</code>)</dt>

      <dd>Generate code for a static parser.  The default for this is
	true.  This must be used consistently with the equivalent
	JavaCC options.  The value of this option is emitted in the
	JavaCC source.</dd>

      <dt><code>VISITOR</code> (default: <code>false</code>)</dt>

      <dd>Insert a <code>jjtAccept()</code> method in the node
	classes, and generate a visitor implementation with an entry
	for every node type used in the grammar.</dd>

      <dt><code>VISITOR_EXCEPTION</code> (default:
	<code>""</code>)</dt>

      <dd>If this option is set, it is used in the signature of the
	generated <code>jjtAccept()</code> methods and the visit()
	methods.  <em>Note:</em> this option will be removed in a
	later version of JJTree.  Don't use it if that bothers
	you.</dd>

      <dt><code>JJTREE_OUTPUT_DIRECTORY</code> (default:
	use value of <code>OUTPUT_DIRECTORY</code>)</dt>

      <dd>By default, JJTree generates its output in the directory
      specified in the global <code>OUTPUT_DIRECTORY</code> setting.
      Explicitly setting this option allows the user to separate the
      parser from the tree files.</dd>
    </dl>


    <h3>JJTree state</h3>

    <p>JJTree keeps its state in a parser class field called
      <code>jjtree</code>.  You can use methods in this member to
      manipulate the node stack.</p>
    
    <pre>
    final class JJTreeState {
      /* Call this to reinitialize the node stack.  */
      void reset();

      /* Return the root node of the AST. */
      Node rootNode();

      /* Determine whether the current node was actually closed and
	 pushed */
      boolean nodeCreated();

      /* Return the number of nodes currently pushed on the node
         stack in the current node scope. */
      int arity();

      /* Push a node on to the stack. */
      void pushNode(Node n);

      /* Return the node on the top of the stack, and remove it from the
	 stack.  */
      Node popNode();

      /* Return the node currently on the top of the stack. */
      Node peekNode();
    }
    </pre>


    <h3>Node Objects</h3>

    <pre>
    /* All AST nodes must implement this interface.  It provides basic
       machinery for constructing the parent and child relationships
       between nodes. */

    public interface Node {
      /** This method is called after the node has been made the current
	node.  It indicates that child nodes can now be added to it. */
      public void jjtOpen();

      /** This method is called after all the child nodes have been
	added. */
      public void jjtClose();

      /** This pair of methods are used to inform the node of its
	parent. */
      public void jjtSetParent(Node n);
      public Node jjtGetParent();

      /** This method tells the node to add its argument to the node's
	list of children.  */
      public void jjtAddChild(Node n, int i);

      /** This method returns a child node.  The children are numbered
	 from zero, left to right. */
      public Node jjtGetChild(int i);

      /** Return the number of children the node has. */
      int jjtGetNumChildren();
    }
    </pre>

    <p>The class <code>SimpleNode</code> implements the
      <code>Node</code> interface, and is automatically generated by
      JJTree if it doesn't already exist.  You can use this class as a
      template or superclass for your node implementations, or you can
      modify it to suit.  <code>SimpleNode</code> additionally
      provides a rudimentary mechanism for recursively dumping the
      node and its children.  You might use this is in action like
      this:</p>

    <pre>    
    {
        ((SimpleNode)jjtree.rootNode()).dump(">");
    }

    </pre>

    <p>The <code>String</code> parameter to <code>dump()</code> is
      used as padding to indicate the tree hierarchy.</p>

    <p>Another utility method is generated if the VISITOR options is set:</p>
    <pre>
    {
        public void childrenAccept(MyParserVisitor visitor);
    }
    </pre>

    <p>This walks over the node's children in turn, asking them to
      accept the visitor.  This can be useful when implementing
      preorder and postorder traversals.</p>

    <h3>Examples</h3>

    <p>JJTree is distributed with some simple examples
      containing a grammar that parses arithmetic expressions.  See
      the file <code>examples/JJTreeExamples/README</code> for further
      details.</p>

    <p>There is also an interpreter for a simple language that uses
      JJTree to build the program representation.  See the file
      <code>examples/Interpreter/README</code> for more
      information.</p>

    <p>A grammar for HTML 3.2 is also included in the distribution.
      See <code>examples/HTMLGrammars/RobsHTML/README</code> to find
      out more.</p>

    <p>Information about an example using the visitor support is in
      <code>examples/VTransformer/README</code>.</p>

</BODY>
</HTML>
javacc4-doc 4.0-2 / usr / share / doc / javacc4 / doc / JJTree.html
