Как перечислить строки контекстно-свободной грамматики?

Question

Какой алгоритм вы используете для перечисления строк, генерируемых без контекстной грамматики?

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

(я не ищу эзотерическое решение, как один на this page, я ищу алгоритм, который я мог бы привязать к стандартному императивному коду.)

Answer 1

Вот очевидный, но несколько неэффективного алгоритм :

Construct R, the Earley parser for the grammar. 

For each string S in A* (A is the alphabet for the grammar): 
    If R recognizes S: 
    Output S 

Здесь я пропущу подробности построения R - смотри, например, Earley's thesis или, более кратко, в статье Википедии о the Earley algorithm. Я также пропущу проблему перечисления всех строк в A *, которая является простой базой счетчика |A|.

Очевидно, что этот алгоритм можно сделать более эффективным, используя сам анализатор Эрли, чтобы избежать (некоторых) тупиков. Вместо перечисления всех строк в A* мы начинаем с очереди <string, state-set> кортежей, инициализированных кортежем, состоящим из пустой строки и пустого набора состояний. Затем (бесконечно) удаляем один кортеж из головы очереди и добавляем в конец очереди все возможные кортежи, которые могут быть построены путем подачи одного символа из A в анализатор Эрли (как правило, синтаксический анализатор не сможет обрабатывать каждый символ, на самом деле он не сможет справиться с каким-либо). Если синтаксический анализатор распознает строку в кортеже, мы выводим ее.

В обоих случаях, если мы знаем, что данная грамматика относится к некоторому легко анализируемому подмножеству CFG, мы могли бы заменить синтаксический анализатор Эрли для более эффективного анализатора для грамматики.

Оба эти алгоритма имеют преимущество генерации строк языка в простом предсказуемом порядке: сначала по длине и в пределах заданной длины, лексикографически, что гарантирует, что каждая строка будет генерироваться ровно один раз, даже если грамматика неоднозначна.

Другим решением является построение строк в порядке количества требуемых сокращений; по сути, это порождает все (крайние левые) сокращения. Здесь мы начинаем очередь с начального символа, а затем повторно:

Remove the first sentence in the queue. 
If it contains only terminals, output it. 
Otherwise, for each production for the first non-terminal in the sentence, 
    append to the queue the result of expanding that production. 

выше алгоритм будет работать нормально для однозначных грамматик, но, учитывая неоднозначную грамматику, она будет порождать предложения несколько раз (один раз в крайнем левом выводе). Чтобы исправить эту проблему, мы могли бы сначала преобразовать грамматику в Chomsky Normal Form (см. Ссылку на алгоритм). Затем мы создаем общий порядок для терминалов и нетерминалов, в которых не-терминалы все предшествуют терминалам, и соответствующий порядок предложений, в которых более короткое предложение предшествует более длинному предложению, а предложения с равной длиной упорядочены лексикографически. Затем мы используем вышеуказанный алгоритм, но используем очередь приоритетов вместо очереди FIFO и удаляем дубликаты записей перед их обработкой.

В CNF, с порядком длины-лексикографии, все производственные процессы растут, поскольку они либо заменяют не терминал терминалом, либо делают предложение одним символом дольше. (Остальное доказательство правильности есть индукция). Следовательно, полностью производные предложения будут перечислены в методе длины, а затем лексикографии, как и наивный алгоритм, который запустил этот ответ.