На ocamlyacc, функция приложения грамматика и приоритет

Я новичок OCaml, и я пытаюсь написать простую грамматику, похожую на OCaml, и я не могу понять это. Моя грамматика позволяет что-то вроде этого:

let sub = fun x -> fun y -> x - y;;

Однако, если я хочу использовать функцию, определенную таким образом, я могу написать: (sub 7) 3 но я не могу написать sub 7 3, что действительно меня беспокоит. По какой-то причине это интерпретируется так, как будто я написал sub (7 3) (что бы лечить 7 как функция с аргументом 3). Соответствующие разделы:

/* other operators, then at the very end: */
%left APPLY

/* ... */

expr:
    /* ... */
    | expr expr %prec APPLY      { Apply($1, $2) }

Спасибо!

Источник

3 ответа

Решение

Компилятор ocaml выполняет следующие функции: (из ocaml/parsing/parser.mly)

expr:
...
  | simple_expr simple_labeled_expr_list
      { mkexp(Pexp_apply($1, List.rev $2)) }

где simple_expr является подмножеством возможных значений expr, которые могут вычисляться для функции без использования скобок. Это исключает использование всех конструкций, не заключенных в квадратные скобки, внутри строки при вызове функции. Это также разъясняет ассоциативность подвыражений, поскольку второе подвыражение явно является списком.

Что касается того, почему ваша попытка использовать %left APPLY чтобы получить правильную ассоциативность не работает, из комментариев в ocaml's parser.mly:

We will only use associativities with operators of the kind  x * x -> x
for example, in the rules of the form    expr: expr BINOP expr
in all other cases, we define two precedences if needed to resolve
conflicts.

Я бы сказал, что это означает, что вы не можете использовать% prec для ассоциативности без оператора. Попробуйте создать ассоциативность, которую вы хотите, определив больше правил, и посмотрите, к чему это приведет.

Источник

Если вы подошли к этому вопросу и подумали, что, наконец, достигли того момента, когда вы нашли именно то, что искали, то были разочарованы, вот более четкий ответ:

Вы не можете использовать% prec по причине, упомянутой Телемой. Таким образом, вы должны определить ассоциативность при создании рекурсивного набора правил.

Вот упрощенный parser.mly

    %token <int> Num
    %token <string> Id
    %token TRUE FALSE
    %token LET REC EQ IN FUN ARROW IF THEN ELSE
    %token PLUS MINUS MUL DIV LT LE NE AND OR
    %token EOF          

    %start exp
    %type <Simple.expr> exp

    %%

/* Associativity increases from exp to exp8
 * Each precedence level trickles down to higher level expressions if the pattern is not matched 
 */

/* Parses the LET, LET REC, FUN, and IF expressions */
exp:
      LET Id EQ exp IN exp      { Let($2,$4,$6) }
    | LET REC Id EQ exp IN exp  { Letrec($3,$5,$7) }
    | FUN Id ARROW exp          { Fun($2,$4) }
    | IF exp THEN exp ELSE exp  { If($2,$4,$6) }
    | exp2                      { $1 }

/* Parses OR expressions */
exp2:
      exp2 OR exp3              { Bin($1,Or,$3) }
    | exp3                      { $1 }

/* Parses AND expressions */
exp3:
      exp3 AND exp4             { Bin($1,And,$3) }
    | exp4                      { $1 }

/* Parses EQ, NE, LT, and LE expressions */
exp4:
      exp4 EQ exp5              { Bin($1,Eq,$3) }
    | exp4 NE exp5              { Bin($1,Ne,$3) }
    | exp4 LT exp5              { Bin($1,Lt,$3) }
    | exp4 LE exp5              { Bin($1,Le,$3) }
    | exp5                      { $1 }

/* Parses PLUS and MINUS expressions */
exp5:
      exp5 PLUS exp6            { Bin($1,Plus,$3) }
    | exp5 MINUS exp6           { Bin($1,Minus,$3) }
    | exp6                      { $1 }

/* Parses MUL and DIV expressions */
exp6:
      exp6 MUL exp7             { Bin($1,Mul,$3)}
    | exp6 DIV exp7             { Bin($1,Div,$3)}
    | exp7                      { $1 }

/* Parses Function Application expressions */
exp7:
      exp7 exp8                 { Apply($1,$2) }
    | exp8                      { $1 }

/* Parses numbers (Num), strings (Id), booleans (True | False), and expressions in parentheses */
exp8:
      Num                       { Const($1) }
    | Id                        { Var($1) }
    | TRUE                      { True }
    | FALSE                     { False }
    | LPAREN exp RPAREN         { $2 }

Рекурсивный обходной путь действительно предназначен для выявления случая, в котором мы заинтересованы относительно этого вопроса, однако легко увидеть, как его можно применять для определения ассоциативности и для остальных выражений.

Суть этого подхода состоит в том, чтобы попытаться сопоставить рассматриваемый шаблон с шаблонами, определенными в начальном случае (exp), и вы оставляете вызов непосредственно последующему случаю (exp2) как универсальный шаблон, если ваш шаблон не сопоставить с любым до этого; продолжая с этим подходом, пока образец наконец не совпадает. Это подразумевает, что шаблон с наивысшим приоритетом существует в крайнем нижнем регистре - в этом примере, exp8.

В этом примере дело для Apply (Function Application) в exp7. Это связано с тем, что в этом примере Apply определен, чтобы иметь наивысшую ассоциативность среди всех шаблонов Причина, по которой он не имеет приоритета над случаями в exp8, связана с оценкой Применить для дальнейших вызовов к случаям выражения, а не к вызовам значений. Если бы exp8 не существовало, у нас был бы бесконечный взгляд в наших руках.

В гипотетическом файле simple.ml приложение функции определяется как выражение следующего свойства: Apply of expr * expr. А поскольку Apply является рекурсивным слева, мы оцениваем правильное выражение (exp8) и рекурсивно слева (exp7).

Источник

Можно также использовать такие вещи, чтобы избежать разбиения выражений на множество уровней:

%nonassoc LET FUN IF

%left OR

%left AND

%left EQ NE LT LE

%left PLUS MINUS

%left MUL DIV
Источник
Другие вопросы по тегам