Log In
0 votes

Which of the following is a requirement for an LL(1) grammar?

  1. Unambiguity
  2. No left recursion
  3. If $A \to \alpha \mid \beta$ are two productions, then $FIRST(\alpha)$ and $FIRST(\beta)$ are disjoint
    1. (i) and (ii)
    2. (iii)
    3. (i), (ii) and (iii)
    4. (ii) and (iii)
in Compiler Design 920 views

option c.

top down parser cannot parse ambigious , left recursive grammer.


FIRST(α) and FIRST(β) -> if these are same then parser will get confuse about which production to use for reduction.



For a grammar to be LL(1) it should be

i) Unambiguous

ii) Not left recursed

iii) If A→α∣βA→α∣β are two productions, then FIRST(α)FIRST(α) and FIRST(β)FIRST(β) are disjoint
To correct left recursion, left factoring is used?
sorry sir corrected.

left factoring is used to remove common prefix problem.
Even if we use left recursion, there is no guarantee that the grammar will be LL(1).

example :

S -> A/B

A ->Aa/a

B -> Bb/b

converted into

S -> A/B

A -> aA/a

B ->aB/a

its not left recursive but it still not LL(1).

1 Answer

2 votes

LL(1) Parser

it is a top down parser without backtracking.

top down parser without backtracking doesn't allow ambiguous garmmar,left recursion,non determinism.

Here the 1st L represents that the scanning of the Input will be done from Left to Right manner and second L shows that in this Parsing technique we are going to use Left most Derivation Tree. and finally the 1 represents the number of look ahead, means how many symbols are you going to see when you want to make a decision.

If a grammar has to be LL(1) then it shouldn't have

--> Ambiguous grammar

(A Garmmar is said to be ambiguous if more than one parse tree (either LMD or RMD)of the same string is generated from the grammar 

we don't want ambiguous grammar because we are getting more than one parse tree therefore No parser will work for ambiguous grammar except operator precedence parser, so we want only unambiguous grammar

some of the grammar can be converted ambiguous to unambiguous gramm by using disambiguity rule.)


-->left recursion

(The production is left-recursive if the leftmost symbol on the right side is the same as the non terminal on the left side)

we dont want left recursive grammar because top down parser fall in infinite loop.

eg- A-->Aa  






A is calling A without doing any work so it will fall in infinite loop.)

-->Non determinism

(for the same input, the compiler may produce different output in different runs. In fact non-deterministic algorithms can’t solve the problem in polynomial time and can’t determine what is the next step. The non-deterministic algorithms can show different behaviors for the same input on different execution and there is a degree of randomness to it.

Problem with Non Det. is Backtracking 

we have many option 

A-->aB1 | aB2 | aB3

let us we want this [aB3]

A -->aB1 (backtracking)

A -->aB2 (backtracking)

A -->aB3 (result)

The problem is backtracking,backtracking happening because of common prefix,one or more production on RHS or something common in the prefix is known as common prefix.we are making decision on the basis of prefixes.

Backtracking so parser will fail.

we can eliminate non det.,by converting non deterministic to deterministic is called left factoring.

Eliminating non det. or applying left factoring does not eliminate ambiguity.)

A→α∣βA→α∣β are two productions, then FIRST(α)FIRST(α) and FIRST(β)FIRST(β) are disjoint 

Therefore C is correct.


edited by
That's correct. But not a good answer. You should say why for each.
okay sir i will do it
Better. But again, you did not even say what is an LL(1) parser and how it works (at least intuitively). Without this you cannot explain how the given constructs cause problem in its working.
Leftmost lookahead of 1 symbol -- you should use this to show how the given constructs cause parsing problem.

Related questions

4 votes
2 answers
If we merge states in LR(1) parser to form a LALR(1) parser, we may introduce shift-reduce conflict reduce-reduce conflict no extra conflict both shift-reduce as well as reduce-reduce
asked Jan 26, 2019 in Compiler Design Arjun 387 views
0 votes
2 answers
Suppose we have a rightmost derivation which proceeds as follows: $\begin{array}{ccc}S &\rightarrow & Aabw \\ & \rightarrow &ABw \end{array}$ Which of the following is a possible handle for it? $\begin{array}{ccc} A &\rightarrow & ab \end{array}$ ... $\begin{array}{ccc} S &\rightarrow & A \end{array}$ $\begin{array}{ccc} B &\rightarrow & ab \end{array}$
asked Jan 26, 2019 in Compiler Design Arjun 284 views
4 votes
2 answers
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 1.1k views
2 votes
1 answer
Which of the following statements is FALSE? In a SLR(1) parser, it is allowable for both shift and reduce items to be in the same state In a SLR(1) parser, it is allowable for multiple reduce items to be in the same state All SLR(1) grammars are LR(0) All LR(0) grammars are SLR(1)
asked Jan 26, 2019 in Compiler Design Arjun 1.1k views