2

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

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

这里，exists和forall是关键字，x,y,z,a,b,h,k是标识符。对应的记号是EXISTS和。FORALLIDENTIFIER 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, exists 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是实现的方式......）

4

1 回答 1

2

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

于 2015-07-09T23:36:21.757 回答