31-10-2012, 05:01 PM
LR Parsing
LR parser.ppt (Size: 304 KB / Downloads: 40)
LR parsing is attractive because:
LR parsing is most general non-backtracking shift-reduce parsing, yet it is still efficient.
The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive parsers. LL(1)-Grammars LR(1)-Grammars
An LR-parser can detect a syntactic error as soon as it is possible to do so a left-to-right scan of the input.
LR-Parsers
covers wide range of grammars.
SLR – simple LR parser
LR – most general LR parser
LALR – intermediate LR parser (look-head LR parser)
SLR, LR and LALR work same (they used the same algorithm), only their parsing tables are different.
shift/reduce and reduce/reduce conflicts
If a state does not know whether it will make a shift operation or reduction for a terminal, we say that there is a shift/reduce conflict.
If a state does not know whether it will make a reduction operation using the production rule i or j for a terminal, we say that there is a reduce/reduce conflict.
If the SLR parsing table of a grammar G has a conflict, we say that that grammar is not SLR grammar.
Using Ambiguous Grammars
All grammars used in the construction of LR-parsing tables must be un-ambiguous.
Can we create LR-parsing tables for ambiguous grammars ?
Yes, but they will have conflicts.
We can resolve these conflicts in favor of one of them to disambiguate the grammar.
At the end, we will have again an unambiguous grammar.
Why we want to use an ambiguous grammar?
Some of the ambiguous grammars are much natural, and a corresponding unambiguous grammar can be very complex.
Usage of an ambiguous grammar may eliminate unnecessary reductions.