0

我有一个在大多数情况下都有效的简单语法，但在一个地方它会报告错误，我认为它不应该，因为它可以使用回溯来解决。

这是有问题的部分。

command: object message_chain;
object: ID;
message_chain: unary_message_chain keyword_message?
             | binary_message_chain keyword_message?
             | keyword_message;
unary_message_chain: unary_message+;
binary_message_chain: binary_message+;
unary_message: ID;
binary_message: BINARY_OPERATOR object;
keyword_message: (ID ':' object)+;

这是简化版本，对象更复杂（它可以是其他命令、原始值等的结果，但那部分工作正常）。问题在于message_chain，在第一个替代方案中。对于像这样的输入，obj unary1 unary2它工作正常，但对于像这样的输入，它obj unary1 unary2 keyword1:obj2会尝试匹配keyword1为一元消息并在到达时失败:。我认为这种情况解析器会回溯并确定存在:并识别出这是关键字消息。

如果我将关键字消息设为非可选，它可以正常工作，但我需要关键字消息是可选的。

如果关键字消息在第二个备选方案（binary_message）和第三个备选方案（只是关键字消息）中，解析器会找到它。所以这样的事情会产生很好的结果：1 + 2 + 3 Keyword1:Value

我错过了什么？回溯在选项中设置为 true，并且在相同语法的其他情况下可以正常工作。

谢谢。

4

1 回答 1

1

对于 PEG 式回溯，这并不是真正的情况，因为一旦失败，它只会在未完成的推导中返回决策点。对于 input obj unary1 unary2 keyword1:obj2，具有单个标记前瞻，keyword1可以由unary_message_chain. 失败之前可能不会发生keyword_message，接下来要尝试的是 message_chain 的第二种选择，即binary_message_chain，因此缺少正确的解析。

但是，由于该语法是 LL(2)，因此应该可以扩展前瞻以避免keyword1从内部消耗unary_message_chain. 您是否尝试过明确设置k=2而不回溯？

于 2012-04-08T18:09:25.997 回答