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

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

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

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


grammar context-free-grammar ambiguous-grammar
person Neri Villa    schedule 05.10.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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

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

person Patrick87    schedule 09.10.2018

arrow_upward
0
arrow_downward 

STRING @ STRING @ STRING

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

B --> B @ B

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

Удовольствие разобраться в остальном я оставляю вам.

person Joop Eggen    schedule 05.10.2018
comment
Спасибо Юп. Я отредактировал свой пост, указав то, что, по моему мнению, я мог бы сделать лучше всего, однако я чувствую, что моя реализация асимметрии неверна. - person Neri Villa; 05.10.2018
comment
Вы должны мысленно проработать такую ​​грамматику самостоятельно, так как грамматики поначалу сложны. B --> X (@ Y)* будет больше похоже на конечный желаемый результат. Возможно, поможет рисование деревьев синтаксического анализа. - person Joop Eggen; 05.10.2018
comment
Извините, вся эта концепция CFG для меня нова, но что означает «*» и как бы вы применили это в CFG? - person Neri Villa; 05.10.2018
comment
Это было задумано как псевдокод. Постфиксный оператор `*` означает 0 или более повторений предшествующего выражения. Возможно, вы знаете то же самое, что и ` { @ Y }. B -> C | Б | @ С` . будет однозначное повторение. - person Joop Eggen; 06.10.2018