How to identify whether a grammar is LL(1), LR(0) or SLR(1)?

Question

How do you identify whether a grammar is LL(1), LR(0), or SLR(1)?

Can anyone please explain it using this example, or any other example?

X → Yz | a

Y → bZ | ε

Z → ε

Scorpaenid

Answer 1

To check if a grammar is LL(1), one option is to construct the LL(1) parsing table and check for any conflicts. These conflicts can be

• FIRST/FIRST conflicts, where two different productions would have to be predicted for a nonterminal/terminal pair.
• FIRST/FOLLOW conflicts, where two different productions are predicted, one representing that some production should be taken and expands out to a nonzero number of symbols, and one representing that a production should be used indicating that some nonterminal should be ultimately expanded out to the empty string.
• FOLLOW/FOLLOW conflicts, where two productions indicating that a nonterminal should ultimately be expanded to the empty string conflict with one another.

Let's try this on your grammar by building the FIRST and FOLLOW sets for each of the nonterminals. Here, we get that

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

We also have that the FOLLOW sets are

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

From this, we can build the following LL(1) parsing table:

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

Since we can build this parsing table with no conflicts, the grammar is LL(1).

To check if a grammar is LR(0) or SLR(1), we begin by building up all of the LR(0) configurating sets for the grammar. In this case, assuming that X is your start symbol, we get the following:

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

From this, we can see that the grammar is not LR(0) because there is a shift/reduce conflicts in state (1). Specifically, because we have the shift item X → .a and Y → ., we can't tell whether to shift the a or reduce the empty string. More generally, no grammar with ε-productions is LR(0).

However, this grammar might be SLR(1). To see this, we augment each reduction with the lookahead set for the particular nonterminals. This gives back this set of SLR(1) configurating sets:

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

The shift/reduce conflict in state (1) has been eliminated because we only reduce when the lookahead is z, which doesn't conflict with any of the other items.

Amitosis

Isn't there a FIRST/FIRST conflict between X and Y in your LL(1) grammar discussion? They both contain b. – Sweetmeat

@JohnRoberts- A FIRST/FIRST conflict occurs when two productions for the same nonterminal have overlapping FIRST sets. Even though X and Y contain b in their FIRST sets, there is no nonterminal in the grammar with two productions, one of which starts with X and one of which starts with Y. Does that make sense? – Amitosis

So you're saying that because the two productions relate to different nonterminals, there is no conflict? – Sweetmeat

@JohnRoberts- Yes, exactly. FIRST/FIRST conflicts can only involve productions for a single nonterminal. Intuitively, the error would cause you to fill the same box in the LL(1) table with two different productions, so those productions have to have the same nonterminal on their left-hand side. – Amitosis

Interesting. This seems to directly contradict Wikipedia - en.wikipedia.org/wiki/LL_parser. Regarding the FIRST/FIRST conflict, it states that "FIRST/FIRST conflict: The FIRST sets of two different non-terminals intersect". – Sweetmeat

@JohnRoberts- I could be mistaken about this, but I've taught a compilers class twice and have read over two books on parsing. I am fairly confident that I'm correct about this. All LL(1) conflicts result in having two or more entries in the parsing table, and that can only happen if there are two productions for a nonterminal that cannot be split apart. That in turn only happens when the sets collide in a way that matters in the production. Take a look at the example here: research.microsoft.com/en-us/um/people/abegel/cs164/ll1.html, where E, T, and F all have ( and int in FIRST. – Amitosis

I think I trust a teacher over Wikipedia. Could you please take a look at my own question regarding this? https://mcmap.net/q/260860/-making-a-grammar-ll-1 – Sweetmeat

so can we say that the only difference between lr(0) and slr(1) is grammar with ε-productions ? – Wavell

@Wavell No, that's not necessarily the case. Some grammars that aren't LR(0) aren't LR(0) because there are productions that have common prefixes of one another and the parser isn't able to determine, having read the prefix, whether to continue shifting or not. SLR(1) parsers can often handle these grammars. – Amitosis

Are you sure LR(0) is the same as SLR(1)?? – Pyroxylin

@YuhuanJiang Oh, they're definitely not the same. Did I say something that gave the impression that they were? – Amitosis

@JohnRoberts: I trust neither a teacher nor Wikipedia :-) but you would only have a conflict if your parser saw a z and didn't know whether to parse an X or an Y; but when the parser knows which one to parse, it knows which rule to apply. You would have a conflict if there were rules S->X and S->Y, because then the parser wouldn't know which rule to apply if the next symbol is z in state S. – Chirr

