Modeling and implementation of context free grammar combinatorial parser

The purpose of the research is to model and implement a system of functions and combinators for parsing languages that can be defined using context-free grammars, as well as to reduce the source code of the parsing program.  
Methods. Using denotational semantics, a formal model of a system of functions and combinators for parsing was constructed, the type of parsing function was determined, and basic parsing functions were defined: successful parsing, unsuccessful parsing, and predicate parsing. Based on the basic functions, a function for parsing a given character is defined. A  formal model of a combinator of a  sequence of parsing  functions, a combinator of parallel  (alternative) parsing, and a combinator of applying a function to the results of parsing is given. Denotational semantics is also used to define combinators for repeating the parsing function.
Results. Based on  the obtained combinators and parsing  functions,  the implementation of Common Lisp parsing  is demonstrated. First, the grammar of the language in the extended Backus-Naur form is given. Then the parsing func- tions for lexical analysis are given: functions of voids, decimal numbers, hexadecimal numbers, identifiers, and single characters. Then, based on the previous functions, functions for parsing numbers, strings, atoms, lists, arrays, func- tional closures, and the s-expressions themselves are set. The resulting function combining the previous functions is also provided. The resulting program is compared by the LOC metric (number of lines of code) with a reference imple- mentation of a lexical and syntactic analyzer written in C.
Conclusion. As a result of the work, a model of a system of functions and combinators for parsing languages that can be specified by context-free grammars was built and  implemented. The parsing program using  this system  is quite compact due to the fact that grammars and semantic rules are written declaratively in almost their denotational form. This allows you to reduce the number of lines of code several times compared to the top-down recursive implementation of parsing.

1. Alfred V. Aho, Monica S. Lam, Ravi Sethi Jeffrey. Compilers: principles, technologies and tools. 2nd ed. Moscow: Williams; 2020. 1184 p. (In Russ.)

2. Evans E. Domain-oriented design (DDD): structuring complex software systems. Moscow: Williams; 2020. 448 p. (In Russ.)

3. Dushkin R. V. Functional programming in the Haskell language. Moscow: DMK Press; 2016. 608 p. (In Russ.)

4. Abelson H., Sussman D. Structure and interpretation of computer programs. Moscow: KDU; 2022. 608 p. (In Russ.)

5. Chaplygin A.A. The use of metaprogramming tools of the Common Lisp language for the development of emulator systems. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie = Proceedings of the Southwest State University. Series: Control, Computer Engineering, Information Science. Medical Instruments Engineering. 2023;(3):135–145. (In Russ.)

6. Khalilov E.R. Development of an interpreter for the video game programming language. Informatsionno-komp'yuternye tekhnologii v ekonomike, obrazovanii i sotsial'noi sfere = Information and computer technologies in economics, education and the social sphere. 2020;(1):79–89. (In Russ.) EDN KNIRUT

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

8. Solomatin D.I. Experimental investigation and optimization of the algorithm of descending parsing with limited returns for PEG grammars. Vestnik Voronezhskogo gosudarstvennogo universiteta. Seriya: Sistemnyi analiz i informatsionnye tekhnologii = Bulletin of Voronezh State University. Series: System Analysis and Information Technologies. 2013;(2):144–152. (In Russ.) EDN RLTABV

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

10. Hutton G., Meijer E. Monadic Parser Combinators. Available at: https://people.cs.nott.ac.uk /pszgmh/monparsing.pdf (accessed 22.03.2025).

11. Eginov D.I., Lebedev A.A., Dorofeeva O.S. Methods of syntactic analysis of contextfree grammars. In: Fionovoi L.R. (ed.) Informatsionnye tekhnologii v nauke i obrazovanii. Problemy i perspektivy: sbornik nauchnykh statei VI Vserossiiskoi mezhvuzovskoi nauchnoprakticheskoi konferentsii, g. Penza, 13 marta 2019 goda = Information technologies in science and education. Problems and prospects: Collection of scientific articles of the VI All-Russian Interuniversity Scientific and Practical Conference, 13 March 2019, Penza. Penza: Penza State University; 2019. P. 15–17. (In Russ.) EDN EJCXLL

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

13. Frost R.A. Monadic Memoization towards Correctness-Preserving Reduction of Search. In: 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 Am-biguity and Left Recursion in Polynomial Time. ACM SIGPLAN Notices. 2006;(41):46–54. https://doi.org/10.1145/1149982.1149988.S2CID8006549

15. Saibel P. Practical use of Common Lisp. Moscow: DMK Press; 2017. 488 p. (In Russ.)

16. Graham Paul. ANSI Common LISP. Saint Petersburg: Symbol-Plus; 2020. 448 p. (In Russ.)

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

18. Chaplygin A.A. Modeling of a functional programming language interpreter with metaprogramming capabilities. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie = Proceedings of the Southwest State University. Series: Control, Computer Engineering, Information Science. Medical Instruments Engineering. 2024;(14):181–193. (In Russ.) https://doi.org/10.21869/2223-1536-2024-14-2-181-193