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

Question

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

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

现在我想为上述语法编写一个解析器，例如

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

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

我不足以处理序言中的 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] ;
...

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

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::=[] 规则放在第一位，否则如果您要求生成所有解决方案，序言将陷入无限循环。在更复杂的语法中解决这个问题可能并不容易。要获得解决方案，您可以使用 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].