The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 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)
asked in Compiler Design by Veteran (96.1k points)
edited by | 2.2k views

1 Answer

+28 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).

answered 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) ?

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
49,534 questions
54,122 answers
71,040 users