The default class used to represent nodes is antlr.CommonAST. It extends abstract class antlr.BaseAST. The AST is a Child-Sibling tree (see BaseAST.java) A node has only one child, and the other children are linked beetwin them. So a node actually contains a linked list of children. Walking/modifying an AST with custom code requires that you know what you are doing, so we'll just introduce the interfaces of the functions you will need. BaseAST's interface provides some useful functions to walk/check the tree and use pattern matching:

    /** Is node t equal to this in terms of token type and text? */
    public boolean equals(AST t)

    /** Is t an exact structural and equals() match of this tree.  The
    *  'this' reference is considered the start of a sibling list.
    */
    public boolean equalsList(AST t)

    /** Is 'sub' a subtree of this list?
     *  The siblings of the root are NOT ignored.
     */
    public boolean equalsListPartial(AST sub)

    /** Is tree rooted at 'this' equal to 't'?  The siblings
     *  of 'this' are ignored.
     */
    public boolean equalsTree(AST t)

    /** Is 't' a subtree of the tree rooted at 'this'?  The siblings
     *  of 'this' are ignored. 
     */
    public boolean equalsTreePartial(AST sub)

    /** Walk the tree looking for all exact subtree matches.  Return
     *  an ASTEnumerator that lets the caller walk the list
     *  of subtree roots found herein.
     */
    public ASTEnumeration findAll(AST target)

    /** Walk the tree looking for all subtrees.  Return
     *  an ASTEnumerator that lets the caller walk the list
     *  of subtree roots found herein.
     */
    public ASTEnumeration findAllPartial(AST sub)

    /** Get the first child of this node; null if not children */
    public AST getFirstChild()

    /** Get the next sibling in line after this one */
    public AST getNextSibling() 

    /** Get the token text for this node */
    public String getText()

    /** Get the token type for this node */
    public int getType()

and other ones to modify the tree:

    /**Add a node to the end of the child list for this node */
    public void addChild(AST node)

    public void setFirstChild(AST c)

    public void setNextSibling(AST n)

    /** Set the token text for this node */
    public void setText(String text)

    /** Set the token type for this node */
    public void setType(int ttype)

