Неоднозначная грамматика

Контекстно свободная грамматика

A → A + A | A − A | a

является неоднозначной, так как есть два левосторонних вывода для строки a + a + a:

Также, грамматика является неоднозначной, поскольку есть два дерева разбора для строки a + a − a:

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

A → A + a | A − a | a

Общая задача определения, является ли грамматика неоднозначной, алгоритмически неразрешима. Не может существовать алгоритма, определяющего неоднозначность грамматики, поскольку неразрешимая задача соответствия Поста сводится к задаче неоднозначности.

Существует очевидная трудность в синтаксическом анализе неоднозначной грамматики детерминированным анализатором, но недетерминированный анализ приводит к значительному проигрышу в эффективности. Большинство конструкций, требующих синтаксического анализа, могут быть распознаны однозначными грамматиками. Некоторые неоднозначные грамматики могут быть преобразованы в однозначные, но общей процедуры для этого преобразования нет, так же как нет и алгоритма определения неоднозначности грамматики. Генераторы компиляторов, такие как YACC, способны устранять некоторые виды неоднозначности, например используя ограничения приоритета и ассоциативности.

В то время как некоторые языки (множества строк, порождаемых грамматикой) имеют как однозначные, так и неоднозначные грамматики, существуют языки, для которых не существует однозначной грамматики. Примером существенно неоднозначного языка является объединение ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}$ и ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}}$. Это контекстно-свободный язык как объединение контекстно-свободных языков, но Введение в теорию автоматов… содержит доказательство того, что нет возможности однозначно разобрать строки в (не контекстно-свободном) подмножестве ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$, являющемся пересечением этих двух языков.