CS606 - Compiler Construction - Lecture Handout 20

User Rating:  / 0

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

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:


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

S ⇒ aABe
⇒ aAde
⇒ aAbcde
⇒ abbcde

S ⇒ aBy ⇒ aγy ⇒ xy

Terminals only

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)

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