LookAheadEnumerator: 在你的解析器中实现回溯

• 下载源文件 - 8.3 KB

引言

复杂的解析器通常需要支持回溯，这是一种重新访问你已经遇到的项目的方法。这个技巧有两个方面，高效地实现它，以及透明地实现它。LookAheadEnumerator<T>类提供了这两者。

更新： 修复错误，更稳健，文档注释，并将代码的90%进行了“俚语化”（删除了switch/nameof等），以便Slang可以处理它，并且我可以在我的生成的解析器代码中使用它。

更新： LookAheadEnumerator现在广泛用于我的Parsley解析器生成器，该生成器可以解析C#（解析大型子集的示例在链接中）

背景

在解析器代码中，通常需要为输入使用某种“流”接口，例如TextReader类或实现IEnumerator<T>的类。我更喜欢枚举器，因为它们无处不在且简单。然而，在没有将流式源预加载到内存中的情况下进行解析，回溯可能很困难。这对于小文本来说很好，但不适用于大量数据，例如大量的JSON。

通常，对于枚举器，你所能做的就是MoveNext()，有时是Reset()，如果幸运的话。无法回溯到特定的先前位置，即使可以，对于真正的流式源（如HTTP响应或控制台输入）也可能不起作用。

另一方面，回溯解析器需要“标记”其当前位置，然后在尝试几种备选方案之前，直到找到一个可以解析的方案。这意味着多次重新访问相同的文本序列。

回溯解析器本质上效率较低，但比非回溯解析器更灵活。我已尽力优化此类，使其尽可能高效地用于此目的。

概念化这个混乱

我将一个数组支持的队列嵌入到这个类中，该队列用于支持前瞻缓冲区。队列从16个元素开始，并根据需要增长（几乎每次翻倍以避免太多重新分配 - .NET中的堆比CPU便宜），这取决于需要多少前瞻。当一个LookAheadEnumeratorEnumerator<T>（前瞻光标）前进时，它通常需要主类将更多数据读入队列以满足它。当主光标前进时，它将丢弃队列中的项目（只需递增_queueHead，这非常快）。在使用前瞻光标时，不建议前进或重置主光标。在这种情况下，结果是不确定的，因为我尚未在这些枚举器中实现版本控制。

如何使用这个项目

你像标准IEnumerator<T>一样使用代码，并带有一个附加属性 - LookAhead，它允许你从当前位置foreach，而无需移动光标。还有Peek()和TryPeek()，它们向前看指定数量的位置，以及DiscardLookAhead()，它只是将光标移动到物理位置并清除缓冲区。

var text = "fubarfoobaz";
var la = new LookAheadEnumerator<char>(text.GetEnumerator());
la.MoveNext(); // can't look ahead until we're already over the position 
               // we want to start look at.
foreach (var ch in la.LookAhead)
    Console.Write(ch);
Console.WriteLine();
while (la.MoveNext())
{
    foreach (var ch in la.LookAhead)
        Console.Write(ch);
    Console.WriteLine();
}

这将在控制台中打印以下内容

fubarfoobaz
ubarfoobaz
barfoobaz
arfoobaz
rfoobaz
foobaz
oobaz
obaz
baz
az
z

正如你所看到的，我们在每次迭代中将主光标增加一，然后我们从那里枚举LookAhead。枚举LookAhead不会影响主光标*。

* 基础物理读取光标会像必须的那样前进，但使用一个队列提供了一个外观，该队列为你缓冲了已经读取的输入，并将其作为下一个输入呈现。

通常在解析器中，你将使用它处理令牌，例如LookAheadEnumerator<Token>，然后每次需要回溯时，你将沿着LookAhead而不是主光标进行解析。当你找到一个匹配项时，你将不得不丢弃所有匹配的令牌，可以通过沿着主光标重新解析，或者通过计数和前进（如果你知道解析了多少个令牌）来实现。如果你只解析了主解析的一个备选项，你可以在匹配备选项后简单地使用DiscardLookAhead()。

大概就是这样了。这是一个非常专业的类，但是当你需要它时，你真的需要它。

历史

• 2019年12月19日：初步提交
• 2019年12月23日：更新