My<cod/>.net
Разрешение конфликта reduce / reduce в yacc / ocamlyacc
Я пытаюсь разобрать grammar в ocamlyacc (почти то же самое, что и обычный yacc), который поддерживает приложение функций без операторов (например, в Ocaml или Haskell) и обычный набор двоичных и унарных операторов. Я получаю конфликт reduce/reduce с оператором' -', который может использоваться как для вычитания, так и для отрицания. Вот пример grammar, который я использую:
%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" (вычитание). Уменьшение вычитания является правильным. Как мне разрешить конфликт в пользу этого правила?
К сожалению, единственный ответ, который я могу придумать, означает увеличение сложности grammar.
- разделить
exprнаsimple_exprиexpr_with_prefix - разрешить только
simple_exprили(expr_with_prefix)в APPLY
Первый шаг превращает ваш конфликт reduce/reduce в конфликт shift/reduce,но скобки решают эту проблему.
У вас будет та же проблема с "A b c": это a(b(c)) или (a(b))(c) ? Вам также нужно будет разорвать applied_expression и обязательный (applied_expression) в grammar.
Я думаю, что это поможет, но я не уверен:
expr := INT
| parenthesized_expr
| expr MINUS expr
parenthesized_expr := ( expr )
| ( applied_expr )
| ( expr_with_prefix )
applied_expr := expr expr
expr_with_prefix := MINUS expr
Ну, этот самый простой ответ состоит в том, чтобы просто игнорировать его и позволить по умолчанию уменьшить/уменьшить разрешение обрабатывать его-уменьшить правило, которое появляется первым в grammar. В данном случае это означает уменьшение предпочтения expr MINUS expr до MINUS expr, что именно то , что вы хотите. Увидев a-b, вы хотите разобрать его как двоичный минус, а не унарный минус, а затем применить.