State 6 is not a shift-reduce conflict. The only action in that state is to reduce. "Shifting" Z is a GOTO, not a shift; it happens unconditionally when the GOTO table is consulted after the reduction action is performed. LR(0) grammars can have ε-productions if there is no other production for that non-terminal. (Or if the non-terminal is unreachable, which is a different pathology.) The ε-production for Y does inevitably lead to a shift-reduce conflict. – Voronezh

I apologize for the very late comment. Your answer was linked from this question, and the claim here about LR(0) grammars and ε-productions was confusing for that poster. Although the answer is otherwise excellent. – Voronezh

@Voronezh Thanks for spotting that - I've updated the answer to correct this. And more generally, thanks for all your contributions here to all things parsing! – Amitosis

I think to find whether the given grammar is LL(1) we need to first remove left recursion (also left factor) and then proceed to checking FIRST and FOLLOW conflicts. This may be a simple step but for novices they may accidentally label grammar as not LL(1) in case they don't left factor and remove left recursion. – Fairfield

@Fairfield There’s a distinction between two closely related concepts. The first is whether a grammar is LL(1), which asks “is this grammar free of FIRST/FIRST and FIRST/FOLLOW conflicts?” For that, you wouldn’t do any left factoring, since the grammar is given and we can’t modify it. The second is whether a language is LL(1), in which we’re given a CFG and ask “is there some way to make an LL(1) CFG for the same language described by this CFG?” In the latter case, you would be free to do whatever you’d like to try to remove these conflicts. – Amitosis

@Amitosis Thanks for clarifying. I got it what you mean. – Fairfield

Answer 2

If you have no FIRST/FIRST conflicts and no FIRST/FOLLOW conflicts, your grammar is LL(1).

An example of a FIRST/FIRST conflict:

S -> Xb | Yc
X -> a 
Y -> a 

By seeing only the first input symbol "a", you cannot know whether to apply the production S -> Xb or S -> Yc, because "a" is in the FIRST set of both X and Y.

An example of a FIRST/FOLLOW conflict:

S -> AB 
A -> fe | ε 
B -> fg 

By seeing only the first input symbol "f", you cannot decide whether to apply the production A -> fe or A -> ε, because "f" is in both the FIRST set of A and the FOLLOW set of A (A can be parsed as ε/empty and B as f).

Notice that if you have no epsilon-productions you cannot have a FIRST/FOLLOW conflict.

Adamson

By seeing "f" (or "a") do you mean in the first of the sentence or anywhere in the sentence? – Eleonoraeleonore

@MehdiCharife if your grammar has a FIRST/FIRST or FIRST/FOLLOW conflict anywhere, then it is not LL(1). It does not matter how far you can progress through a given string before the conflict becomes relevant. If there is any rule in your grammar where the production to apply is not immediately known with a lookahead of 1, then your grammar is not LL(1). – Adamson

Can we say instead that by seeing the symbol "f" we cannot know whether we are at the start of the end of A? – Eleonoraeleonore

Answer 3

Simple answer:A grammar is said to be an LL(1),if the associated LL(1) parsing table has atmost one production in each table entry.

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    -------------------------------------------- 

As [S,b] contains two Productions there is a confusion as to which rule to choose.So it is not LL(1).

Some simple checks to see whether a grammar is LL(1) or not. Check 1: The Grammar should not be left Recursive. Example: E --> E+T. is not LL(1) because it is Left recursive. Check 2: The Grammar should be Left Factored.

Left factoring is required when two or more grammar rule choices share a common prefix string. Example: S-->A+int|A.

Check 3:The Grammar should not be ambiguous.

These are some simple checks.

Refer

Your answer could be improved by including an example of how to apply this rule and potentially a source to backup your claims. – Ap

Thanks for the comment.I have added an example and some other useful information. – Refer

Answer 4

LL(1) grammar is Context free unambiguous grammar which can be parsed by LL(1) parsers.

In LL(1)

• First L stands for scanning input from Left to Right. Second L stands for Left Most Derivation. 1 stands for using one input symbol at each step.

For Checking grammar is LL(1) you can draw predictive parsing table. And if you find any multiple entries in table then you can say grammar is not LL(1).

Their is also short cut to check if the grammar is LL(1) or not . Shortcut Technique

Cleodell

Answer 5

With these two steps we can check if it LL(1) or not. Both of them have to be satisfied.

1.If we have the production:A->a1|a2|a3|a4|.....|an. Then,First(a(i)) intersection First(a(j)) must be phi(empty set)[a(i)-a subscript i.]

2.For every non terminal 'A',if First(A) contains epsilon Then First(A) intersection Follow(A) must be phi(empty set).

Kalif