Зубр LALR сдвиг / уменьшение конфликтов

Question

Недавно я снова взял бизона, но я все еще борюсь с тем, как работает старшинство и как решить основные сдвиги / уменьшить конфликты. Мне довольно удобно писать правила грамматики и то, как работает рекурсия и т. Д., Но я все еще не могу обернуть голову вокруг правил предшествования.

Я был бы очень признателен за некоторые комментарии к следующим примерам и моим проблемам и их пониманию.

test1.y

%token              ID
%token              TYPE_NAME
%token              ASTERIX

%nonassoc           F_T
%nonassoc           P_T

%%
f_type:
                    ID type         %prec F_T
;

type:
                    TYPE_NAME
|                   type ASTERIX    %prec P_T
|                   f_type
;
%%

test1.output

State 5

     1 f_type: ID type .
     3 type: type . ASTERIX

     ASTERIX  shift, and go to state 7

     ASTERIX   [reduce using rule 1 (f_type)]
     $default  reduce using rule 1 (f_type)

В этом примере создается конфликт уменьшения сдвига, поскольку конечный автомат не может определить, следует ли ему уменьшить Тип ID * -> Тип * -> Тип или Тип ID * -> Тип ID - > введите . Это последний желаемый результат. Я попытался разрешить этот конфликт, указав тип правила: type ASTERIX с более высоким приоритетом, чем f_type: ID type , но это, похоже, не работает. Я также не хотел бы назначать какой-либо приоритет терминалу ASTERIX , так как я хотел бы использовать его в других контекстах.

test2.y

%token      ID
%token      DOUBLE_PLUS

%left       POSTFIX_OP
%right      PREFIX_OP

%%
exp:
            ID
|           exp DOUBLE_PLUS     %prec POSTFIX_OP
|           DOUBLE_PLUS exp     %prec PREFIX_OP
;
%%

test2.output

State 4

    2 exp: exp . DOUBLE_PLUS
    3    | DOUBLE_PLUS exp .

    DOUBLE_PLUS  shift, and go to state 6

    DOUBLE_PLUS  [reduce using rule 3 (exp)]
    $default     reduce using rule 3 (exp)

В этом примере возникает конфликт сдвига / уменьшения, поскольку при уменьшении DOUBLE_PLUS exp DOUBLE_PLUS существует неоднозначность. Поэтому я попытался присвоить более высокий приоритет DOUBLE_PLUS exp , чем exp DOUBLE_PLUS , но это тоже не работает. Можно разрешить этот конфликт, назначив левый или правый приоритет терминалу DOUBLE_PLUS , и я предполагаю, что назначение левого приоритета означает, что exp DOUBLE_PLUS уменьшается первым, а правое означает DOUBLE_PLUS exp сначала уменьшается, но я также надеюсь, что есть какой-то способ сделать это, просто используя аннотацию % prec .

Я также не уверен, правильно ли я понимаю файл .output . . в правилах указывает, что находится в стеке и что такое маркер ожидания, но почему тогда упоминалось правило 2 в последнем примере? Я имею в виду exp: exp. DOUBLE_PLUS не должно быть никаких конфликтов?

Answer 1

Вот цитата из другого ответа Я писал об алгоритме приоритета yacc / bison. Я не знаю, понятнее ли это, чем документация или описание в Книге Дракона, но это лучшее, что я смог сделать до сих пор. Пожалуйста, дайте мне знать, если вас это смущает:

Напомним, что отношение приоритета определяется между производством и терминал. Это не касается двух терминалов или двух производств (и поэтому не может быть использован для разрешения конфликтов уменьшения-уменьшения). Сравнение между приоритетом производства, которое может быть уменьшено, и Терминал предпросмотра определяет, произойдет ли уменьшение или смещение. Для удобства записи продукция представлена ​​названием терминал, обычно единственный терминал в производстве; этот соответствует общему варианту использования, но иногда сбивает с толку. В в частности, объявление %prec служит только для присвоения правилу имени для использования в декларациях предшествования, и, вероятно, лучше подумать об этом таким образом, а не как «явное» объявление.

Поскольку сравнение приоритетов никогда не проводится между двумя правилами - они всегда между правилом и токеном предварительного просмотра - объявления порядка приоритета должны включать как правила (неявно или явно), так и имена токенов. Итак, в вашем первом примере порядок старшинства между F_T и P_T никак не влияет. Аналогично, во втором примере PREFIX_OP и POSTFIX_OP являются приоритетами, связанными только с правилами, поэтому порядок приоритетов не имеет значения.

Если возможны как сдвиг, так и уменьшение, и сравнение правила с маркером предпросмотра может выявить, что правило имеет более высокий приоритет, то будет создано действие сокращения. Если жетон предпросмотра имеет более высокий приоритет, будет сгенерировано действие сдвига. Но с заявлениями можно ознакомиться только в том случае, если возможны как сдвиг, так и сокращение. Если грамматика может выполнять только одно действие, то это действие, которое она будет выполнять, независимо. (Исключение: %nonassoc объявления фактически запретят определенные сокращения.)

Если сравнение приводит к равенству - и правило, и токен находятся в одной и той же группе приоритетов - тогда сдвиг будет предпочтительным для групп %left и уменьшением для групп %right. Этот случай обычно не применяется в случае унарных операторов, будь то префикс или постфикс, потому что в таком контексте возможно только одно действие.

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

Что касается вывода конечного автомата в файле .output, то печатается все состояние, а не только та часть, которая вызывает конфликты. Конфликты указываются в действиях; действия, заключенные в […], конфликтовали с другими действиями и были устранены с помощью механизма разрешения конфликтов по умолчанию bison (предпочитайте shift, чтобы уменьшить; предпочитайте shift, правило которого находится ранее в файле). Грубо говоря, правило смены имеет . перед токеном; Правило сокращения имеет . в конце правила.