The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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?

asked in Compiler Design by Veteran (68.8k points)
edited by | 609 views

2 Answers

+21 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$

answered by Veteran (33.9k points)
edited by

Two derivation so it is ambiguous

Gammer is ambiguous. But above statement requires 

Refer --> Option(A) for

ping @kenzou

@Chhotu, its edited now.
+4 votes

Remove left-recursion from the following grammar:


so by the basic rule==>


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

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


answered by Active (1.2k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,470 questions
39,199 answers
36,575 users