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

On Mon, 21 Jul 2014 06:07:55 +0000 (UTC), Chris Dodd <cdodd@acm.org>
wrote:


>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.


Yes and no.


For every LL(k) grammar where both k and the set T of tokens is fixed,
there is an equivalent LL(1) grammar. In the worst case, the
equivalent LL(1) grammar will have k**T rules.


Only where k or T is unbounded, so that the power set of {n:1<=n<=k}
lookahead tokens for some rule is not enumerable, can you not derive
an equivalent in LL(1).


The problem is that an LL({n:1<n<=k}) rule explodes multiplicatively
into an n-level tree of LL(1) rules, with each branch at each level
m<=n having to cover follow(m).


Meaning that it is effectively unworkable for any but small k.


Fortunately, for any reasonable LL(k>1) grammar, k will be bounded and
small, and the grammar will contain just a handful of rules requiring
the maximum k lookahead. Most rules will be LL({n:1<=n<k}) where n is
very small.


George

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