Re: How test if language is LL(k) or LR(k) ?

Stephen Horne <sh006d3592@blueyonder.co.uk> writes:




> For LR, *almost* all context-free grammars are LR(k < infinity), so if
> you can prove that the grammar is context-free you are almost there.


That's not very useful, and not even true. There are many useful
grammars that are not LR(k) for any k and even useful languages for
which there doesn't exits LR(k) grammars for any k.


> You can always construct an LR(1) - or even LR(0) - state model to
> parse a context-free grammar, but if the grammar is not LR(1) that
> state model will have shift/reduce or reduce/reduce conflicts.
>
> Almost all such conflicts can be resolved finitely. This is the logic
> behind Tomita and other generalised LR parsing algorithms. The basic
> principle is that conflicts are resolved by checking all possibilities
> - the Tomita approach being to check them concurrently using stack
> duplication, whereas another common approach is to use backtracking.


This does, however, not give you any k, since the amount you have to
read ahead before backtracking may depend on the input.


> The basic problem is that sometimes, there are infinite possibilities
> to check. This can occur when the grammar contains empty rules - when
> there are reductions that pop zero tokens from the stack. However, it
> doesn't happen for *all* cases where empty rules are used - except in
> the case of LR(0), I think - and it is not reasonable to ban such
> rules.
>
> In such cases, Tomita will give an infinite number of stack
> duplicates, whereas the backtracking approach will simply give an
> infinite loop.


Empty productions can be eliminated automatically using a fairly
simple procedure (which, however, may increase the grammar size
quadratically), so these are not the problem. The problem is that you
often have to look to the end of the input before backtracking, which
effectively gives you unbounded lookahead.


If you just want to parse a text with a grammar, there are plenty of
algorithms around (such as Early's universal parser) that will give
you a lazy list of all possible parse trees. But that doesn't help
you decide if the language is LR(k).


> I have designed an variant of GLR (though I have never implemented it)
> which should theoretically give constant-time parsing of any context
> free grammar


I assume you mean "linear-time", as constant-time parsing sounds
implausible. But even linear-time parsing for any context-free
grammar sounds suspect and would be a very big result (if you can
prove it).


> that can be parsed,


Any context-free grammar can be parsed, so this restriction is
meaningless.


Torben

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