Scribd
Upload
9 views

bottom up

This document covers bottom-up parsing techniques in compiler construction, focusing on LR methods such as SLR, Canonical LR, and LALR, as well as shift-reduce parsing and operator-precedence parsing. It discusses the concept of handles, stack implementation of shift-reduce parsing, and various types of conflicts that can arise, including shift-reduce and reduce-reduce conflicts. Additionally, it outlines error recovery strategies in LR parsing, including panic mode and phrase-level recovery.

Uploaded by

ARKAMIDES OFFICIAL
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
9 views

bottom up

This document covers bottom-up parsing techniques in compiler construction, focusing on LR methods such as SLR, Canonical LR, and LALR, as well as shift-reduce parsing and operator-precedence parsing. It discusses the concept of handles, stack implementation of shift-reduce parsing, and various types of conflicts that can arise, including shift-reduce and reduce-reduce conflicts. Additionally, it outlines error recovery strategies in LR parsing, including panic mode and phrase-level recovery.

Uploaded by

ARKAMIDES OFFICIAL
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/ 10

1

Syntax Analysis
Part II
Chapter 4

COP5621 Compiler Construction


Copyright Robert van Engelen, Florida State University, 2007-2013
2

Bottom-Up Parsing
• LR methods (Left-to-right, Rightmost
derivation)
– SLR, Canonical LR, LALR
• Other special cases:
– Shift-reduce parsing
– Operator-precedence parsing
3

Operator-Precedence Parsing
• Special case of shift-reduce parsing
• We will not further discuss (you can skip
textbook section 4.6)
4

Shift-Reduce Parsing
Grammar: Reducing a sentence: Shift-reduce corresponds
SaABe abbcde to a rightmost derivation:
AAbc|b aAbcde S rm a A B e
Bd aAde rm a A d e
aABe rm a A b c d e
These match S
production’s rm a b b c d e
right-hand sides
S

A A A
A A A B A B
a b b c d e a b b c d e a b b c d e a b b c d e
5

Handles
A handle is a substring of grammar symbols in a
right-sentential form that matches a right-hand side
of a production
Grammar: abbcde
SaABe aAbcde
AAbc|b aAde Handle
Bd aABe
S
abbcde
aAbcde NOT a handle, because
aAAe further reductions will fail
…? (result is not a sentential form)
6

Stack Implementation of
Shift-Reduce Parsing
Stack Input Action
$ id+id*id$ shift
$id +id*id$ reduce E  id How to
Grammar: $E +id*id$ shift
$E+ id*id$ shift
resolve
EE+E conflicts?
$E+id *id$ reduce E  id
EE*E $E+E *id$ shift (or reduce?)
E(E) $E+E* id$ shift
E  id $E+E*id $ reduce E  id
$E+E*E $ reduce E  E * E
$E+E $ reduce E  E + E
Found handles $E $ accept
to reduce
7

Conflicts
• Shift-reduce and reduce-reduce conflicts
are caused by
– The limitations of the LR parsing method (even
when the grammar is unambiguous)
– Ambiguity of the grammar
8

Shift-Reduce Parsing:
Shift-Reduce Conflicts
Stack Input Action
$… …$ …
$…if E then S else…$ shift or reduce?
Ambiguous grammar:
S  if E then S
| if E then S else S
| other

Resolve in favor
of shift, so else
matches closest if
9

Shift-Reduce Parsing:
Reduce-Reduce Conflicts
Stack Input Action
$ aa$ shift
$a a$ reduce A  a or B  a ?
Grammar:
CAB
Aa
Ba

Resolve in favor
of reducing A  a,
otherwise we’re stuck!
10

Error Recovery in LR Parsing


• Panic mode
– Pop until state with a goto on a nonterminal A is found,
(where A represents a major programming construct), push A
– Discard input symbols until one is found in the FOLLOW
set of A
• Phrase-level recovery
– Implement error routines for every error entry in table
• Error productions
– Pop until state has error production, then shift on stack
– Discard input until symbol is encountered that allows
parsing to continue

You might also like