Сомневаюсь в использовании полиморфизма при кодировании дерева синтаксического анализа / оценки - PullRequest
Новая
       30

Сомневаюсь в использовании полиморфизма при кодировании дерева синтаксического анализа / оценки

0 голосов
/ 22 декабря 2009

Я работаю над переводчиком для игрушечного языка, просто чтобы научиться создавать переводчика. Я уже реализовал простой синтаксический анализатор для грамматики, которая генерирует дерево разбора. Теперь обычным способом оценки дерева разбора будет использование полиморфизма в узлах дерева разбора, с кодом, который выглядит примерно так (в Python): 

class Node:
    def __init__(self,left,right):
        self.left=left
        self.right=right

    def evaluate(self):
        print "throw an exception"

class AddNode(Node):
    def evaluate(self):
        return evaluate(self.left)+evaluate(self.right)

class SubNode(Node):
    def evaluate(self):
        return evaluate(self.left)-evaluate(self.right)

Метод оценки переопределяется в каждом потомке узла и защищается, чтобы вести себя как нужно. Значение выражения можно найти, просто вызвав методуборка () в корне.

Другой способ состоит в том, чтобы не иметь какой-либо функции оценки в узлах, но генерировать дерево разбора, которое просто назначает тип узлу. Код оценки выполняется в отдельной функции, которая рекурсивно исследует каждый узел и решает, как его оценить. Это приведет к функции с большой конструкцией «if else», переключателем или таблицей переходов.

Почти в каждом месте, куда я смотрю, и то, чему меня учили в колледже, кажется, указывает на то, что первый метод всегда лучше. Я не совсем понимаю, почему первый метод должен превосходить второй. Почему полиморфизм обязательно лучше в этом случае? Функция с большой таблицей «если еще» отсутствует, но в основном тот же код все еще там, но перемещен в другое место и разбросан по множеству разных классов.

Это привлекло мое внимание, потому что я подумал, что мне может понадобиться изменить значение некоторых операторов позже, возможно, даже разрешить переопределение операторов во время выполнения. Я также отношусь к вызовам функций так же, как к операторам, поэтому было бы неплохо иметь что-то вроде таблицы переходов, которую можно добавить во время выполнения.

Вероятно, есть какое-то существенное преимущество с первым методом, которого я сейчас не вижу. Может кто-нибудь указать на это?

1 Ответ

1 голос
/ 22 декабря 2009

Это интересный вопрос. Мне кажется, что полиморфизм все еще хороший путь, даже если у вас перегрузка операторов.

То, что вы определяете с помощью своих полиморфных классов, - это примитивные операции, которые поддерживаются в языке. Перегрузка оператора не добавляет больше примитивных возможностей в язык. Перегруженный оператор фактически эквивалентен вызову функции и должен быть реализован аналогичным образом.

Сохранение семантики оператора, локализованного в классе оператора, по моему мнению, сделает ваш проект чище. Это связано с тем, что для реализации новой примитивной операции вам просто нужно определить класс, а затем создать экземпляр во время синтаксического анализа. Альтернатива потребует изменения парсера и оценщика. У меня просто есть ощущение, что оценщик может стать большим гнездом операторов if для обработки различных особых случаев для операторов, и эти специальные случаи могут быть хорошо спрятаны в классах операторов.

Мне трудно поверить в то, что я говорю здесь, потому что я использовал обе техники в прошлом, и они обе работали хорошо. ; -)

...