给定 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 和 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']
最佳答案
这里的问题是 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']
关于python - 无法从给定的 python 代码生成 S=>Ba,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55912076/