这些用于检测有限文法歧义的Python程序正确吗？
我最近在学习Udacity的CS262课程，关于检测歧义的问题，我不太确定我的解决方案是否正确，也不确定“官方”解决方案是否正确。
问题的简单描述是：写一个函数isambig(grammar, start, string)，这个函数接受一个有限的上下文无关文法（用Python字典表示）、文法的起始符号和一个字符串。如果有两棵解析树可以生成这个字符串，那么这个文法就是歧义的（至少这是我对歧义的理解，如果我错了请纠正我）。如果文法是歧义的，就返回True；否则返回False。
测试案例：
grammar1 = [
("S", [ "P", ]),
("S", [ "a", "Q", ]) ,
("P", [ "a", "T"]),
("P", [ "c" ]),
("Q", [ "b" ]),
("T", [ "b" ]),
]
print isambig(grammar1, "S", ["a", "b"]) == True
print isambig(grammar1, "S", ["c"]) == False
grammar2 = [
("A", [ "B", ]),
("B", [ "C", ]),
("C", [ "D", ]),
("D", [ "E", ]),
("E", [ "F", ]),
("E", [ "G", ]),
("E", [ "x", "H", ]),
("F", [ "x", "H"]),
("G", [ "x", "H"]),
("H", [ "y", ]),
]
print isambig(grammar2, "A", ["x", "y"]) == True
print isambig(grammar2, "E", ["y"]) == False
grammar3 = [ # Rivers in Kenya
("A", [ "B", "C"]),
("A", [ "D", ]),
("B", [ "Dawa", ]),
("C", [ "Gucha", ]),
("D", [ "B", "Gucha"]),
("A", [ "E", "Mbagathi"]),
("A", [ "F", "Nairobi"]),
("E", [ "Tsavo" ]),
("F", [ "Dawa", "Gucha" ])
]
print isambig(grammar3, "A", ["Dawa", "Gucha"]) == True
print isambig(grammar3, "A", ["Dawa", "Gucha", "Nairobi"]) == False
print isambig(grammar3, "A", ["Tsavo"]) == False
我添加了自己的测试案例。我不确定这是否正确，但我只看到一棵解析树可以生成字符串“a b”，所以这个字符串并不能证明文法是歧义的。我也不认为这个文法是歧义的。
grammar4 = [ # Simple test case
("S", [ "P", "Q"]),
("P", [ "a", ]),
("Q", [ "b", ]),
]
print isambig(grammar4, "S", ["a", "b"]) == False
这是“官方”的程序：
def expand(tokens_and_derivation, grammar):
(tokens,derivation) = tokens_and_derivation
for token_pos in range(len(tokens)):
for rule_index in range(len(grammar)):
rule = grammar[rule_index]
if tokens[token_pos] == rule[0]:
yield ((tokens[0:token_pos] + rule[1] + tokens[token_pos+1:]), derivation + [rule_index])
def isambig(grammar, start, utterance):
enumerated = [([start], [])]
while True:
new_enumerated = enumerated
for u in enumerated:
for i in expand(u,grammar):
if not i in new_enumerated:
new_enumerated = new_enumerated + [i]
if new_enumerated != enumerated:
enumerated = new_enumerated
else:
break
result = [xrange for xrange in enumerated if xrange[0] == utterance]
print result
return len(result) > 1
这是我自己写的，程序要长得多：
def expand(grammar, symbol):
result = []
for rule in grammar:
if rule[0] == symbol:
result.append(rule[1])
return result
def expand_first_nonterminal(grammar, string):
result = []
for i in xrange(len(string)):
if isterminal(grammar, string[i]) == False:
for j in expand(grammar, string[i]):
result.append(string[:i]+j+string[i+1:])
return result
return None
def full_expand_string(grammar,string, result):
for i in expand_first_nonterminal(grammar,string):
if allterminals(grammar,i):
result.append(i)
else:
full_expand_string(grammar,i,result)
def isterminal(grammar,symbol):
for rule in grammar:
if rule[0] == symbol:
return False
return True
def allterminals(grammar,string):
for symbol in string:
if isterminal(grammar,symbol) == False:
return False
return True
def returnall(grammar, start):
result = []
for rule in grammar:
if rule[0] == start:
if allterminals(grammar,rule[1]):
return rule[1]
else:
full_expand_string(grammar, rule[1], result)
return result
def isambig(grammar, start, utterance):
count = 0
for i in returnall(grammar,start):
if i == utterance:
count+=1
if count > 1:
return True
else:
return False
现在，我的程序通过了所有的测试案例，包括我添加的那个（grammar4），但官方的解决方案通过了所有测试案例，除了我添加的那个。对我来说，要么是测试案例有问题，要么是官方的解决方案有问题。
官方的解决方案正确吗？我的解决方案正确吗？
1 个回答
在我看来，grammar4 这个语法是没有歧义的。它只有一棵解析树：
S -> PQ
P -> a
Q -> b
S
|
___|____
P Q
| |
a b
不过，官方程序却说它是有歧义的，因为它连续使用了规则 P -> a 和 Q -> b：
[(['a', 'b'], [0, 1, 2]), (['a', 'b'], [0, 2, 1])]
(现在有两个规则序列 0,1,2 和 0,2,1。)
所以这个“官方”的程序似乎错误地把 grammar4 检测成了有歧义。
更新：我查看了你的代码并做了一些测试，除了没有处理递归（官方版本也不处理递归）之外，你的程序似乎能正确区分有歧义和没有歧义的情况。
简单测试：
grammar5 = [
("S", ["A", "B"]),
("S", ["B", "A"]),
("A", ["a"]),
("B", ["a"]),
]
print(isambig(grammar5, "S", ["a", "a"]))
S -> AB
S -> BA
A -> a
B -> a
S
|
___|____
A B
| |
a a
S
|
___|____
B A
| |
a a
你的版本返回“有歧义”（官方版本也是如此）。
如果你去掉 ("S", ["B", "A"])，你的版本就能正确地切换到“没有歧义”，而另一个版本仍然返回“有歧义”（我们又回到了 grammar4 的情况）。
也许其他人（比我更有经验的人）可以参与讨论。
更新 2：Ira Baxter 提到，判断一个上下文无关语法是否有歧义是一个不可判定的问题。