python - 无法从给定的 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 和 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_products 更改为函数的参数，以便更容易更改其值。

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)

语法输出:

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']