Проблема преобразования AST обратно в исходный код обычно называется «prettyprinting».Есть два тонких варианта: воссоздание текста, максимально приближенного к оригиналу (я называю это «печатью верности»), и (приятное) prettyprinting, которое генерирует красиво отформатированный текст.И то, как вы печатаете, зависит от того, будут ли кодеры работать над восстановленным кодом (им часто требуется точная печать) или ваше единственное намерение - скомпилировать его (в этот момент подойдет любая легальная печать).
ВыполнениеДля красивой печати обычно требуется больше информации, чем собирает классический анализатор, что усугубляется тем фактом, что большинство генераторов синтаксического анализатора не поддерживают этот сбор дополнительной информации.Я называю парсеры, которые собирают достаточно информации, чтобы сделать это хорошо, «реинжиниринг парсеров».Более подробная информация приведена ниже.
Фундаментальный способ довольно красивой печати достигается путем обхода AST («шаблон посетителя», как вы его называете) и генерации текста на основе содержимого узла AST.Основная хитрость заключается в следующем: вызывать дочерние узлы слева направо (предполагая, что это порядок исходного текста), чтобы сгенерировать текст, который они представляют, добавляя дополнительный текст в соответствии с типом этого узла AST.Чтобы распечатать блок утверждений, у вас может быть следующий псевдокод:
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, представляющих литералы, необходимо восстановить значение литерала.Это сложнее, чем кажется, если вы хотите, чтобы ответ был точным.Печать чисел с плавающей запятой без потери точности на лот сложнее, чем кажется (ученые ненавидят это, когда вы повреждаете значение Pi).Для строковых литералов вы должны регенерировать кавычки и содержимое строкового литерала;Вы должны быть осторожны, чтобы восстановить escape-последовательности для символов, которые должны быть экранированы.Строковые литералы с двойными кавычками в PHP могут быть немного сложнее, поскольку в AST они не представлены одиночными токенами.(Наш PHP Front End (реинжиниринг парсера / prettyprinter представляет их по существу как выражение, объединяющее фрагменты строки, позволяя применять преобразования внутри строки "литерал").
Интервал: в некоторых языках требуются пробелы в критических местах. Маркеры ABC17 42 лучше не печатать как ABC1742, но все токены (ABC17) можно печатать как (ABC17). Один из способов решения этой проблемы -поставить пробел везде, где это разрешено, но людям не понравится результат: слишком много пробелов. Не проблема, если вы только компилируете результат.
Новые строки: языки, которые позволяютпроизвольный пробел может быть технически восстановлен в виде одной строки текста. Люди ненавидят это, даже если вы собираетесь скомпилировать результат, иногда вы имеете , чтобы посмотреть на сгенерированный код, и это делает это невозможным.нужен способ ввести новые строки для узлов AST, представляющих основные языковые элементы (операторы, блокs, методы, классы и т. д.).Это обычно не сложно;при посещении узла, представляющего такую конструкцию, распечатайте конструкцию и добавьте новую строку.
Вы обнаружите, что если вы хотите, чтобы пользователи приняли ваш результат, вам придется сохранить некоторые из них.свойства исходного текста, которые вы обычно не думаете хранить. Для литералов вам может потребоваться восстановить основание литерала;кодеры, введя число в виде шестнадцатеричного литерала, недовольны, когда вы воссоздаете десятичный эквивалент, даже если это означает то же самое.Точно так же строки должны иметь «оригинальные» кавычки;большинство языков допускают либо ", либо" как символы строковых кавычек, и люди хотят, чтобы они использовали изначально. Для 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's Oberon PrettyPrinter , показывающего, как объединяются правила грамматики и правила довольно печати.Интерфейс PHP выглядит следующим образом, но он намного больше, очевидно.
Более сложный способ сделать красивую печать - это создать синтаксически-ориентированный транслятор (значит, пройтись по дереву и построить текст или другие структуры данных вдревовидный порядок) для создания текстовых полей в специальном текстовом поле AST.Текстовое поле AST затем довольно печатается другим обходом дерева, но действия для него в основном тривиальны: печатать текстовые поля.См. Этот технический документ: Pretty-Printing для реинжиниринга программного обеспечения
Дополнительный момент: вы, конечно, можете сами собрать все это оборудование.Но та же причина, по которой вы решили использовать генератор синтаксического анализатора (для его создания требуется много работы, и эта работа не способствует интересной цели), - это та же причина, по которой вы хотите выбрать сторонний генератор.полка довольнопринтер генератор.Вокруг много генераторов парсеров.Не так много генераторов prettyprinter.[DMS является одним из немногих, кто встроил оба.]