NLP PROLOG 语法

Question

我们有正式的语言

G 1 = { V , T , S , P }, where
V = { S , E }
T = { x , y , z }
P = { S->E , E->xE , E->yE , E->z }

我们可以接受七个句子 { xz , xy , xyz , xyxz , z , xxyz , Xyz } 作为格式良好的公式吗？使用 Prolog 验证这一点。

这是我的代码：

s --> e.
e --> [x], e.
e --> [y], e.
e --> [z].

它只能识别 s([z], R)。为什么？

?- s([z], R).
R = [].

?- s([xz], R).
false.

?- s([x], R).
false.

Answer 1

首先，正如@lurker 在评论中已经指出的那样，在调用 DCG 时始终使用phrase/2或phrase/3。其次，正如@TomasBy 和@WillBeason 所指出的，您的 DCG 正在描述一个包含由逗号分隔的原子x,y和的列表z。因此，要s根据您的语法测试 xz 是否是一个实际的句子（我认为这就是代表的意思），您可以查询：

?- phrase(s,[x,z]).
true ;
false.

的确是。现在我们来看看最一般的查询，即问有哪些句子？：

?- phrase(s,S).
ERROR: Out of local stack

那不太顺利。原因是DCG规则的顺序：调用s//0导致e//0被调用的第一条规则，递归调用e//0，也就是说，第一条规则，e//0如此循环，直到Prolog用完堆栈。因此，让我们通过将非递归规则放在首位来改变规则的顺序......

s --> e.

e --> [z].          % <- moved here from last position
e --> [x], e.
e --> [y], e.

...并重试查询：

?- phrase(s,S).
S = [z] ;
S = [x, z] ;
S = [x, x, z] ;
S = [x, x, x, z] ;
.
.
.

现在我们得到了实际的解决方案。所以 DCG 规则的顺序很重要。然而，答案的上市是不公平的，因为最后一条规则e//0，一处理y，实际上是永远不会被调用。这可以通过在目标前加上前缀来解决length/2。查询...

?- length(S,_).
S = [] ;
S = [_G3671] ;
S = [_G3671, _G3674] ;
S = [_G3671, _G3674, _G3677] ;
.
.
.

...yields 具有所有可能长度的列表，因此将其添加到 DCG 调用前，将使 Prolog 在移动到长度 1 之前寻找长度为 0 的所有解，然后再移动到长度 2 等等......

?- length(S,_), phrase(s,S).
S = [z] ;                    % <- solutions of length 1 from here
S = [x, z] ;                 % <- solutions of length 2 from here
S = [y, z] ;
S = [x, x, z] ;              % <- solutions of length 3 from here
S = [x, y, z] ;
S = [y, x, z] ;
S = [y, y, z] ;
S = [x, x, x, z] ;           % <- solutions of length 4 from here
.
.
.

所以你的语法实际上产生了任意长度的句子，这是应该的。继续您的七句话示例，如果您的应用程序需要限制列表的长度，您可以通过在between/3查询前添加一个目标来实现...

?- between(1,3,N), length(S,N), phrase(s,S).
N = 1,
S = [z] ;
N = 2,
S = [x, z] ;
N = 2,
S = [y, z] ;
N = 3,
S = [x, x, z] ;
N = 3,
S = [x, y, z] ;
N = 3,
S = [y, x, z] ;
N = 3,
S = [y, y, z] ;
false.

...现在将产生最多由 3 个单词组成的所有七个句子。请注意，您的示例 { xz , xy , xyz , xyxz , z , xxyz , xyz } 不完全是您的语法所描述的句子集。根据语法规则，元素xy根本不是一个句子。句子xyxz和xxyz由您的语法指定，但要求最大长度至少为四个单词，这将产生 16 个答案。七个句子中的最后一个xyz在您的示例中出现两次，除非您的意思是查询...

?- phrase(s,[X,y,z]).
X = x ;
X = y ;
false.

......产生两个句子，其中第一个仍然构成重复。

最后，如果您真的非常需要获得原子作为答案，您可以更改 DCG 以将x,y和对应的代码z放入列表中，而不是实际的原子。然后您可以使用atom_codes/2将句子作为单个原子而不是单词列表获取：

s --> e.

e --> [0'z].      % 0'z denotes the code corresponding to z
e --> [0'x], e.   % 0'x denotes the code corresponding to x
e --> [0'y], e.   % 0'y denotes the code corresponding to y

?- between(1,3,N), length(S,N), phrase(s,S), atom_codes(A,S).
N = 1,
S = [122],
A = z ;
N = 2,
S = [120, 122],
A = xz ;
N = 2,
S = [121, 122],
A = yz ;
N = 3,
S = [120, 120, 122],
A = xxz ;
N = 3,
S = [120, 121, 122],
A = xyz ;
N = 3,
S = [121, 120, 122],
A = yxz ;
N = 3,
S = [121, 121, 122],
A = yyz ;
false.