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

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

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

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

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

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

В отличие от других существующих ответов [ 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].

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

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

Имеет ли 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

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

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

bar foo(foobar());

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

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

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

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

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

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

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

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

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

Например, если вы посмотрите на грамматики, скомпилированные с помощью 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 и тому подобное, как правило, гораздо более серьезной проблемой, чем конфликт сдвига / уменьшения).

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