(c) Copyright 1979, Massachusetts Institute of Technology.  All rights reserved.

Parser Paper

    This paper is intended as a rather technical description of the Zork
parser, with particular emphasis on the actual algorithm and mechanics
of parsing an english command.  The method is quite specific to the task
and is not very 'elegant'; it nonetheless meets the two basic
requirements for a game of this type: the ability to understand a
moderately complex sentence, and fast response. The parser itself is a
rather small piece of code, considering the assortment of command
syntaxes that it is called upon to parser.  As can be from a small
amount of game playing, the parser is   Much (perhaps most) of the code
in the parser deals with matters peripheral to the central task of
parsing; however, these 'peripherals' in fact make the parser, and
therefore the game, much more pleasant to use.  These peripherals
include the use of 'memory frames' and defaulting, both of which will be
discused below.

    The Zork parser can understand the following sentence: 'Put all of
the valuables except the torch and the coin into the trophy case'.  That
may indeed be impressive, but it belies the fact that the Zork parser
is actually a three-word parser: its 'output' is a structure which
contains at most a verb and two nouns (objects in the game) and in the
simplest case only a verb.  The parser's job then is to take a possibly
complex set of words and distill them into a small and managable size.
The actual parsing is an iterative procedure involving a number of mostly
unrelated processing (that is, there is very little 'communication' 
between the modules).  This does not mean that this is the preferable
way of parsing; indeed, it causes the parser appear less than intelligent
in a number of cases, as will be seen below.  The modules in the parser
perform the following tasks and each will be discussed in turn:

    1) Making words from the input stream, 
    2) Making verbs and noun clauses out of the words,
    3) Defaulting from previous inputs, if needed (memory frames),
    4) Matching the verbs and noun clauses with known syntaxes (this
	may include doing defaulting and using memory frames), and
    5) Performing various housekeeping chores.

    The simplest of the modules is the first.  All of the characters
in the input stream are examined looking for word breaks and each word
as it is found is truncated to five characters (a restriction imposed
by space limitations; each word is one PDP-10 machine word, i.e. 36 bits).
Commas are replaced by the word 'AND' and periods are replaced by the
word 'THEN'.  These are used for separating multiple objects (e.g. 'Take
the knife, sword, and the matchbook') and in separating multiple commands
in one command line (e.g. 'North. East. Open the window. Go in.),
respectively.

    The second phase is the one in which the actual verbs and noun clauses
of the sentence are found.  Essentially, this phase is a single loop
through all of the words in each logical command which is terminated
either by an end of line specifier (the null string) or by the word
'THEN'.  Each word is examined in the following manner:

     1) If no verb has been specified and the word is in the verb
        dictionary, make that word the current verb.
     2) If no verb has been specified and the word is in the directions
        dictionary, the command is assumed to be movement in that
	direction.  The entire parse completes immediately.  This
	makes movement commands parse very quickly, which is important
	in a game in which most of the coomands are movements.
     3) If the word is in the adjectives dictionary, that word is made
	the current adjective, regardless of whether other adjectives
	have been given previously.  This allows a sentence like
	'Take the burned-out useless lantern' to work.  Note also
	that 'Take the green nasty square burned-out useless lantern'
	will also work and that 'Take the burned-out useless green
	nasty square' lantern will not, assuming that only burned-out
	and useless are legal adjectives for the lantern.
     4) If the word is in the prepositions dictionary, that word is
	made the current preposition, unless a preposition has
	already been given, in which case others are ignored.  This
	allows 'Get out of the boat' to work.  Also, 'Get out down
	under of with to for the boat' will also work.  The point
	of the previous two examples (here and 3 above) is that
	the parser is more interested in finding something that can
	parse than in correcting silly sentences.  This don't-care
	approach provides for some of the parser's speed.
     5) If the word is in the 'buzzword' dictionary, it is ignored.
	Buzzwords include A, THE, IS, etc.  For the final silly but
	parsable input, try out the following:
	'The put a the is large small clean rusty the knife is in with
	down under for the a blue orange gold trophy case'.
  	Interpretation:
	'Put the rusty knife in the trophy case'
	The moral is: Most people will not expect the former to work
	and thus will not try it.  Thus, there is no harm done in
	providing the optimization of simply ignoring those cases.
     6) If the word is in the objects dictionary, the fun begins, as
	described below.
     7) Otherwise the word is unknown, the parser prints 'I don't
	know the word <unknown word>', and the parse ends abruptly.

    When an object name is specified the parser tries to fill one of the
