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

Question

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

Check whether the grammar is ambiguous or not. If it is, then the grammar is not LL(1) because no ambiguous grammar is LL(1).

Answer 3

Straight from the book "Compilers: Principles, Techniques, & Tools" by Aho, et. al.

Page 223:

A grammar G is LL(1) if and only if whenever A -> alpha | beta are two distinct productions of G, the following conditions hold:

1. For no terminal "a" do both alpha and beta derive strings beginning with "a"
2. At most one of alpha and beta can derive the empty string
3. If beta can reach the empty transition via zero or more transitions, then alpha does not derive any string beginning with a terminal in FOLLOW(A). Likewise, if alpha can reach the empty transition via zero or more transitions, then beta does not derive any string beginning with a terminal in FOLLOW(A)

Essentially this is a matter of verifying the grammar passes the Pairwise Disjointness Test and also does not involve Left Recursion. Or more succinctly a grammar G that is left-recursive or ambiguous cannot be LL(1).

Answer 4

ya there are shortcuts for ll(1) grammar

1) if A->B1|B2|.......|Bn then first(B1)intersection first(B2)intersection .first(Bn)=empty set then it is ll(1) grammar

2) if A->B1|epsilon then B1 intersection follow(A)is empty set

3) if G is any grammar such that every non terminal derives only one production then the grammar is LL(1)

Answer 5

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id

• Construct the LR(0) DFA, the FOLLOW set for E and the SLR action/goto tables.
• Is this an LR(0) grammar? Prove your answer.
• Using the SLR tables, show the steps (shifts, reductions, accept) of an LR parser parsing:
  id ( id + id )

Answer 6

In answer to your main question: For a very simple grammar, it may be possible to determine whether it is LL(1) without constructing FIRST and FOLLOW sets, e.g.

A → A + A | a

is not LL(1), while

A → a | b

is.

But when you get more complex than that, you'll need to do some analysis.

A → B | a
B → A + A

This is not LL(1), but it may not be immediately obvious

The grammar rules for arithmetic quickly get very complex:

expr → term { '+' term }
term → factor { '*' factor }
factor → number | '(' expr ')'

This grammar handles only multiplication and addition, and already it's not immediately clear whether the grammar is LL(1). It's still possible to evaluate it by looking through the grammar, but as the grammar grows it becomes less feasable. If we're defining a grammar for an entire programming language, it's almost certainly going to take some complex analysis.

That said, there are a few obvious telltale signs that the grammar is not LL(1) — like the A → A + A above — and if you can find any of these in your grammar, you'll know it needs to be rewritten if you're writing a recursive descent parser. But there's no shortcut to verify that the grammar is LL(1).