CODEWITHSUNDEEP
parsingcompiler-constructionscanningambiguityformal-languages
Millennial
Millennial

Reputation: 89

Removing ambiguity in a grammar

I have a grammar with one production rule:

S → aSbS | bSaS | ∈

This is ambiguous. Is it allowed to remove the ambiguity this way?

S → A|B|∈
A → aS
B → bS

This makes it unambiguous. Another grammar:

S → A | B
A → aAb | ab
B → abB | ∈

Correction to make it unambiguous

S → A | B
A → aA'b 
A' → ab
B → abB | ∈

I am not using any rules to make the grammars unambiguous. If it is wrong to remove ambiguity in a grammar this way, can anyone point a proper set of rules for removing ambiguity in ambiguous grammars?

Upvotes: 0

Views: 1477

Answers (1)

rici
rici

Reputation: 241931

As @kaby76 points out in a comment, in your first example, you haven't just removed the unambiguity. You have also changed the language recognised by the grammar.

S → a S b S
  | b S a A
  | ε

recognises only strings with the same number of a's and b's, while

S → A
  | B
  | ε
A → a S
B → b S

recognises any string made up of a's and b's.

So that's certainly not a legitimate disambiguation.

By the way, your second grammar could have been simplified; A and B serve no useful purpose.

S → a S
  | b S
  | ε

There are unambiguous grammars for this language. One example:

S → a A S
  | b B S
A → a
  | b A A
B → b
  | a B B

See this post on the Computer Science StackExchange for an explanation.

In your second example, the grammar

S → A
  | B
A → a A b
  | a b
B → a b B
  | ε

is ambiguous, but only because A and B both match ab. Every other recognised string has exactly one possible parse.

In this grammar, A matches strings which consist of some number of as followed by the same number of bs, while B matches strings which consist of any number of repetitions of ab.

ab fits both criteria: it is a repetition of ab (consisting of just one copy) and it is a sequence of as followed by the same number of bs (in this case, one of each). The empty string also matches both criteria (with repetition count 0), but it has been excluded from A by making the starting rule A → a b. An easy way to make the grammar unambiguous would be to change that base rule to A → a a b b.

Again, your disambiguated grammar does not recognise the same language as the original grammar. Your change makes A non-recursive, so that it only recognises aabb and now strings like aaabbb, aaaabbbb, and so on are not recognised. So once again, it is not simply an unambiguous version of the original.

Note that this grammar only matches strings with an equal number of as and bs, but it does not match all such strings. There are many other strings with an equal number of as and bs which are not matched, such as ba or aabbab. So its language is a subset of the language of the first grammar, but it is not the same language.

Finally, you ask if there is a mechanical procedure which can create an unambiguous grammar given an ambiguous grammar. The answer is no. It can be proven that there is no algorithm which can even decide whether a particular context-free grammar is ambiguous. Nor is there an algorithm which can decide whether two context-free grammars have the same language. So it shouldn't be surprising that there is no algorithm which can construct an equivalent unambiguous grammar from an ambiguous grammar.

That doesn't mean that the task cannot be done for certain grammars. But it's not a simple mechanical procedure, and it might not work for a particular grammar.

Upvotes: 1

Related Questions