Перемещение / уменьшение конфликта с C-подобной грамматикой под Bison - PullRequest
Новая
       7

Перемещение / уменьшение конфликта с C-подобной грамматикой под Bison

4 голосов
/ 15 января 2010

Я работаю над грамматикой в ​​стиле C для моего личного удовольствия. Однако я столкнулся с конфликтами сдвига / уменьшения и уверен, что их можно разрешить.

Прямо сейчас мои expressions выглядят так, в упрощенном виде, без действий: 

%left '+' '-'

%%
expr
 : NUMBER
 | IDENTIFIER
 | expr '+' expr
 | expr '-' expr
 /* other operators like '*', '/', etc. */
 | expr '(' expr ')' /* function call */
%%

Однако это приводит к конфликтам сдвига / уменьшения: синтаксический анализатор не уверен, как обращаться с круглыми скобками. Из того, что -v говорит мне, неясно, должно ли выражение типа expr '+' expr '(' уменьшать expr '+' expr до expr или сдвигать скобки.

Очевидно, я хочу, чтобы скобки были сдвинуты. foo % bar(4) не должно в конечном итоге быть (foo % bar)(4). Однако я не добился успеха, используя директиву %prec для этого значения. Добавление %left FUNCALL и %prec FUNCALL после правила не приводит к изменениям.

Я знаю, что путь парсера Bison LALR по умолчанию при обнаружении сдвига / уменьшения будет означать сдвиг, и что я мог бы просто использовать %expect to fix , чтобы обойти проблему. Однако для каждого выражения генерируется один конфликт, и если мне когда-нибудь понадобится изменить этот список, мне также нужно будет изменить объявление %expect, что для меня выглядит довольно некрасивым решением. Кроме того, я уверен, что у одного из вас, мудрых детей, есть решение этой проблемы.

Моя цель состоит в том, чтобы иметь правило, подобное приведенному выше, для которого Бизон будет знать, что всякий раз, когда он встречает '(' из правила вызова функции, он сдвигает скобки, без возможного конфликта сдвига / уменьшения. Для справки, я использую директиву %prec следующим образом, так что, если я просто делаю это неправильно, вы можете исправить меня. У него есть конфликт сдвига / уменьшения. 

%left '+' '-'
%left FUNCALL

%%

expr
    : NUMBER
    | IDENTIFIER
    | expr '+' expr
    | expr '-' expr
    /* other operators like '*', '/', etc. */
    | expr '(' expr ')' %prec FUNCALL /* function call */

%%

1 Ответ

4 голосов
/ 15 января 2010

Вам необходимо добавить %left '(' к своим правилам приоритета (или %nonassoc '(' может быть лучше).

Способ, которым приоритет работает для разрешения конфликтов сдвига / уменьшения в yacc / bison, заключается в том, что он сравнивает приоритет правила , который нужно уменьшить, с приоритетом токена сдвинуты. В вашем примере конфликт между уменьшением expr: expr '+' expr и сдвигом '(', поэтому для его разрешения вам нужно иметь приоритет над '(' (и вы хотите, чтобы он был выше, чем правило, которое исходит из '+' )

Директива %prec просто устанавливает приоритет правила, переопределяя его приоритет по умолчанию, который исходит от первого токена на его rhs. Это никак не влияет на приоритет токенов, которые появляются в правиле.

...