как кодировать эту рекурсивную грамматику? - PullRequest
Новая
       4

как кодировать эту рекурсивную грамматику?

0 голосов
/ 16 сентября 2011

У меня есть следующая грамматика:

S -> S {S} S | null

Здесь ноль означает, что ничто не должно быть там вместо S. Мне нужно сгенерировать все возможные строки из 2n скобок, сгенерированных этой грамматикой. Я пытался закодировать его, но программе не хватает памяти. Может ли кто-нибудь помочь мне написать эту грамматику для двух скобок?

Заранее большое спасибо

Ответы [ 2 ]

1 голос
/ 25 сентября 2011

Сначала докажите, что эта грамматика генерирует все строки из сбалансированных фигурных скобок.

(Подсказка: начните с доказательства, что S -> S{S} | null генерирует все такие строки.)

Затем просто напишите функцию для генерации всех этих: 

function generate(num_opens, num_closes, string_so_far, N)
    if (num_opens + num_closes == N)
        print string_so_far;
        return;
    if (num_opens > num_closes)
        generate(num_opens, num_closes+1, string_so_far . '}', N)
    generate(num_opens+1, num_closes, string_so_far . '{', N)

generate(0, 0, N)

Это может или не может быть в "духе" вопроса.

0 голосов
/ 25 сентября 2011

Псевдокод для вас: 

function grammar: S(string), n(int), generatedStrings(collection)
    if (|S| == 2*n)
        // Store in generatedStrings
        return
    else if (|S| > 2*n)
        return

    grammar(S + '{}', n, generatedStrings)
    grammar(S +'{'+ S +'}', n, generatedStrings)
    grammar(S +'{'+ S +'}'+ S, n, generatedStrings)
    grammar('{'+ S +'}'+ S, n, generatedStrings)
    grammar('{'+ S +'}', n, generatedStrings)
    grammar('{}'+ S, n, generatedStrings)

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

...