1

writing a parser for lambda expressions,

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

When writing the .mly file how can I express the idea that a sequence of expressions

e1 e2 e3 e4

should be parsed as

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

Using the rules:

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

gives the structure (e1 , (e2 , (e3 , e4))) as opposed to (((e1, e2), e3), e4). Is there a way of controlling the associativity of a rule as opposed to a token?

4

1 回答 1

2

免责声明：我使用ocamlyacc, not menhir，所以我的答案基于前者。AFAIUI，后者向后兼容它，所以我认为我的答案可能还是有用的。

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

规则还可以在右侧部分包含 %prec 符号指令，以使用给定符号的优先级和关联性覆盖规则的默认优先级和关联性。

所以我会尝试

%left Application

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

| expr_expr expr_expr { Apply ($1, $2) } %prec Application

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

注1：以上部分是我的猜测。显然我从来没有（成功地）那样尝试过。当我曾经写过一个 lambda 语法时，我通过修改语法来强制关联性。

注2：如果不能如上，你可以看一下OCaml源代码。OCaml 语言具有相同的应用程序语法。

于 2016-12-18T07:58:51.833 回答