前言
我已经编写了具有错误恢复功能的 GLR 解析器。当它遇到错误时,它会分成以下替代方案:
- 将预期的元素插入输入中(可能是用户刚刚错过了它)并照常进行。
- 用预期的元素替换错误的元素(可能是用户刚刚输入错误)并照常进行。
- 跳过错误元素,如果下一个元素也是错误的,则转到#2。
但是,如果输入有很多错误(例如,用户错误地将 JPEG 文件提供给解析器),则替代方案的数量会呈指数增长。
例子
这样的解析器对应如下文法:
Program -> Identifier WS Identifier WS '=' WS Identifier
Identifier -> ('a'..'z' | 'A'..'Z' | '0'..'9')*
WS -> ' '*
适用于以下文本:
x = "abc\"def"; y = "ghi\"jkl";
在中等现代的台式计算机上因“内存不足”而失败。
问题
如果输入错误,如何减少备选方案的数量?