BSU bulletin. Mathematics, Informatics
IMPLEMENTATION OF THE ALGORITHM FOR CF GRAMMAR TESTING FOR CLASS LL(K) // BSU bulletin. Mathematics, Informatics. - 2021. №2. . - С. 17-27.
IMPLEMENTATION OF THE ALGORITHM FOR CF GRAMMAR TESTING FOR CLASS LL(K)
The article discusses an algorithm for testing a KS grammar in the Backus-Naur form for belonging to the LL(k) subclass of grammars. This is the most "natural" class of left-sided grammars in which left-sided analysis can be implemented in a deterministic manner. They allow the construction of left-hand input-output language strings using only the knowledge of k symbols ahead of going.
The implementation of the basic properties of such grammars as FIRST-FOLLOW- Sigma and the testing algorithm is considered. C # was chosen as the development language. The application is implemented on the .NET Core 3.1 platform, which allows you to create programs for various operating systems. Testing is carried out using the code XUnit library, which is one of the most popular solutions for testing on the .NET platform.
context-free grammars; Backus-Naur form; testing algorithm; LL(k) grammars; FIRST, FOLLOW, Sigma functions.
List of references:
Aho Alfred V., Ullman Jeffrey D. The Theory of Parsing, Translation, and Compil- ing. USA, New Jersey, 1972. 562 p.
Martynenko B. K. Languages and Broadcasts. St. Petersburg State University Pub- lishing House, St. Petersburg, 2013. 305 p.