The Gateway to Computer Science Excellence
+27 votes

The grammar $ S \to aSa \mid bS \mid 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)
in Compiler Design by Veteran (105k points)
edited by | 2.9k views

1 Answer

+35 votes
Best answer

It will be C.

For LL(1) take First(S). and do intersection between the result. if intersection is Phi then LL(1) else not.

Making a parsing table and checking if there are two or more entries under any terminal. If yes then neither LL(1) nor LR(1).

by Boss (19.9k points)
edited by
how is LR checking done?
if it is LL(1), it is LR(1) -easy.

Otherwise, we have to do LR table.
@arjun sir nice one.
@Gate Keeda intersection of First() is Phi but we also check intersection of first(S) and Follow(S)  here a is intersection result.

take First(S). and do intersection between the result, what does it mean for intersection with the result?

First(S) = {a,b,c} now what to take intersection with?


 @iarnav Taking first will ensure that in parsing table there is not conflict seeing any terminal in the production thus under $ you can accept the string while parsing while getting any terminal {a,b,c} reduce it appropriately with the respective production.

those first(S)=a,b,c places its respective prod rule to its column

i.e a will have entry aSa, b will have entry bS and c has entry c, a intersection b intersection  c has phi, so it's LL

Suppose, if we have episilon prod instead of 'c', for epsilon, we add follow of S, i.e a will come to picture and make it not LL(1).
First(aSa) = a
First(bS) = b
First(c) = c
All are mutually disjoint i.e no common terminal 
between them, the given grammar is LL(1).
@Arjun sir if grammar is LR(0) we can say it is slr, clr n all coz reduce entries will be less than LR(0). But LL(1) is top down parser and the parsing algorithm also differ, then how can we say if it is LL1 then it is LR1
How to check LR(1)?

------->  CLR(1) is also called as LR(1)?

-------> Every Grammar which is LL(1), then it is definitely  LALR(1)?
every LL(1) is also LALR (1) grammar and hence LR(1). CLR(1) grammar is also called LR(1).

LALR (1) is subset of CLR(1).
@Arjun Sir how LR(1) table is drawn

@ anchitjindal07 , here no need to check for LR(1). why because it's LL(1) so obviously LR(1).

@Raju Kalagoni, I know here in this example it is not needed, but if some language is not LL(1), then we have to check for LR(1)

@ anchitjindal07 , there is a procedure for finding LR(1) items and then we need to check for conflicting operations like Reduce - Reduce / Shift - Reduce conflict. please check below link..

i think every LALR is CLR but  every CLR is not LALR so every LL(1) is LR(1) but not LALR
It is not always true
Can anyone explain if it is LL(1) then how it is LR(1)?
That is proved in any Compiler text. Any LL(x) grammar is also LR(x).
i.e every LL(1) is also LR(0) ?

LL grammars are strict subset of LR grammar.

Go through this link once & observe the given figure also.


@amarsharma  bro that's not true.


@Raju Kalagoni

every LL(1) is also LALR (1) grammar and hence LR(1)

I think this statement is incorrect. 

Refer this


You are right, @Shiva Sagar Rao, LL(1) grammar may not be subset of LALR(1).


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,919 users