Разрешение уменьшить/уменьшить конфликт в yacc/ocamlyacc

Я пытаюсь разобрать грамматику в ocamlyacc (почти такой же, как обычный yacc), который поддерживает приложение-приложение без каких-либо операторов (например, в Ocaml или Haskell) и обычный ассортимент двоичных и унарных операторов. Я получаю конфликт сокращения/уменьшения с оператором "-", который может использоваться как для вычитания, так и для отрицания. Вот пример грамматики, которую я использую:

%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, а затем приложение) или "a - b" (вычитание). Сокращение вычитания является правильным. Как разрешить конфликт в пользу этого правила?

Ответы

Ответ 1

К сожалению, единственный ответ, который я могу придумать, означает увеличение сложности грамматики.

  • split expr в simple_expr и expr_with_prefix
  • разрешить только simple_expr или (expr_with_prefix) в APPLY

Первый шаг превращает конфликт сокращения/уменьшения в конфликт смены/уменьшения, но скобки разрешают это.

У вас будет такая же проблема с '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

Ответ 2

Ну, этот простой ответ состоит в том, чтобы просто игнорировать его и позволить разрешению уменьшить/уменьшить разрешение по умолчанию - уменьшить правило, которое появляется сначала в грамматике. В этом случае это означает уменьшение expr MINUS expr по сравнению с MINUS expr, что именно то, что вы хотите. После просмотра a-b вы хотите проанализировать его как двоичный минус, а не унарный минус, а затем применить.