GLL Parser Combinator или Generator в / для C или переполнения стека
Есть ли существующая реализация GLL алгоритм, либо в виде парсера комбинаторов (предпочтительно) или в качестве генератора парсера для C или C ++?
Мои требования состоят в том, чтобы выходные данные представляли собой общий упакованный лес анализа (SPPF), который позже я могу устранить неоднозначность, используя семантические и / или контекстные правила. Существуют и другие алгоритмы синтаксического анализа, такие как GLR, которые способны справиться с общими контекстно-свободными грамматиками, однако все генераторы синтаксического анализатора GLR, которые я мог найти, либо возвращают первое успешное дерево синтаксического анализа, либо завершаются ошибкой, если в конце сохраняется неопределенность.
Решение
Что делать, если вы попробуете GLL Combinators? Хотя он использует Scala, вы можете написать для него «тонкие» обертки с помощью JNI.
GLL Combinators это структура, предназначенная для реализации Алгоритм разбора GLL
(Скотт и Джонстон, LDTA 2009) в функциональной манере. Более конкретно,
фреймворк использует атомарные синтаксические анализаторы для составления грамматик, которые
затем оценивается с использованием алгоритма GLL. Структура предоставляет синтаксис для этого
задача, которая почти идентична задаче встроенного каркаса синтаксического анализатора
в Скала. Например, мы можем визуализировать классическую «грамматику скобок», используя
GLL комбинаторы:lazy val expr: Parser [Any] = ( "(" ~ expr ~ ")" | "")Как следует из аннотации типа,
exprбудет ссылаться на экземпляр типа
Parser[Any], То есть атомарный парсер, который потребляет некоторый ввод и возвращает
значение типаAny, Мы можем вызвать этот парсер противStringвход
следующим образом:выражение ( "((()))")Это вернет значение типа
Stream[Result[Any]],Result[A]ADT является
определяется как одно из следующего (для некоторого типаA):
Success[A]— Представляет успешный анализ и содержит результирующее значение.Failure— Представляет неудачный анализ и содержит соответствующее сообщение об ошибке.
а также остаток потока разбора (символы, которые не были
потребляются).Если какой-либо результат успешен (то есть экземпляр
Success[A]), то без сбоев
будет возвращен. Таким образомStreamвозвращение будет полностью однородным,
содержащий илиSuccessили жеFailure, но не оба.Streamявляется
возвращено, а не одно значение, чтобы допустить неоднозначность в грамматике (см.
ниже).Стоит отметить, что GLL является формой рекурсивно-спусковой разбор. Она имеет
все преимущества обычного рекурсивного спуска, в том числе интуитивный
поток управления, произвольное позиционирование семантических действий и превосходная ошибка
Сообщения. Фактически, тот факт, что GLL является рекурсивным спуском, позволяет
быть реализованным с использованием атомных комбинаторов. Другие алгоритмы, которые разделяют
те же возможности, что и GLL (например, GLR, анализ Earley и т. д.),
несовместимы с моделью комбинатора из-за их крайне неинтуитивного управления
течь. В разборе GLL поток управления следует за грамматикой, так как
в традиционных парсерных комбинаторах или любой другой форме рекурсивного спуска.
Другие решения
Других решений пока нет …