Eli   Documents
Eli: Translator Construction Made Easy

General Information

o Eli: Translator Construction Made Easy
o Global Index
o Frequently Asked Questions
o Typical Eli Usage Errors

Tutorials

o Quick Reference Card
o Guide For new Eli Users
o Release Notes of Eli
o Tutorial on Name Analysis
o Tutorial on Scope Graphs
o Tutorial on Type Analysis
o Typical Eli Usage Errors

Reference Manuals

o User Interface
o Eli products and parameters
o LIDO Reference Manual
o Typical Eli Usage Errors

Libraries

o Eli library routines
o Specification Module Library

Translation Tasks

o Lexical analysis specification
o Syntactic Analysis Manual
o Computation in Trees

Tools

o LIGA Control Language
o Debugging Information for LIDO
o Graphical ORder TOol

o FunnelWeb User's Manual

o Pattern-based Text Generator
o Property Definition Language
o Operator Identification Language
o Tree Grammar Specification Language
o Command Line Processing
o COLA Options Reference Manual

o Generating Unparsing Code

o Monitoring a Processor's Execution

Administration

o System Administration Guide
Mail Home

Tree Parsing

Previous Chapter Next Chapter Table of Contents

Summary of the Specification Language

The phrase structure of the specification language is described by the following ambiguous grammar: 

Source: (Include / Declaration / Rule)+ .

Declaration: (Nonterm // ',') ':' Type ';' .
Nonterm: Identifier .
Type: Identifier .

Rule:
  Nonterm '::=' Node    (':' / '::') Action ['COST' Integer] ';' /
  Nonterm '::=' Nonterm  ':'         Action ['COST' Integer] ';' /
  Nonterm '::=' Fragment ':'         Action ['COST' Integer] ';' .
Action: Identifier .

Node:
  Terminal /
  Terminal '(' Nonterm [',' Nonterm] ')' /
  Terminal '(' (Type // ',') ')' /
  Terminal '(' Nonterm [',' Nonterm] ',' (Type // ',') ')' .
Terminal: Identifier .

Fragment: Terminal '(' Child [',' Child] ')' .
Child: Nonterm / Fragment .

Declarations and rules are the main components of a specification. Includes are simply names of files that are needed to define the identifiers representing types and actions.

An Include is a sequence of characters delimited by quotation marks ("). It is used unchanged in an #include directive output by the specification language translator. Only one #include directive is output for each distinct Include, regardless of how many times that Include appears in the specification.

An Identifier is a sequence of letters and digits, the first of which is a letter. As in C, the underscore (_) is considered a letter.

Declarations

Each nonterminal symbol must be declared, stating the type of the value associated with it: 

Declaration: (Nonterm // ',') ':' Type ';' .
Nonterm: Identifier .
Type: Identifier .

Types are always represented by identifiers. If the type is a C basic type, no further declaration is necessary. Other types must be defined by a typedef construct that appears in some file named by an Include (see Summary of the Specification Language).

Here is a set of declarations that is appropriate for the examples given earlier in this document: 

IntLit: int;
IntReg, FltReg: reg;  "mydefs.h"

Because int is a C basic type, no further information is necessary. reg, on the other hand, is declared by a typedef construct that appears in file `mydefs.h'. Thus the Include `"mydefs.h"' is used to provide access to that information.

Rules

As discussed earlier, there are three kinds of rules: node rules (see Rules Describing Tree Nodes), chain rules (see Chain Rules), and fragment rules (see Rules Describing Tree Fragments): 

Rule:
  Nonterm '::=' Node    (':' / '::') Action ['COST' Integer] ';' /
  Nonterm '::=' Nonterm  ':'         Action ['COST' Integer] ';' /
  Nonterm '::=' Fragment ':'         Action ['COST' Integer] ';' .
Action: Identifier .

Each rule has an associated action and an optional cost (which defaults to 1 if not specified). The action is defined by an identifier, which must be defined in the file described by one of the Include components of the specification. That definition might be an extern statement or a #define directive (see Implementing Actions). The signature of the action is determined by the type of the left-hand-side Nonterm and the right-hand side as discussed above (see Actions and Values).

A node rule describes a single, possibly decorated, node of the tree being parsed (see Rules Describing Tree Nodes): 

Node:
  Terminal /
  Terminal '(' Nonterm [',' Nonterm] ')' /
  Terminal '(' (Type // ',') ')' /
  Terminal '(' Nonterm [',' Nonterm] ',' (Type // ',') ')' .
Terminal: Identifier .

Terminal is the symbol of the ranked alphabet that is represented by the node. The Node must have k Nonterm children if Terminal has arity k.

Each Terminal is also associated with a specific set (possibly empty) of attributes. There is no limit to the number or types of the attributes decorating a node. Each attribute is denoted by a Type, which must be either a C basic type or an identifier defined by a typedef construct that appears in some file named by an Include (see Summary of the Specification Language).

The :: marker distinguishes a commutative node (see Commutative Actions). This node must have two children, and those children must be distinct nonterminals. A commutative node rule may have arbitrary decorations.

A fragment rule describes a fragment consisting of two or more adjacent nodes: 

Fragment: Terminal '(' Child [',' Child] ')' .
Child: Nonterm / Fragment .

Nodes participating in fragments may not be decorated. There is no limit on the size of a fragment.

Previous Chapter Next Chapter Table of Contents