在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

如果你遇到这个问题并且认为你终于到达那个时刻,当你找到你正在寻找的东西时,那么感到很失望,这是一个更明确的答案:

由于Thelema提到的原因,你不能使用%prec.因此,您必须在建立递归规则集时定义关联性.

这是一个简化的解析器.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被定义为以下属性的表达式:应用expr*expr.由于Apply是左递归的,我们正在评估正确的表达式(exp8)并在左侧(exp7)进行递归.

Answer 2

ocaml编译器的功能如下:(来自ocaml/parsing/parser.mly)

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

where 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用于关联性.尝试通过定义更多规则来创建所需的关联性,并查看其引导的位置.