Бизон / YACC - избегайте уменьшения / уменьшения конфликта с двумя правилами отрицания - PullRequest
Новая
       49

Бизон / YACC - избегайте уменьшения / уменьшения конфликта с двумя правилами отрицания

5 голосов
/ 05 октября 2011

Следующая грамматика (где INTEGER - последовательность цифр) вызывает конфликт уменьшения / уменьшения, потому что, например, -4 может быть уменьшено на expr -> -expr или expr -> num -> -INTEGER. В моей грамматике num и expr возвращают разные типы, поэтому я должен различать -num и -expr. Моя цель состоит в том, чтобы -5 уменьшилось на число, в то время как, например, - (...) является expr. Как мне этого добиться? 

%token      INTEGER

%left       '+'     '-'

%%

start: expr
    ;

expr: expr '+' expr
    | expr '-' expr
    | '-' expr
    | '(' expr ')'
    | num
    ;

num:  INTEGER
    | '-' INTEGER
    ;
%%

Ответы [ 2 ]

2 голосов
/ 06 октября 2011

Для этого конкретного случая вы можете изменить правило для отрицательных выражений на 

expr: '-' '(' expr ')'

и распознавать отрицания только в выражениях в скобках. Это, однако, не распознает двойные негативы (например, - - x) и, что более важно, не будет масштабироваться, поскольку оно сломается, если вы попытаетесь добавить другие унарные операторы.

Теперь вы можете просто поместить правила num ДО правил expr и разрешить разрешение конфликтов уменьшения / уменьшения по умолчанию, чтобы справиться с ним (первое правило, появляющееся в файле, будет использоваться, если оба варианта возможны), но Это довольно уродливо, потому что вы получаете эти предупреждения о конфликтах каждый раз, когда запускаете зубров, и игнорировать их, когда вы точно не знаете, что происходит, - плохая идея.

Общий способ устранения такой неоднозначности заключается в разделении грамматики на разделение нарушающего правила на два правила и использовании соответствующей версии в каждом контексте, чтобы избежать конфликтов. В этом случае вы бы разбили expr на num_expr для выражений, которые начинаются с num и non_num_expr для других выражений: 

expr: num_expr | non_num_expr ;

num_expr: num_expr '+' expr
        | num_expr '-' expr
        | num
        ;

non_num_expr: non_num_expr '+' expr
            | non_num_expr '-' expr
            | '-' non_num_expr
            | '(' expr ')'
            ;

По сути, каждое правило для expr, начинающееся с expr в RHS, должно быть продублировано, а другие варианты использования expr, возможно, придется изменить на один из вариантов, чтобы избежать конфликта.

К сожалению, в этом случае это не работает чисто, так как вы используете уровни приоритета, чтобы разрешить внутреннюю неоднозначность грамматики выражения, и факторные правила мешают этому - дополнительный один шаг правила вызывают проблемы. Таким образом, вам необходимо либо исключить эти правила (дублируя каждое правило с expr на RHS - одно с версией num_expr, а другое с non_num_version ИЛИ вам нужно реорганизовать грамматику с дополнительными правилами для старшинство / ассоциативность 

expr: expr '+' term
    | expr '-' term
    | term
;

term: non_num_term | num_term ;

non_num_term: '-' non_num_term
            | '(' expr ')'
;

num_term: num ;

Обратите внимание, что в этом случае факторинг num / non_num был выполнен для term, а не expr

0 голосов
/ 06 октября 2011

Вам не ясно, почему num должно представлять отрицательные числа. Я не могу сказать, если вы используете num в другом месте в вашей грамматике. Вы также не говорите, почему вы хотите, чтобы num и expr были различны.

Обычно отрицательные числа обрабатываются на уровне лексера. В вашем случае правило будет примерно таким: -?[0-9]+. Это исключает необходимость в num и приводит к следующему: 

expr: expr '+' expr
    | expr '-' expr
    | '-' expr
    | '(' expr ')'
    | INTEGER
    ;

РЕДАКТИРОВАТЬ: Крис Додд имеет точку. Так что вам нужно переместить отрицание целиком в парсер. Вы по-прежнему избавляетесь от num, просто не проверяйте наличие негативов в шаблоне лексера INTEGER (то есть шаблон будет выглядеть как [0-9]+, что вы и делаете сейчас, верно?). Правило expr, которое я дал выше, не меняется.

  • Отрицательное число (-5) анализируется как: '-' INTEGER, которое становится '-' expr (вариант 5), затем expr (вариант 3).
  • Разница между двумя целыми числами (3-2) анализируется как INTEGER '-' INTEGER, которая становится expr - expr (выбор 5 дважды), затем expr (выбор 2).
  • Разница между целым и отрицательным целым числом (5--1) анализируется как INTEGER '-' '-' INTEGER, который становится expr '-' '-' expr (выбор 5 дважды), затем expr '-' expr (выбор 3), затем expr (выбор 2 ).

И так далее. Основная проблема в том, что у вас есть отрицание в двух разных местах , и нет способа, который не может быть неоднозначным.

...