无法从给定的 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)

S=>aBa ,B=>b 给出 S=>aBa|aa 和 B=>b
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']

无法从给定的 python 代码生成 S=>Ba

Failing to generate S=>Ba from python code given

python

grammar

python-3.x