Как решить грамматическую неоднозначность LR(1) между троичными выражениями (a ? b : c) и, возможно, выражениями (a?)?

Я создал грамматику, урезанная версия которой воспроизводится ниже:

(0) exp1: ternary;
(1) exp1: exp2;
(2) ternary: exp2 "?" exp1 ":" exp1;
(3) exp2: exp2 "+" exp3;
(4) exp2: exp3;
(5) exp3: maybe;
(6) exp3: "1";
(7) maybe: exp3 "?";

Я считаю, что этот язык однозначен и должен быть LR-разборным. (Пожалуйста, дайте мне знать, если я ошибаюсь!)

Однако, когда я пытаюсь сгенерировать анализатор LR(1) для этой грамматики, я получаю конфликты сдвига/уменьшения, потому что, когда анализатор видит exp3 с опережением ?, он не знает, следует ли сдвигать или уменьшать:

Conflicts in state 3:
    Reduction using rule 4: exp2:  exp3 · | "?"
    Shift to state 6

Conflicts in state 9:
    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"
    Shift to state 6

Conflicts in state 13:
    Reduction using rule 4: exp2:  exp3 · | "?"
    Shift to state 16

Conflicts in state 20:
    Reduction using rule 4: exp2:  exp3 · | "?"
    Shift to state 23

Conflicts in state 25:
    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"
    Shift to state 23

Conflicts in state 28:
    Reduction using rule 3: exp2:  exp2 "+" exp3 · | "?"
    Shift to state 16

Есть ли разумный способ сделать этот язык LR(1)-парсируемым (без конфликтов)?

Или GLR (или, может быть, LR(2)?) — мои единственные реалистичные варианты для такого языка?
(Или я вообще ошибаюсь, полагая, что язык недвусмыслен с самого начала?)

Для справки, сгенерированный мной неоднозначный конечный автомат выглядит следующим образом (где ♦ — EOF):

State 0:
    exp1:  · ternary | {♦} → shift 1
    ternary:  · exp2 "?" exp1 ":" exp1 | {♦} → shift 2
    exp2:  · exp2 "+" exp3 | {"?", "+"} → shift 2
    exp2:  · exp3 | {"?", "+"} → shift 3
    exp3:  · maybe | {"?", "+"} → shift 4
    exp3:  · "1" | {"?", "+"} → shift 5
    maybe:  · exp3 "?" | {"?", "+"} → shift 3

State 1:
    exp1:  ternary · | {♦} → reduce 0

State 2:
    ternary:  exp2 · "?" exp1 ":" exp1 | {♦} → shift 7
    exp2:  exp2 · "+" exp3 | {"?", "+"} → shift 8

State 3:
    exp2:  exp3 · | {"+"} → reduce 4
    exp2:  exp3 · | {"?"} → reduce 4 shift 6
    maybe:  exp3 · "?" | {"?", "+"} → reduce 4 shift 6

State 4:
    exp3:  maybe · | {"?", "+"} → reduce 5

State 5:
    exp3:  "1" · | {"?", "+"} → reduce 6

State 6:
    maybe:  exp3 "?" · | {"?", "+"} → reduce 7

State 7:
    exp1:  · ternary | {":"} → shift 10
    exp1:  · exp2 | {":"} → shift 11
    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11
    ternary:  exp2 "?" · exp1 ":" exp1 | {♦} → shift 12
    exp2:  · exp2 "+" exp3 | {"?", ":", "+"} → shift 11
    exp2:  · exp3 | {"?", ":", "+"} → shift 13
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 13

State 8:
    exp2:  exp2 "+" · exp3 | {"?", "+"} → shift 9
    exp3:  · maybe | {"?", "+"} → shift 4
    exp3:  · "1" | {"?", "+"} → shift 5
    maybe:  · exp3 "?" | {"?", "+"} → shift 9

State 9:
    exp2:  exp2 "+" exp3 · | {"+"} → reduce 3
    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 6
    maybe:  exp3 · "?" | {"?", "+"} → reduce 3 shift 6

State 10:
    exp1:  ternary · | {":"} → reduce 0

State 11:
    exp1:  exp2 · | {":"} → reduce 1
    ternary:  exp2 · "?" exp1 ":" exp1 | {":"} → shift 26
    exp2:  exp2 · "+" exp3 | {"?", ":", "+"} → shift 27

