CSCE 434 Lecture 21

« previous | Friday, October 11, 2013 | next »

Lecture Slides

Exam on Friday will cover Chapters 1-4
Work on Gradience Homeworks for Practice!

Resolving Parse Conflicts

Happens when certain LR items are found in the same state

Parser may choose between LR items using lookahead; resolves such conflicts

	Shift-Reduce $[A::=\alpha \cdot ,\delta ]$ $[B::=\beta \cdot \gamma ,\eta ]$	Reduce-Reduce $[A::=\alpha \cdot ,\delta ]$ $[B::=\beta \cdot ,\eta ]$
LR(0)	conflict	conflict
SLR(1)	$\mathrm {follow} (A)\cap \mathrm {first} (\gamma )$	$\mathrm {follow} (A)\cap \mathrm {follow} (B)$
LALR(1)	$\delta \cap \mathrm {first} (\gamma )$	$\delta \cap \eta$

LALR(1) Parsing

Same number of states as SLR(1) (fewer than LR(1)) but have more power because of lookahead.

core of set of LR(1) items:

If two sets of LR(1) items, $I_{i}$ and $I_{j}$ have the same core, we can merge the states that represent them in the ACTION and GOTO tables

Approach 1

Build LR(1) sets and merge

LALR(1) Table Construction

More space-efficient

LALR derived from LR with no shift-reduce conflict will also have no shift-reduce conflict

LALR may create reduce-reduce conflicts not in LR from which LALR is derived. Perhaps combined states really weren't that identical.

Order of inclusiveness from low power to high power

1. SLR(1)
2. LALR(1)
3. LR(1)
4. LR(k)

However, all recognize the same language

Precedence

An approach to solve S/R conflicts is to use operator precedence:

Given $S\Rightarrow ^{*}\alpha S_{1}S_{2}\beta$, there are three possible precedence relations between $S_{1}$ and $S_{2}$:

1. $S_{1}$ in handle, but not $S_{2}$ ($S_{1}>S_{2}$)
2. Both in handle ($S_{1}=S_{2}$)
3. $S_{2}$ in handle, but not $S_{1}$ ($S_{1}>S_{2}$)

We want operators of higher precedence to be resolved (reduced) first: e.g. addition should be reduced after multiplication

Review

Hand-coded recursive descent

LL(k): able to recognize production rule after seeing only the first $k$ symbols

LR(k):

Lecture Slides

Associativity

Left-recursion is left-associativity (natural for left-to-right human languages) Right-recursion is right-associativity

However, we have discovered that left and right recursion have specific applications:

• Left-associative for bottom-up
• Right-associative for top-down

Error Recovery

• For each non-terminal, construct a set of terminals on which the parser can synchronize
• When an error occurs when looking for $A$, scan until an element of $\mathrm {SYNCH} (A)$ is found, then pop $A$ and continue.

What is SYNCH?

1. If $a$ is in $\mathrm {follow} (A)$, then put $a$ in $\mathrm {SYNCH} (A)$.