The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 votes

The grammar $ S \to aSa \mid bS \mid c$ is

- LL(1) but not LR(1)
- LR(1) but not LL(1)
- Both LL(1) and LR(1)
- Neither LL(1) nor LR(1)

+28 votes

Best answer

0

@Gate Keeda intersection of First() is Phi but we also check intersection of first(S) and Follow(S) here a is intersection result.

+1

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

+1

@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.

+1

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

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

+2

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

0

@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

0

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

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

-------> Every Grammar which is LL(1), then it is definitely LALR(1)?

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

LALR (1) is subset of CLR(1).

0

@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)

0

@ 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..

https://www.tutorialspoint.com/compiler_design/calculations_of_set_of_lr1_items.asp

https://stackoverflow.com/questions/14103199/lr1-item-dfa-computing-lookaheads

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,534 questions

54,122 answers

187,321 comments

71,040 users