Проблема с устранением конфликта shift-reduce в моей грамматике

Question

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

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->И->ИЛИ."asd" может быть заменен выражением, предназначенным для ваших условий.

Answer 1

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

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

Answer 2

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

Answer 3

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

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).

Answer 4

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