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 		Open PDF File

Tree Parsing

This document describes a language for defining tree parsers. Tree parsers can be used to transform, interpret and print tree-structured data. They are particularly useful for problems in which the action at a node depends strongly on the context in which that node appears. Code selection is a common example of this kind of problem: The code selected for an operation is largely determined by that operation's context.

Consider the problem of selecting an instruction to implement an integer addition operation on a typical RISC machine. The machine has two integer add instructions, one taking two register operands and the other taking a register and a constant operand. Both of these instructions leave their result in a register. Load and store instructions also take a register and a constant operand, which are integers added to obtain the memory address. Integer addition is a commutative operation, so the instructions involving constant operands can be used regardless of which operand is constant. The code selector must perform a distinct action in each of the five possible situations resulting from these conditions.

The language described in this document allows the user to specify the possible situations and required actions in an intuitive way as a set of pattern/action rules: 

IntReg ::= Plus(IntReg,IntReg) :  IntRR_add
IntReg ::= Plus(IntReg,IntLit) :: IntRI_add
MemAdr ::= Plus(IntReg,IntLit) :: RI_address

Here the first rule specifies that one possible situation is to compute a value into an integer register by adding the contents of two integer registers. The required action in that situation is the IntRR_add action. Two situations are specified by the second rule. In one the left operand is in an integer register and the right operand is an integer constant, and in the other the operands are reversed. Both situations can be handled by the IntRI_add action, provided that the operands are always presented to it in the order stated (first the register operand, then the constant operand).

In addition to supplying the set of rules as a type-`tp' file, a user must make certain that implementations of the actions (like IntRR_add, IntRI_add and RI_address in the above example) are available. The actions might be written by the user or produced by other components of the system like PTG (see Top of Pattern-Based Text Generator).

Actions are arbitrary functions. They may or may not have results, and may or may not have side effects. The effect of the whole process is nothing more than the sum total of the effects of the actions.

To get the specified actions executed, the user must first call functions that are generated from the set of rules. These functions create a tree embodying the contextual relationships among the operators (like Plus above). Once the complete tree has been established, another generated function is called to parse it (e.g. to determine whether a given node is an IntReg or IntLit in the example above). Action routines are invoked as a side effect of the parse.