GATE Overflow | Compiler Design | Test 1 | Parsing | Question: 7

Question

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
    
   • A. (i) and (ii)
   • B. (iii)
   • C. (i), (ii) and (iii)
   • D. (ii) and (iii)

Comments

To correct left recursion, left factoring is used?

---

sorry sir ...now 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).

Answer 1

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.

 

Comments

done!

---

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.