GLL Parser Combinator или генератор в / для C или C++

Question

Существует ли какая-либо существующая реализация алгоритма GLL, либо в форме комбинаторов синтаксического анализа (предпочтительно), либо в качестве генератора синтаксического анализатора для C или C++?

Мои требования состоят в том, чтобы выходные данные представляли собой общий упакованный лес анализа (SPPF), который позже я могу устранить неоднозначность, используя семантические и / или контекстные правила. Существуют и другие алгоритмы синтаксического анализа, такие как GLR, которые могут справиться с общими контекстно-свободными грамматиками, однако все генераторы синтаксического анализатора GLR, которые я смог найти, либо возвращают первое успешное дерево синтаксического анализа, либо завершаются неудачей, если в конце сохраняется неопределенность.

Answer 1

Что если вы попробуете GLL Combinators? Хотя он использует Scala, вы можете написать для него "тонкие" оболочки с помощью JNI.

GLL Combinators - это структура, разработанная для функциональной реализации алгоритма синтаксического анализа GLL (Скотт и Джонстон, LDTA 2009). Более конкретно, в фреймворке используются атомарные синтаксические анализаторы для составления грамматик, которые затем оцениваются с использованием алгоритма GLL. Платформа обеспечивает синтаксис для этой задачи, который почти идентичен синтаксису структуры комбинатора синтаксического анализатора, встроенной в Scala. Например, мы можем отобразить классическую "грамматику скобок" с помощью комбинаторов 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 поток управления следует за грамматикой, как это происходит в традиционных комбинаторах синтаксического анализа или любой другой форме рекурсивного спуска.