python rply反向解析器

Question

我正在使用rplyPython3.6 为一个小型私有项目创建词法分析器和解析器。但我注意到的是，解析器似乎翻转了词法流的顺序。这是我正在解析的文件：let test:string = "test";print(test);词法分析器输出：Token('LET', 'let')Token('NAME', 'test')Token('COLON', ':')Token('NAME', 'string')Token('EQUALS', '=')Token('STRING', '"test"')Token('SEMI_COLON', ';')Token('PRINT', 'print')Token('OPEN_PARENS', '(')Token('STRING', '"test"')Token('CLOSE_PARENS', ')')Token('SEMI_COLON', ';')如您所见，它是按脚本顺序排列的。我使用解析器创建一个带有 name test、 typestring和 value的变量test。然后我想打印变量。它确实创建了变量，但是当我想打印出来时，什么也没有。但是当我像这样翻转脚本时print(test);let test:string = "test";它能够正确打印值。两个解析器“规则”如下所示： 打印：@self.pg.production('expression : PRINT OPEN_PARENS expression CLOSE_PARENS SEMI_COLON expression')def print_s(p):    ...创建变量：@self.pg.production('expression : LET expression COLON expression EQUALS expression SEMI_COLON expression')def create_var(p):    ...所以我的问题是：如何翻转解析内容的顺序？编辑：我在文档中寻找了类似的问题或问题，但没有找到任何东西。

Answer 1

这是一个更简单的例子；希望你能看到这个模式。

关键的见解是当生产的匹配被完全解析时执行缩减操作（即解析器函数）。这意味着如果一个产生式包含非终结符，则这些非终结符的动作在整个产生式的动作之前执行。

应该清楚为什么这是真的。每个生产动作取决于所有组件的语义值，在非终结符的情况下，这些值是通过运行相应的动作产生的。

现在，考虑这两种非常相似的解析 a listof things 的方法。在这两种情况下，我们都假设有一个基础产生式，它识别出一个空的list( list :) 并且什么都不做。

1. 右递归：

   list : thing list

2. 左递归：

   list : list thing

在这两种情况下，操作都会打印thing，这p[0]在右递归的情况下，p[1]在左递归的情况下。

右递归产生将导致things 以相反的顺序打印，因为thing直到内部list被解析（并且它的组件被打印）之后才会打印 s 。

但thing出于同样的原因，左递归产生式将按从左到右的顺序打印s。区别在于左递归情况下的 tgat，内部（递归）list包含初始things，而在右递归情况下，则list包含最终things。

如果您只是构建things的 Python 列表，这可能无关紧要，因为执行顺序并不重要。它仅在此示例中可见，因为该操作具有副作用（打印值），这使得执行顺序可见。

在极少数情况下确实有必要时，还有其他技术可以对操作进行排序。但最佳实践是在语法上可行时始终使用左递归。左递归解析器效率更高，因为解析器不需要累积一堆不完整的产生式。并且左递归通常也更适合您的操作。

例如，在这里，左递归操作可以附加新值 ( p[0].append(p[1]); return p[0])，而右递归操作需要创建一个新列表 ( return [p[0] + p[1])。由于重复追加是平均线性时间，而重复串联是二次的，左递归解析器对于大列表更具可扩展性。