search
Log In
3 votes
310 views

Which of the following is TRUE regarding LL(0) grammar?

  1. We can have a LL(0) grammar for any regular language
  2. We can have a LL(0) grammar for a regular language only if it does not contain empty string
  3. We can have a LL(0) grammar for any regular language if and only if it has prefix property
  4. We can have a LL(0) grammar for only single string languages
in Compiler Design 310 views
7

@Arjun sir, i think the answer is D.

LL(0) means the grammar which can be generated with 0 look-a-heads.

So we have to generate a string even without looking at the first production symbol. this is only possible if there is only 1 string that the grammar can generate.

example:

S -> abc

now to generate the language of the grammar we need not even look at the sarting symbol 'a', because the only string it can generate is 'abc'

 

3
Yes. Or no string also. That is why we don't have a real LL(0) parser :)
1
sir, please explain point no 3 for both LL(o) and LL(1) grammar.
0

@OneZero  Can you explain option C or any article where I can read more about prefix property ?

only if it has prefix property

Did you discarded it because if a grammer has same prefix and there is no disjoint it won't be LL(1)?

0

@OneZero for LL(0) , 0 look-aheads

S->abc or S->epsilon 

Here null atring also be there

@Arjun sir, am i right ?

1 Answer

1 vote

LL(0) grammars have no lookahead. And since they follow Leftmost derivation, at each step the parser has to derive the string by seeing 0 symbols. => Parser sees nothing.

So whenever we have multiple choices for any Variable in the grammar, LL(0) fails.

Hence, LL(0) parser can only parse grammars that strictly generate one single string.

Option D

Answer:

Related questions

4 votes
2 answers
1
567 views
Which of the following statements is FALSE? Any DCFL has an equivalent grammar that can be parsed by a SLR(1) parser with end string delimiter Languages of grammars parsed by LR(2) parsers is a strict super set of the languages of grammars parsed by LR(1) parsers Languages of ... of grammars parsed by LL(1) parsers There is no DCFL which is not having a grammar that can be parsed by a LR(1) parser
asked Jan 26, 2019 in Compiler Design Arjun 567 views
2 votes
2 answers
2
296 views
Which of the following statements regarding $LR(0)$ parser is FALSE? A $LR(0)$ configurating set cannot have multiple reduce items A $LR(0)$ configurating set cannot have both shift as well as reduce items If a reduce item is present in a $LR(0)$ configurating set it cannot have any other item A $LR(0)$ parser can parse any regular grammar
asked Jan 26, 2019 in Compiler Design Arjun 296 views
2 votes
2 answers
3
329 views
Which of the following sentences regarding Viable prefixes is/are CORRECT? Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the ... prefixes can be recognized using a DFA Only (i) Only (ii) Only (i) and (ii) (i), (ii) and (iii)
asked Jan 26, 2019 in Compiler Design Arjun 329 views
3 votes
1 answer
4
256 views
Match the following: $\begin{array}{|cc|cc|} \hline (i) &LL(1)&(A)& \text{bottom-up} \\ \hline (ii)& \text{Recursive Descent}& (B) &\text{Predictive} \\ \hline (iii) &\text{Recursive Ascent}& (C)& \text{Top-down} \\ \hline (iv) &LR(1) &(D)& \text{Deterministic CFL} \\ \hline \end{array}$ i-b; ii-c; iii-a; iv-d i-d; ii-a; iii-c; iv-d i-c; ii-b; iii-d; iv-a i-a; ii-c; iii-b; iv-d
asked Jan 26, 2019 in Compiler Design Arjun 256 views
...