menhir

Question

为 lambda 表达式编写解析器，

data expr = Symbol of string | Lambda of string * expr | App of expr * expr

在编写.mly文件时，如何表达一系列表达式的想法

e1 e2 e3 e4

应该解析为

App ((App (App e1 e2) e3) e4)

使用规则：

%public expr_expr:
    | ID        { Symbol () }
    | NUMBER    { Symbol () }
    | LPAREN expr_expr RPAREN { () }
    | LAMBDA ID ARROW expr_expr { Lambda (, ) }
    | expr_expr expr_expr { Apply (, ) }

给出结构 (e1 , (e2 , (e3 , e4))) 而不是 (((e1, e2), e3), e4)。有没有一种方法可以控制规则而不是标记的关联性？

Answer 1

免责声明：我使用 ocamlyacc，而不是 menhir，所以我的回答基于前者。 AFAIUI，后者是向后兼容的，所以我想我的回答可能还是有用的。

引用文档 http://caml.inria.fr/pub/docs/manual-ocaml/lexyacc.html:

Rules can also contain the %prec symbol directive in the right-hand side part, to override the default precedence and associativity of the rule with the precedence and associativity of the given symbol.

所以我会尝试

%left Application

让你的规则保持关联（在你定义优先级的地方；你需要至少定义应用程序和 lambda 抽象的相对优先级）然后将你的规则更改为

| expr_expr expr_expr { Apply (, ) } %prec Application

这使得 Application 成为一个虚拟符号，仅用于分配关联性和优先级。

注1：以上部分是我的猜测。显然我自己从来没有（成功地）那样尝试过。我曾经写过 lambda 文法，我通过修改文法来强制执行结合性。

注2：如果还是不行，可以看看OCaml源码。 OCaml 语言具有相同的应用程序语法。

menhir - 减少表达式序列的关联性规则

menhir - associativity rules for reducing sequences of expressions

ocaml

yacc