Вы можете сделать это, написав процедурный код, или вы можете использовать систему преобразования программ преобразования исходных текстов (PTS).

Написание процедурного кода состоит только из вызова вспомогательных функций для перемещения вверх и вниз по дереву, удаления ссылок между узлами, удаления узлов, создания узлов и узлов ссылок. Любая библиотека AST имеет (должна иметь!) Такие функции.

Таким образом, процедурное решение для «a * (b + c)» переписывается в «a b + a c» так:

 Find tree root of "a*(b+c)".  That's the "*" node.
 Unlink the "a" child and the "b+c" child.
 Unlink the "b" and "c" children from the "+" node.
 Create a second "*" node.
 Link "a" and "b" nodes under the original "*" node, producing subtree "a*b*
 Copy the "a" node.
 Link the copyied-"a" and "c" under the second "*" node, producing subtree "a*c"
 Link the subtrees under the "+" node.
 Return "+" as the root of the tree.

В этом нет ничего сложного, это просто перетасовка ссылок.

Но писать раздражает, не помогает разобрать выражение из языка, которым вы, вероятно, хотите манипулировать («C #»?), Не выполняет сложные преобразования легко и не помогает вам найти этот вид поддерево гораздо большего AST, которое вы, вероятно, пытаетесь изменить.

Вот почему вы хотите PTS. Хороший PTS предоставляет механизм синтаксического анализа, позволяющий создавать синтаксические анализаторы для сложных языков, таких как Java, COBOL, C ++ или C #. Он также предоставляет способ написания шаблонно-ориентированных переписок . Он получает очки брауни, если случается, что он серьезно проверил парсеры для языков, которыми вы хотите манипулировать (потому что в противном случае вы получите запись парсера тоже поверх вашей проблемы манипулирования деревом).

Например, с помощью нашего набора инструментов для реинжиниринга программного обеспечения DMS вы можете воспользоваться полностью проверенными синтаксическими анализаторами для перечисленных выше языков. Предполагая, что вы хотите манипулировать C #, вы можете написать этот сценарий DMS для выполнения вашего примера на произвольно больших CST AST:

domain CSharp~CSharp7_5; -- establishes which parser to use to read source code

rule distribute_times_over_plus(a:multiplicative_expression,
                                b:additive_expression,
                                c:multiplicative_expression)
   :multiplicative_expression->multiplicative_expression
   = "\a*(\b+\c)"  -> "(\a*\b+\a*\c)";

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

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

Подробнее о том, что вы можете написать в правилах, можно найти в Правила перезаписи DMS .

Если вы хотите увидеть этот пример во всех подробностях, начиная с определения языка («исчисление колледжа») и применения правил к этому языку («как дифференцировать формулы»), вы можете увидеть его по адресу: Алгебра как DMS Домен

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

Но суть в том, что ваши правила перезаписи часто должны зависеть от семантических свойств языка программирования, которым вы собираетесь манипулировать. DMS правила решают эту проблему, допуская дополнительное условие if condition , которое может вызывать семантические предикаты, определенные для этого языка в DMS. Вы можете увидеть несколько простых примеров этого в примере алгебры.