Exercise 4.44 · 习题

Exercise 4.44: Exercise 2.42 described the
“eight-queens puzzle” of placing queens on a chessboard so that no two attack
each other. Write a nondeterministic program to solve this puzzle.

Parsing natural language

Programs designed to accept natural language as input usually start by
attempting to
parse the input, that is, to match the input against
some grammatical structure. For example, we might try to recognize simple
sentences consisting of an article followed by a noun followed by a verb, such
as “The cat eats.” To accomplish such an analysis, we must be able to
identify the parts of speech of individual words. We could start with some
lists that classify various words:

(define nouns
'(noun student professor cat class))

(define verbs
'(verb studies lectures eats sleeps))

(define articles '(article the a))

We also need a
grammar, that is, a set of rules describing how
grammatical elements are composed from simpler elements. A very simple grammar
might stipulate that a sentence always consists of two pieces—a noun phrase
followed by a verb—and that a noun phrase consists of an article followed by
a noun. With this grammar, the sentence “The cat eats” is parsed as follows:

(sentence
(noun-phrase (article the) (noun cat))
(verb eats))

We can generate such a parse with a simple program that has separate procedures
for each of the grammatical rules. To parse a sentence, we identify its two
constituent pieces and return a list of these two elements, tagged with the
symbol sentence:

(define (parse-sentence)
(list 'sentence
(parse-noun-phrase)
(parse-word verbs)))

A noun phrase, similarly, is parsed by finding an article followed by a
noun:

(define (parse-noun-phrase)
(list 'noun-phrase
(parse-word articles)
(parse-word nouns)))

At the lowest level, parsing boils down to repeatedly checking that the next
unparsed word is a member of the list of words for the required part of speech.
To implement this, we maintain a global variable *unparsed*, which is
the input that has not yet been parsed. Each time we check a word, we require
that *unparsed* must be non-empty and that it should begin with a word
from the designated list. If so, we remove that word from *unparsed*
and return the word together with its part of speech (which is found at the
head of the list):

(define (parse-word word-list)
(require (not (null? *unparsed*)))
(require (memq (car *unparsed*)
(cdr word-list)))
(let ((found-word (car *unparsed*)))
(set! *unparsed* (cdr *unparsed*))
(list (car word-list) found-word)))

To start the parsing, all we need to do is set *unparsed* to be the
entire input, try to parse a sentence, and check that nothing is left over:

(define *unparsed* '())
(define (parse input)
(set! *unparsed* input)
(let ((sent (parse-sentence)))
(require (null? *unparsed*))
sent))

We can now try the parser and verify that it works for our simple test
sentence:

;;; Amb-Eval input:
(parse '(the cat eats))

;;; Starting a new problem
;;; Amb-Eval value:
(sentence
(noun-phrase (article the) (noun cat))
(verb eats))

The amb evaluator is useful here because it is convenient to express the
parsing constraints with the aid of require. Automatic search and
backtracking really pay off, however, when we consider more complex grammars
where there are choices for how the units can be decomposed.

Let’s add to our grammar a list of prepositions:

(define prepositions
'(prep for to in by with))

and define a prepositional phrase (e.g., “for the cat”) to be a preposition
followed by a noun phrase:

(define (parse-prepositional-phrase)
(list 'prep-phrase
(parse-word prepositions)
(parse-noun-phrase)))

Now we can define a sentence to be a noun phrase followed by a verb phrase,
where a verb phrase can be either a verb or a verb phrase extended by a
prepositional phrase:

(define (parse-sentence)
(list 'sentence
(parse-noun-phrase)
(parse-verb-phrase)))

(define (parse-verb-phrase)
(define (maybe-extend verb-phrase)
(amb
verb-phrase
(maybe-extend
(list 'verb-phrase
verb-phrase
(parse-prepositional-phrase)))))
(maybe-extend (parse-word verbs)))

While we’re at it, we can also elaborate the definition of noun phrases to
permit such things as “a cat in the class.” What we used to call a noun
phrase, we’ll now call a simple noun phrase, and a noun phrase will now be
either a simple noun phrase or a noun phrase extended by a prepositional
phrase:

(define (parse-simple-noun-phrase)
(list 'simple-noun-phrase
(parse-word articles)
(parse-word nouns)))

(define (parse-noun-phrase)
(define (maybe-extend noun-phrase)
(amb
noun-phrase
(maybe-extend
(list 'noun-phrase
noun-phrase
(parse-prepositional-phrase)))))
(maybe-extend (parse-simple-noun-phrase)))

Our new grammar lets us parse more complex sentences. For example

(parse '(the student with the cat
sleeps in the class))

produces

(sentence
(noun-phrase
(simple-noun-phrase (article the)
(noun student))
(prep-phrase (prep with)
(simple-noun-phrase
(article the)
(noun cat))))
(verb-phrase
(verb sleeps)
(prep-phrase (prep in)
(simple-noun-phrase
(article the)
(noun class)))))

Observe that a given input may have more than one legal parse. In the sentence
“The professor lectures to the student with the cat,” it may be that the
professor is lecturing with the cat, or that the student has the cat. Our
nondeterministic program finds both possibilities:

(parse '(the professor lectures to
the student with the cat))

produces

(sentence
(simple-noun-phrase (article the)
(noun professor))
(verb-phrase
(verb-phrase
(verb lectures)
(prep-phrase (prep to)
(simple-noun-phrase
(article the)
(noun student))))
(prep-phrase (prep with)
(simple-noun-phrase
(article the)
(noun cat)))))

Asking the evaluator to try again yields

(sentence

(simple-noun-phrase (article the)

(noun professor))

(verb-phrase (verb lectures)

(prep-phrase

(prep to)

(noun-phrase

(simple-noun-phrase

(article the)

(noun student))

(prep-phrase

(prep with)

(simple-noun-phrase

(article the)

(noun cat)))))))

练习 4.44：练习 2.42 描述了"八皇后谜题"，即在棋盘上放置八个皇后使得任意两个皇后互不攻击。请编写一个非确定性程序来求解这一谜题。

对自然语言进行语法分析

以自然语言作为输入的程序，通常首先尝试对输入进行语法分析 (parse)，即将输入与某种语法结构相匹配。例如，我们可以尝试识别由冠词、名词、动词依次构成的简单句子，如"The cat eats."。为了完成这种分析，我们必须能够识别各个词的词性。我们可以从几个对各类词进行分类的表开始：

(define nouns
'(noun student professor cat class))

(define verbs
'(verb studies lectures eats sleeps))

(define articles '(article the a))

我们还需要一个语法 (grammar)，即一组描述语法单元如何由更简单的单元构成的规则。一个非常简单的语法可以规定：一个句子总是由两部分组成——一个名词短语后跟一个动词——而名词短语由冠词后跟名词构成。按照这一语法，句子"The cat eats"的分析结果如下：

(sentence
(noun-phrase (article the) (noun cat))
(verb eats))

我们可以用一个简单程序来生成这样的分析结果，该程序为每条语法规则设置一个单独的过程。要分析一个句子，我们识别其两个组成部分，并返回由这两个元素构成的表，以符号 sentence 标记：

(define (parse-sentence)
(list 'sentence
(parse-noun-phrase)
(parse-word verbs)))

类似地，名词短语通过寻找一个冠词后跟一个名词来分析：

(define (parse-noun-phrase)
(list 'noun-phrase
(parse-word articles)
(parse-word nouns)))

在最底层，语法分析归结为反复检查下一个待分析的词是否属于所需词性的词表。为此，我们维护一个全局变量 *unparsed*，用于存放尚未被分析的输入。每次检查一个词时，我们要求 *unparsed* 非空，且其首元素属于指定的词表。若满足条件，则将该词从 *unparsed* 中删除，并返回该词连同其词性（即词表的首元素）：

(define (parse-word word-list)
(require (not (null? *unparsed*)))
(require (memq (car *unparsed*)
(cdr word-list)))
(let ((found-word (car *unparsed*)))
(set! *unparsed* (cdr *unparsed*))
(list (car word-list) found-word)))

要启动语法分析，只需将 *unparsed* 设为整个输入，尝试分析一个句子，并检查没有剩余内容：

(define *unparsed* '())
(define (parse input)
(set! *unparsed* input)
(let ((sent (parse-sentence)))
(require (null? *unparsed*))
sent))

现在可以试用这个语法分析器，验证它能正确处理我们的简单测试句子：

;;; Amb-Eval input:
(parse '(the cat eats))

;;; Starting a new problem
;;; Amb-Eval value:
(sentence
(noun-phrase (article the) (noun cat))
(verb eats))

amb 求值器在这里很有用，因为借助 require 来表达语法分析约束十分方便。然而，自动搜索与回溯真正发挥作用的地方，是当我们考虑更复杂的语法时——在那里，语法单元的分解方式存在多种选择。

让我们在语法中加入一个介词表：

(define prepositions
'(prep for to in by with))

并将介词短语（例如"for the cat"）定义为介词后跟名词短语：

(define (parse-prepositional-phrase)
(list 'prep-phrase
(parse-word prepositions)
(parse-noun-phrase)))

现在可以将句子定义为名词短语后跟动词短语，其中动词短语可以是一个动词，也可以是由动词短语加介词短语扩展而成的结构：

(define (parse-sentence)
(list 'sentence
(parse-noun-phrase)
(parse-verb-phrase)))

(define (parse-verb-phrase)
(define (maybe-extend verb-phrase)
(amb
verb-phrase
(maybe-extend
(list 'verb-phrase
verb-phrase
(parse-prepositional-phrase)))))
(maybe-extend (parse-word verbs)))

同时，我们也可以扩展名词短语的定义，以允许"a cat in the class"这样的结构。原来称为名词短语的结构，现在改称简单名词短语，而名词短语现在可以是简单名词短语，也可以是由名词短语加介词短语扩展而成的结构：

(define (parse-simple-noun-phrase)
(list 'simple-noun-phrase
(parse-word articles)
(parse-word nouns)))

(define (parse-noun-phrase)
(define (maybe-extend noun-phrase)
(amb
noun-phrase
(maybe-extend
(list 'noun-phrase
noun-phrase
(parse-prepositional-phrase)))))
(maybe-extend (parse-simple-noun-phrase)))

我们的新语法能够分析更复杂的句子。例如

(parse '(the student with the cat
sleeps in the class))

产生

(sentence
(noun-phrase
(simple-noun-phrase (article the)
(noun student))
(prep-phrase (prep with)
(simple-noun-phrase
(article the)
(noun cat))))
(verb-phrase
(verb sleeps)
(prep-phrase (prep in)
(simple-noun-phrase
(article the)
(noun class)))))

注意，同一输入可能有多种合法的分析结果。在句子"The professor lectures to the student with the cat"中，可能是教授带着猫在讲课，也可能是那个学生养着那只猫。我们的非确定性程序能找到这两种可能性：

(parse '(the professor lectures to
the student with the cat))

产生

(sentence
(simple-noun-phrase (article the)
(noun professor))
(verb-phrase
(verb-phrase
(verb lectures)
(prep-phrase (prep to)
(simple-noun-phrase
(article the)
(noun student))))
(prep-phrase (prep with)
(simple-noun-phrase
(article the)
(noun cat)))))

再次要求求值器继续尝试，得到

(sentence
(simple-noun-phrase (article the)
(noun professor))
(verb-phrase (verb lectures)
(prep-phrase
(prep to)
(noun-phrase
(simple-noun-phrase
(article the)
(noun student))
(prep-phrase
(prep with)
(simple-noun-phrase
(article the)
(noun cat)))))))