转载自：https://mp.weixin.qq.com/s/PqjUQHSDy90KqX-tCugSuA

3 练习

练习7.1。假设我们正在使用以下DCG：

s --> foo,bar,wiggle.

foo --> [choo].

foo --> foo,foo.

bar --> mar,zar.

mar --> me,my.

me --> [i].

my --> [am].

zar --> blar,car.

blar --> [a].

car --> [train].

wiggle --> [toot].

wiggle --> wiggle,wiggle.

写下与这些DCG规则相对应的普通Prolog规则。 Prolog对查询s(X,[])的前三个响应是什么？

练习7.2  形式语言anbn − {ǫ}由anbn中的所有字符串组成，除了空字符串。编写生成这种语言的DCG。

练习7.3  假设anb2n是形式语言，它包含以下所有形式的字符串：长度为n的连续块，其后是长度为2n的bs的连续块，除此之外没有其他内容，例如abb，aabbbb和aaabbbbbb属于anb2n ，空字符串也是如此。编写生成这种语言的DCG。

4 实践环节

本课程的目的是帮助您熟悉DCG，差异列表及其之间的关系，并为您提供一些编写基本DCG的经验。正如您将在下一章中了解到的那样，DCG的功能远不止上述。但是，到目前为止，您所学到的知识无疑是核心知识，在继续学习之前，对基本概念感到满意非常重要。

首先是一些键盘练习：

1.输入或下载本文中讨论的基于简单的append / 3的简单识别器，然后运行一些跟踪。如您所见，当我们说它们的性能很差时，我们并没有夸张。即使是像“The woman shot a man”这样简单的句子，您也会看到轨迹很长且难以追踪。

2.接下来，键入或下载我们的第二个识别器，该识别器基于差异列表，并运行更多跟踪。如您所见，效率显着提高。此外，您会看到这些轨迹非常易于理解，尤其是与基于append / 3的实现所产生的怪物进行比较时。

3.接下来，键入或下载本文讨论的DCG。键入清单，以便您可以看到Prolog将规则转换为什么。系统如何转换Det—> [the]形式的规则？也就是说，是将其转换为det([the | X],X)之类的规则，还是利用包含“ C”谓词的规则？

4.现在运行一些跟踪。除了变量名称之外，您在此处观察到的跟踪应该与运行差异列表识别器时观察到的跟踪非常相似。

现在是时候编写一些DCGs了：

1.形式语言even非常简单：它由包含偶数个as的所有字符串组成，而没有其他字符串。注意，空字符串ǫ属于偶数。写一个生成偶数的DCG。

2.形式语言anb2mc2mdn由以下形式的所有字符串组成：不间断的as块，然后是不间断的bs块，然后是不间断的cs块，然后是不间断的ds块，这样a和d块是长度完全相同，并且b和c块的长度也完全相同，而且分别由偶数个bs和cs组成。例如，ǫ，abbccd和aabbbbccccdd都属于anb2mc2mdn。编写生成这种语言的DCG。

3.逻辑学家称之为“关于命题符号p，q和r的命题逻辑”的语言可以通过以下上下文无关的语法来定义：

prop -> p

prop -> q

prop -> r

prop -> ¬  prop

prop -> (prop ∧ prop)

prop -> (prop ∨ prop)

prop -> (prop → prop)

编写生成这种语言的DCG。实际上，由于我们还不了解Prolog运算符，因此您将不得不做出一些相当笨拙的折衷方案。例如，与其让它识别

¬ (p → q)

您将必须让它识别诸如

[not, ’(’, p, implies, q, ’)’]

代替。在第9章中，我们将更自然地学习如何处理命题逻辑。同时，编写一个接受该语言外观笨拙的DCG。对or 使用∨，对and使用 ∧。