Компиляция AST обратно к исходному коду

Question

В настоящее время я нахожусь в процессе создания парсера PHP, написанного на PHP, так как в моем предыдущем вопросе не было парсера. Сам парсер работает довольно хорошо.

Теперь, очевидно, парсер сам по себе мало что дает (кроме статического анализа). Я хотел бы применить преобразования к AST, а затем скомпилировать его обратно в исходный код. Применение преобразований не является большой проблемой, это должен делать обычный шаблон Visitor.

В настоящее время моя проблема заключается в том, как скомпилировать AST обратно в исходный код. Я вижу в основном две возможности:

1. Скомпилируйте код, используя некоторую предопределенную схему
2. Сохраните форматирование исходного кода и примените 1. только к узлам, которые были изменены.

На данный момент я хотел бы сосредоточиться на 1. как 2. кажется довольно сложным для выполнения (но если у вас есть советы по этому поводу, я хотел бы услышать их).

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

Я слышал, что шаблон Visitor также может быть использован для этого, но я не могу себе представить, как это должно работать. Насколько я понимаю шаблон посетителей, у вас есть некоторые NodeTraverser который рекурсивно перебирает все узлы и вызывает ->visit метод Visitor, Это звучит довольно многообещающе для манипулирования узлами, где Visitor->visit Метод может просто изменить узел, который был передан, но я не знаю, как его можно использовать для компиляции. Очевидная идея состоит в том, чтобы перебрать дерево узлов от листьев к корню и заменить посещенные узлы исходным кодом. Но это как-то не кажется очень чистым решением?

Answer 1

Проблема преобразования AST обратно в исходный код обычно называется "prettyprinting". Есть два тонких варианта: воссоздание текста, максимально приближенного к оригиналу (я называю это "печатью верности"), и (приятное) prettyprinting, которое генерирует красиво отформатированный текст. И то, как вы печатаете, зависит от того, будут ли кодеры работать над восстановленным кодом (им часто требуется точная печать), или ваше единственное намерение - скомпилировать его (в этот момент любая легальная печать вполне приемлема).

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

Фундаментальный способ довольно приятной печати достигается путем обхода AST ("шаблон посетителя", как вы его выразили) и генерирования текста на основе содержимого узла AST. Основная хитрость заключается в следующем: вызывать дочерние узлы слева направо (предполагая, что это порядок исходного текста), чтобы сгенерировать текст, который они представляют, добавляя дополнительный текст в соответствии с типом этого узла AST. Чтобы распечатать блок операторов, вы можете использовать следующий psuedocode:

 PrettyPrintBlock:
     Print("{"}; PrintNewline();
     Call PrettyPrint(Node.children[1]); // prints out statements in block
     Print("}"); PrintNewline();
     return;


 PrettyPrintStatements:
     do i=1,number_of_children
         Call PrettyPrint(Node.children[i]); Print(";"); PrintNewline(); // print one statement
     endo
     return;

Обратите внимание, что это выкладывает текст на лету, когда вы посещаете дерево.

Есть ряд деталей, которыми нужно управлять:

