关于ocamlyacc、函数应用语法和优先级的问题

Question

我是OCaml的新手，正在尝试编写一个类似OCaml的简单语法，但我无法理解这个问题。我的语法允许像这样的内容：

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

然而，如果我想使用这个定义的函数，可以写成：(sub 7) 3，但是我不能写成sub 7 3，这真的让我很困扰。由于某种原因，它会被解释为我写了sub (7 3)（这将把7作为参数传递给一个名为sub的函数）。相关部分如下：

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

/* ... */

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

谢谢！

- Amadan

Answer 1

如果你来到这个问题并认为你终于找到了想要的答案，但是感到失望，那么这里有一个更明确的答案：

你不能使用 %prec，因为Thelema提到的原因。所以你必须在建立递归规则时定义结合性。

这是一个简化的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。

在本例中，应用（函数应用）的情况在exp7中。这是因为Apply被定义为具有此示例中任何模式中最高结合性。它没有超过exp8中的情况是因为Apply计算为进一步调用表达式情况，而不是值调用。如果exp8不存在，我们就会遇到无限循环的情况。

在假想的simple.ml中，函数应用被定义为以下属性的表达式：expr * expr的Apply。由于Apply是左递归的，我们正在评估右表达式（exp8）并在左侧（exp7）递归。

- anxiety

Answer 2

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来指定结合性。尝试通过定义更多规则来创建所需的结合性，看看会有什么结果。

- Thelema

---

你使用的解决方案是什么？ - Thelema

Answer 3

我们也可以使用类似这样的东西来避免将表达式分解成太多层：

%nonassoc LET FUN IF

%left OR

%left AND

%left EQ NE LT LE

%left PLUS MINUS

%left MUL DIV

- Katrina