Как сгенерировать код для дерева AST, разобранного с вымышленного языка?

Question

Я прочитал статью на http://parsingintro.sourceforge.net/ и решил попробовать переписать ее как упражнение на Ruby. Две причины заставили меня сделать это: я хотел узнать больше о том, как кодировать Ruby (опыт работы с Java, PHP, C и немного Python), и я хотел узнать больше о парсерах / компиляторах.

У меня есть весь код, размещенный на https://github.com/parse/boatcaptain. Дерево AST генерируется, к сожалению, автор статьи не знаком с такими понятиями, как генерация кода и оптимизация.

Может ли кто-нибудь помочь мне, указав мне в правильном направлении, как превратить это дерево AST в «код»? Это дерево AST, которое генерируется

Я написал калькулятор на Java несколько лет назад, в нем используется много схожей терминологии и техник, которые я использовал в этом парсере. Но в калькуляторе у меня были методы для eval () - мои «классы» и, следовательно, получение вывода, должен ли я стремиться сделать что-то подобное здесь? Источник для калькулятора: https://github.com/parse/Uppsala-University-Courses/blob/master/ImpOOP-Calculator/src/Calculator.java

Мне бы очень хотелось получить отзыв о моем способе написания Ruby, я думаю, что я все еще пишу Ruby, как если бы я писал на Python, упуская некоторые приятные преимущества Ruby.

Answer 1

Генерация кода в его основной форме просто пересекает вашу промежуточную форму - AST - и выдает соответствующие инструкции на вашем целевом языке.

Во-первых, вам нужно выбрать целевой язык. На какой платформе вы хотите, чтобы ваш входной файл работал? Основные доступные вам варианты:

• Переводчик из источника в источник
• Компилятор для нативного кода
• Компилятор для байт-кода (для своевременного запуска на ВМ)

Выбор целевого языка может определить объем работы, которую вам придется выполнить для сопоставления между языками. Например, сложно / было бы сложно отобразить объектно-ориентированные классы в ASM. Сопоставление процедурного кода по своей сути со стековым кодом также может оказаться проблемой.

Какой бы язык вы ни выбрали, проблема, без сомнения, сводится к следующей процедуре: посетите узлы вашего дерева и, в зависимости от их типа, выведите соответствующую инструкцию.

Допустим, в вашем AST вы встретили следующий узел (как и тот, к которому вы подключились):

        =
delta       /
      alpha   beta

Видя, что это узел «назначения», Генератор кода затем знает, что он должен оценить RHS дерева, прежде чем вставить это значение в LHS; «Дельта». Итак, мы следуем за узлом RHS вниз и видим, что это операция деления. Затем мы знаем, что мы должны оценить как LHS, так и RHS этого узла, прежде чем делить их и записать результат в «delta».

Так что теперь мы движемся вниз по LHS, видим, что это переменная, и мы выдаем инструкцию «load». Мы возвращаемся назад, а затем вниз по RHS, и аналогично излучаем «нагрузку» для «бета». Затем мы возвращаемся вверх по дереву (взяв с собой и альфа, и бета), испускаем инструкцию деления для обоих операндов, сохраняем полученный результат, передаем его по дереву в эмиттер присваивания и оставляем его в «дельте».

Таким образом, результирующий код для этого фрагмента может быть:

load alpha
load beta
tmp = div alpha beta
store delta tmp

Что касается уже существующих библиотек Ruby Code Generator, я не знаю ни одной, извините. Я надеюсь, что этот ответ не был слишком общим или упрощенным для вас.