prolog - 从歧义语法转换为明确语法

Question

我有模棱两可的上下文无关语法，它有产品：

s --> [0],s,[1].
s --> [0],s.
s --> [].

这当然是模棱两可的，因为对于 00011 我可以绘制另外两个解析树。我必须编写我的语法，这是明确的语法并描述相同的语言。我的想法是：

   s --> [0],s,[1].
   s --> [0],a.
   s --> [].
   a --> [0],a.
   a --> [].

很好？我怎么能证明呢？

Answer 1

那么如何证明歧义呢？在 Prolog 中，这对于具体的句子很容易实现：

| ?- length(Xs,N), bagof(t,phrase(s,Xs),[_,_|_]).              

N = 3
Xs = [0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 5
Xs = [0,0,0,0,1] ? ;

N = 5
Xs = [0,0,0,1,1] ? ;

N = 6
Xs = [0,0,0,0,0,1] ? 

这证明了具体长度存在歧义，并给出了相关反例。

然而，有一个警告可能会在一段时间后显示：bagof/3必须以某种方式存储整个解决方案集。所以如果这个集合非常大，bagof/3可能会溢出。以下查询以获取冗余解决方案为代价避免了此错误：

| ?- length(Xs,N), phrase(s,Xs), bagof(t,phrase(s,Xs),[_,_|_]).

N = 3
Xs = [0,0,1] ? ;

N = 3
Xs = [0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 4
Xs = [0,0,0,1] ? ;

N = 5
Xs = [0,0,0,1,1] ...

随着您改进的语法，查询循环。这意味着系统找不到反例。至少我测试的长度不会低于 1000。

关于在 Prolog 中编写 DCG 的一些一般性说明：

• 尝试将递归情况放在最后，这可能会节省一些空间。

• 您可能希望使用双引号字符串来表示终端。有关更多信息，请参阅此答案。