3,955 views
2 votes
2 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)

1 Answer

4 votes
4 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()

    {

     A()

     a

     }

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
Answer:

Related questions

6 votes
6 votes
2 answers
1
Arjun asked Jan 26, 2019
1,691 views
If we merge states in LR(1) parser to form a LALR(1) parser, we may introduceshift-reduce conflictreduce-reduce conflictno extra conflictboth shift-reduce as well as redu...
4 votes
4 votes
2 answers
2
Arjun asked Jan 26, 2019
835 views
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 po...
3 votes
3 votes
1 answer
4