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

User · Answer

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

User · Answer

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 - gt  Xb   Yc X - gt  a  Y - gt  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 - gt  AB  A - gt  fe   epsilon  B - gt  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

User · Answer

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

User · Answer

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  - gt   X X - gt   Yz X - gt   a Y - gt    Y - gt   bZ   2  X  - gt  X    3  X - gt  Y z   4  X - gt  Yz    5  X - gt  a    6  Y - gt  b Z Z - gt      7  Y - gt  bZ    From this  we can see that the grammar is not LR 0  because there are shift reduce conflicts in states  1  and  6    Specifically  because we have the reduce items Z  rarr    and Y  rarr     we can t tell whether to reduce the empty string to these symbols or to shift some other symbol   More generally  no grammar with  epsilon -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  - gt   X X - gt   Yz     X - gt   a      Y - gt       z  Y - gt   bZ  z    2  X  - gt  X    3  X - gt  Y z       4  X - gt  Yz        5  X - gt  a         6  Y - gt  b Z  z  Z - gt       z    7  Y - gt  bZ   z    Now  we don t have any more shift-reduce conflicts   The 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   Similarly  the conflict in  6  is gone for the same reason   Hope this helps

User · Answer

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 -- gt Aa b  A is non-terminal  amp  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-- gt a                                            A-- gt 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

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

Examples related to parsing

Examples related to grammar

Examples related to lr

Examples related to ll