The Gateway to Computer Science Excellence

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

+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

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

+3

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

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

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

+2

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

https://en.wikipedia.org/wiki/LL_grammar#Relation_to_other_grammar_classes

0

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

I think this statement is incorrect.

Refer this

0

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

stackoverflow.com/questions/49493005/is-every-ll1-grammar-also-a-lalr1-grammar

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,236 comments

104,919 users