15,196 views

3 Answers

7 votes
7 votes
For LL(1) You have to check by using First and Follow method.

For LR(0) and SLR(1) you have to do augmented transition method, and then by making state transition diagram, you have to look where Shift-Reduce and Reduce Reduce conflicts are present and according to that you've to eliminate the parser.

For LR(1) items such as CLR(1), LALR(1) you've to do again state transition diagram again using Look-Ahead.

Though this method seems tough, but by practice, it will be very easy.
edited by
4 votes
4 votes

Conditon for LL(1) and hence LR(1)

Check for following condition:

  1. grammar is not left recursive 
  2. grammar is not left factored using first or follow method

Also if a grammar is LL(1) then it is in LR(1) . So you don't have to check for LR(1) separately

Condtion  for LR(0) -using LR(0) automaton

in LR(0) generally the conflict arise due to a reducing production. If we have any production such A-->b. (ie with dot at rightmost position) we place the r in all column of row corresponing to the state. This r occuping the whole row cause the SR or RR conflict. 
check   the corresponding LR(0) automaton. If for any state , production A-->b. (dot at rightmost position) exists in that state , it should not contain any other production. 
 

Conditon for SLR(1) 

No shortcut. check via parsing table. Any conflict while filling table , means not SLR(1).

Conditon for LALR(1)

No shortcut .. check via parsing table for LR(1) parser. if conflict arise while merging , then not LALR(1).

order of checking  

LL(1) ---> LALR(1)--> SLR(1)--> LR(0). ( in decreasing parsing power) 

Note: this answer is not from any text. Please correct me if i m wrong. 

4 votes
4 votes
FOR A GIVEN GRAMMAR, IF you want to check LL(1) OR NOT

simply check - is given grammar CONTAIN (1) LEFT RECURSION

                                                                       (2) LECT FACTORING

                                                                         (3) AMBIGUOUS OR NOT(MORE THAN ONE PARSE TREE POSSIBLE FOR ALTEAST ONE STRING)

IF YOUR GRAMMAR CONTAIN ABOVE ANYONE TRUE THEN YOU CAN SURELY SAY THAT, GIVEN GRAMMAR IS NOT LL(1)

 SUPPOSE  YOUR GRAMMAR NOT  CONTAINING ANYONE OF THE ABOVE THEN  CHECK FOR FIRST AND FOLLOW OF EACH PRODUCTION AND TAKE INTERSECTION OF THEM AND IF YOU U FOUND a COMMON BETWEEN THEM, THEN GIVEN GRAMMAR IS NOT LL(1)

 and if suppose your grammar is LL(1) THEN it is CLR(1) ALSO no need to check for CLR(1) again

 NOW,

 FOR LR(0) SIMPLY expand your production and  your LR(0) ITEMS doesn't contain any S/R, R/R CONFLICT THEN

your grammar is LR(0) AND HENCE ITS IS SLR(1) AND LALR(1) AND CLR(1) ALSO

BECAUSE LR(0)  HAVING LESS CONDITION, COMPARE TO ALL ,

 and suppose LR(0) CONTAIN A CONFLICT LIKE R/R AND S/R (ANYONE) THEN YOUR GRAMMAR IS NOT LR(0) SO NOW CHECK FOR SLR(1)

SIMPLY  PLACE THE REDUCE MOVE IN FOLLOW OF LHS AND AGAIN CHECK THE LR(0) TABLE IF STILL YOU ANR CONFLICT  PRESENT LIKE R/R AND S/R THEN  YOUR GRAMMAR IS  NOT SLR(1) AND IF YOU NO CONFLICT PRESENT THEN YOUR GRAMMAR IS SLR(1)

FOR LALR(1) DRAW THE LR(1) TABLE AND CHECK ANY CONFLICT PRESENT OR NOT, IF NOT THEN YOUR GRAMMAR IS LALR (1) AND FOR SLR(1) SIMPLY MINIMIZED THE LR(1) TABLE TRY TO MERGE THE STATE WHICH IS DIFFER BY ONLY LOOK -AHEAD SYMBOL. AFTER MINIMIZING THE LR(1) TABLE SUPPOSE YOU GET NO CONFLICT THEN YOU GRAMMAR IS SLR(1) .....

REMEMBER FOR SLR(1)  WE ARE SIMPLY MINIMIZED THE LR(1) TABLE, IF MINIMIZATION POSSIBLE THEN TRY TO MINIMIZE AND THEN CHECK THE TABLE IS THERE ANY CONFLICT PRESENT OR NOT, IF NOT THEN GRAMMAR IS SLR(1)  

 AND SUPPOSE YOU DRAW THE LR(1) TABLE AND FURTHER MINIMIZATION NOT   POSSIBLE THEN STOP AND SAY YOUR GRAMMAR IS LALR(1) AND CLR(1) ALSO.
edited by

Related questions

2 votes
2 votes
1 answer
1
sripo asked Nov 10, 2018
3,180 views
Can you give an example which is not LL(1) but is CLR(1)
0 votes
0 votes
3 answers
2
1 votes
1 votes
1 answer
3
0 votes
0 votes
0 answers
4
rahul sharma 5 asked Nov 12, 2017
1,102 views
Can LL(k) and LR(k) gammer has null and unit productions?