maximum two slots which the parser allows for objects.  If more than two
objects are specified in a command, the parse ends in error.  The method
for finding an object from its name is rather more compicated than it
would seem.  This is because the parser must decide which objects, from
among all of the objects in the game, can be referenced legally at
any given time, and then decide which object matches a given description
uniquely from those possibilities.  Here's what it does:

    First, it attempts to find the unique object represented by the
input which can be found in the current environment.  To this end, a
routine called 'GET-OBJECT' is called with the object name and the
current adjective. GET-OBJECT tries to find an object matching those
specifications and which is available in the current environment (i.e.
room).  In so doing, it checks the possessions of the player, the
contents of the room, and the current 'global' objects. The latter
consist of 'global global' objects, which are defined to always be
available (e.g. parts of the body, the ground) and 'local global'
objects which may be part of the current environment (e.g. a house might
be referenced in the various parts of the house and in the house's
immediate surroundings).  The latter type of global is specified in the
definition of each particular room. In 'checking' these groups of
objects, the parser enforces such restrictions as being unable to find
an object which is inside a closed receptacle or a darkened room.
GET-OBJECT may find more than one object which is completely specified
in the current environment by the object name and adjective.  When it
returns with an 'ambiguity', the parse stops and the player is asked to
disambiguate the object (e.g. saying 'Push the button' might lead to the
reply 'Which button?' if there were more than one button present).
Similarly, returns indicating a darkened room or the total inability to
find a given object result in the parser giving the messages 'It's too
dark in here to see' and 'I can't see any <adjective> <object name>
here'.  In these cases the parse is again ended prematurely.

    Assuming that no error has occured thus far, a unique object has
been returned by GET-OBJECT.  The parser now checks for two special
cases: multiple objects and prepositional phrases.  In the first, the
object found is appended to a group which includes all of the objects
specified thus far within the 'AND'.  If this was the first object in
the group, a special 'AND' object is made the value of the current
slot.  In the case in which a preposition has been specified, the phrase
and object are joined into a structure called, unsurprisingly, a phrase,
which is then saved into the current slot.  This pass through the input
continues until a command terminator is reached (end of line or the word
'THEN').  If the command terminator is the word 'THEN', a pointer to
the remainder of the is saved in order that processing can continue after
the current command is processed.

    The third phase of parsing is a simple-minded attempt to use the
parser's 'memory frames' to supply those parts of a command which are
absolutely required for further processing (e.g. a verb) and to cause
dangling prepositions and adjectives to be examined.  This phase is
again iterative, performing the following checks in turn:

     1. If there is no verb, try to find one in 'memory'.  If unable
	to, give an error message and save whatever input has been
	processed.  For example, if the input were 'THE BOTTLE' and
	no verb was specified or is in 'memory', the parser will ask
	'What should I do with the bottle?' and save in 'memory' the
	object representing the word 'BOTTLE'.  This provides the
	mechanism for the player being able to respond 'OPEN IT'.
	How this is done will be discussed later.

     2. If there is a preposition in 'memory' and the last object
	specified is not already part of a phrase, the preposition
	is joined with the object to make a phrase.  Since this
	might cause an inappropriate use of 'memory' in a fully
	specified sentence, a check is also made to insure that
	if a verb was specified in the current input, that the
	same verb was the one saved in 'memory'.

     3. If there is a dangling preposition in the input and the
	last object specified is not part of a phrase, a phrase
	is constructed from the two.  This enables 'Turn the lamp off'
	to be 'turned into' 'Turn off the lamp'.
	
    The fourth phase of parsing now begins: that of syntax checking.
In order to discuss what syntax checking entails, the definition of
a syntax must be described.  In the simplest case, a syntax definition
might look like:	

 	Verb DIRECT:	[OBJ  [ACTION-SPECIFICATION]]
  
    The 'OBJ' specifies that any object is legal for the verb and ACTION-
SPECIFICATION refers to the verb routine which will be called if this
syntax is used.  This verb, then, takes only a direct object.  Similarly,
a verb which takes both a direct and indirect object might look like:

	Verb BOTH:	[OBJ OBJ [ACTION-SPECIFICATION]]

    Note that each item before the action specification refers to one
object which may be specified in the syntax.  Prepositions can now be
added to the syntax definition by placing the desired one appropriately.
The following are plausible definitions for the verbs 'put' and 'pick'.
They describe the syntaxes 'Put something in something' and 'Pick up
something', respectively.

	Verb PUT:	[OBJ "IN" OBJ [ACTION-PUT]]
	Verb PICK:	["UP" OBJ [ACTION-TAKE]]
   
    Most Zork verbs have more than one possible syntax.  Thus, a verb
