                        SLOT AND FRAME PARSING

                            Matthew Probert
                           Servile  Software


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              
                

              An example slot-and-frame phrase and response table


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. 

