В информатике , неоднозначная грамматика является контекстно-свободной грамматикой , для которого существует строка , которая может иметь более чем один крайний левый вывод или дерево разбора , [1] в то время как однозначную грамматикаэто контекстно-свободная грамматика, для которой каждая допустимая строка имеет уникальное самое левое дерево производных или синтаксического анализа. Многие языки допускают как неоднозначные, так и недвусмысленные грамматики, в то время как некоторые языки допускают только неоднозначные грамматики. Любой непустой язык допускает неоднозначную грамматику, беря однозначную грамматику и вводя повторяющееся правило или синоним (единственный язык без неоднозначных грамматик - это пустой язык). Язык, допускающий только неоднозначные грамматики, называется по своей сути неоднозначным языком , и существуют по своей сути неоднозначные контекстно-свободные языки . Детерминированные контекстно-свободные грамматики всегда однозначны и являются важным подклассом однозначных грамматик; однако существуют недетерминированные однозначные грамматики.
Для языков компьютерного программирования справочная грамматика часто бывает неоднозначной из-за таких проблем, как проблема зависания else . Если они присутствуют, эти неоднозначности обычно разрешаются путем добавления правил приоритета или других контекстно-зависимых правил синтаксического анализа, поэтому общая грамматика фраз является однозначной. [ необходима цитата ] Некоторые алгоритмы синтаксического анализа (такие как ( Earley [2] или парсеры GLR ) могут генерировать наборы синтаксических деревьев (или "синтаксических лесов") из строк, которые синтаксически неоднозначны . [3])
Примеры
Банальный язык
Самый простой пример - это следующая неоднозначная грамматика для тривиального языка, состоящая только из пустой строки:
- 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:
Однако язык, который он генерирует, по своей сути не является двусмысленным; Ниже приводится однозначная грамматика, порождающая один и тот же язык:
- A → A + a | А - а | а
Болтается еще
Типичный пример неоднозначности в языках программирования - это проблема висячего else . Во многих языках else
оператор in if – then (–else) является необязательным, что приводит к тому, что вложенные условные выражения имеют несколько способов распознавания в терминах контекстно-свободной грамматики.
Конкретно, на многих языках можно писать условные выражения в двух допустимых формах: форма if-then и форма if-then-else - по сути, делая предложение else необязательным: [примечание 1]
В грамматике, содержащей правила
Заявление → если Условие, то Заявление | if Условие then Заявление else Заявление | ...Состояние → ...
могут появиться некоторые неоднозначные структуры фраз. Выражение
if a then if b then s else s2
может быть проанализирован как
если a, то начать, если b, то s конец, иначе s2
или как
если а то начало, если б то s иначе s2 конец
в зависимости от того, else
связан ли с первым if
или вторым if
.
Это решается по-разному на разных языках. Иногда грамматика изменяется, чтобы сделать ее недвусмысленной, например, требуя endif
утверждения или делая else
обязательным. В других случаях грамматика остается неоднозначной, но неоднозначность разрешается путем создания общей грамматики фразы контекстно-зависимой, например, путем связывания else
с ближайшим if
. В последнем случае грамматика однозначна, но контекстно-свободная грамматика неоднозначна. [ требуется разъяснение ]
Однозначная грамматика с множественными производными
Существование нескольких производных одной и той же строки недостаточно, чтобы указать, что грамматика неоднозначна; только несколько крайних левых производных (или, что то же самое, несколько деревьев синтаксического анализа) указывают на неоднозначность.
Например, простая грамматика
S → А + А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.
Только первый вывод является крайним левым.
Распознавание неоднозначных грамматик
Проблема решения о том, является ли произвольная грамматика неоднозначной, неразрешима, потому что можно показать, что она эквивалентна проблеме соответствия Поста . [4] По крайней мере, есть инструменты, реализующие некоторую процедуру полурешения для обнаружения двусмысленности контекстно-свободных грамматик. [5]
Эффективность контекстно-свободного разбора грамматики определяется автоматом, который его принимает. Детерминированные контекстно-свободные грамматики принимаются детерминированными выталкивающими автоматами и могут анализироваться за линейное время, например, парсером LR . [6] Это подмножество контекстно-свободных грамматик, которые принимаются автоматом выталкивания и могут быть проанализированы за полиномиальное время, например, с помощью алгоритма CYK . Однозначные контекстно-свободные грамматики могут быть недетерминированными.
Например, язык палиндромов четной длины на алфавите 0 и 1 имеет однозначную контекстно-свободную грамматику S → 0S0 | 1S1 | ε. Произвольная строка этого языка не может быть проанализирована, не прочитав сначала все ее буквы, что означает, что выталкивающий автомат должен пробовать альтернативные переходы между состояниями, чтобы приспособиться к различной возможной длине частично проанализированной строки. [7] Тем не менее, устранение грамматической двусмысленности может привести к детерминированной контекстно-свободной грамматике и, таким образом, обеспечить более эффективный синтаксический анализ. Генераторы компилятора, такие как YACC, включают функции для разрешения некоторых видов неоднозначности, например, с помощью ограничений приоритета и ассоциативности.
По своей сути неоднозначные языки
Существование по своей сути неоднозначных языков было доказано теоремой Париха в 1961 году Рохитом Парихом в исследовательском отчете Массачусетского технологического института. [8]
Хотя некоторые контекстно-свободные языки (набор строк, которые могут быть сгенерированы грамматикой) имеют как неоднозначную, так и однозначную грамматику, существуют контекстно-свободные языки, для которых не может существовать однозначная контекстно-свободная грамматика. Примером по своей сути неоднозначного языка является объединение с участием . Этот набор контекстно-независимый, поскольку объединение двух контекстно-свободных языков всегда контекстно-независимое. Но Хопкрофт и Ульман (1979) приводят доказательство того, что нет способа однозначно проанализировать строки в (неконтекстно-независимом) общем подмножестве.. [9]
Смотрите также
- Парсер GLR , тип парсера для неоднозначных и недетерминированных грамматик
- Парсер диаграмм , другой тип парсера для неоднозначных грамматик
- Синтаксическая двусмысленность
Рекомендации
- ^ Willem JM левелевский (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. ISBN 978-90-272-3250-2.
- ^ Скотт, Элизабет (1 апреля 2008 г.). «Разбор в стиле SPPF от распознавателей Earley» . Электронные заметки по теоретической информатике . 203 (2): 53–67. DOI : 10.1016 / j.entcs.2008.03.044 .
- ↑ Томита, Масару. « Эффективный алгоритм анализа без расширенного контекста ». Компьютерная лингвистика 13.1-2 (1987): 31-46.
- ^ Хопкрофт, Джон ; Мотвани, Раджив ; Ульман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. Теорема 9.20, с. 405–406. ISBN 0-201-44124-1.
- ^ Аксельссон, Роланд; Хельянко, Кейджо; Ланге, Мартин (2008). «Анализ контекстно-свободных грамматик с помощью инкрементального решателя SAT» (PDF) . Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'08), Рейкьявик, Исландия . Конспект лекций по информатике . 5126 . Springer-Verlag. С. 410–422. DOI : 10.1007 / 978-3-540-70583-3_34 .
- ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
- ^ Хопкрофт, Джон ; Мотвани, Раджив ; Ульман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. С. 249–253. ISBN 0-201-44124-1.
- ^ Парих, Рохит (январь 1961 г.). Устройства, генерирующие язык . Ежеквартальный отчет, Исследовательская лаборатория электроники, Массачусетский технологический институт.
- ^ стр.99-103, раздел 4.7
- Гросс, Морис (сентябрь 1964). «Внутренняя неоднозначность минимальных линейных грамматик» . Информация и контроль . 7 (3): 366–368. DOI : 10.1016 / S0019-9958 (64) 90422-X .
- Майкл, Харрисон (1978). Введение в теорию формального языка . Эддисон-Уэсли. ISBN 0201029553.
- Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли.
- Хопкрофт, Джон; Мотвани, Раджив; Ульман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон Уэсли. С. 217 .
- Брабранд, Клаус; Гигерих, Роберт; Мёллер, Андерс (март 2010 г.). «Анализ неоднозначности контекстно-свободных грамматик». Наука компьютерного программирования . Эльзевир. 75 (3): 176–191. CiteSeerX 10.1.1.86.3118 . DOI : 10.1016 / j.scico.2009.11.002 .
Заметки
- ^ В следующем примере используетсясинтаксис Паскаля.
Внешние ссылки
- dk.brics.grammar - анализатор грамматической неоднозначности.
- CFGAnalyzer - инструмент для анализа контекстно-свободных грамматик на предмет универсальности, неоднозначности и аналогичных свойств языка.