The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
855 views
  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 (59.6k points)
edited by | 855 views

2 Answers

+24 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 Boss (31.8k points)
edited by
0

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.
+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
 

answered by Active (1.2k points)

Related questions



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

42,687 questions
48,653 answers
156,493 comments
63,963 users