Проблема разрешения сдвига-уменьшения конфликта в моей грамматике - PullRequest
Новая
       54

Проблема разрешения сдвига-уменьшения конфликта в моей грамматике

6 голосов
/ 26 мая 2009

Я пытаюсь написать небольшой парсер с Ирония . К сожалению, я получаю «сдвиг-уменьшение конфликта». Грамматика не моя сильная сторона, и мне нужно сделать только одну маленькую вещь. Вот сокращенная грамматика, которая выдает ошибку: 

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

Что означает «конфликт сдвига-уменьшения» и как я могу его решить? Я понимаю, что это означает, что моя грамматика неоднозначна, но я не могу достаточно перевернуть свою логику, чтобы понять, как это сделать.

Добавлено: Для пояснения - "asd" - это просто буквальная строка "asd". Поэтому я ожидаю, что по этой грамматике будут проанализированы следующие выражения: 

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

Добавлено 2: Забыл сказать, корень грамматики - LogicalExpression.

Добавлено 3: Ах, я понял! Неоднозначность заключается в том, что выражение типа 

asd AND asd OR asd

можно интерпретировать двумя различными способами: 

(asd AND asd) OR asd
asd AND (asd OR asd)

Но как я могу решить это? Хорошо, я могу поставить один из И или ИЛИ, чтобы он был сильнее другого (я все равно намеревался). Но теперь я вижу, что ошибка появляется, даже если есть только один оператор. Другими словами, это также вызывает ту же ошибку: 

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

В этом случае я хочу это: 

asd OR asd OR asd

будет проанализирован на это: 

(asd OR asd) OR asd

Что такое недвусмысленный способ сделать это?

Добавлено 4: Понятно! 

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

При этом анализируются все логические выражения с приоритетом оператора NOT-> AND-> OR. «asd» можно заменить на выражение, предназначенное для ваших терминов.

Ответы [ 4 ]

3 голосов
/ 26 мая 2009

Ваша грамматика неоднозначна, если вы используете только один взгляд. Чтобы проиллюстрировать, что такое «asd»? Это ExpressionTerm или более длительный срок. Это конфликт сдвига-уменьшения. Я подозреваю, что и здесь есть конфликт с сокращением.

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

1 голос
/ 26 мая 2009

Конфликт Shift-Reduce означает, что ваша грамматика неоднозначна. С вашим рекурсивным правилом токен «asd» может быть интерпретирован как часть либо ExpressionTerm, либо LogicalExpression, и анализатор не может решить, какой именно. Нужно дополнительное правило, чтобы разорвать галстук.

0 голосов
/ 08 сентября 2013

грамматика неоднозначна в LL(1) или LALR(1), поскольку токен asd можно заменить в ExpressionTerm, а также LogicalExpression сгладить правила грамматики для разрешения конфликтов сдвига / уменьшения

0 голосов
/ 04 июня 2009

Конфликты с уменьшением сдвига - одна из самых сложных задач, которые нужно решить, когда дело доходит до парсеров. Самый простой способ проиллюстрировать конфликт в этом псевдокоде: 

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

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

Кроме того, вы можете использовать синтаксический анализатор LL (k) или LL (*). Эти типы парсеров не имеют сдвига / уменьшения неоднозначности. В зависимости от вашего приложения они могут быть проще или сложнее, чем анализатор LALR (1).

...