GLR解析器具有错误恢复：输入中存在错误时的替代方案太多

Question

前言

我已经编写了GLR-Parser，并使用了错误恢复。当它遇到错误时，它将分为以下替代方案：

1. 将预期元素插入输入（可能是用户只是错过的）并照常进行。
2. 用预期的元素替换错误的元素（可能是用户刚刚制作错误）并照常继续进行。
3. 跳过错误的元素，如果下一个元素也错误，请转到＃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错误恢复过程在令牌上运行，因此并不那么糟糕。

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

我已经构建了具有错误恢复的GLR解析器。我不是那么雄心勃勃。通常，当活解析器的数量超过“大数字”（例如10,000）或遇到的语法错误数量超过阈值时，解析器通常只是中断（例如，10,000）（例如，10或20）。如果未在最后一秒钟内提出输入流，则可以考虑中止解析器，这是一个间接的符号，它的实时解析器太多。