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

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

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

Примеры

Тривиальный язык

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

А → А | е

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

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

А → е

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

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

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

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

А → аА | ε

…но также имеет неоднозначную грамматику:

А → аА | Аа | ε

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

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

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

А → А + А | А − А | а

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

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

Другой пример: грамматика неоднозначна, поскольку существует два дерева разбора для строки a + a − a :

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

А → А + а | А - а | а

висит еще

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

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

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

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

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

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

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

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

Однозначные контекстно-свободные грамматики могут быть недетерминированными. четной длины Например, язык палиндромов в алфавите 0 и 1 имеет однозначную контекстно-свободную грамматику S → 0S0 | 1С1 | е. Произвольная строка этого языка не может быть проанализирована без предварительного чтения всех ее символов, а это означает, что автомату с выталкиванием вниз приходится пробовать альтернативные переходы состояний, чтобы приспособиться к различным возможным длинам полуразобранной строки. ^[7]

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

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

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

Не существует по своей сути двусмысленных регулярных языков. ^[8]^[9]

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

Язык $\{x|x=a^{n}b^{m}a^{n^{\prime }}b^{m}{\text{ or }}x=a^{n}b^{m}a^{n}b^{m^{\prime }},{\text{ where }}n,n',m,m'\geq 1\}$ по своей сути неоднозначен. ^[11]

Лемма Огдена ^[12] можно использовать для доказательства того, что некоторые контекстно-свободные языки, такие как $\{a^{n}b^{m}c^{m}|m,n\geq 1\}\cup \{a^{m}b^{m}c^{n}|m,n\geq 1\}$ , по своей сути неоднозначны. См. эту страницу для доказательства.

Союз $\{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}$ с $\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}$ по своей сути неоднозначен. Этот набор является контекстно-свободным, поскольку объединение двух контекстно-свободных языков всегда является контекстно-свободным. Но Хопкрофт и Ульман (1979) приводят доказательство того, что любая контекстно-свободная грамматика для этого языка объединения не может однозначно анализировать строки вида $a^{n}b^{n}c^{n}d^{n},(n>0)$ . ^[13]

Дополнительные примеры и общий обзор методов доказательства присущей контекстно-свободным языкам неоднозначности можно найти у Бассино и Нико (2011). ^[14]

См. также

GLR-парсер — тип парсера для неоднозначных и недетерминированных грамматик.
Анализатор диаграмм , еще один тип анализатора неоднозначных грамматик.
Синтаксическая неоднозначность

Ссылки

^ Виллем Дж. М. Левельт (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. ISBN 978-90-272-3250-2 .
^ Скотт, Элизабет (1 апреля 2008 г.). «Разбор в стиле SPPF от распознавателей Earley» . Электронные заметки по теоретической информатике . 203 (2): 53–67. дои : 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. Шпрингер-Верлаг. стр. 410–422. дои : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6 .
^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо». Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 .
^ Хопкрофт, Джон ; Мотвани, Раджив ; Уллман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Аддисон-Уэсли. стр. 249–253. ISBN 0-201-44124-1 .
^ Книга, Р.; Эвен, С.; Грейбах, С.; Отт, Г. (февраль 1971 г.). «Неоднозначность в графиках и выражениях» . Транзакции IEEE на компьютерах . С-20 (2): 149–153. дои : 10.1109/tc.1971.223204 . ISSN 0018-9340 . S2CID 20676251 .
^ «формальные языки. Можно ли сделать регулярные выражения однозначными?» . MathOverflow . Проверено 23 февраля 2023 г.
^ Парих, Рохит (январь 1961 г.). Устройства, генерирующие язык . Ежеквартальный отчет о проделанной работе, Исследовательская лаборатория электроники, Массачусетский технологический институт.
^ Парих, Рохит Дж. (1 октября 1966 г.). «О контекстно-свободных языках» . Журнал АКМ . 13 (4): 570–581. дои : 10.1145/321356.321364 . ISSN 0004-5411 . S2CID 12263468 . Здесь: Теорема 3.
^ Огден, Уильям (сентябрь 1968 г.). «Полезный результат для доказательства внутренней двусмысленности» . Теория математических систем . 2 (3): 191–194. дои : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .
^ стр.99-103, раздел 4.7.
^ Фредерик Бассино и Сирил Нико (16 декабря 2011 г.). «Филипп Флажоле и аналитическая комбинаторика: присущая контекстно-свободным языкам неоднозначность» (PDF) . Архивировано (PDF) из оригинала 25 сентября 2022 г.

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

Примечания

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

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

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

[Levelt2008-1] Виллем Дж. М. Левельт (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. ISBN 978-90-272-3250-2 .

[2] Скотт, Элизабет (1 апреля 2008 г.). «Разбор в стиле SPPF от распознавателей Earley» . Электронные заметки по теоретической информатике . 203 (2): 53–67. дои : 10.1016/j.entcs.2008.03.044 .

[3] Томита, Масару. « Эффективный алгоритм синтаксического анализа с расширенным контекстом ». Компьютерная лингвистика 13.1-2 (1987): 31-46.

[5] Хопкрофт, Джон ; Мотвани, Раджив ; Уллман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Аддисон-Уэсли. Теорема 9.20, стр. 405–406. ISBN 0-201-44124-1 .

[6] Аксельссон, Роланд; Хельянко, Кейо; Ланге, Мартин (2008). «Анализ контекстно-свободных грамматик с использованием инкрементного решателя SAT» (PDF) . Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'08), Рейкьявик, Исландия . Конспекты лекций по информатике . Том. 5126. Шпрингер-Верлаг. стр. 410–422. дои : 10.1007/978-3-540-70583-3_34 . ISBN 978-3-540-70582-6 .

[7] Кнут, DE (июль 1965 г.). «О переводе языков слева направо». Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 .

[8] Хопкрофт, Джон ; Мотвани, Раджив ; Уллман, Джеффри (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Аддисон-Уэсли. стр. 249–253. ISBN 0-201-44124-1 .

[9] Книга, Р.; Эвен, С.; Грейбах, С.; Отт, Г. (февраль 1971 г.). «Неоднозначность в графиках и выражениях» . Транзакции IEEE на компьютерах . С-20 (2): 149–153. дои : 10.1109/tc.1971.223204 . ISSN 0018-9340 . S2CID 20676251 .

[10] «формальные языки. Можно ли сделать регулярные выражения однозначными?» . MathOverflow . Проверено 23 февраля 2023 г.

[11] Парих, Рохит (январь 1961 г.). Устройства, генерирующие язык . Ежеквартальный отчет о проделанной работе, Исследовательская лаборатория электроники, Массачусетский технологический институт.

[12] Парих, Рохит Дж. (1 октября 1966 г.). «О контекстно-свободных языках» . Журнал АКМ . 13 (4): 570–581. дои : 10.1145/321356.321364 . ISSN 0004-5411 . S2CID 12263468 . Здесь: Теорема 3.

[13] Огден, Уильям (сентябрь 1968 г.). «Полезный результат для доказательства внутренней двусмысленности» . Теория математических систем . 2 (3): 191–194. дои : 10.1007/bf01694004 . ISSN 0025-5661 . S2CID 13197551 .

[14] стр.99-103, раздел 4.7.

[15] Фредерик Бассино и Сирил Нико (16 декабря 2011 г.). «Филипп Флажоле и аналитическая комбинаторика: присущая контекстно-свободным языкам неоднозначность» (PDF) . Архивировано (PDF) из оригинала 25 сентября 2022 г.

[4] В следующем примере используется Pascal . синтаксис

[1]

[2]

[3]

[примечание 1]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]