964 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?

edited | 964 views

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

Remove left-recursion from the following grammar:

a)  $S\rightarrow Sa|Sb|a|b$

$A\rightarrow A\alpha|\beta by \left\{\begin{matrix} A\rightarrow \beta A' & \\ A'\rightarrow \alpha A'|\epsilon & \end{matrix}\right.$

so by the basic rule==> $S'\rightarrow aS'|bS'|\epsilon$

b) $S\rightarrow aSbS|bSaS|\epsilon$

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

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

1
2