Ответ Леонардо технически верен;не существует завершающего алгоритма, который будет возвращать набор слов для общего CFG, потому что часто этот набор бесконечен.
Но есть алгоритмы, которые генерируют последовательность слов для CFG, где каждое слово, соответствующее грамматике, появляется "в конце концов".Одного из них должно быть достаточно для ваших целей.Довольно просто написать один из них на языке yield, таком как Python.
Набросок такого алгоритма (боюсь, в довольно безнадежном псевдокоде):
generate(g):
if g is empty:
yield ""
otherwise if g is a terminal a:
yield "a"
otherwise if g is a single nonterminal:
for c in every construction of g:
start a generator for generate(c)
until all generators are exhausted:
looping over each nonexhausted generator gen:
yield "a" where a = next(gen)
otherwise if g is a pair of symbols m and n:
for c in every construction of m:
start a generator in set 1 for generate(c)
for d in every construction of m:
start a generator in set 2 for generate(d)
until all in set 1 or all in set 2 are exhausted:
loop over all pairs gen1,gen2 of nonexhausted in set 1 and set 2:
yield "a b" where a = next(gen1) and b = next(gen2)
Предполагая, что грамматика была преобразована так, что каждая конструкция от нуля до двух терминалов, будет выполняться поиск в ширину по дереву всех деревьев разбора грамматики.BFS необходима, потому что размер любого данного поддерева может быть бесконечным - DFS может застрять, глядя на одного из них навсегда.
Время и память, ожидающие получения данного дерева синтаксического анализа, могут бытьпроизвольно, но конечно для этого дерева разбора.