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

parsing compiler-construction theory grammar bnf
Chris picture Chris · Jan 24, 2009 · Viewed 26.5k times · Source

Is there a simple way to determine whether a grammar is LL(1), LR(0), SLR(1)... just from looking on the grammar without doing any complex analysis?

For instance: To decide whether a BNF Grammar is LL(1) you have to calculate First and Follow sets - which can be time consuming in some cases.

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

Answer

Aaron Maenpaa picture Aaron Maenpaa · Jan 24, 2009

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

Related questions

Difference between Left Factoring and Left Recursion

What is the difference between Left Factoring and Left Recursion ? I understand that Left factoring is a predictive top down parsing technique. But I get confused when I hear these two terms.

Read More
What is the difference between LR, SLR, and LALR parsers?

What is the actual difference between LR, SLR, and LALR parsers? I know that SLR and LALR are types of LR parsers, but what is the actual difference as far as their parsing tables are concerned? And how to show …

Read More
What is the difference between LR(0) and SLR parsing?

I am working on my compilers concepts however I am a little confused... Googling got me nowhere to a definite answer. Is SLR and LR(0) parsers one and same? If not, whats the difference?

Read More