基于树位置的Lark解析

Question

我正在尝试编写一个Lark语法和解析器来编写一个在numpy之上的DSL。但是，Transformer需要输出Python代码，而不是eval代码。所以，例如，我想：

my_parser("max(mat1/mat2, 20) / lag(mat1, 5)")

这会产生一个字符串：

'''
v0 = mat1
v1 = mat2
v2 = v0/v1
v3 = np.max(v2[-20:, :], axis=0)
v4 = mat1
v5 = v4[-5, :]
v6 = v3/v5
'''

其中mat1和mat2是已知的numpy矩阵。我正在尝试：

这给了

from __future__ import print_function
import itertools
from lark import Lark, Transformer

grammar = r"""

    ?value: list
          | max
          | mat1
          | mat2
          | lag
          | div
          | max
          | SIGNED_NUMBER
          | ESCAPED_STRING

    list : "(" [value ("," value)*] ")"
    lag: "lag" "(" value "," SIGNED_NUMBER ")"
    mat1: "mat1"
    mat2: "mat2"
    max: "max" "(" value "," SIGNED_NUMBER ")"
    div: value "/" value

    %import common.SIGNED_NUMBER
    %import common.ESCAPED_STRING
    %import common.WS
    %ignore WS

    """

class MyTransformer(Transformer):
    vcounter = itertools.count()

    def __init__(self):
        self.nplist = []

    def list(self):
        pass

    def mat1(self, items):
        thisv = self.vcounter.next()
        self.nplist.append(
            "v" + str(thisv) + " = mat1"
        )

    def mat2(self, items):
        thisv = self.vcounter.next()
        self.nplist.append(
            "v" + str(thisv) + " = mat2"
        )

    def div(self, items):
        thisv = self.vcounter.next()
        self.nplist.append(
            "v" + str(thisv) + " = v" + str(thisv - 2) + "/v" + str(thisv-1)
        )

    def lag(self, items):
        thisv = self.vcounter.next()
        self.nplist.append(
            "v" + str(thisv) + " = v" + str(thisv -1) + "[-" + items[1] + ", :]"
        )

    def max(self, items):
        thisv = self.vcounter.next()
        self.nplist.append(
            "v" + str(thisv) + " = np.max(v" + str(thisv-1) + "[-" + items[1] +":, :], axis=0)"
        )

    def transform(self, tree):
        self._transform_tree(tree)
        return self.nplist

my_parser = Lark(grammar, start='value')

text = "max(mat1/mat2, 20) / lag(mat1, 5)"
tree = my_parser.parse(text)
print(*MyTransformer().transform(tree), sep='\n')

这给了

v0 = mat1
v1 = mat2
v2 = v0/v1
v3 = np.max(v2[-20:, :], axis=0)
v4 = mat1
v5 = v4[-5, :]
v6 = v4/v5

这是非常接近的！

提前感谢任何指导。

Answer 1

您的程序正在尝试生成three-address code (TAC)，这是一种完全可以接受的方式。但是，生成值的每个规则都必须返回该值的名称，因为父规则实际上无法猜测名称是什么。特别是，您不能假设名称恰好是生成的最后两个名称。通常情况下，第二个操作数将具有最后生成的名称（虽然不坚持这允许进行一些优化）但第一个操作数实际上从来没有第二个姓。实际上，如果第二个操作数的计算根本不需要名字，它只能有第二个姓。

从外部除法运算符的生成代码中的错误可以清楚地看出这一点。你正在使用的变换器规则说/的操作数是thisv - 2和thisv - 1，但这导致v4/v5的输出。 v4是由lag运算符创建的，用于计算v5，所以它肯定不是/的第一个操作数。

要解决此问题，您只需要从每个操作返回值的名称（或数字），然后您需要使用此名称而不是尝试猜测它。所以div将成为：

def div(self, items):
    # Name of this value
    thisv = "v" + str(self.vcounter.next())
    # Output code to define name
    self.nplist.append(
        thisv " = " + items[0] + "/" + items[1])
    )
    # Return name so that whoever uses this value knows it
    return thisv

这是否真的是最佳解决方案至少是开放的辩论。在python中，变量是在函数范围内创建的，因此它们的值会一直存在，直到函数返回为止。结果可能是在进行这样的计算时积累了大量垃圾。可能值得尝试基于堆栈的方法。在基于堆栈的方法中，您可以依赖于每个操作的操作数位于堆栈顶部的事实。

在这种情况下，您甚至不必跟踪堆栈大小（并且没有要跟踪的名称）。尽管跟踪堆栈大小很有用（一方面，它可以让你知道每个expresion需要多少堆栈），但跟踪看起来完全不同：它不是一个简单的计数器。通常，操作数增加堆栈计数，一元运算符不管它，二元运算符递减。