parsing - GLR 解析器错误恢复 : too much alternatives when there are errors in input

Question

序言

我已经编写了具有错误恢复功能的 GLR 解析器。当它遇到错误时，它会拆分为以下选项:

将预期的元素插入输入(可能是用户刚刚错过了它)并照常进行。

用预期的元素替换错误的元素(可能是用户刚刚输入错误)并照常进行。

跳过错误的元素，如果下一个元素也有错误，则转到#2。

但是如果输入有很多错误(例如，用户错误地将 JPEG 文件提供给解析器)，则许多替代方案会呈指数增长。

示例

这样的解析器对应如下文法:

Program -> Identifier WS Identifier WS '=' WS Identifier
Identifier -> ('a'..'z' | 'A'..'Z' | '0'..'9')*
WS -> ' '*

应用于以下文本:

x = "abc\"def"; y = "ghi\"jkl";

在中等现代的台式计算机上因“内存不足”而失败。

问题

如果输入错误，如何减少备选方案的数量？

Answer 1

在字符级别进行 GLR(因此解析)错误更正是可能的，但会加剧您的问题。

我们使用的 GLR 错误恢复程序对 token 进行操作，因此它并没有那么糟糕。

但是当输入有大量错误时，很难恢复。更复杂的错误恢复方案基本上使用解析器来识别输入中语言的有效子字符串，然后尝试将子字符串修补在一起以获得结果。这是相当雄心勃勃的。

我已经构建了具有错误恢复功能的 GLR 解析器。我没有那么雄心勃勃。一般来说
当实时解析器的数量超过“大量”(例如，10,000)或遇到的语法错误数量超过阈值(例如，10 或 20)时，解析器通常会中止。如果解析器在最后一秒没有推进输入流，您可能会考虑中止解析器，这是一个间接标志，它有太多的实时解析器。