ВІДОКРЕМЛЕННЯ СТРУКТУРИ ВІД ДАНИХ В АБСТРАКТНИХ СИНТАКСИЧНИХ ДЕРЕВАХ ДЛЯ ЕФЕКТИВНИХ ПЕРЕТВОРЕНЬ НЕЗМІННИХ ОБ’ЄКТІВ
DOI:
https://doi.org/10.36994/2788-5518-2025-01-09-08Ключові слова:
компілятори, абстрактне синтаксичне дерево, трансформація, незмінні об’єкти, JavaАнотація
У дизайні компіляторів абстрактне синтаксичне дерево (АСД) є основною структурою даних, яка використовується для представлення синтаксичної структури програми під час трансляції й аналізу. Традиційні представлення АСД моделюють структуру й дані як єдине ціле, де структурні зв’язки неявно кодуються через посилання на об’єкти, а дані є частиною самих об’єктів. Хоча цей підхід є інтуїтивним, він ускладнює моделювання та реалізацію перетворень АСД, особливо для незмінних об’єктів. Навіть прості модифікації часто потребують явного обходу АСД та значного копіювання, що додає другорядну складність до перетворень і знижує швидкодію.У роботі досліджується альтернативний підхід, який явно відокремлює структуру від даних у представленні АСД. Внутрішня форма АСД моделюється як пара масиву вершин, що містять лише дані, і матриці суміжності, яка явно кодує структуру АСД. Така модель уможливлює ефективні перетворення завдяки незалежним оновленням даних без зміни структури. Структурні зміни також є можливими, виконуються незалежно, змінюючи матрицю суміжності й масив вершин.Таке відокремлення спрощує розуміння перетворень та уможливлює лаконічне вираження без другорядної складності, що стосується обходу АСД.Аби продемонструвати застосовність наведеного підходу, представлено компілятор для мінімальної мови запитів до даних. Дослідили три типові операції над АСД: верифікацію, оновлення лише даних, структурну модифікацію, ілюструючи, як така модель сприяє різним видам перетворень. Запропонований підхід порівнюється з традиційними об’єктно-орієнтованими представленнями й наявними системами рерайтингу. Розширюваність і першокласна природа запропонованої моделі роблять її застосовною до низки компіляційних процесів, що виходять за рамки представленого прикладу. Ця модель слугує основою для створення надійних, практичних компіляторів і засобів перетворення. Серед майбутніх напрямів дослідження – оптимізація внутрішнього представлення АСД та підтримка альтернативних стратегій обходу.
Посилання
Ghosh, D. (2010). DSLs in action. Manning.
Bravenboer, M., Kalleberg, K. T., Vermaas, R., & Visser, E. (2006). Stratego/XT 0.16. In PEPM ’06: Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, 95–99. https://doi. org/10.1145/1111542.1111558.
Cordy, J. R., Dean, T. R., Malton, A. J., & Schneider, K. A. (2002). Source transformation in software engineering using the TXL transformation system. Information and Software Technology, 44(13), 827–837. https://doi.org/10.1016/s0950-5849(02)00104-0.
Brooks, F. (1987). No Silver Bullet Essence and Accidents of Software Engineering. Computer, 20(4), 10–19. https://doi.org/10.1109/mc.1987.1663532.
Helland, P. (2015). Immutability changes everything. Communications of the ACM, 59(1), 64–70. https://doi.org/10.1145/2844112.
Okasaki, C. (1998). Purely functional data structures. Cambridge University Press. https://doi.org/10.1017/cbo9780511530104.
Huet, G. (1997). The Zipper. Journal of Functional Programming, 7(5), 549–554. https://doi.org/10.1017/s0956796897002864.
Sampson, A. (2023, May 1). Flattening ASTs (and Other Compiler Data Structures). https://www.cs.cornell.edu/~asampson/blog/flattening.html.
Balland, E., Moreau, P., Reilles, A. (2008). Rewriting strategies in Java. Electronic Notes in Theoretical Computer Science, 219, 97–111. https://doi.org/10.1016/j.entcs.2008.10.037.
Hemel, Z., Kats, L. C. L., Groenewegen, D. M., & Visser, E. (2009). Code generation by model transformation: a case study in transformation modularity. Software & Systems Modeling, 9(3), 375–402. https://doi.org/10.1007/s10270-009-0136-1.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
