Sethi–Ullman algorithm: Difference between revisions

Revision as of 13:52, 16 November 2019

Revision as of 13:52, 16 November 2019

Line 8:

# Traverse the [[abstract syntax tree]] in pre- or postorder

## For every non-constant leaf node, assign a 1 (i.e. 1 register is needed to hold the variable/field/etc.) if it's is the left child of it'sits parent else assign a 0. For every constant leaf node (RHS of an operation – literals, values), assign a 0.

## For every non-leaf node ''n'', assign the number of registers needed to evaluate the respective subtrees of ''n''. If the number of registers needed in the left subtree (''l'') are not equal to the number of registers needed in the right subtree (''r''), the number of registers needed for the current node ''n'' is max(l, r). If ''l == r'', then the number of registers needed for the current node is ''r'' + 1.

# Code emission