prolog - 为给定的上下文无关语法生成符号串（句子）

Question

我有一个简单的语法，例如

S::=a S b
S::=[] (empty string)

现在我想为上面的语法写一个解析器，比如

cfg('S', [a,'S',b])

它通过最左推导生成一个句子aaabbb。

我不够好，无法在 prolog 中处理 dcg/cfg。所以请帮助我这个例子，这样我就可以继续尝试更大的东西。

Answer 1

考虑这个 DCG 代码：

s-->[].
s-->[a],s,[b].

要运行由 DCG 定义的谓词，您应该在最后添加两个参数：“输入”和剩下的内容。如果您想识别整个列表，只需输入 []。所以，当你运行它时，你会得到：

38 ?- s(C,[]).
C = [] ;
C = [a, b] ;
C = [a, a, b, b] ;
C = [a, a, a, b, b, b] ;
C = [a, a, a, a, b, b, b, b] ;
...

如果您想要某种“返回”字符串，您可以将其添加为额外的 arg。要在 dcg 子句中编写序言代码，请使用 {}：

s('')-->[].
s(S)-->
    [a],s(SI),[b],
    { atomic_list_concat([a,SI,b],S)}.

你得到：

40 ?- s(R,X,[]).
R = '',
X = [] ;
R = ab,
X = [a, b] ;
R = aabb,
X = [a, a, b, b] ;
R = aaabbb,
X = [a, a, a, b, b, b] ;
R = aaaabbbb,
X = [a, a, a, a, b, b, b, b] ;
R = aaaaabbbbb,
...

我们生成了该语法识别的所有字符串；通常你只想检查一个字符串是否被语法识别。为此，您只需将其作为输入：

41 ?- s([a,b],[]).
true 

42 ?- s([a,b,b],[]).
false.

请注意，我们将 S::=[] 规则放在首位，否则如果您要求生成所有解决方案，prolog 将陷入无限循环。这个问题在更复杂的语法中可能不是微不足道的。要获得解决方案，您可以使用 length/2：

?- length(X,_),s(X,[]).
X = [] ;
X = [a, b] ;
X = [a, a, b, b] ;
X = [a, a, a, b, b, b] ;
X = [a, a, a, a, b, b, b, b] 

即使您的代码是：

s-->[].
s-->[a],s,[b].