CS 1104 Introduction to Computer Science
COMPILERS AND TRANSLATORS
BOTTOM-UP (REDUCTIVE) ANALYSIS
Obviously each of the symbols w, x, and z are right-hand-sides of the rule for <factor>, so we can "reduce" the string to:
Now we can notice that + only occurs in one rule:
and * only occurs in
From these we can produce a partial syntactic tree:
We must now look for other links that can be matched. One possibility is that the <factor> in the right-hand partial sub-tree is the same element as occurs below it. Thus these two can merge. The language_symbol <term> and <factor> can be linked directly to each other in both the sub-trees.
<expr> is linked to a rule that contains * through two transformations through <term> and then to <factor> * <term>. Hence we may connect the right-hand-side of the leftmost sub-tree to the other subtree.
Finally the top of the tree may be linked to the "root" language-symbol <expr> through the first production rule:
Last updated 00/03/30
© J.A.N. Lee, 2000.