State 12:
    ternary:  exp2 "?" exp1 · ":" exp1 | {♦} → shift 17

State 13:
    exp2:  exp3 · | {":", "+"} → reduce 4
    exp2:  exp3 · | {"?"} → reduce 4 shift 16
    maybe:  exp3 · "?" | {"?", ":", "+"} → reduce 4 shift 16

State 14:
    exp3:  maybe · | {"?", ":", "+"} → reduce 5

State 15:
    exp3:  "1" · | {"?", ":", "+"} → reduce 6

State 16:
    maybe:  exp3 "?" · | {"?", ":", "+"} → reduce 7

State 17:
    exp1:  · ternary | {♦} → shift 1
    exp1:  · exp2 | {♦} → shift 18
    ternary:  · exp2 "?" exp1 ":" exp1 | {♦} → shift 18
    ternary:  exp2 "?" exp1 ":" · exp1 | {♦} → shift 19
    exp2:  · exp2 "+" exp3 | {♦, "?", "+"} → shift 18
    exp2:  · exp3 | {♦, "?", "+"} → shift 20
    exp3:  · maybe | {♦, "?", "+"} → shift 21
    exp3:  · "1" | {♦, "?", "+"} → shift 22
    maybe:  · exp3 "?" | {♦, "?", "+"} → shift 20

State 18:
    exp1:  exp2 · | {♦} → reduce 1
    ternary:  exp2 · "?" exp1 ":" exp1 | {♦} → shift 7
    exp2:  exp2 · "+" exp3 | {♦, "?", "+"} → shift 24

State 19:
    ternary:  exp2 "?" exp1 ":" exp1 · | {♦} → reduce 2

State 20:
    exp2:  exp3 · | {♦, "+"} → reduce 4
    exp2:  exp3 · | {"?"} → reduce 4 shift 23
    maybe:  exp3 · "?" | {♦, "?", "+"} → reduce 4 shift 23

State 21:
    exp3:  maybe · | {♦, "?", "+"} → reduce 5

State 22:
    exp3:  "1" · | {♦, "?", "+"} → reduce 6

State 23:
    maybe:  exp3 "?" · | {♦, "?", "+"} → reduce 7

State 24:
    exp2:  exp2 "+" · exp3 | {♦, "?", "+"} → shift 25
    exp3:  · maybe | {♦, "?", "+"} → shift 21
    exp3:  · "1" | {♦, "?", "+"} → shift 22
    maybe:  · exp3 "?" | {♦, "?", "+"} → shift 25

State 25:
    exp2:  exp2 "+" exp3 · | {♦, "+"} → reduce 3
    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 23
    maybe:  exp3 · "?" | {♦, "?", "+"} → reduce 3 shift 23

State 26:
    exp1:  · ternary | {":"} → shift 10
    exp1:  · exp2 | {":"} → shift 11
    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11
    ternary:  exp2 "?" · exp1 ":" exp1 | {":"} → shift 29
    exp2:  · exp2 "+" exp3 | {"?", ":", "+"} → shift 11
    exp2:  · exp3 | {"?", ":", "+"} → shift 13
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 13

State 27:
    exp2:  exp2 "+" · exp3 | {"?", ":", "+"} → shift 28
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 28

State 28:
    exp2:  exp2 "+" exp3 · | {":", "+"} → reduce 3
    exp2:  exp2 "+" exp3 · | {"?"} → reduce 3 shift 16
    maybe:  exp3 · "?" | {"?", ":", "+"} → reduce 3 shift 16

State 29:
    ternary:  exp2 "?" exp1 · ":" exp1 | {":"} → shift 30

State 30:
    exp1:  · ternary | {":"} → shift 10
    exp1:  · exp2 | {":"} → shift 11
    ternary:  · exp2 "?" exp1 ":" exp1 | {":"} → shift 11
    ternary:  exp2 "?" exp1 ":" · exp1 | {":"} → shift 31
    exp2:  · exp2 "+" exp3 | {"?", ":", "+"} → shift 11
    exp2:  · exp3 | {"?", ":", "+"} → shift 13
    exp3:  · maybe | {"?", ":", "+"} → shift 14
    exp3:  · "1" | {"?", ":", "+"} → shift 15
    maybe:  · exp3 "?" | {"?", ":", "+"} → shift 13

State 31:
    ternary:  exp2 "?" exp1 ":" exp1 · | {":"} → reduce 2

