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.