Вы можете сделать это, написав процедурный код, или вы можете использовать систему преобразования программ (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 не очень эффективна, если они представляют языковые языки программирования, потому что вы не можете игнорировать значение и область действия идентификаторов. См. Жизнь после разбора " для глубокого обсуждения.
Но суть в том, что ваши правила перезаписи часто должны зависеть от семантических свойств языка программирования, которым вы собираетесь манипулировать. Правила DMS обрабатывают это, допуская дополнительное условие if условие , которое может вызывать семантические предикаты, определенные для этого языка, в DMS. Вы можете увидеть несколько простых примеров этого в примере алгебры.