CS 1104 Introduction to Computer Science

COMPILERS AND TRANSLATORS

BOTTOM-UP (REDUCTIVE) ANALYSIS

Consider:

w + x * z

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:

<factor> + <factor> * <factor>

Now we can notice that + only occurs in one rule:

<expr> ::= <term> + <expr>

and * only occurs in

<factor> * <term>

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:

[TOC]

Last updated 00/03/30
© J.A.N. Lee, 2000.