递归下降解析器中的错误报告

Question

我将为配置文件编写递归下降解析器。这些文件与ini文件大致相似。以下是类似EBNF格式的语言：

document     ::= { category }
category     ::= title {entry}
title        ::= "[" <name> "]"
entry        ::= <key> ":" <value>

这里是一个在结尾处应该会产生解析错误的文件示例：

[Category1]
key1:val1
key2 :val2
key3 : val3

[Category2]
key4: val4

this line right here should produce an error

我能找到的所有示例都会解析输入，直到遇到无效符号就退出而不打印有用的错误信息。我有一个遵循这种行为的工作解析器，但我不知道如何实现有用的错误报告。

例如，一个document由零个或多个类别组成。当前两个类别被解析而没有错误时，第三个包含语法错误怎么办？如果输入在第二个类别后结束，并且由于没有标记而无法解析第三个类别（这不应该产生错误消息），该怎么办？我该如何区分这些情况？无效行可以通过两种方式变得有效：成为条目或标题。这让我感到困惑。

当程序到达上面输入的最后一行时，我希望我的程序打印类似于line 9: expected entry or title的内容。人们通常如何在递归下降解析器中实现错误消息？

- user836218

---

我通常会做这样的事情：“解析错误第42行：找到'％'，期望'＆'。” - rossum

使一个无效的字符串变为有效是非常复杂的任务。首先要进行简单的错误报告。 - Alexei Kaigorodov

Answer 1

我认为您在问几个不相关的问题，我来试着回答一下：

当前两个类别被解析而无错误，但第三个包含语法错误时，您应该怎么做？

当然，这取决于您的要求。从严格意义上讲，这将是验证失败，因为传递的文档实际上不符合您的语法规则，因为存在您提到的违规情况。它是否会抛出错误、返回false、返回部分结果，这完全取决于您的要求。

如果输入在第二个类别后结束，并且由于没有剩余标记而无法解析第三个类别（这不应产生错误消息），那么该怎么办？如何区分这些情况？

这里没有问题，因为它遵循"document"符号。如果您对实际实现感到困惑，那么这就是一个实现细节（您没有提供任何代码）。

也许您应该尝试将EBNF可视化为更基本的BNF形式，不使用"{ }"扩展，以下是一个示例：

document     ::= category
category     ::= title entries category | title entries
title        ::= "[" <name> "]"
entries      ::= entry | entries
entry        ::= <key> ":" <value>

我个人认为用这种方式表示您的语法会更有助于指导您需要递归的位置。例如，在这种情况下，您将希望尝试在“category”符号解析内解析“category”。您的代码结构会大致遵循此规则 - 即，如果无法将下一个符号解析为类别，则无论如何返回true（因为第二个定义“title entries”将遵循）。

“人们通常如何在递归下降解析器中实现错误消息？”我也有同样的问题，但是看到我在SO上找不到任何答案，我将按照以下方式实现它：

1.当我解析和读取标记时，我将存储消耗的长度。 2.当达到错误时，请不要立即抛出它 - 将其与已解析的标记数量一起存储。 3.在包括回溯在内的解析结束时，如果没有可解析的解决方案，请抛出消耗了最多符号的错误。

关键是第2条。在使用回溯的递归下降解析器中执行此操作时，可能会抛出多个误报。我认为从可用性的角度来看，简单地抛出最远解析的那个错误是一个相当不错的启发式方法。

- badunk

---

我也找不到任何好的例子。好的解决方案！ - Sheldon Juncker