Это грамматика зеркалки? - PullRequest
       8

Это грамматика зеркалки?

1 голос
/ 21 апреля 2010

E -> A | B

A -> a | с

B -> b | с

Мой ответ - нет, потому что конфликт конфликтует, может кто-нибудь еще это проверить?

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

Спасибо за помощь!

P.S Рекурсивный спуск сможет разобрать это?

1 Ответ

3 голосов
/ 21 апреля 2010

Вы правы - начиная с 'c' на входе, нет способа решить, следует ли рассматривать это как 'A' или 'B'. Я сомневаюсь, что есть что-то, что действительно может разобрать это правильно - это просто неоднозначно. Использование другого типа парсера не поможет; вам действительно нужно изменить язык.

Существуют некоторые формальные методы обнаружения таких двусмысленностей, но я с трудом могу себе представить, что с ними так мало грамматики Один простой способ выявить эту конкретную проблему - мысленно упорядочить ее в дерево:

alt text

Две строки, выходящие из поля 'c', представляют конфликт уменьшения / уменьшения. Нет причин предпочитать один путь от 'c' до 'E' другому, поэтому грамматика неоднозначна.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...