РЕАЛИЗАЦИЯ АЛГОРИТМА ТЕСТИРОВАНИЯ КОНТЕКСТНО-СВОБОДНОЙ ГРАММАТИКИ НА ПРИНАДЛЕЖНОСТЬ К КЛАССУ LL(K) // Вестник БГУ. Математика, информатика. - 2021. №2. . - С. 17-27.

РЕАЛИЗАЦИЯ АЛГОРИТМА ТЕСТИРОВАНИЯ КОНТЕКСТНО-СВОБОДНОЙ ГРАММАТИКИ НА ПРИНАДЛЕЖНОСТЬ К КЛАССУ LL(K)

DOI: 10.18101/2304-5728-2021-2-17-27 УДК: 004.4

В статье рассматривается алгоритм тестирования КС-грамматики в форме Бэкуса — Наура на принадлежность ее к подклассу LL(k) грамматик. Это наибольший «естественный» класс левоанализируемых грамматик, в которых левосторонний анализ может быть реализован детерминированным образом. Они допускают построение левостороннего вывода входной цепочки языка с использованием знания лишь о k впереди идущих символах. Такой анализ, в свою очередь, дает детерминированный метод определения выхода правильной трансляции. Рассматривается реализация основных свойств таких грамматик, как FIRST-FOLLOW-Sigma и алгоритм тестирования. В качестве языка разработки был выбран язык C#. Приложение реализовано на платформе .NET Core 3.1, позволяющей создавать программы для различных операционных систем.
Тестирование кода осуществляется при помощи библиотеки XUnit, которая является одним из наиболее популярных решений для тестирования на платформе .NET.
Благодарности. Работа выполнена при участии студента математико- механического факультета СПбГУ Паршина Максима Алексеевича.

контекстно-свободные грамматики; форма Бэкуса — Наура; алгоритм тестирования; LL(k) грамматики; функции FIRST, FOLLOW, Sigma.

Aho Alfred V., Ullman Jeffrey D. The Theory of Parsing, Translation, and Compil- ing. USA, New Jersey, 1972. 562 р.

Мартыненко Б. К. Языки и трансляции. Санкт-Петербург: Изд-во СПбГУ, 2013. 305 с. Текст: непосредственный.