Разбор жаворонка в зависимости от местоположения дерева

Question

Я пытаюсь написать грамматику Lark и парсер, чтобы написать DSL поверх numpy. Однако Transformer должен выводить код Python, а не проверять этот код. Так, например, я хотел бы иметь:

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 Известны матерчатые матрицы. Я пытаюсь с:

и это дает

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

Ваша программа пытается сгенерировать трехадресный код (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 переменные создаются в области действия функции, поэтому их значения сохраняются до тех пор, пока функция не вернется. Следствием этого может стать накопление большого количества мусора при выполнении подобных вычислений. Возможно, стоит попробовать подход на основе стека. В подходе, основанном на стеке, вы можете рассчитывать на то, что операнды каждой операции находятся на вершине стека.

В этом сценарии вам даже не обязательно отслеживать размер стека (и нет имен для отслеживания). Хотя может быть полезно отслеживать размер стека (во-первых, он позволяет узнать, сколько стека нужно каждому выражению), но отслеживание выглядит совсем иначе: это не простой счетчик. Обычно операнды увеличивают количество стеков, унарные операторы оставляют его в покое, а бинарные операторы уменьшают.