20 votes 20 votes Remove left-recursion from the following grammar: $S \rightarrow Sa \mid Sb \mid a \mid b$ Consider the following grammar: $S \rightarrow aSbS\mid bSaS \mid ∊$ Construct all possible parse trees for the string abab. Is the grammar ambiguous? Compiler Design gatecse-2001 compiler-design grammar descriptive + – Kathleen asked Sep 14, 2014 edited May 14, 2018 by Milicevic3306 Kathleen 3.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 35 votes 35 votes $S \rightarrow aS'\mid bS'$ $S' \rightarrow aS' \mid bS' \mid \epsilon$ $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. Pooja Palod answered Aug 5, 2015 edited Jan 1, 2018 by joshi_nitish Pooja Palod comment Share Follow See all 3 Comments See all 3 3 Comments reply Chhotu commented Jan 1, 2018 reply Follow Share 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 votes 0 votes joshi_nitish commented Jan 1, 2018 reply Follow Share @Chhotu, its edited now. 0 votes 0 votes mohithjagalmohanan commented Jan 30, 2020 reply Follow Share Or the answer can be simplified as: S$\rightarrow$aS|bS|a|b 0 votes 0 votes Please log in or register to add a comment.
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 jaiganeshcse94 answered Aug 10, 2016 jaiganeshcse94 comment Share Follow See all 0 reply Please log in or register to add a comment.