python - 这些用于检测有限语法歧义的 Python 程序是否正确？

Question

我一直在做 Udacity CS262，对于 Detecting Ambiguity 问题，我不确定我的解决方案是否正确，我也不确定“官方”解决方案是否正确。

问题简要描述:编写一个函数 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)，但是官方解决方案通过了除我添加的测试用例之外的所有测试用例。看来要么是测试用例不对，要么就是官方的方案不对。

官方解法正确吗？我的解决方案正确吗？

Answer 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 提到这是一个无法确定的问题上下文无关文法是有歧义的。

另见 How is proving a context free language to be ambiguous undecidable?