Составление АСТ обратно в исходный код

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

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

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

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

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

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

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

Ответы

Ответ 1

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

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

Основополагающим способом довольно печатания является прохождение AST ( "Шаблон посетителя", как вы выразились) и генерирование текста на основе контента AST node. Основной трюк: вызвать дочерние узлы слева направо (при условии, что порядок исходного текста) сгенерировать текст, который они представляют, вкратце ввести дополнительный текст, подходящий для этого типа AST node. Чтобы отпечатать блок утверждений, у вас может быть следующий 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, представляющих литералы, вам необходимо восстановить литерал. Это сложнее, чем кажется, если вы хотите, чтобы ответ был точным. Печать чисел с плавающей точкой без потери точности намного сложнее, чем кажется (ученые ненавидят ее, когда вы повредите значение Pi). Для строковых литералов вам необходимо восстановить кавычки и содержимое литерала строки; вы должны быть осторожны, чтобы регенерировать escape-последовательности для символов, которые должны быть экранированы. Строковые литералы с двумя строками PHP могут быть немного сложнее, поскольку они не представлены одиночными токенами в AST. (Наш PHP Front End (реинжиниринговый парсер /prettyprinter представляет их по существу как выражение, которое объединяет фрагменты строки, позволяя применять преобразования внутри строки "буквальный" ).

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

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

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

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

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

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

Хорошо организованный подход к красивой печати заключается в том, чтобы понять, что практически весь текстовый язык программирования отлично отрисовывается в виде прямоугольных блоков текста. (У генератора документов Knuth 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;

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

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

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

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

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

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

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

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