От однозначной грамматики до неоднозначной

Question

Я не знаю, если это правильный сайт, чтобы спросить это. Но мы изучаем неясности грамматики. Включая самый левый вывод и самый правый вывод. Моя проблема с практикой заключается в следующем:

E -> E * E | E + E | N
N -> 0N | 1N |
Output: 0110 + 110 * 01111

Есть ли способ сделать это неоднозначным? И какие-нибудь подсказки в том, чтобы сделать грамматику неоднозначной?

Answer 1

Учитывая вашу грамматику, это явно неоднозначно. Здесь это не определяет предпочтение между + а также * оператор.

Как вы сказали, если вам нужно разобрать это 0110 + 110 * 01111это можно сделать двумя способами:

1. 0110 + 110 * 01111 ----> (0110 + 110) * 01111

2. 0110 + 110 * 01111 ----> 0110 + (110 * 01111)

Таким образом, эта грамматика довольно неоднозначна, поскольку она не определяет приоритет оператора. Также отсутствует предоставление ассоциативности операторов.

От правил производства, указанных в грамматике, явно зависит устранение неоднозначности путем определения различий между конфликтующими случаями. Некоторые вещи, возникающие при выполнении синтаксического анализа сверху вниз, относятся к факторингу слева и левой рекурсии, приводящей к неоднозначным грамматикам.

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