Разрешение уменьшить/уменьшить конфликт в 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
вы хотите проанализировать его как двоичный минус, а не унарный минус, а затем применить.