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

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

0 голосов
/ 31 августа 2018

Я пытаюсь написать грамматику и анализатор Ларка, чтобы написать 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

Что мучительно близко!

Заранее спасибо за любые рекомендации.

1 Ответ

0 голосов
/ 31 августа 2018

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

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

...