Преобразование неоднозначного языка в однозначный

Question

Мне дали задание на домашнюю работу, чтобы преобразовать следующую грамматику в однозначную.

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

, где A и B нетерминальные, а STRING и DOUBLE нетерминальные.

Я могу вывести, что это неоднозначно, учитывая, что для такой строки можно построить два разных дерева разбора, например:

STRING @ STRING @ DOUBLE(STRING).

Пока что у меня есть:

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

, но оно не завершено в виде строки, такой как:

STRING @ DOUBLE (STRING) @ STRING

не может быть сделано.Как бы я преобразовал эту грамматику в однозначную?

Answer 1

Продолжая ответ Joop, вы можете ввести новый символ D, чтобы устранить неоднозначность вокруг B --> B @ B:

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

С этим изменением для любой строки в языке возможно только одно дерево.

Answer 2

STRING @ STRING @ STRING

может быть результатом A ⇒ B @ (B @ B) или A ⇒ (B @ B) @ B из-за

B --> B @ B

Решение состоит в том, чтобы ввести новый B-подобный нетерминал и заменить вхождения на этот нетерминал.Это вводит асимметрию, которую вы найдете во многих грамматиках.

Удовольствие выяснить остальное, что я оставляю вам.