Goal:Map subtrees to machine instructions or address modes using a tree grammar called a BURG or a bottom up rewrite generator. The parse tree is usually called a tree cover in this realm. BURM (bottom up rewrite machine) is the name of the tree parser. Tree grammars are usually ambiguous and we will prefer the tree cover with minimal cost. To do that, tree grammar productions have associated costs either integer constants or computations. The idea is that the same tree structure can be matched by an infinite number of grammars. The grammar reflects the instructions and addressing modes of the target processor. Rules are either single nodes, single subtrees, or a chain rule that simply references another rule. Rules look like:

const : INT 0 ; // match an INT node; cost is zero

If the cost is zero, it can be omitted.

Producing the minimal cover requires two passes: a labeling pass and a reducing pass:

void label(tree);
int reduce(tree, nonterminal);

The labeler computes all non-terminals that match for a given node and records the best match for each non-terminal; that is, it records the production with a minimal cost for each non-terminal at a given node. The reducer picks the best match for each goal non-terminal at a particular node. The list of productions applied tells us the list of instructions to generate as we walk during the reducer. The label or works bottom-up and left to right while the reducer works top down and left to right.

The bottom up label or does not know which matches were needed about it so it records all possible matches; well, it matches only the best production/rule for a given non-terminal if multiple match. The top-down reducer then selects the appropriate production to apply to get the minimum cost cover.

Consider some simple patterns without costs.

stmt : ^('=' addr reg) ;
addr : ID ;
addr : ^('+' addr const) ;
indirect : ^('*' addr );
reg : const ;
const : INT ;

Consider tree for x=4;: (= x 4).

Consider tree for p[4] = 5: (= ^(+ ^(* p) 4) 5). Label the tree with rules that match for each node.

Now let us do the costs:

(1)  const  :   INT ;
(2)  addr   :   ID ;
(3)  addr   :   ^('+' reg const) ;
(4)  rc     :   const ;
(5)  rc     :   reg ;
(6)  reg    :   ^('+' reg rc)               1 ;
(7)  reg    :   ^(CVCI ^('*' addr)) addr    1 ;
(8)  reg    :   addr                        1 ;
(9)  stmt   :   ^('=' addr reg)             1 ;

Input i = c + 4; where c is a char and i is an int.

Label nodes with (production, cost, nonterminal) or just (cost, production).