# Few doubts in compiler design

1.4k views
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?

edited
0
No..every language is LL(1), because we can have a regular grammar for it,which is LL(1).

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

found this that

Every regular Language is LL(1)
but Every regular grammar is not LL(1)
0

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​​​​​​​

selected
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?
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..

1
okay..thanku very much :)
1
Thanks Sudsho :)
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.
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.
0
why not regular grammars?
1
Every regular grammar is context free, so it didn't mention it.
0
ok :)
0
Hi, you said "every LL(1) is CLR(1)" ?

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

Thanks
0

@sudsho

but if all variables of ur LL(1) grammar derives epsilon and other varibles too then it eill be LALR(1)

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.

edited
0
1. CLR(1) is the most powerful one.I think u got confused?

0
Yeah.Editted now:)
0
we know for every DCFL we have LR parser...can we say, ALL THE CFL have LR parser???
0
he is correct LR(1) is one other name of CLR(1) in short . and it is most powerful

## Related questions

1
716 views
Consider the following grammer:- Stmts -> Stmt | Stmts;Stmt Stmt -> Var =E Var ->id[E] | id E-> id | (E) Find the number of conflicts in LR(0)?
1 vote
In Fig. $4.56$ is a grammar for certain statements, similar to that discussed in Question $4.4.12$. Again, $e$ and $s$ are terminals standing for conditional expressions and "other statements," respectively. Build an LR parsing table for this grammar, resolving conflicts in the usual way ... your parser on the following inputs: if e then s ; if e then s end while e do begin s ; if e then s ; end
Consider the family of grammars $G_{n}$, defined by: $S\rightarrow A_{i}b_{i}$ for $1\leq i\leq n$ $A_{i} \rightarrow a_{j} A_{i}\mid a_{j}$ for $1\leq i,j\leq n$ and $i\neq j$ Show that: $G_{n}$, has $2n^{2}-n$ productions. $G_{n}$, has $2^{n} + n^{2} + n$ sets of $LR(0)$ items. $G_{n}$ is $SLR(1)$. What does this analysis say about how large $LR$ parsers can get?