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

23.08.2008 19:18:48
2 ОТВЕТА
РЕШЕНИЕ

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

  1. разделить exprна simple_exprиexpr_with_prefix
  2. разрешить только simple_exprили (expr_with_prefix)в заявке

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

У вас будет та же проблема с «ab 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
8
23.08.2008 21:53:35
%left APPLY/ %prec APPLYУстраняет неоднозначность для a b c- ее левой ассоциативной (так его (АВ) С) и более низкий приоритет , чем все остальное. Проблема в том, что правила приоритета не работают для неоднозначностей, которые проявляются как уменьшение / уменьшение конфликтов.
Chris Dodd 6.10.2011 17:59:03

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

0
6.10.2011 18:14:52