retagged by
2,673 views
10 votes
10 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?
retagged by

2 Answers

Best answer
12 votes
12 votes

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

1. If a grammar is LL(1), then it has to be LALR(1)
no. it's false(if u have watched ravindrababu sir's video..then he has done a mistake there) for the correct diagram refer to Dragon Book. every LL(1) is CLR(1)..but may or may not be LALR...ill nt confuse u here but if all variables of ur LL(1) grammar derive epsilon and other variables too then it will 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 look ahead means just reduce. So why not? you can make it. it's your compiler. make whatever u want.

3. Does every DCFL have LL(1) grammar??
no..every LL(1) can have a DCFL but not converse..why? because LL(1) doesn't want any left recursion and non-determinism.DFL doesn't guarantee this..

4. Does every DCFL have LR(1) grammar??​​​​​​​
yes..there is one to one correspondence between DCFL and LR parsers..similarly, we have one to one correspondence between CFLs and CFGs

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

edited by
1 votes
1 votes
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 by

Related questions

0 votes
0 votes
2 answers
2
Parshu gate asked Nov 10, 2017
1,065 views
For the below given grammar:S→-SS→S-aS→aThe number of inadequate states (states which have conflicts) and number of shift reduce conflicts are _____ and _____ respe...
2 votes
2 votes
0 answers
3
rahul sharma 5 asked Oct 14, 2017
1,494 views
Consider the following grammer:-Stmts - Stmt | Stmts;StmtStmt - Var =EVar ->id[E] | idE- id | (E)Find the number of conflicts in LR(0)?
0 votes
0 votes
0 answers
4
rahul sharma 5 asked Oct 14, 2017
1,325 views
Consider the following augmented grammar G which is used to build LR (0) parsing table.E' __ EE __ E+T/TT __ T*F/FF >(E)/idHow many rows are there in the parsing rable ?...