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

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

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

• 1 Примеры
  • 1.1 Простой язык
  • 1.2 Унарная строка
  • 1.3 Сложение и вычитание
  • 1.4 Висячие else
  • 1.5 Однозначная грамматика с множественными производными
• 2 Распознавание неоднозначных грамматик
• 3 Неоднозначные языки
• 4 См. Также
• 5 Ссылки
• 6 Примечания
• 7 Внешние ссылки

Обычный язык

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

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

Dangling else

Распространенным примером неоднозначности в языках программирования является проблема dangling else. Во многих языках elseв операторе If – then (–else) является необязательным, что приводит к появлению нескольких способов распознавания с точки зрения контекстно-свободной грамматики.

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

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

оператор → if Condition then Statement | if Condition then Statement else Statement |... Условие →...

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

ifa, затем ifb, затем s else s2

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

ifa, затемbegin ifb затем s endelse s2

или как

ifa затемbegin ifb затем 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 году Рохитом Парихом в исследовательском отчете MIT.

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

• анализатор GLR, тип синтаксического анализатора для неоднозначных и недетерминированных грамматик
• Анализатор диаграмм, другой тип синтаксического анализатора для неоднозначных грамматик
• Синтаксическая неоднозначность

1. ^Виллем Дж. М. Левелт (2008). Введение в теорию формальных языков и автоматов. John Benjamins Publishing. ISBN 90-272-3250-4.
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. ^Hopcroft, Джон ; Мотвани, Раджив ; Уллман, Джеффри (20 01). Введение в теорию автоматов, языки и вычисления (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. ^Кнут, Д. Э. (июль 1965 г.). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2. Архивировано из оригинального (PDF) 15 марта 2012 г. Дата обращения 29 мая 2011 г. CS1 maint: ref = harv (ссылка )
7. ^Хопкрофт, Джон ; Мотвани, Раджив ; Уллман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Addison-Wesley. Pp. 249–253. ISBN 0-201-44124-1.
8. ^Парих, Рохит (январь 1961 г.). Устройства, генерирующие язык. Ежеквартальный отчет, Исследовательская лаборатория электроники, Массачусетский технологический институт.
9. ^стр. 99-103, Sect.4.7

• Гросс, Морис (сентябрь 1964 г.) «Внутренняя неоднозначность минимальных линейных грамматик». Информация и контроль. Информация и контроль. 7 (3): 366–368. doi : 10.1016 / S0019-9958 (64) 90422-X.
• Майкл, Харрисон (1978). Введение в теорию формального языка. Аддисон-Уэсли.. ISBN 0201029553.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Аддисон-Уэсли. CS1 maint: ref = harv (lin k )
• Хопкрофт, Джон; Мотвани, Раджив; Ульман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон Уэсли. стр. 217. CS1 maint: ref = harv (ссылка )
• Брабранд, Клаус; Гигерих, Роберт; Мёллер, Андерс (март 2010 г.). «Анализ неоднозначности контекстно-свободного Грамматики ». Наука компьютерного программирования. Elsevier. 75 (3): 176–191. CiteSeerX 10.1.1.86.3118. doi : 10.1016 / j.scico.2009.11.002. CS1 maint: ref = harv (ссылка )

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