Re: LR(1) Parsing : Error Handling & Recovery

George Neuner <gneuner2@comcast.net> wrote in news:14-07-041@comp.compilers:
> LL(k) always can be refactored to single token lookahead, but it
> causes an explosion of grammar states. E.g., given a single LL(3)
> rule, an equivalent set of LL(1) rules must match every valid
> combination of tokens at +1, +2 and +3.


Not true -- LL(k+1) languages are a strict superset of LL(k) languages, so
there exist LL(k) grammars that cannot be refactored to a smaller k.


LR(k) languages are equivalent the LR(1), so every LR(k) grammar can be
refactored to LR(1)


A useful summary of the relationships between various types of languages and
grammars can be found at


<http://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars>


Chris Dodd
cdodd@acm.org

Return to the comp.compilers page.
Search the comp.compilers archives again.