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

В информатике , неоднозначная грамматика является контекстно-свободной грамматикой , для которых существует строка , которая может иметь более одного левое порождение или синтаксическое дерево , в то время как однозначная грамматика является контекстно-свободной грамматикой , для которых каждая допустимой строка имеет уникальную крайнюю левую дерево вывода или синтаксического анализа. Многие языки допускают как неоднозначные, так и недвусмысленные грамматики, в то время как некоторые языки допускают только неоднозначные грамматики. Любой непустой язык допускает неоднозначную грамматику, беря однозначную грамматику и вводя повторяющееся правило или синоним (единственный язык без неоднозначных грамматик - это пустой язык). Язык, допускающий только неоднозначные грамматики, называется по своей сути неоднозначным языком , и существуют по своей сути неоднозначные контекстно-свободные языки . Детерминированные контекстно-свободные грамматики всегда однозначны и являются важным подклассом однозначных грамматик; однако существуют недетерминированные однозначные грамматики.

Для языков компьютерного программирования справочная грамматика часто бывает неоднозначной из-за таких проблем, как проблема зависания else . Если они присутствуют, эти неоднозначности обычно разрешаются путем добавления правил приоритета или других контекстно-зависимых правил синтаксического анализа, поэтому общая грамматика фразы является однозначной. Некоторые алгоритмы синтаксического анализа (такие как ( анализаторы Эрли или GLR ) могут генерировать наборы деревьев синтаксического анализа (или "леса синтаксического анализа") из строк, которые синтаксически неоднозначны .

Примеры

Банальный язык

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

A → A | ε

… Означает, что продукция может быть либо самим собой, либо пустой строкой. Таким образом, пустая строка имеет самые левые производные длины 1, 2, 3 и даже любой длины, в зависимости от того, сколько раз используется правило A → A.

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

A → ε

… Означает, что уникальная продукция может создать только пустую строку, которая является уникальной строкой в ​​языке.

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

Унарная строка

Регулярный язык из одинарных строк заданного символа, скажет 'a'(регулярное выражение a*), имеет однозначную грамматику:

A → aA | ε

… Но также имеет двусмысленную грамматику:

A → aA | Аа | ε

Они соответствуют созданию правоассоциативного дерева (для однозначной грамматики) или разрешению как левой, так и правой ассоциации. Это подробно описано ниже.

Сложение и вычитание

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

A → A + A | А - А | а

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

     А → А + А      А → А + А
     → а + А      → A + A + A (Первый A заменяется на A + A. Замена второго A приведет к аналогичному выводу)
     → а + А + А      → а + А + А
     → а + а + А      → а + а + А
     → а + а + а      → а + а + а

В качестве другого примера, грамматика неоднозначна, поскольку есть два дерева синтаксического анализа для строки a + a - a:

Крайние левые производные jaredwf.svg

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

A → A + a | А - а | а

Болтается еще

Типичный пример неоднозначности в языках программирования - это проблема висячего else . Во многих языках elseоператор in if – then (–else) является необязательным, что приводит к тому, что вложенные условные выражения имеют несколько способов распознавания в терминах контекстно-свободной грамматики.

Конкретно, на многих языках можно писать условные выражения в двух допустимых формах: форма if-then и форма if-then-else - по сути, делая предложение else необязательным:

В грамматике, содержащей правила

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

могут появиться некоторые неоднозначные структуры фраз. Выражение

if a then if b then s else s2

может быть проанализирован как

if a then begin if b then s end else s2

или как

if a then begin if b then s else s2 end

в зависимости от того, elseсвязан ли с первым ifили вторым if.

Это решается по-разному на разных языках. Иногда грамматика модифицируется, чтобы сделать ее недвусмысленной, например, требуя endifутверждения или делая elseобязательным. В других случаях грамматика остается неоднозначной, но неоднозначность разрешается путем создания общей грамматики фразы контекстно-зависимой, например, путем связывания elseс ближайшим if. В последнем случае грамматика однозначна, но контекстно-свободная грамматика неоднозначна.

Однозначная грамматика с множественными производными

Существование нескольких производных одной и той же строки недостаточно, чтобы указать, что грамматика неоднозначна; только несколько крайних левых производных (или, что то же самое, несколько деревьев синтаксического анализа) указывают на неоднозначность.

Например, простая грамматика

S → A + A
A → 0 | 1

является однозначной грамматикой для языка {0 + 0, 0 + 1, 1 + 0, 1 + 1}. Хотя каждая из этих четырех строк имеет только одну самую левую производную, у нее есть два разных производных, например

S  A + A ⇒ 0 + A ⇒ 0 + 0

а также

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

Только первый вывод является крайним левым.

Распознавание неоднозначных грамматик

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

Эффективность контекстно-свободного разбора грамматики определяется автоматом, который его принимает. Детерминированные контекстно-свободные грамматики принимаются детерминированными выталкивающими автоматами и могут анализироваться за линейное время, например, парсером LR . Это подмножество контекстно-свободных грамматик, которые принимаются автоматом выталкивания и могут быть проанализированы за полиномиальное время, например, с помощью алгоритма CYK . Однозначные контекстно-свободные грамматики могут быть недетерминированными.

Например, язык палиндромов четной длины на алфавите 0 и 1 имеет однозначную контекстно-свободную грамматику S → 0S0 | 1S1 | ε. Произвольная строка этого языка не может быть проанализирована, не прочитав сначала все ее буквы, что означает, что выталкивающий автомат должен пробовать альтернативные переходы между состояниями, чтобы приспособиться к различной возможной длине частично проанализированной строки. Тем не менее, устранение грамматической двусмысленности может привести к детерминированной контекстно-свободной грамматике и, таким образом, обеспечить более эффективный синтаксический анализ. Генераторы компилятора, такие как YACC, включают функции для разрешения некоторых видов неоднозначности, например, с помощью ограничений приоритета и ассоциативности.

По своей сути неоднозначные языки

Существование по своей сути неоднозначных языков было доказано теоремой Париха в 1961 году Рохитом Парихом в исследовательском отчете Массачусетского технологического института.

В то время как некоторые контекстно-свободные языки (набор строк, которые могут быть сгенерированы грамматикой) имеют как неоднозначную, так и однозначную грамматику, существуют контекстно-свободные языки, для которых не может существовать однозначная контекстно-свободная грамматика. Примером по своей сути неоднозначного языка является объединение с . Этот набор контекстно-независимый, поскольку объединение двух контекстно-свободных языков всегда контекстно-независимое. Но Хопкрофт и Ульман (1979) приводят доказательство того, что не существует способа однозначного синтаксического анализа строк в (неконтекстно-независимом) общем подмножестве .

Смотрите также

Рекомендации

  1. ^ Willem JM левелевский (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. ISBN 978-90-272-3250-2.
  2. Скотт, Элизабет (1 апреля 2008 г.). «Разбор в стиле SPPF от распознавателей Earley» . Электронные заметки по теоретической информатике . 203 (2): 53–67. DOI : 10.1016 / j.entcs.2008.03.044 .
  3. Томита, Масару. « Эффективный алгоритм анализа без расширенного контекста ». Компьютерная лингвистика 13.1-2 (1987): 31-46.
  4. ^ Хопкрофт, Джон ; Мотвани, Раджив ; Ульман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. Теорема 9.20, с. 405–406. ISBN 0-201-44124-1.
  5. ^ Аксельссон, Роланд; Хельянко, Кейджо; Ланге, Мартин (2008). «Анализ контекстно-свободных грамматик с помощью инкрементального решателя SAT» (PDF) . Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'08), Рейкьявик, Исландия . Конспект лекций по информатике . 5126 . Springer-Verlag. С. 410–422. DOI : 10.1007 / 978-3-540-70583-3_34 .
  6. Knuth, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
  7. ^ Хопкрофт, Джон ; Мотвани, Раджив ; Ульман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. С. 249–253. ISBN 0-201-44124-1.
  8. ^ Рарикх Рохит (январь 1961). Устройства, генерирующие язык . Ежеквартальный отчет, Исследовательская лаборатория электроники, Массачусетский технологический институт.
  9. ^ стр.99-103, раздел 4.7

Заметки

Внешние ссылки

  • dk.brics.grammar - анализатор грамматической неоднозначности.
  • CFGAnalyzer - инструмент для анализа контекстно-свободных грамматик на предмет универсальности, неоднозначности и аналогичных свойств языка.