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 $
0 comments:
Post a Comment