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

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

我可以在网上找到的所有示例都会解析输入，直到到达无效符号，然后退出而不打印有用的错误消息。我有一个遵循这种行为的工作解析器，但我不确定如何实现有用的错误报告。

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

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

Answer 1

我认为你问了几个大且不相关的问题，我会尽力回答：

如果前两个类别解析没有错误，但第三个类别包含语法错误，我该怎么办？

这当然取决于您的要求。从严格意义上讲，这将是验证失败，因为由于您提到的违规行为，传入的文档实际上并不符合您的语法规则。无论是抛出Error、返回false、返回部分结果，一切都取决于您的要求。

如果输入在第二个类别之后结束并且我无法解析第三个类别，因为没有留下标记（这不应该产生错误消息）怎么办？我如何区分这些情况？

正如你所说，这里没有问题，因为它符合符号document。如果您对实际实现感到困惑，那么这就是实现细节（您没有提供任何代码）。

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

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

我个人认为，以这种方式表示语法可以为需要递归的地方提供更多指导。例如，在这种情况下，您将希望尝试category在category符号解析中进行解析。代码的结构或多或少会遵循这一点 - 即，如果它无法将下一个符号解析为类别，则无论如何返回 true （因为title entries遵循第二个定义）

人们通常如何在递归下降解析器中实现错误消息？

我自己也有同样的问题，但是看到我找不到任何答案，我将按以下方式实现它：

1. 当我解析和吃掉令牌时，我将存储消耗的长度。
2. 当出现错误时，不要立即抛出它 - 将其与已解析的标记数量一起存储。
3. 解析结束时，包括回溯，如果没有可解析的解，则抛出消耗符号最多的错误

关键是#2。在实现带有回溯的递归下降解析器时，可能会引发多个误报。我认为就可用性而言，简单地抛出解析最远的启发式通常是一种不错的启发式。