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

parsing grammar lr ll

120,794

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

Hope this helps!

Solution 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 | epsilon 
B -> fg

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

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

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

Solution 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

View more solutions

120,794

Author by

Prashant Bhardwaj

Updated on July 05, 2022

Comments

Prashant Bhardwaj almost 2 years

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 → ε
John Roberts about 11 years

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

@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?
John Roberts about 11 years

So you're saying that because the two productions relate to different nonterminals, there is no conflict?
templatetypedef about 11 years

@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.
John Roberts about 11 years

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".
templatetypedef about 11 years

@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.
John Roberts about 11 years

I think I trust a teacher over Wikipedia. Could you please take a look at my own question regarding this? stackoverflow.com/questions/15161636/making-a-grammar-ll1
Khaledvic over 10 years

so can we say that the only difference between lr(0) and slr(1) is grammar with ε-productions ?
templatetypedef over 10 years

@Khaledvic 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.
Yuhuan Jiang about 9 years

Are you sure LR(0) is the same as SLR(1)??
templatetypedef about 9 years

@YuhuanJiang Oh, they're definitely not the same. Did I say something that gave the impression that they were?
ankh-morpork almost 9 years

Your answer could be improved by including an example of how to apply this rule and potentially a source to backup your claims.
Anil Kumar almost 9 years

Thanks for the comment.I have added an example and some other useful information.
gnasher729 about 8 years

@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.
rici over 2 years

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.
rici over 2 years

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.
templatetypedef over 2 years

@rici 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!