8

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

谢谢！

4

3 回答 3

11

如果您遇到这个问题并认为您终于找到了您正在寻找的东西的那一刻，然后感到失望，这里有一个更明确的答案：

由于 Thelema 提到的原因，您不能使用 %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 中的情况的原因是由于 Apply 评估以进一步调用表达式情况，而不是值调用。如果 exp8 不存在，我们将拥有无限的外观。

在假设的 simple.ml 中，Function Application 定义为以下属性的表达式：Apply of expr * expr。由于 Apply 是左递归的，我们正在计算右表达式 (exp8) 并在左递归 (exp7)。

于 2011-02-12T10:06:53.000 回答
5

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

于 2010-05-23T22:44:34.050 回答
0

人们也可以使用这样的东西来避免将表达式分解成这么多层次：

%nonassoc LET FUN IF

%left OR

%left AND

%left EQ NE LT LE

%left PLUS MINUS

%left MUL DIV
于 2011-11-01T03:45:17.660 回答