未能从给定的python代码生成S=>Ba

Question

给定S=>BaB、B=>b和null(B)，代码应该生成S=>BaB|aB|Ba|a和B=>b，但它没有生成Ba，即输出是S=>BaB|aB|a和B=>b，这是不正确的。你知道吗

如果终端不在中间，代码可以正确地生成值，例如S=>BBa，B=>b给出S=>BBa|Ba|a和B=>b 唯一不起作用的情况是终端处于重复空生产的中间

其他例子null(B)

1. S=>aBa，B=>b发出S=>aBa|aa和B=>b

2. S=>aaB，B=>b发出S=>aaB|aa and B=>b

grammar = ["S = B a B", "B = b"]
def remove_null_productions(grammar):
    null_productions = ["B"]
    print("Null productions: {0}".format(null_productions))
    new_productions = []

    for rule in grammar:
        if('$' in rule):
            continue
        else:
            new_productions.append(rule.split(" "))

    print("\nProductions:{0}".format(new_productions))
    for null in null_productions:

        for param in new_productions:

            if(null in param[2:]):
                temp = param[2:]
                temp.remove(null)

                if(len(temp)==0):
                    pass
                else:
                    clever_array = param[0:2]
                    for val in temp:
                        clever_array.append(val)

                    new_productions.append(clever_array)
            else:
                pass

    print("\nResultant Productions")
    for rule in new_productions:
        print(rule)
    return new_productions
remove_null_productions(grammar)

我希望语法S=>BaB和B=>b的输出是

Null productions: ['B']

Productions:[['S', '=', 'B', 'a', 'B'], ['B', '=', 'b']]

Resultant Productions
['S', '=', 'B', 'a', 'B']
['B', '=', 'b']
['S', '=', 'a', 'B']
['S', '=', 'B', 'a']
['S', '=', 'a']

但是输出是

Null productions: ['B']

Productions:[['S', '=', 'B', 'a', 'B'], ['B', '=', 'b']]

Resultant Productions
['S', '=', 'B', 'a', 'B']
['B', '=', 'b']
['S', '=', 'a', 'B']
['S', '=', 'a']

Answer 1

这里的问题是temp.remove(null)只会删除temp中null的第一个实例。因此，最后添加的是'S=>；aB'，而不是'S=>；Ba'。您需要遍历右侧的所有符号并替换空值的每个实例。你知道吗

但是，天真地这样做会导致重复的结果（例如，“S=>；aB”和“S=>；Ba”都会给出“S=>；a”）。您可以通过使用集合来跟踪已经生成的产品的元组来避免此问题（必须使用元组而不是列表，因为集合中的项必须是不可变的）。然后可以检查此集合，以确保没有附加已添加的产品。你知道吗

下面是一些工作代码，它为“s=>；BaB”和“s=>；BBa”生成预期的输出。除了修改逻辑以添加新的产品外，我基本上保持了代码不变。我还将null_productions更改为函数的参数，以便更容易更改其值。你知道吗

grammar = ["S = B a B", "B = b"]
def remove_null_productions(grammar, null_productions=None):
    if null_productions is None:
        null_productions = ["B"]
    print("Null productions: {0}".format(null_productions))
    new_productions = []

    seen = set()
    for rule in grammar:
        if('$' in rule):
            continue
        else:
            new_productions.append(rule.split(" "))

    print("\nProductions:{0}".format(new_productions))
    for null in null_productions:

        for param in new_productions:
            for i, word in enumerate(param):
                if i < 2:   # don't degenerate LHS
                    continue
                if word == null:
                    temp = param[:i] + param[i+1:]
                    temp_tup = tuple(temp)
                    if len(temp) > 2 and temp_tup not in seen:
                        new_productions.append(temp)
                        seen.add(temp_tup)

    print("\nResultant Productions")
    for rule in new_productions:
        print(rule)
    return new_productions


remove_null_productions(grammar)

grammar2 = ["S = B B a", "B = b"]

remove_null_productions(grammar2)

grammar的输出：

Null productions: ['B']

Productions:[['S', '=', 'B', 'a', 'B'], ['B', '=', 'b']]

Resultant Productions
['S', '=', 'B', 'a', 'B']
['B', '=', 'b']
['S', '=', 'a', 'B']
['S', '=', 'B', 'a']
['S', '=', 'a']

grammar2的输出（即“S=>；BBa”）：

Null productions: ['B']

Productions:[['S', '=', 'B', 'B', 'a'], ['B', '=', 'b']]

Resultant Productions
['S', '=', 'B', 'B', 'a']
['B', '=', 'b']
['S', '=', 'B', 'a']
['S', '=', 'a']