基于树位置的 Lark 解析

Question

我正在尝试编写 Lark 语法和解析器以在 numpy 之上编写 DSL。但是，Transformer 需要输出 Python 代码，而不是评估该代码。因此，例如，我想要：

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

这会产生一个 string:

'''
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)，这是一种完全可以接受的继续方式。然而，重要的是每个产生值的规则 return 都是该值的名称，因为父规则确实无法猜测这些名称是什么。特别是，您不能假设这些名称恰好是最后生成的两个名称。通常情况下，第二个操作数将具有最后生成的名称（尽管不坚持这一点允许进行一些优化）但第一个操作数实际上从来没有第二个姓氏。事实上，如果第二个操作数的计算根本不需要名字，它只能有第二个姓氏。

从外除运算符生成的代码中的错误可以清楚地看出这一点。您使用的转换器规则表明 / 的操作数是 thisv - 2 和 thisv - 1，但这会导致 v4/v5 的输出。 v4 是由 lag 运算符创建的，目的是计算 v5，因此它肯定不是 /.

的第一个操作数

要解决此问题，您只需 return 从每个操作中获取值的名称（或编号），然后您需要使用此名称而不是尝试猜测它。所以 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 中，变量是在函数范围内创建的，因此它们的值会一直保留到函数 return 为止。结果可能是在进行这样的计算时会积累大量垃圾。尝试使用基于堆栈的方法可能是值得的。在基于堆栈的方法中，您可以指望每个操作的操作数都在堆栈的顶部。

在这种情况下，您甚至不必跟踪堆栈大小（并且没有要跟踪的名称）。虽然跟踪堆栈大小可能很有用（一方面，它让您知道每个表达式需要多少堆栈），但跟踪看起来很不一样：它不是一个简单的计数器。通常，操作数增加堆栈计数，一元运算符保持不变，二元运算符递减。

基于树位置的 Lark 解析

Lark parsing based on tree location

python

dsl

parsing

numpy

lark-parser