Log In
2 votes

GATE 2010 Question

The grammar S→aSa∣bS∣c is 

  1. LL(1) but not LR(1)
  2. LR(1) but not LL(1)
  3. Both LL(1) and LR(1)
  4. Neither LL(1) nor LR(1)

I have 2 small doubt

First Doubt:-If a grammer is LL(1) then it is always LR(0) ? Is there any grammer which is LL(1)  and cannot be parsed by LR(0) ?

Second doubt :- Can any one tell me the above question is write or wrong because they have given LR(1) parser and i haven't heard about LR(1).I have heard about  Brute force ,recursive descent,operator presedence,LL(1) LR(0) SLR(1) LALR(1) CLR(1).So what is the difference between LR(0) AND LR(1) and which one is more powerfull ?

in Compiler Design 908 views
Thanks :)

3 Answers

8 votes
Best answer

First Doubt : A grammar parsed by LL(1) must also be parsed by LR(1) Parser but may not by LR(0)

For e.g 

S. ---> AaAb 

S ---> BbBa

A ---> €

B ---> €

Second doubt : LR(1) also known as canonical LR(1)

So LR(1) and CLR(1) same.

selected by

@Himanshu LL(1) is subset of LR(1)

Also LR(1) are DCFL.

In diagram where will be LL(0)??
2 votes
CLR(1) is also called as LR(1)
0 votes
  1. please check this i am correct or not

Related questions

0 votes
1 answer
Consider the grammar given $S\rightarrow AA$ $A\rightarrow aA / b$ How many entries will be blank in the GOTO table for SR(0) items?
asked Jan 31, 2018 in Compiler Design Utsav09 93 views
0 votes
0 answers
Implement Algorithm $3.23$, which converts a regular expression into a nondeterministic finite automaton, by an L-attributed SDD on a top-down parsable grammar. Assume that there is a token char representing any character, and that char.$lexval$ is the character it ... that is, a state never before returned by this function. Use any convenient notation to specify the transitions of the $NFA$.
asked Sep 6, 2019 in Compiler Design Lakshman Patel RJIT 107 views
1 vote
0 answers
In Fig. $4.56$ is a grammar for certain statements, similar to that discussed in Question $4.4.12$. Again, $e$ and $s$ are terminals standing for conditional expressions and "other statements," respectively. Build an LR parsing table for this grammar, resolving conflicts in the usual way ... your parser on the following inputs: if e then s ; if e then s end while e do begin s ; if e then s ; end
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 81 views
0 votes
0 answers
The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ different levels of precedence: $E\rightarrow E\theta_{1}E\mid E\theta_{2}E\mid \cdot\cdot\cdot E\theta_{n}E\mid(E)\mid id$ ... of the tables for the two (ambiguous and unambiguous) grammars compare? What does that comparison tell you about the use of ambiguous expression grammars?
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 114 views