2

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

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

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

4

1 回答 1

2

我最近进行了类似的研究，遇到了完全相同的困惑，并解决了它。无论您是否仍在研究此主题，这都是我的答案。

你的理解是正确的：

  • Packrat 解析器从左到右扫描输入字符串
  • Packrat 解析器从右到左构造缓存

但只有一种方法，而不是两种。让我们使用一个没有左递归的简单示例解析表达式语法 (PEG) ：E -> Num + E | Num

（注意，左递归的例子需要另外长解释，具体可以参考CPython的实现）

语法定向翻译 (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 的论文，解析器需要从左到右扫描输入字符串并在任意位置构造缓存：

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.

如果您想阅读 Packrat 解析器实现的完整 Python 示例，可以查看我的存储库。它包含一个手工制作的 Packrat 解析器和一个基于简单元语法的CPython PEG 生成的 Packrat 解析器。

于 2021-02-28T07:56:21.800 回答