2

前言

我已经编写了具有错误恢复功能的 GLR 解析器。当它遇到错误时，它会分成以下替代方案：

  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";

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

问题

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

4

1 回答 1

3

在字符级别进行 GLR（因此解析）纠错是可能的，但会加剧您的问题。

我们使用的 GLR 错误恢复过程对令牌进行操作，所以它没有那么糟糕。

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

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

于 2010-12-09T18:18:43.600 回答