Построение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами

Рассматривается задача построения синтаксических анализаторов по синтаксическим диаграммам с многовходовыми компонентами (СД). Предлагается основанный на алгоритме GLL алгоритм построения синтаксического анализатора, результатом работы которого является компактное преставление леса разбора входной цепочки. Предложенный алгоритм позволяет строить синтаксические анализаторы по СД произвольной структуры и не требует предварительных преобразований СД. Построенные синтаксические анализаторы могут применяться для анализа любых контекстно-свободных языков, включая недетерминированные и неоднозначные. Вводятся понятия «дерево вывода» и «лес разбора» для СД, описываются структуры данных, используемые анализатором, такие, как стек с графовой структурой, дескриптор синтаксического анализатора, компактное представление леса разбора. Описывается алгоритм построения синтаксических анализаторов по СД и приводится пример построения такого анализатора.