Как я могу случайным образом генерировать строки с этим CFG?

Question

У меня есть этот код, описывающий контекстно-свободную грамматику, и я пытаюсь сгенерировать случайные строки, которые соответствуют ей; например, вот так:

"Джон думает, что Мэри ненавидит каждого зеленого кота"

Но мой текущий вывод:

[['_S', ['_NP _VP']], ['_NP', ['_Det _Adj _N', '_Det _N', '_Adj _PropN', '_PropN']], ['_VP', ['_Vi', '_Vt _NP', '_Vc _Comp _S']]]
[['_Det', ['the', 'a', 'some', 'any', 'every']], ['_Adj', ['green', 'young', 'tired', 'confused']], ['_N', ['dog', 'cat']], ['_PropN', ['John', 'Mary']], ['_Vi', ['sleeps', 'walks']], ['_Vt', ['loves', 'hates']], ['_Vc', ['says', 'thinks', 'believes']], ['_Comp', ['that']]]

, пожалуйста, помогите!

import random


psg_rules_str = "S → NP VP\n" \
                "NP → Det Adj N | Det N | Adj PropN | PropN\n" \
                "VP → Vi | Vt NP | Vc Comp S"

terminals_str = "Det → the | a | some | any | every\n" \
                "Adj → green | young | tired | confused\n" \
                "N → dog | cat\n" \
                "PropN → John | Mary\n" \
                "Vi → sleeps | walks\n" \
                "Vt → loves | hates\n" \
                "Vc → says | thinks | believes\n" \
                "Comp → that"

psg_rules_list = [a.split("→") for a in psg_rules_str.split("\n")]
for p in psg_rules_list:
    p[0] = "_" + p[0].strip()
    p[1] = p[1].split("|")
    p[1] = ["_" + a.strip().replace(" ", " _") for a in p[1]]
print(psg_rules_list)
# [['_S', ['_NP _VP']], ['_NP', ['_Det _Adj _N', '_Det _N', '_Adj _PropN', '_PropN']], ['_VP', ['_Vi', '_Vt _NP', '_Vc _Comp _S']]]

terminals_list = [a.split("→") for a in terminals_str.split("\n")]
for t in terminals_list:
    t[0] = "_" + t[0].strip()
    t[1] = t[1].split("|")
    t[1] = [a.strip() for a in t[1]]
print(terminals_list)
# [['_Det', ['the', 'a', 'some', 'any', 'every']], ['_Adj', ['green', 'young', 'tired', 'confused']], ['_N', ['dog', 'cat']], ['_PropN', ['John', 'Mary']], ['_Vi', ['sleeps', 'walks']], ['_Vt', ['loves', 'hates']], ['_Vc', ['says', 'thinks', 'believes']], ['_Comp', ['that']]]

def reachTerminals(from_nts, with_rules, with_ts):
    from_nts = str.upper("_" + from_nts.replace("_", "").strip().replace(" ", " _"))
    rule_tags = [a[0] for a in with_rules]
    ts_tags = [a[0] for a in with_ts]
    nts_todo = [a for a in rule_tags if a in from_nts]
    while nts_todo != list():
        tag = nts_todo[0]
        wr_index = rule_tags.index(tag)
        repl_choices = with_rules[wr_index][1]

        nts_todo = [a for a in rule_tags if a in from_nts]


sentence = reachTerminals(from_nts="s", with_rules=psg_rules_list, with_ts=terminals_list)

Answer 1

У вас почти работает программа. Вот способ выполнения функции reachTerminals:

import random

psg_rules_str = "S → NP VP\n" \
                "NP → Det Adj N | Det N | Adj PropN | PropN\n" \
                "VP → Vi | Vt NP | Vc Comp S"

terminals_str = "Det → the | a | some | any | every\n" \
                "Adj → green | young | tired | confused\n" \
                "N → dog | cat\n" \
                "PropN → John | Mary\n" \
                "Vi → sleeps | walks\n" \
                "Vt → loves | hates\n" \
                "Vc → says | thinks | believes\n" \
                "Comp → that"

psg_rules_list = [a.split("→") for a in psg_rules_str.split("\n")]
for p in psg_rules_list:
    p[0] = "_" + p[0].strip()
    p[1] = p[1].split("|")
    p[1] = ["_" + a.strip().replace(" ", " _") for a in p[1]]

terminals_list = [a.split("→") for a in terminals_str.split("\n")]
for t in terminals_list:
    t[0] = "_" + t[0].strip()
    t[1] = t[1].split("|")
    t[1] = [a.strip() for a in t[1]]

def reachTerminals(from_nts, with_rules, with_ts):
    from_nts = str.upper("_" + from_nts.replace("_", "").strip().replace(" ", " _"))
    rule_tags = [a[0] for a in with_rules]
    ts_tags = [a[0] for a in with_ts]
    nts_todo = [a for a in rule_tags if a in from_nts]
    while nts_todo:
        for tag in nts_todo:
            wr_index = rule_tags.index(tag)
            repl_choices = with_rules[wr_index][1]

            choice = random.choice(repl_choices)
            from_nts = from_nts.replace(tag, choice, 1)
        nts_todo = [a for a in rule_tags if a in from_nts]

    ts_todo = [a for a in ts_tags if a in from_nts]
    while ts_todo:
        for tag in ts_todo:
            wr_index = ts_tags.index(tag)
            repl_choices = with_ts[wr_index][1]

            choice = random.choice(repl_choices)
            from_nts = from_nts.replace(tag, choice, 1)
        ts_todo = [a for a in ts_tags if a in from_nts]

    return from_nts


print(reachTerminals(from_nts = "s", with_rules = psg_rules_list, with_ts = terminals_list))

Важными инструментами, которые вы можете использовать, являются функция random.choice и str.replace Третий параметр функции, который позволяет вам заменить только первое вхождение подстроки. Я не полностью протестировал код, но, похоже, он работает, как и ожидалось. Пример выходных данных:

green John loves some confused dog

Mary says that the tired dog says that some green cat hates some cat

every green dog loves young John

John loves the tired cat