General Information

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

Tutorials

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

Reference Manuals

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

Libraries

	Eli library routines
	Specification Module Library

Translation Tasks

	Lexical analysis specification
	Syntactic Analysis Manual
	Computation in Trees

Tools

	LIGA Control Language
	Debugging Information for LIDO
	Graphical ORder TOol

FunnelWeb User's Manual

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

Generating Unparsing Code

Monitoring a Processor's Execution

Administration

System Administration Guide

Tree Parsing

Actions Carried Out During Parsing

Each rule has an associated action, written as an identifier:

N0 ::= s(Ni,aj)    : Action1
N0 ::= N1          : Action2
N0 ::= s(t(Ni),Nj) : Action3

The action associated with a rule is carried out each time the rule is used in a derivation. Each rule may be associated with a distinct action, or a single action may be associated with several rules.

Actions and Values

The action carried out for each use of a rule in a derivation is a function application. The action identifier is the name of the function, and the arguments to which it is applied are the values of the nonterminals and attributes appearing on the right-hand side of the pattern. These values are taken in order from left to right. The result of the function becomes the value of the nonterminal appearing on the left-hand side of the pattern.

For example, consider one of the rules of the specification introduced above (see Rules Describing Tree Nodes), augmented by an action called IntR_loadconst:

IntReg ::= IntegerVal(int) : IntR_loadconst

The types of the attribute values are stated explicitly in the rules. A type is also associated with each nonterminal by means of a declaration (see Summary of the Specification Language). For example, the type associated with the nonterminal IntReg might be structure of type reg defined as follows:

typedef struct { int register; PTGNode code; } reg;

In this case, execution of IntR_loadconst would allocate a register and create a PTG node representing the assembly language instruction loading the integer constant specified by the integer-valued attribute of the leaf into that register. It would return a type-reg structure containing that information. This structure would then become the value of the IntReg nonterminal.

Here's another example of a rule, this time augmented by an action called IntRR_sub:

IntReg ::= Minus(IntReg,IntReg) : IntRR_sub

Execution of IntRR_sub might allocate a register to hold the result of the subtraction and create a PTG node representing the sequence consisting of the PTG nodes passed to it as operands followed by the assembly language instruction that computes the difference of two integer values in registers and leaves the result in a register. IntRR_sub would return a type-reg structure, which would become the value of the IntReg nonterminal on the left-hand side of the rule.

Each nonterminal is associated with a function whose name is TP_ followed by the name of the nonterminal. This function takes as its only argument a tree (of type TPNode, see Node Construction Functions), and returns a value of the type associated with the nonterminal. Whenever one of these functions is applied to the root of a tree, it parses that tree. The parse finds the cheapest derivation of the function's nonterminal at the root of the tree. All of the actions implied by the derivation are executed, and the result of the function is the result delivered by the action executed at the root of the tree. The only guarantee one can make about the order in which the actions are executed is that it respects the data flow constraints implied by the function applications.

A specification with all of the rules described so far has only two nonterminals (IntReg and FltReg). The translator will generate two parsing functions that can be applied to the root of a tree:

: reg TP_IntReg (TPNode tree)

A derivation for the tree rooted in tree in which the root is interpreted as an IntReg will be sought. If such a derivation is possible, the actions associated with the steps for the cheapest will be executed. The result of the action associated with the derivation step at the root will be returned. Otherwise the program will terminate abnormally.

: reg TP_FltReg (TPNode tree)

A derivation for the tree rooted in tree in which the root is interpreted as a FltReg will be sought. If such a derivation is possible, the actions associated with the steps for the cheapest will be executed. The result of the action associated with the derivation step at the root will be returned. Otherwise the program will terminate abnormally.

The program will terminate abnormally when a requested derivation is not possible. This condition always arises from a design fault; either the patterns are incomplete, or the tree to be parsed is malformed.

Implementing Actions

An action is a function application, and the name of the action is the function to be invoked. The rule with which the action is associated determines the signature of the function: Recall that the arguments of the function are the nonterminals and attributes appearing on the right-hand side of the associated rule, in order from left to right. The result of the function becomes the value of the nonterminal appearing on the left-hand side of the associated rule. Each nonterminal and attribute has a fixed type.

Function application can be implemented either by calling a macro or by invoking a routine. If the action requires a routine invocation, and the signature of the routine to be invoked matches the signature determined by the rule, then the routine name can be used directly as the action. Often, however, there is a mismatch between the signatures. In that case, the action can be made the name of a macro that rearranges arguments, inserts constants, or does whatever else is needed to correct the mismatch.

Commutative Actions

Many computers have instruction sets that are asymmetric in their treatment of operands. For example, a machine with two-operand instructions may allow only the second of these operands to be a literal value. If two values in registers are being added, the "add register" instruction is used, but if a literal value were being added to a value in a register the "add immediate" instruction would be necessary. One rule characterizing an integer addition operation for such a machine, with an action to generate the "add immediate" instruction, might be the following:

IntReg ::= Plus(IntReg,IntLit) : IntRI_add

Notice that the children of the Plus node in this rule have different interpretations; this rule cannot be used in a derivation that interprets the left child of the Plus node as an IntLit and the right child as an IntReg.

Because addition is commutative, however, it is possible to interchange the children of the Plus node without changing the resulting value. Therefore if a derivation interprets the left child of the Plus node as an IntLit and the right child as an IntReg, the tree parser should be able to simply invoke the IntRI_add action with the two operands reversed.

This possibility is indicated by using :: instead of : between the rule and its associated action:

IntReg ::= Plus(IntReg,IntLit) :: IntRI_add