The simplest way in which a computer program can respond to supplied natural language is with a slot-and-frame parser. At its most primitive level the slot-and-frame approach simply compares the supplied text with known phrases. This approach was used in early adventure game programs. Anyone who played any of the first adventure games will be familiar with typing in phrases like; "GO EAST" and "TAKE LAMP".
+----------------+
|GET INPUT PHRASE|
+-------|--------+
\|/
+--------+---------+
|INITIALISE COUNTER|
+--------|---------+
\|/
+----------+----------+
+----------->-------------+ COMPARE INPUT PHRASE|
| | WITH LIBRARY PHRASE |
| +----------|----------+
| \|/
| +--+ +--+---+ +---+
| |NO+---------<------+MATCH?|------>-------+YES|
| +|-+ +------+ +-|-+
/|\ \|/ \|/
| +-------+---------+ +------+-------+
| |INCREMENT COUNTER| |PRINT RESPONSE|
| +-------|---------+ +------|-------+
| \|/ |
++-+ +------+-------+ |
|NO+-----+HAS COUNTER | \|/
+--+ |REACHED LIMIT?| |
+------|-------+ |
\|/ +----------+ |
+-+-+ |PRINT | +-+--+
|YES+----->-----+I DON'T +------->-------+STOP|
+---+ |UNDERSTAND| +----+
+----------+
Flow diagram of a slot-and-frame parser
A slot-and-frame parser is simply implemented with two tables: one of known
phrases, a second with corresponding responses.
| Phrase | Response |
| HELLO | HELLO |
| HOW ARE YOU? | VERY WELL THANK YOU |
| HOW'S THE WIFE? | STILL BREATHING |
| DO YOU WANT A BEER? | IS THE POPE A CATHOLIC? |
| DO YOU TAKE SUGAR? | NO THANKS |
The following program illustrates the idea of a slot-and-frame parser. The number of known phrases is very small, but may be expanded to the extent of the available computer's memory.
---------
Listing 1
---------
/* Primitive Slot & Frame parser demonstration */
char *phrase[] = { "HELLO",
"WHAT IS YOUR NAME",
"HOW OLD ARE YOU",
"DO YOU LIKE CRICKET",
"HAVE YOU EVER BEEN TO SPAIN",
"DO YOU LIKE CHIPS",
"" };
char *response[] = { "Hello",
"Billy",
"Too Old!",
"Yes I like cricket",
"No I have never been to Spain",
"Yes, I like chips",
"" };
void RESPOND(char *text)
{
int n;
for(n = 0; *phrase[n]; n++)
{
/* Case insensitive comparison */
if (stricmp(text,phrase[n]) == 0)
{
/* A precise match is found */
printf("%s",response[n]);
return;
}
}
printf("I Don't understand");
}
main()
{
char text[250];
for(;;)
{
printf("\n?");
gets(text);
if (*text)
{
RESPOND(text);
}
else
break;
}
}
The first problem encountered with the primitive slot-and-frame approach is
that even the most irrelevant difference between the entered phrase, and the
known phrase will not be understood. If the phrase "What is your name" is
entered the demonstration program, a response of "Biily" will be printed.
However, the inclusion of the name Billy to a question is enough to cause
confusion. "How old are you Billy" is a seemingly valid question, but the
program cannot find a matching known phrase and so the response is "I don't
understand".
The next generation of slot-and-frame parsers scanned the input phrase for known words or phrases, and responded accordingly. The early slot-and-frame parsers were written in early dialects of BASIC. BASIC still does not have string handling facilities that are as powerful as those provided by C. The differences between this example second generation slot-and-frame parser and the primitive one are twofold. First, the input string is converted to upper case. Second, the C strstr() function is used to locate a known phrase within the input phrase. We have to convert the input phrase to the same case as the known phrases because strstr() is case sensitive.
---------
Listing 2
---------
/* Second Generation Slot & Frame parser demonstration */
char *phrase[] = { "HELLO",
"WHAT IS YOUR NAME",
"HOW OLD ARE YOU",
"DO YOU LIKE CRICKET",
"HAVE YOU EVER BEEN TO SPAIN",
"DO YOU LIKE CHIPS",
"" };
char *response[] = { "Hello",
"Billy",
"Too Old!",
"Yes I like cricket",
"No I have never been to Spain",
"Yes, I like chips",
"" };
void RESPOND(char *text)
{
int n;
for(n = 0; *phrase[n]; n++)
{
/* Search for the known phrase occurring within the text string */
if (strstr(text,phrase[n]))
{
/* The known phrase was located */
printf("%s",response[n]);
return;
}
}
/* No known phrases were located within the text string */
printf("I Don't understand");
}
main()
{
char text[250];
for(;;)
{
printf("\n?");
gets(text);
if (*text)
{
strupr(text);
RESPOND(text);
}
else
break;
}
}
With such a small development, the flexibility of the parser has grown
enormously. Now phrases such as "How old are you?" and "How old are you,
Billy?" generate a sensible response, where before they didn't.
The third generation of slot-and-frame parsers search are sometimes called "verb and noun search parsers". The input phrase is searched for known verbs (action words), and nouns (objects). This type of parser is extensively used in adventure games where the input phrase will be a noun and a verb, with perhaps a smattering or prepositions. Something along the lines of; "TAKE THE BUCKET", or "OPEN THE DOOR" or "SMASH THE WINDOW WITH THE HAMMER". Let us use the phrase "SMASH THE WINDOW WITH THE HAMMER" for an example. The program may recognise the verb "SMASH", the object "WINDOW" but also require a qualification object "HAMMER". So long as the player enters a phrase containing these three words the parser will understand the command. So, "HAMMER WINDOW SMASH" and "SMASH HAMMER WINDOW" and even "SMASH THE HAMMER WITH THE WINDOW" will all be accepted. A verb and noun search parser is very lax on semantics, this doesn't matter too much in the adventure game domain. In conversational computing a lack of semantics can lead to erroneous deductions.
One other point to remember about all the slot-and-frame computer parsers is that the computer program never understands what is being said. Rather it simply makes automated responses to standard phrases.