Packrat 缓存：从右到左还是从左到右？

Question

我目前正在尝试熟悉 Packrat 解析。因此，我阅读了 2002 年链接的 PDF 论文 here，在第 2.3 节中，它将 packrat 缓存描述为一个初步过程（发生在实际解析之前），其中预先构建了一个完整的缓存 table通过从右到左阅读输入。只有这样，真正的从左到右的线性解析才能开始。

但在我发现的每个 PEG 解析器实现中，"cache" 选项通常是在实际从左到右解析期间发生的缓存过程。例如 here。

这两种方法有什么区别吗？谢谢。

Answer 1

我最近在做类似的研究，遇到了完全相同的困惑，并解决了它。不管你是否还在研究这个话题，这就是我的答案。

您的理解是正确的：

Packrat 解析器从左到右
Packrat 解析器从从右到左

但是只有一种方法，没有两种。让我们使用一个没有左递归的简单示例 Parsing Expression Grammar (PEG)：E -> Num + E | Num

（注意，左递归的例子需要另外长篇大论，具体可以参考CPython's implementation）

句法导向翻译 (SDT) 类似于：

E -> a=Num + b=E { a + b }
E -> Num { Num }

我们可以在下面写一个parse_E函数：

def parse_E(idx):
    if idx in cache['parse_E']:
        return cache['parse_E'][idx]

    lval, nidx = parse_Char(idx)
    if nidx < len(self.tokens):
        operator, nnidx = parse_Char(nidx)
        if operator == '+':
            # E -> Num + E
            rval, nnnidx = parse_E(nnidx)
            cache['parse_E'][idx] = lval + rval, nnnidx
            return cache['parse_E'][idx]
    
    # E -> Num
    cache['parse_E'][idx] = lval, nidx
    return cache['parse_E'][idx]

根据Byran Ford's paper，解析器需要从左到右扫描输入字符串并在任意位置构造缓存：

for idx in len(input_string):
    parse_E(idx)
    parse_Char(idx)

那么，让我们检查一下引擎盖下的缓存结构，最初，我们有一个空缓存和输入字符串：

cache: {'parse_E': {}, 'parse_Char': {}}
input string: `2 + 3 + 4`

当 idx=0 时，函数调用按以下顺序发生。显然，我们在位置0从右到左构建缓存（更不用说idx=1或以上）。

parse_Char(Y) 早于 parse_Char(X) (Y > X)
parse_Char(X) 必须早于 parse_E(X)

   parse_E(0)     ---   (E -> Num + E) (pending)
-> parse_Char(0)  --- 2 (pending)
-> parse_Char(1)  --- + (pending)
-> parse_E(2)     --- E (E -> Num + E) (pending)
-> parse_Char(2)  --- 3 (pending)       
-> parse_Char(3)  --- + (pending)
-> parse_E(4)     --- E (E -> Num) (pending)
-> parse_Char(4)  --- 4 (acc)

# Only after parse_Char(4) succeed and fill into cache, parse_E(4) can be successful...and so on.

如果您想阅读完整的 Python Packrat 解析器实现示例，您可以查看 my repository. It contains a handmade Packrat parser and a CPython PEG generated Packrat parser based on a simple meta grammar。

Packrat 缓存：从右到左还是从左到右？

Packrat caching : Right to left vs. Left to right?

algorithm

parsing

peg

packrat