Example of an LR grammar that cannot be represented by LL?

Question

All LL grammars are LR grammars, but not the other way around, but I still struggle to deal with the distinction. I'm curious about small examples, if any exist, of LR grammars which do not have an equivalent LL representation.

Dermal

Answer 1

Well, as far as grammars are concerned, its easy -- any simple left-recursive grammar is LR (probably LR(1)) and not LL. So a list grammar like:

list ::= list ',' element | element

is LR(1) (assuming the production for element is) but not LL. Such grammars can be fairly easily converted into LL grammars by left-factoring and such, so this is not too interesting however.

Of more interest is LANGUAGES that are LR but not LL -- that is a language for which there exists an LR(1) grammar but no LL(k) grammar for any k. An example is things that need optional trailing matches. For example, the language of any number of a symbols followed by the same number or fewer b symbols, but not more bs -- { a^i b^j | i >= j }. There's a trivial LR(1) grammar:

S ::= a S | P
P ::= a P b | \epsilon

but no LL(k) grammar. The reason is that an LL grammar needs to decide whether to match an a+b pair or an odd a when looking at an a, while the LR grammar can defer that decision until after it sees the b or the end of the input.

This post on cs.stackechange.com has lots of references about this

Aggappe

That seems rather unlikely. That grammar seems to match if/else just fine- i.e., statement ::= if (...) statement | if (...) statement else (...) statement. This, as far as I know, is handled by LL parsers just fine. – Dermal

@DeadMG: As you note, the dangling else grammar is this same pattern, which is why its not LL and can't be handled cleanly by any LL parser. Of course, with a hand-written parser, you can use an ad-hoc workaround (usually a mini LR parser for this case), but that doesn't change the fact that the grammar is not LL – Aggappe

Interesting. Does that mean that virtually all languages which follow this construct have non-LL grammars, and virtually all LL parser generators must have workarounds? – Dermal

Yes. This non-LL issue is why many languages have an endif or other ending token that must match the if, as that make the language LL again. – Aggappe

@ChrisDodd: sorry, but the "trivial LR(1) grammar" is ambiguous, so it can't be LR: aab has two different parse trees, with either of the first two alternatives of S at the root. Also I would not say that "any left-recursive grammar is LR", but you possibly meant to say "any left-recursive LR grammar is not LL". – Philodendron

@Gunther: oops, you're right -- I accidentally oversimplified the grammar; it needs a second non-terminal to resolve the ambiguity. – Aggappe