Модель и реализация комбинаторного разбора языков, заданных контекстно-свободными грамматиками

Цель исследования  заключается в моделировании и реализации системы функций и комбинаторов для разбора языков, которые могут быть заданы с помощью контекстно-свободных грамматик, а также уменьшении исходного кода программы разбора.  
Методы. С помощью денотационной семантики была построена формальная модель системы функций и комбинаторов для разбора, определен тип функции разбора, заданы базовые функции разбора: успешный разбор, неудачный разбор, разбор по предикату. На основе базовых функций задана функция разбора заданного символа. Приведена формальная модель комбинатора последовательности функций разбора, комбинатора параллельного (альтернативного) разбора, комбинатора применения функции к результатам разбора. Также с помощью денотационной семантики заданы комбинаторы повторения функции разбора.  
Результаты. На основе полученных комбинаторов и функций разбора продемонстрирована реализация разбора языка Common Lisp. Сначала приводится грамматика языка в расширенной форме Бэкуса-Наура. Затем приводятся функции разбора при лексическом анализе: функции пустот, десятичных чисел, шестнадцатеричных чисел, идентификаторов, одиночных символов. Затем на основе предыдущих функций задаются функции разбора чисел, строк, атомов, списков, массивов, функциональных замыканий и самих s-выражений. Также приводится результирующая функция, объединяющая предыдущие функции. Полученная программа сравнивается по метрике LOC (число строк кода) с эталонной реализацией лексического и синтаксического анализатора, написанных на языке C.  
Заключение. В результате работы была построена и реализована модель системы функций и комбинаторов для разбора языков, которые могут быть заданы контекстно-свободными грамматиками. Программа разбора, использующая данную систему, получается довольно компактной за счет того, что грамматики и семантические правила записываются декларативно практически в своем денотационном виде. Это позволяет в несколько раз сократить число строк кода по сравнению с нисходящей рекурсивной реализацией разбора.

1. Компиляторы: принципы, технологии и инструментарий / Альфред В. Ахо, Моника С. Лам, Рави Сети Джеффри. 2-е изд. М.: Вильямс, 2020. 1184 c.

2. Эванс Э. Предметно-ориентированное проектирование (DDD): структуризация сложных программных систем. М.: Вильямс, 2020. 448 с.

3. Душкин Р. В. Функциональное программирование на языке Haskell. М.: ДМК Пресс, 2016. 608 с.

4. Абельсон Х., Сассман Д. Структура и интерпретация компьютерных программ. М.: КДУ, 2022. 608 с.

5. Чаплыгин А. А. Использование метапрограммных средств языка Common Lisp для разработки систем эмуляторов // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2023. № 3. С. 135–145.

6. Халилов Э. Р. разработка интерпретатора для языка программирования видеоигр // Информационно-компьютерные технологии в экономике, образовании и социальной сфере. 2020. № 1(27). С. 79–89. EDN KNIRUT

7. Frost R., Launchbury J. Constructing natural language interpreters in a lazy functional language // The Computer Journal. 1989. N 32(2). P. 108–121. https://doi.org/10.1093/comjnl/32.2.108

8. Соломатин Д. И. Экспериментальное исследование и оптимизация алгоритма нисходящего разбора с ограниченными возвратами для PEG-грамматик // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2013. № 2. С. 144–152. EDN RLTABV

9. Hutton G. Higher-order functions for parsing // Journal of Functional Programming. 1992. N 2(3). P. 323–343. https://doi.org/10.1017/s0956796800000411

10. Hutton G., Meijer E. Monadic Parser Combinators. URL: https://people.cs.nott.ac.uk/pszgmh/monparsing.pdf (дата обращения: 22.03.2025).

11. Егинов Д. И., Лебедев А. А., Дорофеева О. С. Методы синтаксического разбора контекстно-свободных грамматик // Информационные технологии в науке и образовании. Проблемы и перспективы: сборник научных статей VI Всероссийской межвузовской научно-практической конференции, г. Пенза, 13 марта 2019 года / под ред. Л. Р. Фионовой. Пенза: Пензенский государственный университет, 2019. С. 15–17. EDN EJCXLL

12. Frost R. A., Szydlowski B. Memoizing Purely Functional Top-Down Backtracking Language Processors // Science. Computer. Programming. 1996. N 27(3). P. 263–288. https://doi.org/ 10.1016/0167-6423(96)00014-7

13. Frost R. A. Monadic Memoization towards Correctness-Preserving Reduction of Search // Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence (AI’03). Berlin: Springer, 2003. P. 66–80.

14. Frost R. A., Hafiz R. A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time // ACM SIGPLAN Notices. 2006. N 41(5). P. 46–54. https://doi.org/10.1145/1149982.1149988.S2CID 8006549

15. Сайбель П. Практическое использование Common Lisp. М.: ДМК Пресс, 2017. 488 с.

16. Грэм Пол. ANSI Common LISP. СПб.: Символ-Плюс, 2020. 448 с.

17. Krishnamurthi S. Programming Languages: Application and Interpretation. Providence: Brown University, 2003. 376 p.

18. Чаплыгин А. А. Моделирование интерпретатора функционального языка программирования с возможностями метапрограммирования // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2024. № 14(2). Р. 181–193. https://doi.org/10.21869/2223-1536-2024-14-2-181-193