Введение
Тип контекстно-свободной грамматики. В информатике, неоднозначная грамматика — это контекстно-свободная грамматика, для которой существует строка, имеющая более одного левого вывода или дерева разбора. Любой непустой контекстно-свободный язык допускает неоднозначную грамматику, например, путем добавления дублирующего правила. Язык, допускающий только неоднозначные грамматики, называется внутренне неоднозначным языком. Детерминированные контекстно-свободные грамматики всегда однозначны и являются важным подклассом однозначных грамматик; однако существуют недетерминированные однозначные грамматики. Для языков программирования, эталонная грамматика часто бывает неоднозначной из-за таких проблем, как проблема «висящего else». Если такие неоднозначности присутствуют, они обычно разрешаются путем добавления правил приоритета или других правил разбора, чувствительных к контексту, так что общая грамматика становится однозначной. Некоторые алгоритмы разбора (например, Earley или GLR) могут генерировать наборы деревьев разбора (или «лесов разбора») для строк, которые синтаксически неоднозначны.
In computer science, an ambiguous grammar is a context free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non empty context free language admits an ambiguous grammar by introducing e. g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non deterministic unambiguous grammars, however. For computer programming languages, the reference grammar is often ambiguous, due to issues such as the dangling else problem. If present, these ambiguities are generally resolved by adding precedence rules or other context sensitive parsing rules, so the overall phrase grammar is unambiguous. Some parsing algorithms (such as Earley or GLR parsers) can generate sets of parse trees (or "parse forests") from strings that are syntactically ambiguous.
Распознавание двусмысленных грамматических выражений
Проблема определения, является ли произвольная грамматика неоднозначной, неразрешима, поскольку можно показать, что она эквивалентна задаче о переписке Поста. Однако существуют инструменты, реализующие некоторые процедуры частичного решения для обнаружения неоднозначности контекстно-свободных грамматик. Эффективность разбора контекстно-свободной грамматики определяется автоматом, который её принимает. Детерминированные контекстно-свободные грамматики принимаются детерминированными автоматами с магазинной памятью и могут быть разобраны за линейное время, например, с помощью LR-анализатора. Они являются строгим подмножеством контекстно-свободных грамматик, которые принимаются автоматами с магазинной памятью и могут быть разобраны за полиномиальное время, например, алгоритмом CYK. Неоднозначные контекстно-свободные грамматики могут быть недетерминированными. Например, язык палиндромов четной длины в алфавите из 0 и 1 имеет однозначную контекстно-свободную грамматику S → 0S0 | 1S1 | ε. Произвольную строку этого языка нельзя разобрать, не прочитав все её символы, что означает, что автомат с магазинной памятью должен перебирать альтернативные переходы состояний, чтобы учесть различные возможные длины частично разобранной строки. Тем не менее, устранение неоднозначности грамматики может привести к детерминированной контекстно-свободной грамматике и, следовательно, обеспечить более эффективный разбор. Генераторы компиляторов, такие как YACC, включают в себя средства для разрешения некоторых видов неоднозначности, например, с использованием ограничений приоритета и ассоциативности.
Неоднозначные языки
В то время как некоторые контекстно-свободные языки (множество строк, которые могут быть сгенерированы грамматикой) имеют как неоднозначные, так и однозначные грамматики, существуют контекстно-свободные языки, для которых не может существовать однозначной контекстно-свободной грамматики. Такие языки называются внутренне неоднозначными. Внутренне неоднозначных регулярных языков не существует. Существование внутренне неоднозначных контекстно-свободных языков было доказано теоремой Париха в 1961 году Рохитом Парихом в исследовательском отчете MIT. Язык является внутренне неоднозначным. Лемма Огдена может быть использована для доказательства того, что некоторые контекстно-свободные языки, такие как , являются внутренне неоднозначными. Доказательство можно найти на этой странице. Объединение с является внутренне неоднозначным. Этот набор является контекстно-свободным, поскольку объединение двух контекстно-свободных языков всегда является контекстно-свободным. Однако представляет доказательство того, что любая контекстно-свободная грамматика для этого объединенного языка не может однозначно разбирать строки вида. Дополнительные примеры и общий обзор методов доказательства внутренней неоднозначности контекстно-свободных языков приведены в работе Bassino и Nicaud (2011).
More examples, and a general review of techniques for proving inherent ambiguity of context free languages, are found given by Bassino and Nicaud (2011).