Генерация всех терминальных строк в Python с грамматикой / правилами? - PullRequest
Новая
       37

Генерация всех терминальных строк в Python с грамматикой / правилами?

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

Я пытаюсь сгенерировать все строки терминала из заданного файла до определенной длины. Так, например, если у вас есть что-то вроде 

A = A B
A = B
B = 0
B = 1

Тогда вы получите что-то вроде 

0
1
0 0
0 1
1 0
1 1

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

{'B': [['0'], ['1']], 'A': [['A', 'B'], ['B']]}

Казалось бы, вам нужно начать с одного из нетерминальных символов (например, A или B), а затем выполнить итерации по каждому правилу. Если символ в правиле не является нетерминальным символом, вы распечатали бы его или сохранили его, а если это нетерминальный символ, то заменили бы его правилом и затем проверили его снова. Я нахожусь в тупике о том, как сделать это в Python - я не так много сделал в этом. Любая помощь будет высоко ценится!

1 Ответ

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

псевдокод: 

for each symbol:
    push that symbol onto the stack

while an item X can be popped off the stack:
    if X contains a non-terminal
        calculate each possible result with variation of the leftmost nonterminal
        if that variation is lower than the max length
             push it to the stack
    else
        add the popped X to a set Q of results (for de-duping)

print out the contents of Q (sorted, if so desired)

(Примечание: «нетерминальный вариант с одинарной оценкой» означает, что если бы строка была «AAB», вы оценили бы 1 из A, но не другие (и не B, поскольку у него нет нетерминальных опций.) Затем вы оценили бы другой A в отдельном пути - вы бы в итоге положили две вещи в стек.)

Обратите внимание, что в Python вы можете просто использовать добавление / удаление из конца списка для стека и set() для набора.

...