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

StackOverflow https://stackoverflow.com/questions/24516

  •  09-06-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

  1. расколотый expr в simple_expr и expr_with_prefix
  2. разрешать только simple_expr или (expr_with_prefix) в ПРИЛОЖЕНИИ

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

У вас возникнет та же проблема с '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

Другие советы

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top