in Compiler Design edited by
2,404 views
17 votes
  1. Remove left-recursion from the following grammar: $S \rightarrow Sa \mid Sb \mid a \mid b$
  2. Consider the following grammar: 

             $S \rightarrow aSbS\mid bSaS \mid ∊$

             Construct all possible parse trees for the string abab. Is the grammar ambiguous?

in Compiler Design edited by
2.4k views

2 Answers

30 votes
 
Best answer
  1. $S \rightarrow aS'\mid bS'$
    $S' \rightarrow aS' \mid bS' \mid \epsilon$
     
  2. $S \rightarrow aSbS \rightarrow abS \rightarrow abaSbS \rightarrow ababS \rightarrow abab$
    $S \rightarrow aSbS \rightarrow abSaSbS \rightarrow abaSbS \rightarrow ababS \rightarrow abab$ 

The above two derivations corresponds to two different parse trees and hence the grammar is ambiguous.

edited by

3 Comments

Two derivation so it is ambiguous

Gammer is ambiguous. But above statement requires 

Refer --> Option(A) for https://gateoverflow.in/711/gate2001-1-18

ping @kenzou

0
@Chhotu, its edited now.
0
Or the answer can be simplified as:

S$\rightarrow$aS|bS|a|b
0
4 votes

Remove left-recursion from the following grammar:

a) 

so by the basic rule==>

b)

left side parsing: S->aSbS->abS->abaSbS>ababS->abab

right side parsing:S->aSbS->abSaSbS->abaSbS->ababS->abab so it is ambiguous
 

Related questions