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

Ambiguous grammar

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

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

Примеры

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

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

A → A | ε

… Означает, что продукция может быть либо снова самой собой, либо пустой строкой. Таким образом, пустая строка имеет самые левые производные длины 1, 2, 3 и любой длины, в зависимости от того, сколько раз используется правило 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 | А - а | а

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

Основная статья: Болтается еще

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

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

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

Заявление → если Состояние тогда Заявление | если Состояние тогда утверждение еще Заявление | ... Условие → ...

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

если а тогда если б тогда s еще s2

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

если а тогда начать если б тогда s конец еще s2

или как

если а тогда начать если б тогда s еще s2 конец

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

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

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

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

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

S → A + AA → 0 | 1

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

S ⇒ А + А ⇒ 0 + А ⇒ 0 + 0

и

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

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

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

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

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

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

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

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

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

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

использованная литература

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

Заметки

  1. ^ В следующем примере используется Паскаль синтаксис

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

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