Столяров В. Р., Ларин С. В., Привалов А. Н.

АНАЛИЗ TRIE-АЛГОРИТМА В ЗАДАЧАХ ЛЕКСИЧЕСКОГО АНАЛИЗА НА ПРИМЕРЕ ТОКЕНИЗАЦИИ ЯЗЫКА ПРОГРАММИРОВАНИЯ SOLIDITY

 Резюме: В работе проводится сравнительный анализ двух методов классификации токенов в лексическом анализаторе языка программирования Solidity: классического наивного подхода и оптимизированного алгоритма на основе префиксного дерева (Trie). Цель исследования — формализовать математические характеристики обоих алгоритмов, оценить их временную и пространственную сложность, а также проверить практическую эффективность на реальных примерах кода. Проведено теоретическое обоснование: наивный алгоритм обладает асимптотикой O(n·m·ℓ) при длине входа n, числе шаблонов m и средней длине шаблона ℓ, тогда как Trie-алгоритм достигает сложности O(n·α) при константном алфавите и глубине поиска α. Экспериментальная часть включает реализацию обоих методов на примерах контрактов Solidity разного размера, измерение времени разбора и потребления памяти. Результаты показывают, что наивный алгоритм предпочтителен для небольших входов и ограниченного числа токенов, тогда как Trie-алгоритм демонстрирует значительное преимущество по скорости при анализе крупных кодовых баз. В заключении обсуждаются практические рекомендации по выбору метода и направления дальнейшей оптимизации, такие как использование сжатых деревьев или автоматизированная генерация Trie из грамматики.

Ключевые слова: Trie, Solidity, сравнение алгоритмов.

 V.R. Stolyarov, A.N. Privalov, S.V. Larin

 TRIE ALGORITHM ANAL YSIS IN LEXICAL ANAL YSIS: TOKENIZING THESOLIDITY PROGRAMMING LANGUAGE

Summary: This work presents a comparative analysis of two token‑classification methods in the lexical analyzer for the Solidity programming language: the classic naive approach and an optimized prefix‑tree (Trie)–based algorithm. The study’s objective is to formalize the mathematical properties of both algorithms, evaluate their time and memory complexities, and assess their practical effectiveness on real code samples. A theoretical justification is provided: the naive algorithm has a worst‑case complexity of O(n·m·ℓ) n is the input length, m is the number of patterns, and ℓ is the average pattern length, whereas the Triealgorithm achieves O(n·α) under a constant alphabet size and search depth α. The experimental section includes implementations of both methods on Solidity contracts of varying sizes, with measurements of parsing time and memory usage. The results show that the naive algorithm is preferable for small inputs and a limited token set, while the Trie algorithm offers a significant speed advantage when analyzing large codebases. Finally, practical recommendations for method selection and directions for further optimization—such as using compressed trees or auto‑generating the Trie from the grammar—are discussed.

Keywords: Trie, Solidity, algorithm comparison.

DOI: 10.34219/2078-8320-2025-16-4-112-117