JTB

How JTB builds the nodes trees and the default visitors

This section aims at explaining the main things about the node generation performed by JTB.

JTB does different things: starting with a .jtb grammar file:

Each syntaxtree class / node builds its own (sub-)tree; the grammar usually has one entry point, which will be the root of the grammar tree; but the grammar can be used with different entry points, resulting to different grammar trees, but there is nothing specifically generated for this; the root of the tree is the node corresponding to the entry point used when parsing.

JavaCC & JTB schematic grammars

We first present a schematic layout of parts of interest of the JavaCC grammar, in order to fix terms involved in node generation (in bold and italic).
User grammar writers do not have to know about the JavaCC grammar itself, but as this section aims at explaining things to the JTB contributors as well as to these user grammar writers, we needed to go through the (parts of interest of the) JavaCC/JTB grammars; those are for contributors and examples are for writers).


JavaCodeProduction

  "JAVACODE"

  AccessModifier()

  ResultType()

  IdentifierAsString() // the name of the JavaCodeProduction, used in other productions

  FormalParameters()

  [ "throws" Name() ( "," Name() )* ]

  Block()



BNFProduction

  AccessModifier()

  ResultType()

  IdentifierAsString() // the name of the BNFProduction, used in other productions

  FormalParameters()

  [ "throws" Name() ( "," Name() )* ]

  ":"

  Block()

  "{"

  ExpansionChoices()

  "}"



ExpansionChoices

  Expansion()

  ( "|" Expansion() )*

We can distinguish two types of ExpansionChoices, one without choice and one with choices, as they will lead to different node generations:


ExpansionChoicesWithoutChoices

  Expansion()



ExpansionChoicesWithChoices

  Expansion()

  ( "|" Expansion() )+

Now further down the grammar.




Expansion

  ( "LOOKAHEAD" "(" LocalLookahead() ")" )?

  ( ExpansionUnit() )+



ExpansionUnit

    "LOOKAHEAD" "(" LocalLookahead() ")"

  | Block()

  | "[" ExpansionChoices() "]"

  | ExpansionUnitTCF()

  | [ PrimaryExpression() "=" ]

    ( IdentifierAsString() Arguments()
 // the name of a JavacodeProduction or a BNFProduction

    | RegularExpression() [ "." < IDENTIFIER > ] )
 // any of the 3 ways for a token

  | "(" ExpansionChoices() ")" ( "+" | "*" | "?" )?



