Bottom-Up Parsing

4.5 Bottom-up Parsing

Our text, p.223, give us "A bottom-up parse corresponds to the construction of a parse tree for an input string beginning at the leaves (the bottom) and working up towards the root (the top)." Fig 4.25 illustrates this for the token stream id * id.

4.5.1 Reductions (Fig 4.25)

The key decisions during bottom-up parsing are about when to reduce and about what production to apply, as the parse proceeds. Using our expression grammar (from Monday), we have a sequence of strings

id * id, F * id, T * id, T * F, T, E

which form the rotos of the subtrees in Fig 4.25.

By definition, a reduction is the reverse of a step in a derivatiion (recall that in a derivation, a nonterminal in a sentential form is replaced by the body of one of its productions). The goals of bottom-up parsing is to construct a derivation in revese order. The following derivation corresponds to the parse in Fig. 4.25.

E ⇒ T ⇒ T * F ⇒ T * id ⇒ F * id ⇒ id * id

4.5.2 Handle Pruning

Bottom-up parsing during a left-to-right scan of the input constructs a right-most derivation in reverse. Informally, a "handle" is a subtring that matches the body of a production (LHS), and whose reduction represents one step along the reverse of a rightmost derivation.

Fig 4.26 Handles during a parse of id₁ * id₂

Formally, if S ⇒_rm^* βAω ⇒_rm αβω, as in Fig 4.27, then production A → β in the position following α is a handle of αβω. Alternatively ....

4.5.3 Shift-reduce Parsing

This form of parsing uses a stack to hold grammar symbols and an input buffer to hold the rest of the string to be parsed.