Каков самый простой способ сказать, является ли грамматика BNF неоднозначной или нет?

Ответ 1

Может быть какая-то особенность в грамматиках в стиле BNF, но в целом решение о том, является ли данная контекстно-свободная грамматика (например, BNF) неоднозначной, не представляется возможным.

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

Ответ 2

В общем, нет.

Но как практический подход, то, что вы можете сделать, дается грамматика для каждого правила, перечислять возможные строки правильных терминалов/нетерминалов, чтобы увидеть, имеет ли какое-либо правило два или более эквивалентных вывода (которые были бы неоднозначность).

Наш DMS Software Reengineering Toolkit - это система преобразования программ для произвольных компьютерных языков, управляемая явными описаниями грамматики. DMS использует генератор парсера для управления движком анализатора GLR.

Генератор синтаксического анализатора DMS будет необязательно проверять двусмысленность, описанную выше, путем запуска итеративного углубления поиска по всем правилам грамматики. Это практично, потому что у него есть таблицы синтаксического анализа, чтобы эффективно управлять перечислением вариантов. Вы можете сказать это, чтобы выполнить эту проверку до некоторой выбранной глубины. Это может занять много времени, если вы выберете глубину любого интересного размера, но на самом деле глубина 3 или 4 достаточно, чтобы найти много глупых двусмысленностей, введенных в большую грамматику. Мы обычно делаем это во время нашей начальной грамматической отладки, и в тот момент, когда мы думаем, что у нас это очень хорошо.