为给定的上下文无关语法生成符号串(句子)

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子句中编写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 :: = []规则,否则如果您要求生成所有解,则prolog将陷入无限循环.在更复杂的语法中解决这个问题可能并不容易.要获得解决方案,您可以使用长度/ 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].