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

Проблема преобразования AST обратно в исходный код обычно называется "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, я почти уверен) полностью отбрасывают комментарии. Опять же, люди ненавидят это и отвергнут красиво напечатанный ответ, в котором комментарии теряются. Это основная причина, по которой некоторые красивые принтеры пытаются регенерировать код с использованием исходного текста (другой способ - скопировать исходный макет кода для точной печати, если вы не записали информацию о номере столбца). ИМХО, правильный трюк заключается в том, чтобы фиксировать комментарии в AST, чтобы преобразования AST также могли проверять/генерировать комментарии, но каждый делает свой собственный выбор дизайна.

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

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

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

 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),'}'); };

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

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

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