lecture 2:Compiler II

Shift-Reduce Parsing
In this section, we discuss a bottom-up style of parsing called shift-reduce
parsing. This parsing method is bottom-up because it attempts to construct a
parse tree for an input string beginning at the leaves (the bottom) and
working up towards the root. We can think of this process as one of
"reducing" a string W to the start symbol of a grammar. At each step a string
matching the right side of the production is replaced by the symbol on the
left.
For example, consider the grammar
S a A c B e
A Ab | b
B d
and the string "abbcde". We want to reduce this string to S. We scan this
string looking for substring that matches the right side of any production.
The substring b and d qualify. Let us choose the left most b and replace it by
A the left side of the production A b. We continue according to this
step:-
abbcde aAbcde aAcde aAcBe S
Each replacement of the right side of a production by the left side in the
process above is called "reduction". Thus, by a sequence of four reductions
we were able to reduce abbcde to S. These reductions traced out a right most
derivation in reverse
Informally, a substring which is the right side of a production such that
replacement of that substring by the production left side leads eventually to a
reduction to the start symbol, by a reverse of a rightmost derivation is called
a "handle". The process of bottom-up parsing may be viewed as one of
finding and reducing handles.