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
The required action in that situation is the
In addition to supplying the set of rules as a type-`tp' file,
a user must make certain that implementations of the actions
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