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

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

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

Это анализирует все логические выражения с приоритетом оператора НЕ-> И-> ИЛИ. "asd" можно заменить выражением, предназначенным для ваших условий.


parsing grammar shift-reduce-conflict irony
person Vilx-    schedule 26.05.2009    source источник
comment
Хех, если подумать, я начинаю вспоминать эту закономерность со времен моей учебы в университете. : D   -  person Vilx-    schedule 26.05.2009

Ответы (4)


arrow_upward
3
arrow_downward

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

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

person leppie    schedule 26.05.2009
comment
asd - это просто буквальная строка asd. - person Vilx-; 26.05.2009
comment
Я все еще не понимаю. И и ИЛИ в этом случае должны иметь одинаковый приоритет. - person Vilx-; 26.05.2009
comment
При просмотре вперед на 1 символ вы можете забыть об И и ИЛИ. Конфликт раньше :) - person leppie; 26.05.2009
comment
Я изменил свой вопрос, еще больше упростив проблему. Но как решить эту проблему? - person Vilx-; 26.05.2009

arrow_upward
1
arrow_downward

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

person dwc    schedule 26.05.2009

arrow_upward
0
arrow_downward

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

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

person brianegge    schedule 04.06.2009

arrow_upward
0
arrow_downward

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

person Gourav Saha    schedule 08.09.2013