How to determine whether a grammar is LL(1) LR(0) SLR(1)

Question

Is there a simple way to determine wether a grammar is LL1, LR0, SLR1... just from looking on the grammar without doing any complex analysis?

For instance: To decide wether a BNF Grammar is LL1 you have to calculate First and Follow sets first - which can be very time consuming in some cases.

Has anybody got an idea how to do this faster? Any help would really be appreciated!

Answer 1

First off, a bit of pedantry. You cannot determine whether a language is LL(1) from inspecting a grammar for it, you can only make statements about the grammar itself. It is perfectly possible to write non-LL(1) grammars for languages for which an LL(1) grammar exists.

With that out of the way:

• You could write a parser for the grammar and have a program calculate first and follow sets and other properties for you. After all, that's the big advantage of BNF grammars, they are machine comprehensible.

• Inspect the grammar and look for violations of the constraints of various grammar types. For instance: LL(1) allows for right but not left recursion, thus, a grammar that contains left recursion is not LL(1). (For other grammar properties you're going to have to spend some quality time with the definitions, because I can't remember anything else off the top of my head right now :).

Answer 2

One aspect, "is the language/grammar ambiguous", is a known undecidable question like the Post correspondence and halting problems.

Answer 3

aardvark,

thanks a lot for the clear explanation of LL(1) grammar. it has helped me a lot.

zaza