Converting ambiguous language to unambiguous

Question

I've been given a homework task to convert the following grammar to unambiguous.

A --> B
A --> ε
B --> B @ B
B --> STRING
B --> DOUBLE(STRING)

where A and B are non-terminals and STRING and DOUBLE are non-terminals.

I can derive that it is ambiguous given two different parse trees can be constructed for a string such as :

STRING @ STRING @ DOUBLE(STRING).

So far, I've got:

A --> B | ε
B --> B @ DOUBLE(STRING)
B --> C
C --> C @ STRING | STRING | DOUBLE(STRING)

however it's not complete as the string such as:

STRING @ DOUBLE(STRING) @ STRING

cannot be made. How would I convert this grammar to unambiguous?

Answer 1

STRING @ STRING @ STRING

could result from A ⇒ B @(B @ B) or A ⇒ (B @ B) @ B because of

B --> B @ B

The solution is to introduce a new B-alike non-terminal and replace on of the occurrences with that nonterminal. This introduces an assymetry, you will find in many grammars.

The pleasure to figure out the rest I leave to you.

Answer 2

Continuing Joop's answer, you can introduce a new symbol D to eliminate the ambiguity around B --> B @ B:

A --> D
A --> ε
D --> D @ B
D --> B
B --> STRING
B --> DOUBLE(STRING)

With this change, only one tree is possible for any string in the language.