Scribd
Upload
19 views

Lecture-6-Bottom-Up-Parsing

This lecture covers bottom-up parsing, specifically shift-reduce parsing, which constructs a parse tree from the leaves to the root using LR grammars. It explains the process of reductions and handle pruning, emphasizing the role of a stack in managing grammar symbols during parsing. Exercises are provided to practice identifying handles and performing bottom-up parses for given input strings and grammars.

Uploaded by

itshappyday777
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
19 views

Lecture-6-Bottom-Up-Parsing

This lecture covers bottom-up parsing, specifically shift-reduce parsing, which constructs a parse tree from the leaves to the root using LR grammars. It explains the process of reductions and handle pruning, emphasizing the role of a stack in managing grammar symbols during parsing. Exercises are provided to practice identifying handles and performing bottom-up parses for given input strings and grammars.

Uploaded by

itshappyday777
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 13

Lecture 6: Bottom-Up

Parsing

Dr. Raheel Siddiqi

Compiler Construction
1
Bottom-Up Parsing
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).

A bottom-up parse for id * id


2
 This lecture introduces a general style of bottom-up
parsing known as shift-reduce parsing.
 The largest class of grammars for which shift-reduce
parsers can be built is the LR grammars.
 Although it is too much work to build an LR parser
by hand, tools called automatic parser generators
make it easy to construct efficient LR parsers from
suitable grammars.
3
Reductions
We can think of bottom-up parsing as the process of
"reducing" a string w to the start symbol of the grammar.
At each reduction step, a specific substring matching the
body of a production is replaced by the nonterminal at the
head of that production.

4
 Consider the following expression grammar:
E → E+T | T
T → T*F | F
F → id | (E)
 The following reductions will be done for input “id+id”:

 The key decisions during bottom-up parsing are about when to reduce
and about what production to apply, as the parse proceeds.

5
Handle Pruning
Bottom-up parsing during a left-to-right scan of the input constructs a
rightmost derivation in reverse.
Informally, a "handle" is a substring that matches the body of a
production, and whose reduction represents one step along the
reverse of a rightmost derivation.

6
Handles during a parse of id1 * id2

 For convenience, we refer to the body β rather than A  β as a


handle.
7
Shift-Reduce Parsing
Shift-reduce parsing is a form of bottom-up parsing in which a stack
holds grammar symbols and an input buffer holds the rest of the
string to be parsed.
The handle always appears at the top of the stack just before it is
identified as the handle.
We use $ to mark the bottom of the stack and also the right end of
the input.

8
During a left-to-right scan of the input string, the parser shifts zero or
more input symbols onto the stack, until it is ready to reduce a string β of
grammar symbols on top of the stack.
It then reduces β to the head of the appropriate production.
The parser repeats this cycle until it has detected an error or until the
stack contains the start symbol and the input is empty:

 Upon entering this configuration, the parser halts and announces


successful completion of parsing.
9
Configurations of a shift-reduce parser on input id1 *id2
10
 The use of a stack in shift-reduce parsing is justified by an important
fact: the handle will always eventually appear on top of the stack, never
inside.

11
Exercises
1. For the grammar S  0 S 1 | 0 1, indicate the handle in each of the
following right-sentential forms:
a. 000111
b. 00S11
2. For the grammar SSS+ | SS* | a, indicate the handle in each of the
following right-sentential forms:
a. SSS+a*+
b. SS+a*a+
c. aaa*a++

12
3. Give bottom-up parses for the following input strings and grammars:
a.The input 000111 according to the grammar S0S1 | 01
b.The input aaa*a++ according to the grammar S SS+ | SS* | a.

13

You might also like