Почему двусмысленные грамматики плохи?

30

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

ИРАК МОНДАЛЬ
источник
1
Связанные, но не идентичные: softwareengineering.stackexchange.com/q/343872/206652 (отказ от ответственности: я написал принятый ответ)
marstato
Смотрите также: « Нахождение однозначной грамматики ».
Роб
1
Действительно, однозначная форма лучше подходит для практического использования, однозначная форма, использующая меньшее количество правил производств, строит меньшее дерево в высоком (следовательно, эффективный компилятор требует меньше времени для анализа). Большинство инструментов предоставляют возможность разрешить неоднозначность явно из сторонней грамматики.
Грижеш Чаухан
3
«каждый хочет избавиться от этого». Ну, это просто неправда. В коммерчески релевантных языках часто встречается двусмысленность по мере развития языков. Например, C ++ намеренно добавил неоднозначность std::vector<std::vector<int>>в 2011 году, которая раньше требовала пробела между ними >>. Основная идея заключается в том, что у этих языков гораздо больше пользователей, чем у поставщиков, поэтому исправление незначительного раздражения для пользователей оправдывает большую работу разработчиков.
MSalters

Ответы:

52

Рассмотрим следующую грамматику для арифметических выражений:

XX+XXXXXX/Xvarconst
Рассмотрим следующее выражение:
a-б-с
Какое его значение? Вот два возможных дерева разбора:

(X - X) - X введите описание изображения здесь

Согласно приведенному слева, мы должны интерпретировать a-б-с как (a-б)-с , что является обычной интерпретацией. Согласно тому, что справа, мы должны интерпретировать это как a-(б-с)знак равноa-б+с , что, вероятно, не то, что предполагалось.

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


Разобрать деревья, созданные с использованием генератора синтаксического дерева .

Юваль Фильмус
источник
12
@HIRAKMONDAL Тот факт, что синтаксис неоднозначен, не является реальной проблемой. проблема в том, что два разных дерева разбора имеют разное поведение. Если ваш язык имеет неоднозначную грамматику, но все деревья синтаксического анализа для выражения семантически эквивалентны, то это не будет проблемой (например, возьмите пример Yuval и рассмотрите случай, когда ваш единственный оператор +).
Бакуриу
14
@Bakuriu То, что вы сказали, - правда, но «семантически эквивалентно» - это сложная задача. Например, арифметика с плавающей запятой на самом деле не ассоциативна (поэтому два дерева «+» не будут эквивалентны). Кроме того, даже если ответ получился таким же образом, неопределенный порядок оценки имеет большое значение в языках, где выражения могут иметь побочные эффекты. Так что то, что вы сказали, технически верно, но на практике было бы весьма необычно для неопределенности грамматики не иметь последствий для этой грамматики.
Ричард Раст
Некоторые языки в настоящее время проверяют переполнение целых чисел в дополнениях, поэтому даже a + b + c для целых чисел зависит от порядка вычисления.
gnasher729
3
Хуже того, в некоторых случаях грамматика не дает никакого способа достичь альтернативного значения. Я видел это в языках запросов, где выбор экранирующей грамматики (например, удвоение специального символа для экранирования) делает некоторые запросы невозможными для выражения.
Стоп Harm Моника
12

В отличие от других существующих ответов [ 1 , 2 ], действительно есть область применения, где неоднозначные грамматики полезны . В области обработки естественного языка (NLP), когда вы хотите проанализировать естественный язык (NL) с помощью формальных грамматик, у вас возникает проблема, заключающаяся в том, что NL по своей сути неоднозначен на разных уровнях [адаптировано из Koh18, гл. 6.4]:

  • Синтаксическая двусмысленность:

    Петр преследовал мужчину в красной спортивной машине

    Был ли Питер или человек в красной спортивной машине?

  • Семантическая двусмысленность:

    Питер пошел в банк

    Банк, в котором можно сидеть, или банк, в котором можно снять деньги?

  • Прагматичная двусмысленность:

    Двое мужчин несли две сумки

    Они несли сумки вместе или каждый человек нес две сумки?

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

  1. Разбор NL с неоднозначной грамматикой
  2. Для каждого полученного AST: запустите генерацию модели, чтобы сгенерировать неоднозначные смысловые значения и исключить невозможные синтаксические неоднозначности из шага 1
  3. Для каждой полученной модели: сохраните ее в своем кэше.

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

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

Если вы хотите испачкать руки парсерами, способными выводить несколько производных для неоднозначной грамматики, взгляните на Grammatic Framework . Также [Кох18, гл. 5] имеет введение, показывающее что-то похожее на мой конвейер выше. Заметьте, однако, что, поскольку [Koh18] являются примечаниями к лекциям, сами записи могут быть не так просты для понимания без лекций.


Ссылки

[Koh18]: Майкл Колхазе. «Обработка естественного языка на основе логики. Зимний семестр 2018/19. Конспект лекций». URL: https://kwarc.info/teaching/LBS/notes.pdf . URL описания курса: https://kwarc.info/courses/lbs/ (на немецком языке)

[Ко18, гл. 5]: см. Главу 5 «Реализация фрагментов: грамматические и логические структуры», в [Koh18]

[Ко18, гл. 6.4] См. Главу 6.4 «Вычислительная роль двусмысленностей» в [Koh18].