To create a node:

    public CommonAST()
    
    public CommonAST(Token tok)

    public void initialize(Token tok) {

    public void initialize(int t, String txt)

    public void initialize(AST t)

NOTE: token types are represented with integers. You might want to implement the interface ExpressParserTokenTypes to use token names in your code.

In the future, CommonASTWithHiddenTokens might be used instead of CommonAST. It would allow to store hidden tokens (see Section 1.2 about filtering) in the AST nodes. See ANTLR documentation about token stream splitting.

First of all, we use semantic predicates to force the parser to use modified rules during the first pass. So, lines beginning with

{ isFirst }?

During the first pass, we want to record ids with their types. Sometimes you may have ids with the same name, because Express uses scoping. It means that you can declare an id only once in a block (scope) but you can have ids with the same name in different scopes. It's basically the same as in C, for example you can write:

int a;

{
    int a;
}

but not:

int a;
int a;

So, we need to be able to record different ids with the same name, and attach information about the scopes they are declared in. We also need to be able to detect multiple definition errors (when ids with the same name are declared in the same scope).

To achieve that, we decided to use a scope tree. It means that a tree of objects representing scopes is built during the first pass. Each scope object contains a hashtable (with the id name as the key, and its type as the value) to record the ids. During the first pass, at any time there is a current scope (currentScope variable) that is updated every time we enter a new scope or every time we leave a scope (then the current scope is the scope containing the one we left, its parent). When an id is found, it is recorded in the current scope's hashtable. The type of the id is stored as an integer, according to the definition of the tokentypes in the ExpressParserTokenTypes.java generated interface. So, in the express.g file, every rule where a new scope starts contains a call to newScope() and every rule (sometimes it is the same) where a scope ends contains a call to upScope(). According to section 10 of the ISO 10303-11:1994 document, Express items defining a scope are: alias statement, entity, function, procedure, query expression, repeat statement, rule, schema and type.

>So how are we able to retrieve such information during the second pass ? First, when entering a new scope we need to get the scope object that was created when entering the same scope during the first pass. In order to do so, additional information is recorded during the first pass: the order of the scope objects creations. It means that every scope object has a link to the next scope object created. So we use another variable: lastCreatedScope, which is not equivalent to currentScope. Every time a new scope is entered during the second pass, currentScope is updated with the scope that was created just after lastCreatedScope. Then lastCreatedScope is updated (with the new current scope). When leaving a scope, currentScope becomes the parent scope of itself, but this parent scope was created before, so currentScope becomes different from lastCreatedScope. It may sound a little bit unclear, but here is a drawing that will explain better the way it works.

Consider the rules function_decl and function_head:

function_decl
             :  function_head ( algorithm_head)?  stmt  (  stmt  )*
                "end_function"!  SEMI! { upScope(); }

function_head
             : "function"!  function_id { newScope(); } (  LPAREN!
               formal_parameter  (  SEMI!  formal_parameter  )*
               RPAREN!  )?  COLON! parameter_type  SEMI! 

During the first pass, newScope() creates a new Scope object which parent is currentScope, and then attaches the newly created scope to the last created scope:

public void newScope1() {
                /* creates a new Scope when entering a rule defining
                a scope in the grammar. */
                Scope ns;

                ns = new Scope(currentScope);
                currentScope=ns;
                lastCreatedScope.setNext(ns);
                lastCreatedScope=ns;
        }

And during the second pass, it retrieves this scope from the last created scope:

public void newScope2() {
                /* retrieve the scope created in the first pass when
                entering the same rule. 
                See comments in the lexer's IDENT rule definition */

                currentScope=lastCreatedScope.next;
                lastCreatedScope=currentScope;
        }

In order for this to work, the rootScope (the scope containing every other scope) has to be the same in the first and the second pass, so after the first pass is completed, rootScope is passed to the second pass parser thanks to the setRootScope() method.

Note that currentScope is not always the same as lastCreatedScope, because when you leave a scope, as in the function_decl rule, upScope() is called:

 public void upScope() {
                /* when exiting a scope */
                currentScope=currentScope.parent;
        }

currentScope.parent was created before currentScope, so currentScope changes but not lastCreatedScope.

The recording is very simple, as shown in the function_id rule restricted to its first pass part:

function_id
             : { isFirst }? id:IDENT { addId(id.getText(),FUNCTION_IDENT); }

addId just adds the id name (id.getText()) and its type (FUNCTION_IDENT) to the id table of currentScope. If the id already exists, a double definition warning is displayed (see Scope.java source code)

The retrieval part (second pass) occurs in the lexer. Instead of just producing IDENT tokens for each identifier, the lexer runs a search algorithm through the scope tree, and then produces a token with a specific type (FUNCTION_IDENT for example) The algorithm searchs for the id in the current scope, if it doesn't exist then in the parent scope, and so on. If it doesn't find anything in the end (the rootScope) then it returns a simple IDENT token.

The ANTLR parser code seems to bufferize tokens, and it can be a problem because of the fact that in the second pass, id search is performed by the lexer. The lexer uses currentScope to perform the search, and currentScope is updated depending on the tokens read by the parser. Let's take an example to show what is wrong:

alias_stmt
    : { newScope(); } "alias"! variable_id "for"! general_ref (
      qualifier )* SEMI! stmt ( stmt )* "end_alias"! { upScope(); } SEMI!

Let's parse this piece of code:

FUNCTION a(b : c) : d;
    ALIAS x FOR b;
      [...]
    END_ALIAS;
END_FUNCTION;

We are doing the second pass. Suppose that the parser always has a buffer containing the four next tokens. Then when dealing with the last colon character of the function declaration, the d id, the semi-and colon the ALIAS literal have been read and tokenized by the lexer. So, when dealing with the d id, the x id has been read by the lexer. But we are not in the alias_stmt rule yet, so the newScope() call didn't occur, so the current scope is still the scope of the function. When the lexer is looking for the id x, it believes the current scope is the function's one, but x was recorded in alias' scope, so the lexer is not able to find x, an error occurs.

This problem occurs with rules defining scopes and where an id is declared in this same scope. These rules are: repeat_stmt, alias_stmt, query_expression, and rule_head. For example, the name of a function is recorded in the outer scope of the function, so there is no problem here, but the variable name of a query expression is recorded in the inner scope of the query expression, so there is the same problem as in the alias example. To fix the problem, we update the currentScope in the lexer instead of doing it in the parser's rule. So, when dealing with an identifier (literals are identifiers for the lexer) the string is compared to the ALIAS, REPEAT, QUERY and RULE keywords, and if it is one of those, a newScope() call is performed.

That's why there is no newScope() call in these rules in the parser.

Enumeration ids are different from other ids in two ways. First, they can be duplicated, that is to say you can have several enumeration ids with the same name in the same scope. That's because you can select them by placing the name of their enumeration type before them. The second thing, enumeration ids are not recorded in the scope they are declared in, but in its outer scope. Example:

TYPE a = ENUMERATION OF (u, v, w, x);
END_TYPE;

TYPE b = ENUMERATION OF (u, f, g, h);
END_TYPE;

For enumeration id u, u is recorded twice in the same scope (because the scope where u, v, w, x are visible is not the scope of type a, but the outer scope, the scope where types a and b are declared in).

In order to do that, when dealing with a enumeration id, the addId function of Scope.java then calls a special function of the parent scope. This function doesn't check double definition.

Entities can have supertypes, so when in an entity declaration (in the where clause for example) you can use references to attributes of supertypes of the current entity. You can use attributes defined in the supertype of the supertype, and so on. So, during the second pass and when resolving an id in an entity declaration we also have to search the inheritance tree in addition to search the scope tree. In order to search the inheritance tree, we have to build it. We use the scope tree structure by recording some additional information when parsing an entity declaration. Three pieces of information are recorded. First when parsing an entity declaration, we set a value to specify that the current scope is a scope defined by an entity. Then we tell the outerscope that it contains a scope defined by an entity, and the name of the entity is given to the outerscope. Finally, when in a subtype_declaration, we record the names of the supertypes of the entity in its scope.

see newEntityScope() and addSuper() functions in express.g.

How information is stored ? Every scope has a boolean value to tell whether it is an entity scope. Then the scopes where an entity can be declared (schema, function, procedure, rule) contain a hashtable for the inside entity scopes. The key is the name of the entity declared inside this scope, and the value is a reference to the scope defined by the entity. A scope defined by an entity contains a vector that contains the names of the supertypes of the entity.

How do we use this information ? When looking for an id inside an entity declaration, we first search the inheritance tree. So, we look in the id table of the current entity, then we have to search the supertype entities. We use the vector containing the names of the supertypes. For each name, we search in the scope tree (the supertype must be declared in a scope higher than the current scope) until we find an entity with the good name. To perform this search, we use the entities hashtable described earlier. So, when the entity is found, we get its scope. So we can look for our id in this scope's id table. We do that for every supertype entity, and for every supertype of the supertype entities and so on until we find the id. If the id wasn't found, then we perform the usual scope tree search algorithm.

So, as a conclusion, we first search the whole inheritance tree (the entities are resolved on the fly) and then we search the scope tree.

It is surely the most complicated part of the parser.

In the attribute_qualifier rule, we have to identify an attribute_ref, i.e. an attribute id (ATTRIBUTE_IDENT). In order to find this id, we would have to search from the target of the qualifier, but the target could be anything, an entity_reference, a select type, an array with an index_qualifier. It would be way too hard to try to get the actual type of the target and then get its scope. But why would we need this since thanks to the dot we are sure that we are in an attribute_qualifier rule ? So we do know the identifier is an ATTRIBUTE_IDENT (well if it is not, the code is not correct, but typed ids are not used to check correctness, they are used to help rules reduction), we don't need to search its type. That's why the global_ident pseudo rule was introduced. We use it to say: whatever the id type, we don't care. We use it the same way in the inverse_attr rule.

When an id x is declared in a scope A and then an id with the same name is declared in a scope B included in A, then the second x will hide the first. In the scope B, only the x declared in B is visible. This is not alway true, there is an exception where x declared in A is visible in B even if a new x was declared in B. This exception is described in section 10.2.2 of the ISO 10303-11:1994 document. In our example, if x is an entity or a defined data type identifier, and if:

or

Then both x declared in A and x declared in B are visible in B.

So this text is valid Express:

ENTITY e1;
END_ENTITY;

ENTITY e2;
    e1 : e1;
END_ENTITY;

In this case, the id search algorithm in e2 returns a ENTITY_ATTR_IDENT token. It means that e1 is visible as an attribute or as an entity. So the grammar uses these tokens where they may appear. The TYPE_ATTR_IDENT works the same way for type ids. For the second case (parameters and variables) we use ENTITY_VAR_IDENT, TYPE_VAR_IDENT, ENTITY_PARAM_IDENT and TYPE_PARAM_IDENT. Sometimes, using such tokens leads to ambiguous situations. For example, when reading a TYPE_ATTR_IDENT token, we don't know if it is a TYPE_IDENT or an ATTRIBUTE_IDENT, but sometimes we need to know. The solution is described in Section 2.3.4.6.

Sometimes even with typed id tokens, it is still not possible to break an ambiguous situation between two rules. In these cases, we use the parser's lookahead capability and semantic predicates. Lookahead means we look at the tokens following the current token to make a decision. Example in simple_factor:

 |  { LA(2)==LPAREN }? entity_constructor
 |  { LA(1)==ENUMERATION_IDENT||LA(3)==ENUMERATION_IDENT }? enumeration_reference
 |  (  (  unary_op  )?  (  LPAREN!  expression  RPAREN!  |  primary )  )
 ;

entity_constructor develops as

entity_ref '(' ( expression ( expression )* )? ')'

qualifiable_factor ( qualifier )*

So, reading an ENTITY_IDENT, how do we know whether it is a entity_constructor or a population ? For tree construction matters, we cannot factor these rules, so we just look if there is a ( character just after the ENTITY_IDENT. Thus, we are able to decide between entity_constructor and population.

It works the same for enumeration_reference, but the reason is a little bit more complicated: because of the exception 10.2.2 (see Section 2.3.4.5) we may read a TYPE_ATTR_IDENT token, so since two identifiers with the same name are visible, it may be a TYPE_IDENT or a ATTRIBUTE_IDENT but we don't know which one. So, in case it is a TYPE_IDENT it may be an enumeration_reference:

enumeration_reference -> ( type_ref '.' )? enumeration_ref

in case it is a ATTRIBUTE_IDENT, it may be a

primary -> qualifiable_factor ( qualifier )*

qualifiable_factor -> attribute_ref

qualifier -> attribute_qualifier -> attribute_ref

So, is it type_ref.enumeration_ref or attribute_ref.attribute_ref ? in this case, the only way to know is to check the token after the dot, i.e. the third, LA(3). If LA(3) is a ENUMERATION_IDENT then the answer is enumeration_reference, if it is not, the answer is primary.

If the semantic predicate is not true, then the rule is skipped. So, the obvious case where an ENUMERATION_IDENT leads to the enumeration_reference rule needs to be considered in the semantic predicate, that's why there is a LA(1) condition.

Conclusion:

Such mechanisms are also used in domain_rule.

This parser is not able to read multiple schemas in multiple files at this time, but since the syntax allows to declare multiple schemas in a single file, it supports REFERENCE and USE clauses in this case.

Basically, when an id is referenced or used in a schema, it is added to the root scope of the referencing schema. When the id is renamed, then the new name is added but not the former one. If no id is specified in a REFERENCE clause, all constant, entity, function, procedure and type ids of the referenced schema(s) are added to the referencing schema's root scope. If no id is specified in a USE clause, then all entity and type ids of the used schema(s) are added to the using schema's root scope.

In order to achieve that, we once again record new information in the scope tree, and we use a new object, ExternalId, to store information. Information is stored in the Scope object representing a scope defined by a schema. What is stored is:

Between the first and the second pass, schema names are resolved, ids are added. See the processExternals() function in Scope.java.

Scopes defined by schemas also feature functions to get all referencable or usable ids in the current schema. See getReferencedExternals() and getUsedExternals() functions. The ids are returned as a Vector of ExternalId objects, these objects are just id/type pairs. These functions are used when an entire schema is referenced or used (without specifying the ids).

NOTE: if a stronger mechanism to handle REFERENCE or USE clauses is implemented (such as a mechanism capable of accessing a schema database or of parsing other files to get the ids) then the current mechanism should be removed.