# CS606 - Compiler Construction - Lecture Handout 20

User Rating:     / 0
PoorBest

## Bottom-up Parsing

Bottom-up parsing is more general than top-down parsing. Bottom-up parsers handle a large class of grammars. It is the preferred method in practice. It is also called LR parsing; L means that tokens are read left to right and R means that the parser constructs a rightmost derivation. LR parsers do not need left-factored grammars. LR parsers can handle left-recursive grammars.

LR parsing reduces a string to the start symbol by inverting productions.A derivation consists of a series of rewrite steps

S ⇒ γ0 ⇒ γ1 ⇒ ... ⇒ γn-1
⇒ γn ⇒ sentence

Each γi is a sentential form. If γ contains only terminals, γ is a sentence in L(G). If γ contains ≥ 1 nonterminals, γ is a sentential form. A bottom-up parser builds a derivation by working from input sentence back towards the start symbol S.

Consider the grammar

S → aABe
A → Abc | b
B → d

The sentence abbcde can be reduced to S:

abbcde
aAbcde
aABe
S

These reductions, in fact, trace out the following right-most derivation in reverse:

S ⇒ aABe
⇒ aAbcde
⇒ abbcde

S ⇒ aBy ⇒ aγy ⇒ xy Consider the grammar

1. E → E + (E)
2. | int

The bottom-up parse of the string int + (int) + (int) would be

int + (int) + (int)
E + (int) + (int)
E + (E) + (int)
E + (int)
E + (E)
E

The consequence of an LR parser tracing a rightmost derivation in reverse is that given αβγ be a step of a bottom-up parse, assuming that next reduction is A → β τhen γ is a string of terminals. The reason is that αAγ → αβγ is a step in a rightmost derivation. This observation provides a strategy for building bottom up parsers: split the input string into two substrings. Right substring (a string of terminals) is as yet unexamined by parser and left substring has terminals and non-terminals. The dividing point is marked by a ► (the ► is not part of the string). Initially, all input is unexamined: ►x1 x1 . . . xn.

## Shift-Reduce Parsing

Bottom-up parsing uses only two kinds of actions:

1. Shift
2. Reduce

Shift moves ► one place to the right which shifts a terminal to the left string

E + (► int) ⇒ E + (int ►)

In the reduce action, the parser applies an inverse production at the right end of the left string. If E → E + (E) is a production, then

E + ( E+(E)►) ⇒ E + ( E ►)

Shift-Reduce Example

 ►int + (int) + (int) \$ shift int ► + (int) + (int) \$ reduce E → int E ► + (int) + (int) \$ shift 3 times E + (int ►) + (int) \$ reduce E → int E + (E ►) + (int) \$ shift E + (E) ► + (int) \$ reduce E → E+(E) E ► + (int) \$ shift 3 times E + (int ►) \$ reduce E → int E + (E ►) \$ shift E + (E) ► \$ red E → E+(E) E ► \$ accept