Разбор CFG с альтернативами

Question

У меня довольно простой язык, представленный в виде CFG.

S → A z
A → A y A
  | A x A
  | A w
  | v

Так как есть левая рекурсия, парсер рекурсивного спуска не собирается ее сокращать. Однако мне также нужно найти все возможные толкования: дано v x v y v zМне нужен мой парсер чтобы найти оба (v x (v y v)) z а также ((v x v) y v) z,

Какие варианты у меня есть? Сдвиг-уменьшение с добавленным обратным отслеживанием, чтобы найти все возможности, кажется хорошим, но я слышал, что добавление обратного отслеживания в синтаксический анализатор смещения-сдвига может привести к экспоненциальной временной сложности. Этот CFG достаточно мал, чтобы это не имело значения, но мне нужно увеличить его до значительно более крупных грамматик (с тысячами терминалов).

Answer 1

Алгоритм Эрли (и его варианты, такие как GLR) могут быть реализованы для создания парсера, который работает за кубическое время. Поскольку возможного количества возможных синтаксических разборов может быть экспоненциальное, эта сложность заключается только в создании "леса разбора", который представляет собой группу обеспечения доступности баз данных, содержащую все возможные разборы. На самом деле перечисление разборов займет время, пропорциональное количеству возможностей.

Обратите внимание, что когда мы говорим о сложности времени здесь, мы говорим о длине входной строки, а не о размере грамматики. Размер, если грамматика оказывает влияние, конечно, обычно линейный, но это зависит от того, как вы измеряете размер, но предполагается, что синтаксический анализатор был построен для определенной грамматики (что может потребовать предварительной обработки в зависимости от грамматики размер.)

Ссылка на статью в Википедии, приведенную выше, содержит список реализаций на разных языках, некоторые из которых предназначены для производства, а другие просто для демонстрации алгоритма. Обратите внимание, что синтаксический анализатор GLR, созданный bison, не является кубическим; в патологических случаях это может быть экспоненциальным. Кроме того, он не создает дерево разбора (или лес); это оставлено для пользователя, и наивные алгоритмы, которые не разделяют хранение, могли бы потребовать экспоненциального пространства и времени. (Тем не менее, он вполне пригоден для грамматики реального мира.)

Answer 2

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

Два таких алгоритма - это Эрли (как указал @rici) и CYK. Они предназначены для возврата всех возможных дериваций, как вам требуется, и могут использоваться для создания SPPF (Shared Packed Parse Forest), который является очень эффективной структурой для весьма неоднозначных грамматик (подойдет ли вам это описание или нет, я не могу сказать конечно).

Если вы хотите поэкспериментировать с этим, вы можете попробовать мою библиотеку синтаксического анализа для python Lark, которая реализует как Earley, так и CYK, и может предоставить вам список всех возможных дериваций для вашего ввода (однако поддержка SPPF все еще работает прогресс).