6.7.2 DCG格式

许多Prolog系统允许我们以不同于普通Prolog子句的格式来识别语法。由于Prolog子句有时被称为限定子句，因此这种格式的语法被称为限定子句语法（Definite Clause Grammar），通常缩写为DCG。图6.6格式的DCG语法如图6.15所示。每个非终结符都有一个DCG对象，每条语法规则都有一条DCG子句。由于Prolog中的预测词名称必须与小写字母开头，因此我们需要将S等非终结符转换为s_n类似这种，即“S-non-terminal”。终结符则表示为一个列表元素。

Prolog系统将这些DCG规则转换为Prolog子句。其思想是使得非终结符A的每一个DCG规则都对应一个Prolog规则，该规则都有两个列表类型的逻辑参数，传统上称为Sentence和Remainder，规则如下：

A_n(Sentence, Remainder):- ...

以上规则表示字符列表Sentence与此规则生成的任何A的字符串列表Remainder相等。

更具体的说，DCG规则**d_n-->[a],[b].**与以下Prolog子句

d_n(S,R) :- symbol(S,a,R1), symbol(R1,b,R).

其中我们将Sentence缩写为S，Remainder缩写为R。预测词**symbol()**定义为：

symbol([A|R],A,R).

这是Prolog预测词定义的一种形式，其中条件仅在于参数的匹配：当S可以分为两部分A和R时，预测试symbol(S,a,R₁)就成功了，此时A匹配a，R匹配R₁。简而言之，当有R₁时，则S=aR₁。同样的，预测词symbol(R₁,b,R)也是为了找到R，这样就有R₁=bR。它们一起就得到了S=abR，这正是DCG规则**d_n-->[a],[b].**所表示的：

该技术可以扩展到一个以上的中间逻辑变量中，例如，d_n的第二个DCG规则的转换中：

d_n(S,R) :- symbol(S,a,R1), d_n(R1,R2), symbol(R2,b,R).

Prolog需要找到两个逻辑变量R1和R2的实例，由此S=aR1, R1=P(d_n)R2且R2=bR，其中P(d_n)是d_n的任意终结符生成的。当我们组合这些方程时，我们获得了如上所述的d_n(S,R)语义：S=aP(d_n)bR。（大多数Prolog处理器内部使用的是可读性差得多的格式。）