Scribd
Upload
29 views

CH 4 Syntax Analysis - Part2

Bottom-up parsing constructs a parse tree starting from the leaves and working towards the root. Shift-reduce parsing is a type of bottom-up parsing that uses a stack and input buffer. It performs shift and reduce actions to parse the input string. LR parsing is an efficient bottom-up parsing technique that can parse large classes of context-free grammars. It uses the concept of LR items and states to construct parsing tables to determine the shift and reduce actions.

Uploaded by

Bubblegum
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
29 views

CH 4 Syntax Analysis - Part2

Bottom-up parsing constructs a parse tree starting from the leaves and working towards the root. Shift-reduce parsing is a type of bottom-up parsing that uses a stack and input buffer. It performs shift and reduce actions to parse the input string. LR parsing is an efficient bottom-up parsing technique that can parse large classes of context-free grammars. It uses the concept of LR items and states to construct parsing tables to determine the shift and reduce actions.

Uploaded by

Bubblegum
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/ 31

Chapter 4

Syntax Analysis
CONT….
Bottom-up parsing
Constructing a parse tree for an input string beginning at
the leaves and going towards the root is called bottom-up
parsing.
A general type of bottom-up parser is a shift-reduce
parser.

SHIFT-REDUCE PARSING
Shift-reduce parsing is a type of bottom-up parsing that
attempts to construct a parse tree for an input string
beginning at the leaves (the bottom) and working up
towards the root (the top).

2
Example: Consider the grammar:
S → aABe
A → Abc | b
B→d
The sentence to be recognized is abbcde.

3
Handles
A handle of a string is a substring that matches the right side of a
production, and whose reduction to the non-terminal on the left side
of the production represents one step along the reverse of a
rightmost derivation.

4
Handle Pruning
A rightmost derivation in reverse can be obtained by
“handle pruning”.
(i.e.) if w is a sentence or string of the grammar at hand,
then w = γn, where γn is the nth right-sentinel form of
some rightmost derivation
Right Sentential Reducing
Handle
Form Production
id1 + id2 * id3 id1 E → id
E + id2 * id2 id2 E → id
E + E * id3 id3 E → id
E+E*E E*E E→E*E
E+E E+E E→E+E
5
E
Stack implementation of Shift-reduce parsing
Two data structures are required to implement a shift-reduce parser-
A Stack is required to hold the grammar symbols.
An Input buffer is required to hold the string to be parsed.

Actions in shift-reduce parser:


 shift – The next input symbol is shifted onto the top of the
stack.

 reduce – The parser replaces the handle within a stack


with a non-terminal.

 accept – The parser announces successful completion of


parsing.

 error – The parser discovers that a syntax error has


occurred and calls an error recovery routine. 6
7
Operator precedence parsing
An efficient way of constructing shift-reduce parser is called operator-
precedence parsing.

Operator precedence parser can be constructed from a grammar


called Operator-grammar. These grammars have the property that no
production on right side is ɛ or has two adjacent non- terminals.

Example:
Consider the grammar:
E → EAE | (E) | -E | id
A→+|-|*|/|↑

Since the right side EAE has three consecutive non-terminals, the
grammar can be written as follows:
E → E+E | E-E | E*E | E/E | E↑E | -E | id

8
Operator precedence parsing

Operator precedence relations:


There are three disjoint precedence relations namely
< . less than
= equal to
. > greater than

The relations give the following meaning:


a < . b a yields precedence to b
a = . b a has the same precedence as b
a . > b a takes precedence over b

9
Using Operator precedence relations:-

10
11
12
13
14
15
Construction of parsing table using
leading and trailing

16
Operator precedence table construction algorithm:-

17
LR parsers
An efficient bottom-up syntax analysis technique that can be used to
parse a large class of CFG is called LR(k) parsing.

The ‘L’ is for left-to-right scanning of the input, the ‘R’ for constructing
a rightmost derivation in reverse, and the ‘k’ for the number of input
symbols. When ‘k’ is omitted, it is assumed to be 1.

Types of LR parsing method:


1. SLR- Simple LR
 Easiest to implement, least powerful.

2. CLR- Canonical LR
 Most powerful, most expensive.

3. LALR- Look-Ahead LR
 Intermediate in size and cost between the other two 18
methods.
Advantages of LR parsing:
 It recognizes virtually all programming language
constructs for which CFG can be written.
 It is an efficient non-backtracking shift-reduce parsing
method.
 A grammar that can be parsed using LR method is a
proper superset of a grammar that
can be parsed with predictive parser.
 It detects a syntactic error as soon as possible.

Drawbacks of LR method:
It is too much of work to construct a LR parser by hand for
a programming language grammar. A specialized tool,
called a LR parser generator, is needed. Example: YACC.

19
LR parsing algorithm

20
21
Augmented Grammar: If G is a grammar with a start symbol S, then G′, the
augmented grammar for G is G with a new start symbol S′ and production S′ → S.

Indicates to the parser when it should stop parsing and announce the acceptance
of the input. 22
23
24
Constructing Canonical LR Parsing Tables

25
Algorithm: Construction of the sets of LR(1)
items

26
27
Algorithm: Canonical LR parsing table

28
LALR Parsing

29
Construction of LALR Parsing table

30
Problems solved on lecture
notes pdf….

31

You might also like