edited by
3,573 views
20 votes
20 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?

edited by

2 Answers

Best answer
35 votes
35 votes
  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
4 votes
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

37 votes
37 votes
6 answers
1
Kathleen asked Sep 14, 2014
17,886 views
Which of the following statements is false?An unambiguous grammar has same leftmost and rightmost derivationAn LL(1) parser is a top-down parserLALR is more powerful than...
36 votes
36 votes
2 answers
4
Kathleen asked Sep 14, 2014
12,523 views
The process of assigning load addresses to the various parts of the program and adjusting the code and the data in the program to reflect the assigned addresses is called...