ocaml - 使用Camlp4解析一串全称量词和存在量词

Question

我正在使用 Camlp4 解析一串量词，其中量化关键字和变量用逗号分隔。一个例子如下:

exists x,y,z, forall a,b, exists h,k

这里，exists和forall是关键字，x,y,z,a,b,h,k是标识符。相应的标记是 EXISTS、FORALL 和 IDENTIFIER of string。

我的数据结构:

type quantifier =
  | Exists of string
  | Forall of string

要解析上面的量词字符串，我的规则是:

id: [[
  `IDENTIFIER s-> s
]];

one_kind_quantifiers: [[
  `EXISTS; il=LIST1 id SEP `COMMA -> List.map (fun v -> Exists v) il
 |`FORALL; il=LIST1 id SEP `COMMA -> List.map (fun v -> Forall v) il
]];

quantifiers: [[
  t=LIST0 one_kind_quantifiers SEP `COMMA -> List.flatten t
]];

但是，我的解析器总是抛出错误:

Stream.Error("[id] expected after COMMA (in [one_kind_quantifiers])").

你知道如何解决这个问题吗？如何让LIST1在检测到`COMMA之后的元素是关键字时停止抛出错误？

非常感谢!

(有关更多信息，如果我使用空格来分隔受同一量化关键字影响的变量，例如 exists x y z, forall a b, contains h k。并删除 SEP `COMMA 在 one_kind_quantifiers 规则中，那么解析器就可以完美解析这个新字符串)。

============================

更新解决方案:

根据 Igor (@ygrek) 的建议，我可以通过不使用 LIST1 而是手动编写规则来解析字符串列表来编写预期的解析器。

id_list: [[
  `IDENTIFIER s -> [s]
 |t=`id_list; `COMMA; `IDENTIFIER s -> t@[s]
]];

one_kind_quantifiers: [[
  `EXISTS; il=id_list -> List.map (fun v -> Exists v) il
 |`FORALL; il=id_list -> List.map (fun v -> Forall v) il
]];

quantifiers: [[
  t=LIST0 one_kind_quantifiers SEP `COMMA -> List.flatten t
]];

请注意，解析字符串列表的规则是:

id_list: [[
   `IDENTIFIER s -> [s]
 | t=`id_list; `COMMA; `IDENTIFIER s -> t@[s]
]];

但不是:

id_list: [[
   `IDENTIFIER s -> [s]
 | `IDENTIFIER s; `COMMA; t=`id_list -> [s]@t
]];

编写 id_list 规则的第二种方法会引发与使用 LIST1 时相同的错误。 (所以我猜这可能是 LIST1 的实现方式......)

Answer 1

camlp4 是递归下降解析器，IIRC 它只会在每个规则的第一个标记上回溯，一旦第一个标记匹配，它将继续直到规则结束。在这种情况下，对于 LIST1 它可以匹配逗号，因此它会下降，但第二个标记不符合预期，并且回溯为时已晚。我想展开 LIST1 并内联到语法中可以解决这个问题，但可能会相当难看。