Invalid Reductions – A Problem with SLR Parsers:
In SLR parser, the state “I” calls for a reduction by A → α on input symbol ‘a’
If the
set of items Ii contain the item A →
α and
‘a’ is
an FOLLOW(A)
This causes a problem when ‘i’ is on the top of the stack,
the viable prefix βα on
the stack is such that βA
is not followed by ‘a’ in any right sentential form. This makes reduction by A → α invalid on input ‘a’
Example:
In the previous chapter, an example for a grammar that is
not an SLR(1) is shown. Assume there’s a parser for it and it is called
reduction by R → L in
state I2 with ‘=’ on the input (instead of shift). The resulting right
sentential form R = ….. is not there in the grammar. So, the state I2 should
not call for reduction.
Elimination of the problem with SLR Parsers:
The valid reduction problem by A → α
can be eliminated by making each state to carry extra information by
- Splitting states whenever necessary
- Have each state indicate input symbols that can follow a handle α for which there is a reduction to ‘A’
The extra information is incorporated into a state by redefining
items to include a terminal symbol as the second component
LR(1) Items:
It has the following syntax
[A → α.β,
a]
Where A →
αβ is a production and ‘a’ is
a terminal or the end marker $.
The 1 in
LR(1) refers to the length of the second component also called lookahead of the
item
How to
Lookahead Solves the problem of Invalid Reductions?
The
lookahead tells on what input symbols a reduction can occur
Example: The item [A → α, a] calls for reduction A → α if the next input symbol is ‘a’
Do remember that the lookahead plays no role in case of item
[A → α.β, a] where β ≠ ε
An item [A →
α.β, a] is valid for a viable
prefix γ if there is a
derivation \[S\underset{rm}{\overset{*}{\mathop{\Rightarrow }}}\,\delta A\omega
~\underset{rm}{\mathop{\Rightarrow }}\,\delta \beta \omega \]
Where
γ = δα, and
Either ‘a’ is the first symbol of δω, or ω
is ε and ‘a’ is $
