Разрешение конфликта reduce / уменьшить в yacc / ocamlyacc
Вопрос
Я пытаюсь проанализировать грамматику в ocamlyacc (почти такую же, как обычный yacc), которая поддерживает применение функций без операторов (например, в Ocaml или Haskell) и обычный набор двоичных и унарных операторов.Я получаю конфликт уменьшения / reduce с оператором '-', который может использоваться как для вычитания, так и для отрицания.Вот пример грамматики, которую я использую:
%token <int> INT
%token <string> ID
%token MINUS
%start expr
%type <expr> expr
%nonassoc INT ID
%left MINUS
%left APPLY
%%
expr: INT
{ ExprInt $1 }
| ID
{ ExprId $1 }
| expr MINUS expr
{ ExprSub($1, $3) }
| MINUS expr
{ ExprNeg $2 }
| expr expr %prec APPLY
{ ExprApply($1, $2) };
Проблема в том, что когда вы получаете выражение типа "a - b", анализатор не знает, следует ли это сокращать как "a (-b)" (отрицание b, за которым следует application) или "a - b" (вычитание).Уменьшение вычитания выполнено правильно.Как мне разрешить конфликт в пользу этого правила?
Решение
К сожалению, единственный ответ, который я могу придумать, означает увеличение сложности грамматики.
- расколотый
expr
вsimple_expr
иexpr_with_prefix
- разрешать только
simple_expr
или(expr_with_prefix)
в ПРИЛОЖЕНИИ
Первый шаг превращает ваш конфликт reduce / уменьшить в конфликт shift / уменьшить, но скобки разрешают это.
У вас возникнет та же проблема с 'a b c':так ли это a(b(c))
или (a(b))(c)
?Вам также нужно будет прерваться applied_expression
и требуется (applied_expression)
в грамматике.
Я думаю, что это поможет, но я не уверен:
expr := INT
| parenthesized_expr
| expr MINUS expr
parenthesized_expr := ( expr )
| ( applied_expr )
| ( expr_with_prefix )
applied_expr := expr expr
expr_with_prefix := MINUS expr
Другие советы
Что ж, этот простейший ответ заключается в том, чтобы просто проигнорировать это и позволить уменьшить разрешение по умолчанию - уменьшить правило, которое появляется первым в грамматике.В данном случае это означает сокращение expr MINUS expr
отдавая предпочтение MINUS expr
, а это именно то, чего вы хотите.После того, как увидел a-b
, вы хотите проанализировать его как двоичный минус, а не как унарный минус, а затем применить.