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

Question

我目前正在尝试熟悉packrat解析。我已经阅读了2002年的PDF论文，链接

这里

在2.3节中，它将packrat缓存描述为一个初步过程(在实际解析之前发生)，在该过程中，通过从右到左读取输入来预先构建完整的缓存表。只有这样，才能开始从左到右的实际线性解析。

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

这里

..。

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

Answer 1

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

你的理解是正确的：

Packrat解析器扫描输入字符串

从左到右

Packrat解析器从

从右到左

但只有一种方法，而不是两种。让我们用一个简单的例子

解析表达式语法(PEG)

不使用左递归：

(请注意，左递归示例需要另一个冗长的解释，您可以参考

CPython的实现

有关详细信息，请参见)

语法导向翻译( Syntax Directed Translation，SDT)将类似于：

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

我们可以写一个

下面的函数：

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]

根据

比兰·福特的论文

，解析器需要

从左到右扫描输入字符串

并在任何位置构造缓存：

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

因此，让我们在幕后检查缓存结构，最初，我们有一个空的缓存和输入字符串：

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

当出现以下情况时，函数调用按以下顺序进行

..。显然，我们

从右到左构建缓存

在位置0(更不用说

或更高版本)。

发生的时间早于

(Y > 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.

如果您想阅读Packrat解析器实现的完整Python示例，可以查看

我的存储库

..。它包含一个

手工Packrat解析器

和一个

CPython PEG生成的Packrat解析器

基于

简单元语法

..。