论ocamlyacc、函数应用语法和优先顺序

Question

我是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) }

谢谢!

Answer 1

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的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进行结合性。尝试通过定义更多的规则来创建您想要的关联性，看看这会导致什么情况。

Answer 2

如果你遇到这个问题，并认为你终于找到了你想要的东西，然后感到失望，这里有一个更明确的答案：

出于上述原因，您不能使用%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 (函数应用程序)的大小写是在exp7中。这是因为在本例中，Apply被定义为具有任何模式中最高的关联性。它不比exp8中的cases具有优先级的原因是将计算应用于对表达式cases的进一步调用，而不是值调用。如果exp8不存在，我们手中就会有无限的希望。

在假设的simple.ml中，函数应用被定义为以下属性的表达式: Apply of expr * expr。由于Apply是左递归的，因此我们将计算右表达式(exp8)和左递归(exp7)。

Answer 3

人们也可以使用这样的东西来避免将表达式分解为如此多的级别：

%nonassoc LET FUN IF

%left OR

%left AND

%left EQ NE LT LE

%left PLUS MINUS

%left MUL DIV