Решение небольших сдвигов уменьшает конфликт - PullRequest
Новая
       119

Решение небольших сдвигов уменьшает конфликт

0 голосов
/ 01 апреля 2020

У меня был конфликт сдвига-уменьшения и я сократил его до пары строк: 

start               : instruction_A;

instruction_A       : instruction_A instruction
                    |
                    ;

instruction         : RETURN 'X'
                    | RETURN
                    | 'X' '!'
                    ;

3: shift/reduce conflict (shift 6, reduce 5) on 'X'
state 3
    instruction : RETURN . 'X'  (4)
    instruction : RETURN .  (5)

    'X'  shift 6
    $end  reduce 5
    RETURN  reduce 5

Я предполагаю, что выражение X! RETURN X! не может быть проанализировано, потому что, когда анализатор достигает Токен «X» не знает, следует ли продолжить инструкцию или начать другую.

В основном, ожидаемые варианты:

{X! RETURN} {X!}

{X! RETURN X}

Как это решить? Кажется, что чтение дополнительного токена решило бы проблему, но это должно быть сделано с помощью LALR (1).

1 Ответ

0 голосов
/ 01 апреля 2020

Это, безусловно, правильный анализ этого конфликта сдвига-уменьшения. Грамматика однозначна, но LALR (2).

Существует механическая процедура для построения грамматики LALR (1) из грамматики, которая является LALR ( k ), и она может быть применена к этому примеру. Но я не написал это, потому что это довольно долго, и я сомневаюсь, что это действительно полезно. Я подозреваю, что оригинальная грамматика была больше похожа на 

statement
    : return_statement
    | expr_statement
    | ...
return_statement
    : "return" expression
    | "return"
expression_statement
    : expression '!'

, где X был заменен нетерминалом, который может выводить фразы неограниченной длины. В результате эта грамматика не является LALR ( k ) для любого k . Но это все еще однозначно.

Таким образом, ваш лучший вариант - попросить Bison сгенерировать синтаксический анализатор GLR, который может обрабатывать произвольные однозначные грамматики. Если вы используете бизона, а конфликтующие состояния возникают на практике редко, то издержки GLR очень малы, поскольку бизон оптимизирует GLR для детерминированных c состояний.

...