2. The Internal Representation of a Grammar

  1. 2.1. The GrammarT Type and Structure
  2. 2.2. The TableT Type
  3. 2.3. Internal Representation of Actions
  4. 2.4. Internal Representation of Rules
  5. 2.5. Internal Representation of Non-Locals

We present the internal representation in a top down structure. Many functions are provided that hides the implementation; all access to these structures is performed through their respective APIs. Those interfaces are not documented here; rather, a brief functional tour of content is given instead.

The implementation details behind the interfaces are documented in their respective datastructures; see the various header files for details per-field. Virtually all of these are stored in the adt directory.

2.1. The GrammarT Type and Structure

sid stores grammars in a structure called GrammarT.

It contains a TableT hash map containing elements of type EntryT. We'll talk about EntryT later. For the moment remember that an EntryT is a structure that can be used to store either an action, a rule, a type, a terminal, or a nonlocal.

Please note that in the code terminals are referred as basics in the code, probably for historical reasons.

2.2. The TableT Type

It holds most of the information about a grammar, rules, actions, terminals, non-local names, types and local names along with their scopes.

Its definition is very simple, containing only a hash table of EntryT.

2.3. Internal Representation of Actions

Actions are stored in a ActionT. More exactly, they are stored in an EntryT whose union member is an ActionT.

2.4. Internal Representation of Rules

Look at an extremely simple sid rule:

basic-arithmetic = {
        number;plus;number;
    ||  number;minus;number;
};

It has two alternatives, each one holding three items. Alternatives have their special type: AltT.

It also contains a list of ItemT. In our previous example, the list of items of the first alternate would be number, plus and number.

An ItemT is therefore a rule, an action call, a terminal or TODO(rename, name) already declared in table.

And now the RuleT type; this structure is very long.

2.5. Internal Representation of Non-Locals

A non-local is an EntryT whose type is ET_NON_LOCAL and whose member u is also an EntryT*: the target of this pointer is a type giving the type of the non-local. The key member is of course the name of the non-local but also contains its scope. IE, non-locals are accessible to all rules contained in the rule for which the non-local is defined. The scope is indicated in the key string by outer-enclosing-rule::inner-enclosing-rule::name-of-non-local.