is defined to have an arbitrary number of these syntaxes.  As an example,
the verb 'turn' might look like this:

	Verb TURN:	["ON" OBJ [ACTION-LIGHT]]
			["OFF" OBJ [ACTION-EXTINGUISH]]
			[OBJ "WITH" OBJ [ACTION-TURN]]
			[OBJ "TO" OBJ [ACTION-SET]]

    This defines four different syntaxes for the verb 'turn'.  Note that
each syntax describes a different action routine.  If the player types
'Turn off lamp', the EXTINGUISH routine will be called, etc.  With this
brief introduction to syntax definition, it is possible to describe the
step of syntax checking.

    In the simplest case, syntax checking is a loop through all of the
possible syntaxes for a given verb and seeing if there is an exact match.
For example, if the player typed 'Turn the bolt with the knife' the parser
would, by syntax checking time, have the following output:

	[<verb TURN> <object: BOLT> <phrase: WITH KNIFE>]

    Were the proper syntaxes for 'turn' those desribed above, the second
of them would be seen as a match and the action TURN would be
selected.  The simple case is sufficient to demonstrate this parser module
in overview.  What actually happens is this:

    Each syntax for the given verb is taken and compared to the parser's
current output, one 'slot' at a time.  In the given example, the first
'slot' is <object: BOLT> and the second, <phrase: WITH KNIFE>.  If the
first slot matches the current syntax, the second is checked.  If the
second also matches, syntax checking is finished and the appropriate
action is selected.  Otherwise, the following strategy is invoked:

    1st		2nd		Action
    --- 	---		------
    Match	Match		Above case, works immediately
    Match	Non-match	Go to next syntax
    Match	None given	Hold onto this syntax as a possibility.
				If none better come along, save this
				possibility in a 'memory frame' and
				ask the player to supply it.

    Non-match	1st slot	Try putting the first slot into the
		matches 2nd	second, and hold onto this syntax as
		syntax		a possibility - He might have said
		and 2nd not	'Kill with knife', meaning the troll.
		given

    Non-match	Not as above	Go to next syntax

    When this pass is completed, there are two possibilities: either
an exact match was found, in which case the final stages of the parse
are performed (see below) or there is some object or phrase unspecified
in the input which is required to make a legal syntax.  The following
is then done:

    No Held Syntax
  	 ->  Say 'I can't make sense out of that.'

    Held ->  Each slot in the held syntax is examined.  If the same
	     slot in the input is not specified, two things are tried:
		
		1. Find an object in a 'memory frame'
		2. Find a 'reasonable' object
	
    'What', you may ask, 'is a reasonable object'.  This leads directly
into the concept of defaulting which was alluded to previously.  In
Zork, defaulting is done through additional specifications in the syntax
definitions.  As an example of how this is done, consider the following
updated version of a previous example:

	Verb TURN:	["OFF" <ON-property> [ACTION-EXTINGUISH]]

    This means that rather than any object being proper in the syntax
that specifically those objects with some 'ON' property should be 
considered when the object is not specified.  In this example, if
there were only one 'ON' object in the room, it would be chosen as
the 'reasonable' default object.  The facility for specifying a property
in the syntax allows the parser to reject some inputs without having
the action routines do the checking.  The addition of an equals sign
before the property specification tells the parser that the object
specified MUST have that property.  More on this feature later.

    Assuming that none of those strategies has worked, we store
a 'memory frame' and ask the user to provide the missing information.
If, however, all of the objects are specified (or defaulted, or found
in memory), the final phase of the parse is performed.

    The final phase of parsing is the enforcement of conditions
specified in the syntax definitions ('What, more??') as to whether
objects specified by the player should be in his possession before
any action is taken.  This also allows action routines to do less
'paperwork'.  The possible specifications for the taking of objects
are:
	Option					Example
	------					-------
	Don't even try				Take
	Try, but don't care if can't		Read
	Try, and fail if can't			Kill

     The verb 'take' doesn't need to check, since that's what
take does anyway.  'Read' would like the player to have the item
being read, but not caring about the result allows for reading
objects which cannot be taken (e.g. walls).  The best example
of an object which wants to already be in hand is a weapon, with
the verb being 'Kill'.  Clearly, a fighting situation is not
conducive to stooping down to pick up the weapon and then being
able to brandish it in one turn.  Other examples from Zork can
easily be imagined.

(c) Copyright 1979, Massachusetts Institute of Technology.  All rights reserved.