ComFreek
источник
Огромное
1
Не говоря уже о проблемах с Буффало Буффало Буффало Буффало Буффало Буффало ... для подходящего количества буйволов
Хаген фон Айцен
Вы пишете «напротив», но я бы назвал это другой стороной медали из того, что я ответил. Разбор естественных языков с их неоднозначными грамматиками настолько сложен, что традиционные парсеры не могут этого сделать!
Дэвислор
1
@ComFreek Я должен быть более точным здесь. Краткий взгляд на GF (спасибо за ссылку!) Показывает, что он читает не зависящие от контекста грамматики с тремя расширениями (такими как разрешение на дублирование) и возвращает список всех возможных дериваций. Алгоритмы для этого были примерно с 50-х годов. Тем не менее, способность обрабатывать полностью общие CFG означает, что ваши наихудшие сценарии взорвутся, а на практике даже при использовании общего синтаксического анализатора, такого как GLL, инженеры-программисты пытаются использовать подмножество CFG, таких как грамматики LL, которые могут быть проанализирован более эффективно.
Дэвислор
1
@ComFreek Так что не то, чтобы компьютеры не могли обрабатывать CFG (хотя естественные языки на самом деле не являются контекстно-свободными, и фактически полезный машинный перевод использует совершенно разные методы). Это то, что если вам требуется, чтобы ваш синтаксический анализатор обрабатывал неоднозначность, это исключает определенные сочетания клавиш, которые сделали бы его более эффективным.
Дэвислор
10

Даже если существует четко определенный способ обработки неоднозначности (например, неоднозначные выражения являются синтаксическими ошибками), эти грамматики по-прежнему вызывают проблемы. Как только вы вводите двусмысленность в грамматику, парсер больше не может быть уверен, что первое совпадение, которое он получает, является окончательным. Нужно продолжать пробовать все остальные способы анализа заявления, чтобы исключить любую двусмысленность. Вы также не имеете дело с чем-то простым, например с языком LL (1), поэтому вы не можете использовать простой, маленький, быстрый парсер. В вашей грамматике есть символы, которые могут быть прочитаны несколькими способами, поэтому вы должны быть готовы к тому, что вы будете возвращаться назад.

В некоторых доменах с ограниченным доступом вам, возможно, удастся доказать, что все возможные способы анализа выражения эквивалентны (например, потому что они представляют ассоциативную операцию). (a + b) + c = a + (b + c).

Davislor
источник
9

Имеет ли IF a THEN IF b THEN x ELSE yсреднее значение

IF a THEN
    IF b THEN
        x
    ELSE
        y

или

IF a THEN
    IF b THEN x
ELSE
    y

? Ака еще болтающаяся проблема .

Дэвид Ричерби
источник
1
Это хороший пример, показывающий, что даже не неоднозначная грамматика (как в Java, C, C ++, ...) допускает явную (!) Неоднозначность с человеческой точки зрения. Несмотря на то, что с формальной и вычислительной точки зрения все в порядке, теперь у нас возникла проблема разработки без UX / без ошибок.
ComFreek,
5

Возьмем самый неприятный анализ в C ++, например:

bar foo(foobar());

Является ли это объявлением функции fooтипа bar(foobar())(параметр является указателем функции, возвращающим a foobar), или объявлением переменной fooтипа intи инициализируется инициализацией по умолчанию foobar?

Это дифференцируется в компиляторах, предполагая первое, если выражение внутри списка параметров не может быть интерпретировано как тип.

когда вы получаете такое неоднозначное выражение, компилятор имеет 2 варианта

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

  2. ошибка и требует устранения неоднозначности в любом случае

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

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

чокнутый урод
источник
5

Я думаю, что вопрос содержит предположение, которое в лучшем случае является только правильным.

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

Например, если вы посмотрите на грамматики, скомпилированные с помощью yacc (или аналогичные, такие как bison или byacc), вы обнаружите, что довольно многие выдают предупреждения о «N сдвигах / сокращениях конфликтов» при их компиляции. Когда yacc сталкивается с конфликтом сдвига / уменьшения, это говорит о неоднозначности в грамматике.

Однако конфликт сдвига / уменьшения обычно является довольно незначительной проблемой. Генератор парсера разрешит конфликт в пользу «сдвига», а не уменьшения. Грамматика отлично подходит, если это то, что вы хотите (и, похоже, на практике она работает очень хорошо).

Конфликт сдвига / уменьшения обычно возникает в случае этого общего порядка (с использованием заглавных букв для нетерминалов и строчных букв для терминалов):

A -> B | c
B -> a | c

Когда мы сталкиваемся с a c, возникает двусмысленность: следует ли нам анализировать cнепосредственно как A, или мы должны анализировать как a B, что, в свою очередь, является A? В таком случае yacc и другие выберут более простой / короткий маршрут и проанализируют его как cпрямой A, а не как маршрут c-> B-> A. Это может быть неправильно, но если это так, это, вероятно, означает, что у вас действительно простая ошибка в вашей грамматике, и вы вообще не должны допускать эту cопцию как возможность A.

Теперь, напротив, мы могли бы иметь что-то более похожее на это:

A -> B | C
B -> a | c
C -> b | c

Теперь, когда мы сталкиваемся с, cу нас возникает конфликт между тем, рассматривать ли cкак a Bили a C. Вероятность того, что стратегия автоматического разрешения конфликтов выберет то, чего мы действительно хотим, гораздо меньше. Ни один из них не является «сдвигом» - оба являются «сокращением», так что это «конфликт уменьшения / уменьшения» (который привыкли считать yacc и тому подобное, как правило, гораздо более серьезной проблемой, чем конфликт сдвига / уменьшения).

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

Джерри Гроб
источник
чувак, жаль, что у меня не было этого превосходного объяснения сдвигово-уменьшающих конфликтов 5 месяцев назад! ^^; +1
HotelCalifornia