Utilities

« API | Utilities | St link »

Utilities

Yacc

// .. automodule:: yacc

Burg

Bottom up rewrite generator

This script takes as input a description of patterns and outputs a matcher class that can match trees given the patterns.

Patterns are specified as follows:

reg -> ADDI32(reg, reg) 2 (. add NT0 NT1 .)
reg -> MULI32(reg, reg) 3 (. .)

or a multiply add:

reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .)

The general specification pattern is:

[result] -> [tree] [cost] [template code]

Trees

A tree is described using parenthesis notation. For example a node X with three child nodes is described as:

X(a, b, b)

Trees can be nested:

X(Y(a, a), a)

The ‘a’ in the example above indicates an open connection to a next tree pattern.

In the example above ‘reg’ is a non-terminal. ADDI32 is a terminal. non-terminals cannot have child nodes. A special case occurs in this case:

reg -> rc

where ‘rc’ is a non-terminal. This is an example of a chain rule. Chain rules can be used to allow several variants of non-terminals.

The generated matcher uses dynamic programming to find the best match of the tree. This strategy consists of two steps:

  • label: During this phase the given tree is traversed in a bottom up way. each node is labelled with a possible matching rule and the corresponding cost.
  • select: In this step, the tree is traversed again, selecting at each point the cheapest way to get to the goal.