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

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

10 голосов
/ 23 августа 2008

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

Ответы [ 2 ]

8 голосов
/ 24 августа 2008

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

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

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

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

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

...