Here this regular grammar is not LL(1)..but we can have a LL(1) parser for the language accepted by this grammar.

The Gateway to Computer Science Excellence

+9 votes

1. If a grammar is LL(1), then it has to be LALR(1).Is it correct??

2. Is there anything called as LL(0)??

3. Do every DCFL has LL(1) grammar??

4. Do every DCFL has LR(1) grammar??

5. Can someone please specify, As we can say that every regular language is LL(1), what can we say for CFL,CSL,Recursive and RE??

6. What is the difference between parse tree, syntax tree and abstract syntax tree?

2. Is there anything called as LL(0)??

3. Do every DCFL has LL(1) grammar??

4. Do every DCFL has LR(1) grammar??

5. Can someone please specify, As we can say that every regular language is LL(1), what can we say for CFL,CSL,Recursive and RE??

6. What is the difference between parse tree, syntax tree and abstract syntax tree?

+11 votes

Best answer

this is one of the best questions i have come across..u have asked almost whole compiler design with few questions :)

**1. If a grammar is LL(1), then it has to be LALR(1)**

no..its false(if u have watched ************ sir's video..then he has done a mistake there) for correct diagram refer to dragon book...every LL(1) is CLR(1)..but may or may nt be LALR...ill nt confuse u here but if all variables of ur LL(1) grammar derives epsilon and other varibles too then it eill be LALR(1)

**2.Is there anything called as LL(0)??**

L means left to right..next L means LMD..0 means reduce seeing 0 lookaheads..means just reduce..so why not..u can make it..its ur compiler..make whatever u want..

**3. Do every DCFL has LL(1) grammar??**

no..every LL(1) canhave a DCFL but not converse..why? becasue LL(1) dont want any left recursion and non determinism..DFL doesnt gaurantee this..

**4. Do every DCFL has LR(1) grammar??**

yes..there is one to one correspondance between DCFL and LR parsers..similarly we have one to one correspondance between CFLs and CFGs

**5.u try to answer based on all these points**

0

Thanks....very well explained.I have added one more doubt..please see that one also. :)

1. Yes..I saw two different things by two reliable mentors,and got confused.

2. I was thinking if LR(0) s possible, so should be LL(0). Is it in use or just an idea that can exist?

4. U r saying here, that CFL's and CFGs are having one to one correspondence, but how I mean ambiguity is there in some CFGs and some of them might be inherently ambiguous, then how any LR parser can generate them?

1. Yes..I saw two different things by two reliable mentors,and got confused.

2. I was thinking if LR(0) s possible, so should be LL(0). Is it in use or just an idea that can exist?

4. U r saying here, that CFL's and CFGs are having one to one correspondence, but how I mean ambiguity is there in some CFGs and some of them might be inherently ambiguous, then how any LR parser can generate them?

+6

1.ravi sir has a done a silly mistake there...so go with dragon book diagram here..

2.http://stackoverflow.com/questions/5253816/are-there-such-a-thing-as-ll0-parsers

3.http://stackoverflow.com/questions/5967888/whats-the-difference-between-parse-trees-and-abstract-syntax-trees

4.for every CFL we can have a CFG..and for every CFG we canhave a CFL..this is one to one correspondance..

for all these questions u have to just keep one thing in mind

LL cant handle left recursion,non determinism and ambiguity

LR cant handle ambiguity rest everything is fine...

and whether regular ,CFL etc **can violate** any of these...think fr counter examples always..

0

@sudsho one-to-one correspondence means each element mapped to signle element of another set and each mapping is unique(not the case here). So I dont think one to one correspondence is there.

+1

^https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars

read arjun sirs answer here :)

0

@sudhsho I agree one to one for dcfl and LR parser. But then you added a point for one to one correspondence between cfl and cfg. That should be corrected right???

0

that point i watched in shai simonson lectures so added here....more than bijective definition here it means that we can have a CFG fr every CFL and vice versa

0

Okay. Thanks man for clearing doubts.

For 5th question I think LL and LR parsers work only for CFGs and that too unambigious.

For 5th question I think LL and LR parsers work only for CFGs and that too unambigious.

0

Hi, you said "every LL(1) is CLR(1)" ?

Is this correct or should it be "every LL(1) is LR(1)"?

Thanks

Is this correct or should it be "every LL(1) is LR(1)"?

Thanks

+1 vote

1. If a grammar is LL(1), then it has to be LALR(1).Is it correct??.

NO,It will be LR(1) for sure but we cant say about LALR(1).

2. Is there anything called as LL(0)??

No.LL(1) means one look ahead at a time,if it is 0,how will we identify the unique production

3. Do every DCFL has LL(1) grammar??

No.Every LL(1) has a DCFL corresponding to it,but Every DCFL need not to be LL(1),it goes one way.

4. Do every DCFL has LR(1) grammar??

Yes.A language is DCFL iff it is LR(1).

5. Can someone please specify, As we can say that every regular language is LL(1), what can we say for CFL,CSL,Recursive and RE??

I am not sure about this,but what i can say is that staring from CFL,CSL,REC,RE we might have ambuity in the lanuage as,so it should be false in general.

NO,It will be LR(1) for sure but we cant say about LALR(1).

2. Is there anything called as LL(0)??

No.LL(1) means one look ahead at a time,if it is 0,how will we identify the unique production

3. Do every DCFL has LL(1) grammar??

No.Every LL(1) has a DCFL corresponding to it,but Every DCFL need not to be LL(1),it goes one way.

4. Do every DCFL has LR(1) grammar??

Yes.A language is DCFL iff it is LR(1).

5. Can someone please specify, As we can say that every regular language is LL(1), what can we say for CFL,CSL,Recursive and RE??

I am not sure about this,but what i can say is that staring from CFL,CSL,REC,RE we might have ambuity in the lanuage as,so it should be false in general.

- 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,258 answers

198,087 comments

104,737 users