1
$\begingroup$

I want to remove ambiguity from the grammar below:

S → ABC

A → abA | ab

B → b | BC

C → c | cC

I have removed left recursion and left factoring and obtained the grammar as follows:

S → ABC

A → abA'

A' → A | ε

B → bB'

B' → CB' | ε

C → cC'

C' → ε | C

Now, how can I remove ambiguity from the grammar? Is removing left recursion and left factoring necessary?

$\endgroup$
5
  • 1
    $\begingroup$ Neither left factoring nor left recursion removal will have much impact on ambiguity. Have you tried to figure out what language that grammar produces? $\endgroup$
    – rici
    Dec 6, 2022 at 5:08
  • $\begingroup$ To generate abbcc there are two ways of left derivation. So, it is ambigious grammar, right? $\endgroup$ Dec 7, 2022 at 5:44
  • $\begingroup$ I also create LL(1) parser and there are conflicts in the table. $\endgroup$ Dec 7, 2022 at 5:45
  • 1
    $\begingroup$ The grammar is ambiguous. But the language is regular. So if you figure out what the language is, you can easily write an unambiguous grammar. $\endgroup$
    – rici
    Dec 7, 2022 at 5:56
  • 1
    $\begingroup$ Some sentences generated by this grammar are {a b b c, a b b c c, a b b c c c, a b a b b c, a b b c c c c, a b a b b c c, a b a b b c c c, a b b c c c c c, a b a b a b b c, a b a b b c c c c, a b a b a b b c c, a b a b a b a b b c, a b a b a b b c c c}. The ambiguous sentences are {a b b c c, a b b c c c, a b b c c c c, a b a b b c c, a b a b b c c c}. The language starts with ab and ends with c. $\endgroup$ Dec 7, 2022 at 7:49

1 Answer 1

1
$\begingroup$

"The grammar is ambiguous. But the language is regular. So if you figure out what the language is, you can easily write an unambiguous grammar", says rici.

Denote the language generated by the given grammar by $L$. Let us see what is $L$ in plain English. Or how we can describe the strings in $L$. Or how we can generate the strings in $L$.

A good way to start is, as you have done wonderfully, to generate and list some strings in $L$. You got $$a b b c, a b b c c, a b b c c c, a b a b b c, a b b c c c c, a b a b b c c, a b a b b c c c, a b b c c c c c, a b a b a b b c, a b a b b c c c c, a b a b a b b c c, a b a b a b a b b c, a b a b a b b c c c$$

We can observe that each string starts with one or more $ab$'s, continues with one $b$, and ends with one or more $c$s. (This observation could have been guided by studying the given grammar.)

It turns out the description above characterizes $L$. That is, a string is in $L$ if and only if it starts with one or more $ab$'s, etc. It is not hard to prove that fact.

Instead of transforming the given grammar, we can write an unambiguous grammar from scratch, since we "know" $L$.

In fact, the description above is "unambiguous" in the sense that there is unique way to split a string into one or more $ab$'s, one $b$'s and one or more $c$'s.

$S\to ABC$.
$A\to abA\mid ab$
$B\to b$
$C\to cC\mid c$


The grammar can be simplifed to

$S\to AC$
$A\to abA\mid abb$
$C\to cC\mid c$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.