Разбор 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

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

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

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

Answer 2

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

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

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