ExpansionUnitTCF

  "try" "{" ExpansionChoices() "}"

  ( catch" "(" [ "final" ] Name() < IDENTIFIER > ")" Block() )*

  [ "finally" Block() ]

A few words on ExpansionUnit:

About ExpansionUnitTCF: this case has been extracted (in JTB comparing to JavaCC) as a separate production for cosmetic reasons (to shorten the generating methods) (the cases 2, 4 - 4a/4b & 5 could have also been separated).

Further down the grammar.


RegularExprProduction

  [ "<" "*" ">" | "<" < IDENTIFIER > ( "," < IDENTIFIER > )* ">" ] // lexical states list

  RegExprKind() [ "[" "IGNORE_CASE" "]" ] ":" // TOKEN, SKIP, MORE, ...

  "{"

  RegExprSpec()

  ( "|" RegExprSpec() )*

  "}"



RegExprSpec

  RegularExpression()

  [ Block() ]

  [ ":" < IDENTIFIER > ] // lexical state to switch to



RegularExpression

    StringLiteral() // like "abc"

  | "<" [ [ "#" ] IdentifierAsString() ":" ] ComplexRegularExpressionChoices() ">"
 // like < ID : "a" | "b" >

  | "<" IdentifierAsString() ">" // like < NUMBER >

  | "<" "EOF" ">"

We see that we have recursive cycles of ExpansionChoices -> Expansion(s) -> ExpansionUnit(s) [ -> ExpansionUnitTCF(s) ] -> ExpansionChoices(s) -> … which end on a call to a BNFProduction or a RegularExpression.
And that an ExpansionChoices may have no choice and so reduce to single Expansion.
And that an Expansion may be a list of only one ExpansionUnit and so reduce to single ExpansionUnit.
So even if a BNProduction reduces to single ExpansionUnit, it is handled by JTB as a chain of ExpansionChoices (with no choices) -> Expansion (with no LOOKAHEAD and a single ExpansionUnit) -> ExpansionUnit.

Note also that an Expansion can have no element of type 2, 3, 4 and 5 (no inner ExpansionChoices nor BNFProduction nor RegularExpression), but 0 or 1 Lookahead and 1 or more Block. This will impact on node creation.

JTB base nodes, user nodes, leaf nodes, inner nodes and nullable nodes

A specific concept of JTB is to build nodes - as long as it is meaningful - for the technical constructs

NodeGrammarGenerated class
a *nodes choice*`A | B` [NodeChoice](../../target/generated-tests/jtb/grammars/b/syntaxtree/NodeChoice.java)
an *optional node*`[ A ]` and `( A )?` [NodeOptional](../../target/generated-tests/jtb/grammars/b/syntaxtree/NodeOptional.java)
a *nodes sequence*`A B` and `( A )` [NodeSequence](../../target/generated-tests/jtb/grammars/b/syntaxtree/NodeSequence.java)
a *list of nodes*`( A )+` [NodeList](../../target/generated-tests/jtb/grammars/b/syntaxtree/NodeList.java)
an *optional list of nodes*`( A )*` [NodeListOptional](../../target/generated-tests/jtb/grammars/b/syntaxtree/NodeListOptional.java)
a *Token node*`"abc"` and `< ABC >` [NodeToken](../../target/generated-tests/jtb/grammars/b/syntaxtree/NodeToken.java)

and that will intertwin with nodes that derive from:

NodeGrammarGenerated class
a *BNFProduction*`bp()`bp

Note that in version 1.5.1 & 1.5.2 there was no base class NodeToken, the code was generated in a Token class which also included the JavaCC code for handling tokens.

Note that an ExpansionUnit type 5 with no modifier ( A ) gives a node of the inner node type (here A) which can be another base node or a user node. If A is not a NodeSequence nor a NodeChoice, then the parentheses are superfluous.

BNFProductions nodes will be handled by different generated classes, and are called user nodes.
Nodes choice, optional node, nodes sequence, list of nodes, optional list of nodes and token nodes are called base nodes and are handled by the corresponding generic classes.

User nodes (BNFProductions) and token nodes (RegularExpressions are the leaf nodes of the built tree, and the other nodes of the tree (called internal nodes) are of nodes choice, optional node, nodes sequence, list of nodes and optional list of nodes.

At the syntaxtree classes level, you can have one or more nodes; in that last case JTB does not generate a NodeSequence, but directly as many class fields as nodes, and they may be leaf nodes or inner nodes.

When a node is not under (the scope of) an ExpansionUnitTCF, it always exist, it is always non null (as if an exception is thrown the whole parsing will fail and the tree will not extend further the previous node).

But any node under an ExpansionUnitTCF can potentially not be built, as when an exception is thrown and caught (by the catch(...) part) before successful parsing of the corresponding construct.
So everwhere under an ExpansionUnitTCF (even many expansion levels under) any inner branch can fully exist (if no exception is thrown), partially exist (if an exception is thrown in the middle of the branch building), or not exist (if the exception is thrown before any node of the branch is built), and that depends on the (parsing of the) actual data. We call these nodes nullable nodes.
Note that having nested ExpansionUnitTCFs does not change much things: an inner ExpansionUnitTCF branch can totally exist, partially exist or not exist depending on which catch(...) handles the exception.

How to declare nodes to be built or not?

Default behavior

By default, i.e. without any specific notation (= with pure JavaCC syntax as above):

JTB Custom behavior

JTB allows to add indicators to customize which nodes are built or not. So the JTB grammar can be slightly different from the JavaCC grammar, but do not panic, JTB removes (comments) these indicators when outputting the .jj file, which is compiled by JavaCC.

Build JavacodeProduction nodes

By adding a `%` indicator to the JavacodeProduction definition (before the Block), you tell JTB to generate a user node everywhere an ExpansionUnit type 4a (IdentifierAsString()) refers to it.
Note that the generated user class will have no field, so in essence will be of poor use; you will likely have to overwrite this (derived) class with your custom class. (Note: we plan to add in the future the ability to specify the fields the generated class must have, like % Token f0; Token msg; %).
This can be useful to build tools that are tolerant to the grammar errors (a code editor for example), or to build tools that chosse to enrich a parsed file directly in the tree.


JavaCodeProduction

  "JAVACODE"

  AccessModifier()

  ResultType()

  IdentifierAsString() // the name of the JavaCodeProduction, used in other productions

  FormalParameters()

  [ "throws" Name() ( "," Name() )* ]

  [ "%" ]

  Block()

Example (assuming the generated class is overwritten with 2 fields f0 & msg of type Token)


JAVACODE void skipButBuild() % {

  Token tk = getNextToken(); // eat a token

  f0 = new Token(12, tk); // memorise it

  msg = new Token(87, "extra token eated"); // with some message

}

Do not build all occurrences of some leaf nodes

This feature can be useful to build tools that focus on a small part of the grammar and therefore do not need full trees.

By adding a `!` indicator to the BNFProduction definition (before the :), you tell JTB to not generate a user node everywhere an ExpansionUnit type 4a (IdentifierAsString()) refers to it.


BNFProduction

  AccessModifier()

  ResultType()

  IdentifierAsString() // the name of the BNFProduction, used in other productions

  FormalParameters()

  [ "throws" Name() ( "," Name() )* ]

  [ "!" ]

  ":"

  Block()

  "{"

  ExpansionChoices()

  "}"

Example


// no need to process these modifiers in my tool

void inOutClause() "!" : {

  "IN" | "OUT" | "INOUT"

}

Similarly, by adding a `!` indicator to the RegExprSpec definition (after the RegularExpression), you tell JTB to not generate a leaf node everywhere an ExpansionUnit type 4b (RegularExpression()) refers to it.


RegExprSpec

  RegularExpression()

  [ "!" ]

  [ Block() ]

  [ ":" < IDENTIFIER > ] // lexical state to switch to

Example


// no need to process some wierd tokens in my tool

TOKEN : {

  < ES : "\u00e9\u00e8\u00ea" > "!"

| < #SYN_ESC : "\u0016\u001b" > "!"

| < ID : ([ "a"-"z", "A"-"Z" ])([ "a"-"z", "A"-"Z", "0"-"9" ])* >

}

Do not build some occurrences of some leaf nodes

You may want to not build only some occurrences of some leaf nodes and still build the others. For this just add the indicator where (after) the construct appears, that is in an ExpansionUnit type 4a or 4b.


ExpansionUnit

    "LOOKAHEAD" "(" LocalLookahead() ")"

  | Block()

  | "[" ExpansionChoices() "]"

  | ExpansionUnitTCF()

  | [ PrimaryExpression() "=" ]

    ( IdentifierAsString()</i> Arguments() "!"
 // type 4a

    | RegularExpression() [ "." < IDENTIFIER > ] "!" )
 // type 4b

  | "(" ExpansionChoices() ")" ( "+" | "*" | "?" )?

Example


// keep only the < ID > and my_prod() nodes

void less_nodes() :

{}

{

  < A_BS_B > "!"

  < ID >

  prod_node()

  prod_no_node() "!"

}

Note that case 4a applies only to BNFProduction, not to JavacodeProduction. TODO check and complete.
Note also that for the moment you cannot build some occurrences of a JavacodeProduction in that case 4a (by adding the "%" indicator). TODO check and complete.

Building different trees on the same grammar

For the moment, if you want to build different tools with JTB, you are likely to use one grammar file and create the full tree, or at least the smallest tree that matches all your tools needs, and subclass the default visitors for each of your tools.

You can of course duplicate the grammar file and modify the indicators in the grammar files to produce different trees for your different tools, at the expense of more maintenance work to keep all the grammars up-to-date.

We think to add in the future the ability to specify the build nodes indicators outside the (main) JTB file and therefore enable generating different trees with a single JavaCC grammar.

What happens to the base nodes when sub nodes are not built? Null nodes and empty nodes

When a leaf node is added (for a JavacodeProduction), things are the same as if it was a BNFProdution, the ExpansionUnit counts for the upper inner node.

When a leaf node is not built, similarly the ExpansionUnit does not count for the upper inner node.

And JTB tries to avoid as much as possible at creating ‘permanent’ null nodes in an inner node (nodes that should never exist, which is different from the nullable nodes under an ExpansionUnitTCF.
When a node is not built, you can conceptually think of it as an **empty node, and if it must stay (in a NodeChoice it becomes a null node (with a real null reference), otherwise it disappears, but the construct above is impacted, and may change to another base node type, or even become empty, and this can propagate up to the top (the root), in which case there will no root so no tree.
This happens in parallel of the specific processing for an *ExpansionUnitTCF.

Let’s say B and A give a node and N and M do not give a node:

If we are in an ExpansionUnitTCF, things are the same, just remember that besides this nodes B and A are nullable, i.e. can be null.

What happens to the base nodes when an Expansion is made of only Java blocks?

As noted above, an Expansion can have no element of type 2, 3, 4 and 5 (no inner ExpansionChoices nor BNFProduction nor RegularExpression), but 0 or 1 Lookahead and 1 or more Block.
In that case, we are with an empty node, like above, this propagates up.

Let’s say B gives a node, N does not give a node, {} is a Block, and LH is a Lookahead:

How JTB creates the syntaxtree classes?

A BNFProduction which is declared not to produce a node does not lead to a syntaxtree class.

A BNFProduction which produces a node becomes a method that returns an instance of the syntaxtree class.

This class implements an INode interface that declares the different accept() methods for the different visitors. These accept() methods take as arguments the visitor and the visit arguments if they have been requested, and just call back the visit() methods on the visitors with the given arguments.

This syntaxtree node class will have fields (aka childnodes) that are the first level inner nodes (the class instance is considered as the root of the tree).
These fields are usually named f0, f1…fn, and are of the appropriate base node or leaf node type.

Example bp_v

grammar.jtb


// bnf production returning void

void bp_v() :

{}

{ < ID > }

bp_v.java


// Node class

public class bp_v implements INode {

  // First field, corresponding to < ID > */

  public Token f0;

  // constructor

  public bp_v(final Token n0) {

    f0 = n0;

  }

  // Accepts a void visitor with no arguments

  @Override

  public void accept(final IVoidVisitor vis) {

    vis.visit(this);

  }

How JTB annotates the JJ file for building the nodes?

Nodes types and BNFProduction return type

A BNFProduction which is declared not to produce a node will not be annotated by JTB, i.e. its code stays the same, and the corresponding method returns the declared grammar type.

But a BNFProduction which produces a node becomes a method that returns an instance of the syntaxtree class.
So JTB transforms the BNFProduction code to return a different type than the declared grammar type.

When the grammar return type is void, JTB:

Example bp_v (void return type)

grammar.jj


// changed bnf production return type

bp_v bp_v() :

{

  ...

  // added variable declaration returning the node

  bp_v jtbNode = null;

}

{

  ...

  // added node creation & assignment to the node variable

  { jtbNode = new bp_v(n0); }

  // added return statement

  { return jtbNode; }

}

When the grammar return type is not void, JTB:

Example bp_i / bp_i2 (int return type)

grammar.jtb


// bnf production returning an int

int bp_i() :

{ Token tk = null; }

{

  tk = < ID >

  { return tk.image.length(); }

}



// bnf production using the previous one

void bp_i2() :

{ int i = 0; }

{

  < ID >

  i = bp_i()

}

grammar.jj


// added global return variable declaration of the grammar return type

int jtbrt_bp_i;

...

// changed bnf production return type

bp_i bp_i() :

{

  ...

  // added variable returning the node

  bp_i jtbNode = null;

  ...

}

{

  ...

  // changed return statement into an assignment to the global variable

  { jtbrt_bp_i = tk.image.length(); }

  // added node creation & assignment to the node variable

  { jtbNode = new bp_i(n0); }

  // added return statement

  { return jtbNode; }

}



// changed bnf production return type

bp_i2 bp_i2() :

{

  ...

  // added variable returning the node

  bp_i2 jtbNode = null;

  ...

}

{

  ...

  // added node creation & assignment to the node variable

  { jtbNode = new bp_i2(n0); }

  // added return statement

  { return jtbNode; }

}

Node fields and sub-nodes

For the node fields creation and the tree building, in the BNFProduction code, JTB:

Example bp_v

grammar.jj


// changed bnf production return type

bp_v bp_v() :

{

  // aded variable for the field

  Token n0 = null;

  // added variable for the JavaCC token giving the JTB Token

  Token n1 = null;

  // added variable returning the node

  bp_v jtbNode = null;

}

{

  // splitted JavaCC token variable assignment, first part

  n1 = < ID >

  // added JTB Token creation (here a single cast due to how is defined
 the JavaCC class Token in JTB)

  { n0 = (Token) n1; }

  // splitted JavaCC token variable assignment, second part

  { tk = n1; }

  // changed return statement into an assignment to the global variable

  { jtbrt_bp_i = tk.image.length(); }

  // added node creation & assignment to the node variable

  { jtbNode = new bp_v(n0); }

  // added return statement

  { return jtbNode; }

}

Example bp_i / bp_i2 (int return type)

grammar.jj


// added global return variable declaration of the grammar return type

int jtbrt_bp_i;

...

// changed bnf production return type

bp_i bp_i() :

{

  // added variable for the field

  Token n0 = null;

  // variable for the JavaCC token giving the JTB Token

  Token n1 = null;

  // added variable returning the node

  bp_i jtbNode = null;

  // user variable unchanged

  Token tk = null;

}

{

  // splitted JavaCC token variable assignment, first part

  n1 = < ID >

  // added JTB Token creation (here a single cast due to how is defined
 the JavaCC class Token in JTB)

  { n0 = (Token) n1; }

  // splitted JavaCC token variable assignment, second part

  { tk = n1; }

  // changed return statement into initial return variable assignment

  { jtbrt_bp_i = tk.image.length(); }

  // added node creation & assignment to the node variable

  { jtbNode = new bp_i(n0); }

  // added return statement

  { return jtbNode; }

}



// changed bnf production return type

bp_i2 bp_i2() :

{

  // added variable for the field

  bp_i n0 = null;

  // added variable returning the node

  bp_i2 jtbNode = null;

  // user variable unchanged

  int i = 0;

}

{

  // added save of the returning variable (for recursion)

  { int oldJtbrt_bp_i_1 = jtbrt_bp_i; }

  // splitted JavaCC BNFProduction variable assignment; first part

  n0 = bp_i()

  // splitted JavaCC BNFProduction variable assignment; second part, getting
 the result through the global variable

  { i = jtbrt_bp_i; }

  // added restore of the returning variable

  { jtbrt_bp_i = oldJtbrt_bp_i_1; }

  // added node creation & assignment to the node variable

  { jtbNode = new bp_i2(n0); }

  // added return statement

  { return jtbNode; }

}

JTB adds statements each within java block, but JavaCC removes the enclosing braces, so there are no scope issues.

How are default visitors generated?

JTB allows to specify which (list of) visitors must be generated, and for each visitor its return type and its optional argument. See How to use Visitors.

JTB generates default visitors with the code that fully walks trough the tree, doing nothing else than this.
These default visitors can be sub-classed to perform more limited tree traversals and / or any logic on part or all of the nodes. These default visitors avoid typing the tree traversal code.

We have seen above that in generating the node classes JTB generates accept() methods on visitors that simply call the visit() methods of the visitors.

In a symetrical way, in the visitors JTB generates the visit() methods on the nodes that call the accept() methods on all of their fields (their child nodes), except on *node tokens, where the visit will stop (as there will be no child), and the default method does nothing.

For inner nodes, the user can ask JTB to inline or not the accept() call, that is to generate the traversal of the inner node a level down. We found that it is very convenient to code the logic at the caller level; coding the logic at the called level often requires to test which parent called the node. This saves the user typing the inner nodes traversal code in his visitor sub-classes, he just has to copy / paste the code from the default visitor and to modify it.

Example (int return type)

grammar.jtb


// BNFProduction with Token, NodeOptional, NodeListOptional, NodeChoice and inner NodeSequence

void bp_acc() :

{}

{

  < ID >

  [ "xyz" ]

  ( bp_i() )*

  ( bp_v() | ( bp_w() bp_x() ) )

}

DefpthFirstVoidVisitor.java (not inlined)


  /**

   * Visits a {@link bp_acc} node, whose children are the following :

   * 

   * f0 -> < ID >

   * f1 -> [ "xyz" ]

   * f2 -> ( bp_i() )*

   * f3 -> ( %0 bp_v()

   * .. .. | %1 ( #0 bp_w() #1 bp_x() ) )

   *

   * @param n - the node to visit

   */
</code/
  @Override

  public void visit(final bp_acc n) {

    // f0 -> < ID >

    // here the Token will accept this visitor

    n.f0.accept(this);

    // f1 -> [ "xyz" ]

    // here the NodeOptional will accept this visitor

    n.f1.accept(this);

    // f2 -> ( bp_i() )*

    // here the NodeListOptional will accept this visitor

    n.f2.accept(this);

    // f3 -> ( %0 bp_v()

    // .. .. | %1 ( #0 bp_w() #1 bp_x() ) )

    // here the NodeChoice will accept this visitor

    n.f3.accept(this);

  }

</pre>

**DefpthFirstVoidVisitor.java** (inlined)



  /**

   * Visits a {@link bp_acc} node, whose children are the following :

   * 

   * f0 -> < ID >

   * f1 -> [ "xyz" ]

   * f2 -> ( bp_i() )*

   * f3 -> ( %0 bp_v()

   * .. .. | %1 ( #0 bp_w() #1 bp_x() ) )

   *

   * @param n - the node to visit

   */
</code/
  @Override

  public void visit(final bp_acc n) {

    // f0 -> < ID >

    // here the Token will accept this visitor

    final Token n0 = n.f0;

    n0.accept(this);

    // f1 -> [ "xyz" ]

    // here the NodeOptional is inlined: if present, whatever is under

    // (here a Token) will accept the visitor

    final NodeOptional n1 = n.f1;

    if (n1.present()) {

      n1.accept(this);

    }

    // f2 -> ( bp_i() )*

    // here the NodeListOptional is inlined: if present, all elements of the list,

    // whatever they are (here BNFProductions), will accept the visitor

    final NodeListOptional n2 = n.f2;

    if (n2.present()) {

      for (int i = 0; i < n2.size(); i++) {

        final INode nloeai = n2.elementAt(i);

        nloeai.accept(this);

      }

    }

    // f3 -> ( %0 bp_v()

    // .. .. | | %1 ( #0 bp_w() #1 bp_x() ) )

    // here the NodeChoice is inlined: elements for each choice under

    // (here a BNFProduction for case 0 and the 2 elements - BNFProductions -

    // of the NodeSequence for case 1)
 will accept the visitor

    final NodeChoice n3 = n.f3;

    final NodeChoice nch = n3;

    final INode ich = nch.choice;

    switch (nch.which) {

      case 0:

        //%0 bp_v()

        ich.accept(this);

        break;

      case 1:

        //%1 ( #0 bp_w() #1 bp_x() )

        // here the NodeSequence is also inlined

        final NodeSequence seq = (NodeSequence) ich;

        //#0 bp_w()

        final INode nd = seq.elementAt(0);

        nd.accept(this);

        //#1 bp_x()

        final INode nd1 = seq.elementAt(1);

        nd1.accept(this);

        break;

      default:

        // should not occur !!!

        throw new ShouldNotOccurException(nch);

    }

  }

</pre>

Note that JTB outputs a class javadoc comment describing the grammar and the associated fields, and java
 single line comments for each set of code lines for the fields and inlined nodes.