• Для узлов AST, представляющих литералы, вы должны восстановить значение литерала. Это сложнее, чем кажется, если вы хотите, чтобы ответ был точным. Печать чисел с плавающей точкой без потери точности намного сложнее, чем кажется (ученые ненавидят это, когда вы наносите ущерб значению числа Пи). Для строковых литералов вы должны восстановить кавычки и содержимое строкового литерала; Вы должны быть осторожны, чтобы восстановить escape-последовательности для символов, которые должны быть экранированы. Строковые литералы с двойными кавычками в PHP могут быть немного сложнее, так как они не представлены одиночными токенами в AST. (Наш PHP- интерфейс (реинжиниринг парсера /prettyprinter представляет их по существу как выражение, объединяющее фрагменты строки, что позволяет применять преобразования внутри строки "литерал").

• Интервал: некоторые языки требуют пробелов в критических местах. Жетоны ABC17 42 лучше не печатать как ABC1742, но можно жетоны ( ABC17) печатать как (ABC17). Один из способов решения этой проблемы - разместить место там, где это законно, но результат не понравится людям: слишком много пробелов. Не проблема, если вы только компилируете результат.

• Новые строки: языки, которые допускают произвольные пробелы, технически могут быть преобразованы в одну строку текста. Люди ненавидят это, даже если вы собираетесь скомпилировать результат; иногда вам приходится смотреть на сгенерированный код, и это делает это невозможным. Таким образом, вам нужен способ введения новых строк для узлов AST, представляющих основные элементы языка (операторы, блоки, методы, классы и т. Д.). Это обычно не сложно; при посещении узла, представляющего такую ​​конструкцию, распечатайте конструкцию и добавьте новую строку.

• Если вы захотите, чтобы пользователи приняли ваш результат, вы обнаружите, что вам придется сохранить некоторые свойства исходного текста, которые вы обычно не думаете хранить. Для литералов вам, возможно, придется восстановить основание литерала; кодеры, введя число в виде шестнадцатеричного литерала, недовольны, когда вы воссоздаете десятичный эквивалент, даже если это означает то же самое. Точно так же строки должны иметь "оригинальные" кавычки; большинство языков допускают либо ", либо" как символы строковых кавычек, и люди хотят, чтобы они использовали первоначально. Для PHP, какие кавычки вы используете, имеет значение и определяет, какие символы в строковом литерале необходимо экранировать. Некоторые языки допускают ключевые слова верхнего или нижнего регистра (или даже сокращения), а имена переменных в верхнем и нижнем регистре означают одну и ту же переменную; опять же, авторы оригинала обычно хотят получить свой оригинальный регистр. В PHP есть забавные символы в различном типе идентификаторов (например, "$"), но вы обнаружите, что это не всегда так (см. переменные $ в литеральных строках). Часто люди хотят, чтобы их исходное форматирование макета было выполнено: для этого нужно хранить информацию о номере столбца для конкретных токенов и иметь красивые правила печати о том, когда использовать этот столбец. нумеруйте данные, чтобы расположить текст с хорошей надписью, где это возможно, в одном и том же столбце, и что делать, если за этим столбцом заполняется строка, которая до сих пор была очень красивой.

• Комментарии: Большинство стандартных парсеров (включая тот, который вы реализовали с помощью парсера Zend, я вполне уверен) отбрасывают комментарии полностью. Снова, люди ненавидят это, и отклонят довольно напечатанный ответ, в котором комментарии потеряны. Это основная причина, по которой некоторые prettyprinters пытаются перегенерировать код, используя исходный текст (другая - копировать исходный макет кода для точной печати, если вы не захватили информацию о номере столбца). ИМХО, правильный трюк состоит в том, чтобы фиксировать комментарии в AST, чтобы преобразования AST тоже могли проверять / генерировать комментарии, но каждый делает свой собственный выбор дизайна.

Вся эта "дополнительная" информация собирается хорошим анализатором реинжиниринга. Обычные парсеры обычно не собирают ничего из этого, что затрудняет печать приемлемых AST.

Более принципиальный подход отличает красивую печать, целью которой является хорошее форматирование, от точной печати, цель которой состоит в том, чтобы регенерировать текст так, чтобы он максимально соответствовал исходному источнику. Должно быть понятно, что на уровне терминалов вам в значительной степени нужна верная печать. В зависимости от вашей цели, вы можете печатать с хорошим форматированием или точной печатью. Стратегия, которую мы используем, заключается в том, чтобы по умолчанию печатать с высокой точностью, когда AST не был изменен, и печатать там, где он есть (потому что часто механизм изменения не имеет никакой информации о номерах столбцов или числах и т. Д.). Преобразования помечают узлы AST, которые были недавно сгенерированы, как "отсутствие данных верности".

Организованный подход к красивой печати - это понимание того, что практически все текстовые языки программирования красиво отображаются в виде прямоугольных блоков текста. (Генератор документов TeX Кнута тоже имеет эту идею). Если у вас есть некоторый набор текстовых полей, представляющих фрагменты регенерированного кода (например, примитивные блоки, сгенерированные непосредственно для терминальных токенов), вы можете представить себе операторы для составления этих блоков: Горизонтальная композиция (сложить один блок справа от другого), Вертикальный (укладывать блоки друг на друга; это фактически заменяет печать новых строк), Отступ (Горизонтальная композиция с блоком пробелов) и т. Д. Затем вы можете создать свой симпатичный принтер, создав и создав текстовые поля:

 PrettyPrintBlock:
     Box1=PrimitiveBox("{"); Box2=PrimitiveBox("}");
     ChildBox=PrettyPrint(Node.children[1]); // gets box for statements in block
     ResultBox=VerticalBox(Box1,Indent(3,ChildBox),Box2);
     return ResultBox;

PrettyPrintStatements:
     ResultBox=EmptyBox();
     do i=1,number_of_children
         ResultBox=VerticalBox(ResultBox,HorizontalBox(PrettyPrint(Node.children[i]); PrimitiveBox(";")
     endo
     return;

Реальное значение в этом состоит в том, что любой узел может составлять текстовые поля, созданные его дочерними элементами, в произвольном порядке с произвольным промежуточным текстом. Таким способом вы можете перегруппировать огромные блоки текста (представьте, что VBox'ы используют методы класса в порядке имен методов). Ни один текст не выплевывается при обнаружении; только когда достигнут корень или какой-либо узел AST, где известно, что все дочерние блоки были созданы правильно.

Наш инструментарий реинжиниринга программного обеспечения DMS использует этот подход для печати всех языков, которые он может анализировать (включая PHP, Java, C# и т. Д.). Вместо того, чтобы прикреплять вычисления блоков к узлам AST через посетителей, мы присоединяем вычисления блоков в нотации текстового поля для конкретного домена

• H(...) для горизонтальных коробок
• V(....) для вертикальных ящиков
• Я (...) для отступов коробки)

непосредственно к правилам грамматики, что позволяет нам кратко выразить грамматику (синтаксический анализатор) и prettyprinter ("анти-синтаксический анализатор") в одном месте. Правила коробки prettyprinter автоматически компилируются DMS в посетителя. Механизм prettyprinter должен быть достаточно умным, чтобы понимать, как комментарии к этому влияют, и это, откровенно говоря, немного загадочно, но сделать это нужно только один раз. Пример DMS:

block = '{' statements '}' ; -- grammar rule to recognize block of statements
<<PrettyPrinter>>: { V('{',I(statements),'}'); };

Вы можете увидеть более крупный пример того, как это делается для языка программирования Wirth Oberon PrettyPrinter, показывающий, как объединяются правила грамматики и правила prettyprinting. PHP-интерфейс выглядит так, но, очевидно, он намного больше.

Более сложный способ сделать prettyprinting - это создать синтаксически-ориентированный переводчик (то есть пройтись по дереву и построить текст или другие структуры данных в древовидном порядке) для создания текстовых полей в специальном текстовом поле AST. Текстовое поле AST затем довольно печатается другим обходом дерева, но действия для него в основном тривиальны: напечатайте текстовые поля. Смотрите эту техническую статью: Pretty-printing для реинжиниринга программного обеспечения

Дополнительный момент: вы, конечно, можете сами собрать все эти механизмы. Но та же причина, по которой вы выбираете использовать генератор синтаксического анализатора (для его создания требуется много работы, и эта работа не способствует интересной цели), - это та же причина, по которой вы хотите выбрать сторонний генератор. полка довольнопринтер генератор. Вокруг много генераторов парсеров. Не так много генераторов prettyprinter. [DMS является одним из немногих, кто встроил оба.]