Parsing and semantic analysis of the input sentence are performed in parallel and make heavy use of the POP-11 matcher. All this goes on within the call to procedure S. We shall begin by constructing a simplified version of S which returns <true> if the given list of words satisfies the grammar defined in the body of this chapter and <false> otherwise. In other words we can say that the simplified S `recognizes' or `accepts' sentences in our language. S attempts to match the word list against patterns, and, if a match is found, S returns <true>, otherwise <false>.
There is a pattern for each phrase-structure rule which has S on its left-hand side:
define S(list) -> found;
vars np;
if list matches [how do i get to ??np:NP] or
list matches
[can you tell me how to get to ??np:NP]
then
true -> found
else
false -> found
endif
enddefine;
The patterns should be familiar except for one additional feature: a restriction procedure. This is indicated by the appearance of :NP following each pattern variable.
Until now we have used pattern variables like ??x in such a way that they match any sequence of words. If there is a restriction procedure associated with a pattern variable, then any potential match is offered to the procedure whose name appears after the colon; if this procedure returns <false>, the match is rejected, and otherwise it is accepted. We shall define NP to accept only word lists which are noun-phrases according to our grammar, and so S is guaranteed to accept only well-formed sentences.
The procedure NP is defined in exactly the same fashion as S, by constructing patterns from those rules which have NP on the left and comparing these with the given word list:
define NP(list) -> found;
vars pn, d, n, p, np;
if list matches [??pn:PROPN] or
list matches [?d:DET ??n:NOUN] or
list matches [?d:DET ??n:NOUN ?p:PREP ??np:NP]
then
true -> found
else
false -> found
endif;
enddefine;
Again there are restriction procedures in the patterns to enforce the required syntactic categories. All three forms of the noun-phrase are taken into account, and the third involves a recursive call to NP as a restriction procedure.
If one of the patterns matches the series of words, then this must be a well-formed noun-phrase and <true> is returned; otherwise <false> is returned.
The definitions of restriction procedures DET and PREP are more simple.
define DET(word) -> found;
member(word, [a the]) -> found;
enddefine;
define PREP(word) -> found;
member(word, [in containing]) -> found
enddefine;
Each procedure is given a single word to check, and the phrase-structure rules define legal values for these words. member is a built-in POP-11 procedure that takes an item and a list as input, and returns <true> if the item is a member of the list, and <false> otherwise.
Procedures PROPN and NOUN are defined similarly, except that, to allow for the possibility of nouns and proper nouns containing more than one word, member checks that a given list of words is a member of a list of nouns or proper nouns.
define NOUN(list) -> found;
member(list, [[gallery] [square] [monument] [lake]
[park]]) -> found;
enddefine;
define PROPN(list) -> found;
member(list,
[[trafalgar square] [the national gallery]
[nelsons column] [hyde park]
[the serpentine lake] [the tate gallery]
] ) -> found;
enddefine;
The grammar has now been defined, and S will return <true> for a well-formed sentence:
S([how do i get to the gallery in the square containing a monument]) =>
** <true>
S([how do i get to the monument in trafalgar square]) =>
** <true>
The other procedures will also return <true> if given an appropriate word or phrase:
NP([the gallery in the square]) =>
** <true>
PREP("in") =>
** <true>