parsing lr shift-reduce-conflict glr
person user541686    schedule 03.03.2013    source источник
comment
Тот факт, что грамматика не является неоднозначной, не обязательно означает, что она поддается LR-разбору. Любой детерминированный CFL имеет по крайней мере одну LR(1)-грамматику, и все детерминированные CFL также имеют однозначные грамматики. Однако не все однозначные грамматики описывают детерминированные CFL.   -  person templatetypedef    schedule 04.03.2013
comment
@templatetypedef: Верно, я знаю, что однозначность не подразумевает возможность LR-анализа, но я думал, что это действительно LR-анализ (кажется, что LR (2) справится с этим нормально, хотя не уверен). Вы говорите, что это не так? (например, требуется ли неограниченный просмотр вперед?)   -  person user541686    schedule 04.03.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

 a + b ? c : d

В тот момент, когда синтаксический анализатор увидел a + b ? и просматривает c, он не может решить, нужно ли ему

  1. Уменьшите b?, чтобы он анализировал выражение формы a + (b?) и затем продолжал оттуда, или

  2. Уменьшите a + b, чтобы он анализировал выражение формы (a + b) ? c : d

Я думаю, проблема здесь в том, что в одном случае ? имеет очень низкий приоритет (при использовании в качестве тернарного оператора), а в другом — очень высокий приоритет (при использовании в качестве унарного оператора). Однако, если вы назначите приоритеты таким образом, я думаю, что синтаксический анализатор сможет устранить неоднозначность в этих случаях.

Надеюсь это поможет!

person templatetypedef    schedule 03.03.2013
comment
Хм, a + b ? c : d следует анализировать как (a + b) ? c : d, а не a + (b ? c : d), верно? В этом случае, как только он увидит c, он узнает, что конструкция является троичным выражением. (Я пытался сохранить семантику ? в таких языках, как C.) - person user541686; 04.03.2013
comment
@Mehrdad- Ах, да, моя ошибка. Это настоящий конфликт сдвига и уменьшения. Я обновлю свой ответ. Тем не менее, я все еще думаю, что это вопрос приоритета. - person templatetypedef; 04.03.2013
comment
Ах, да, ладно, так что с нашей точки зрения это проблема приоритета (мне действительно нужно, чтобы унарный ? связывался сильнее, чем троичный ?), но генератор синтаксического анализатора на самом деле не имеет никакого понятия о приоритете; это просто разбор грамматики, и приоритет подразумевается грамматикой. Я не уверен, что вы имеете в виду, если вы назначили приоритеты таким образом... вы предлагаете мне изменить приоритеты, подразумеваемые грамматикой (чего я не могу сделать, потому что изменится семантика), или вы имели в виду Я должен исправить это каким-то другим способом? - person user541686; 04.03.2013
comment
Какой генератор парсеров вы используете? Большинство стандартных генераторов синтаксических анализаторов LR (yacc, bison и т. д.) допускают спецификации приоритета, поскольку это значительно упрощает написание грамматики. - person templatetypedef; 04.03.2013
comment
Это то, что я написал сам. :) - person user541686; 04.03.2013
comment
@Mehrdad- Ты потрясающий! На самом деле не так сложно включить приоритеты в генератор синтаксического анализатора LR(1), и это значительно упрощает создание грамматики. Основная идея состоит в том, что каждый раз, когда вы сталкиваетесь с конфликтом сдвига/уменьшения, вы определяете, следует ли смещать или уменьшать, основываясь на приоритете первого терминала в производстве по сравнению с опережением. В Книге Пурпурного Дракона есть некоторые подробности о том, как это сделать. За исключением этого, вам придется переписать большую часть грамматики, чтобы неявно обеспечить приоритет, что довольно сложно. Это ваш вызов. - person templatetypedef; 04.03.2013
comment
Спасибо! Это хорошая информация, я мог бы сделать это когда-нибудь. :) Но хм, я на самом деле не уверен, что приоритет решит эту проблему. Парсер даже не имеет шанса увидеть здесь c, как в вашем примере. Скорее, он сбивается, когда видит exp3 и имеет ? в качестве упреждающего токена. Как приоритет может решить эту проблему? Он еще не может видеть, что находится после ?. Я чувствую, что мне должен переписать грамматику (сохранив при этом жесткость привязки ?), но я понятия не имею, как это сделать, тем более, что я не уверен, как старшинство решит это. - person user541686; 04.03.2013