When we talk about shift-reduce parsing, we are attempting to construct the parse tree from the leaves to the root. The best way to think about what is going on here is that given a string, w, we attempt to reduce this string to the start string.
[Aho] Consider the following grammar:
S -> aABe A -> Abc | b B -> dThe question arises, can we reduce the string abbcde to the start symbol S?
Algorithm:
1) Look for a substring in abbcde that matches the right side of any production. We find that b, b, and d in the string abbcde matches a substring in abbcde. We chose to replace the leftmost b in the string abbcde with the production A -> b giving us the string aAbcde.
2) Repeat step #1 with the new string aAbcde until the start symbol S is produced (accept) or we run out of matching possibilities (reject).
P#1: Complete the above algorithm until you derive S or reject.
P#2: Show S =>*rm abbcde.
Defn: A handle is a substring of a string that matches some production's right side such that a reduction to a nonterminal on the left can be done in one step along the reverse of a rightmost derivation.
P#3: Give an example of how this definition applies to the rightmost derivation created in P#2.
More formally:
Defn[Aho]: "A handle of a right-sentential form γ is a production A -> β and a position of γ where the string β may be found and replaced by A to produce the previous right-sentential form in the rightmost derivation of γ. That is, if S =>*rmαAw =>rm αβw, then A -> β in the position following α is a handle of αβw."
In our example above, A -> b is a handle of the string abbcde at position 2.
Let's examine Example 4.23 on p. 198.
Let's talk about and take a look at shift-reduce parsing with Example 4.24. on p. 199.
Finally, for certain CFGs, we can have unresolvable conflicts such as a shift/reduce conflict or a reduce/reduce conflict. Let's take a look at Example 4.25 on p. 201.
Reading: Please read operator-precedence parsing, pp. 203-215.