grammarcontext-free-grammarambiguous-grammar

Converting ambiguous language to unambiguous

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?

Solution

  • 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.