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

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

2 голосов
/ 06 июня 2009

Я пытаюсь разобрать простую грамматику с помощью генератора синтаксических анализаторов LALR (1) (Bison, но проблема не связана с этим инструментом), и я вступаю в конфликт с уменьшением сдвига. В документах и ​​других источниках, которые я нашел об их исправлении, обычно говорится об одном или нескольких из следующих:

  • Если грамматика неоднозначна (например, неопределенность if-then-else), измените язык, чтобы исправить неоднозначность.
  • Если это проблема приоритета оператора, укажите приоритет явно.
  • Примите разрешение по умолчанию и попросите генератор не жаловаться на него.

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

Для конкретности, вот грамматика, о которой идет речь: 

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

Цель состоит в том, чтобы разобрать разделенные точкой с запятой строки вида "[A-Za-z] +" или "[A-Za-z] -> [A-Za-z] +".

Ответы [ 2 ]

2 голосов
/ 06 июня 2009

Используя версию yacc Solaris, я получаю: 

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

Итак, проблема, как это часто бывает, в пустом правиле, в частности, в пустом преемнике. Не совсем ясно, хотите ли вы использовать точку с запятой в качестве допустимого ввода - на данный момент это так. Если вы изменили правило преемника на: 

successor: LETTER | successor LETTER;

конфликт сдвига / уменьшения устранен.

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

Спасибо, что сократили грамматику и опубликовали ее. Изменение правила преемника на - 

successor:      /* empty */ | LETTER successor;

... работал на меня. ITYM язык выглядел однозначно.

...