Part 4: Parsing Notes, and Enforcing Grammar
I would like to say again that, although this handles a lot, it is still not a great parser. Inform, TADS, et al. give you a great parser. These ~220 heavily commented lines of Python give you a mediocre-to-reasonably-decent parser.
I’m omitting some helper functions here: regularize_command
moves some elements of possible commands into canonical forms, such as changing “n” to ['go', 'north']
, and making changes such as “eastward” to “east”, so that the main parser code only has to deal with canonical forms. possible_phrasal_endings
helps to work with phrasal verbs in English, so that if the first part of the verb is “look” it knows that it needs to be aware that [‘in’, ‘at’] are possible parts of the verb itself and not necessarily prepositions, because prepositions also are used to separate direct from indirect objects, and this is a headache. (This parser assumes that direct and indirect objects are always separated by prepositions, and indirect objects must be preceded by a preposition. How is this enforced at the parsing level? That’s a great question and I’m glad you asked it and I’m not going to talk about it until later. But the short answer is “decorators.”) So if the player types PUT APPLE ON BED, then APPLE is the direct object, BED is the indirect object, and ON is a preposition specifying their desired relationship. The parser will barf if you type PUT APPLE BED instead of PUT APPLE ON BED because there is no preposition between the direct and indirect objects, so it looks for an object in scope for which APPLE BED is a fair description; and even if it finds one, it will complain that it doesn’t know what to put the apple bed on, because you didn’t specify an indirect object. How could you have? You didn’t use a preposition. Duh.
But here’s the basic strategy it takes: Given a list of strings (the tokenized command), it tries to identify all of the relevant bits of data that might have to be passed to an action-processing routine on an object. The direct object of the command itself is the object being operated on; and the verb is the name of the (non-underscore-named) method that’s being called on that object. There are a few other parameters that might be necessary, depending on the action that is being performed and what the user typed; these include the actor
(who’s performing the action: usually, but not always, the PC); using
(a tool that’s being used to perform the action: SHOOT TROLL WITH ARROW puts the arrow, if one is in scope, in the using
parameter); about
, a string or in-game object specifying a topic of conversation; dest
and prep
, a pair of parameters that specify the thing you’re putting the direct object on/in/under/etc., and which of those relationships it is; a few others. As parsing progresses, these parameters are assembled into a dictionary that’s passed to the action-dispatch method when the action method is called on a particular in-game object.
Processing runs through, roughly, this series of steps:
- Normalization of command forms, as touched on briefly above, but more exhaustively and boringly.
- Checking to see if someone is being directly addressed. This happens by looking to see if any words in the command end with a comma. If any does, the bit of the command before a comma is treated as a description of someone visible, and the parser tries to match that description to someone addressable. Alternate forms of order-giving are not supported, so the parser currently supports RICK, SHAVE YOUR STUPID-LOOKING BEARD but not TELL SHERIFF RICK TO SHAVE HIS BEARD. C’est la vie. The game also implements ASK/TELL in the form ASK RICK ABOUT STUPID BEARD but not RICK, WHAT’S UP WITH YOUR BEARD, because a comma always means that a command is being issued. C’est la vie.
- If no one is being addressed, the protagonist is assumed to be the one the order is being given to.
- Special processing is used for debugging commands, movement commands, and anything handled by the snowflake.
- If we still haven’t figured out what the verb is by this point, which is the case most of the time, we take a look at the first (remaining) word in the command (after dropping anything before a comma, which would be the name of whomever we’re addressing). In English, conveniently, commands begin with the verb, and if the verb is only one word, that’s the verb! Yay!
- We check for uses of quotation marks, which indicate a literal string, usually for talking or writing; the game supports SPRAY “YOU SUCK” ON WALL, and SAY “HELLO” TO BARBARA. Quotation-mark handling is awkward and difficult and the parser currently only supports double quotes with no interior single quotes, and no nested quotes, and ABSOLUTELY NO FUNNY BUSINESS WITH QUOTES. If there is a quoted phrase, there need to be both opening and closing quotes. We construct a
Phrase
, an obscure descendant of Noun that contains a list of words that are treated literally by other code that knows how to handle Phrase
s. That Phrase
is the direct object.
- On the other hand, commands are sometimes made of verbs that, practically, have more than one word as part of the verb: LOOK IN as a synonym for search. Irritatingly, English, because it’s a Germanic language, doesn’t always keep the second and subsequent parts of the verb right next to the first parts. Even worse, whether a phrasal verb requires that the parts be kept together or split apart is a regional and/or age and/or class difference for many verbs: some people find TURN BLENDER OFF to be the natural formulation, whereas others prefer TURN OFF BLENDER. (Zach de la Rocha encourages you to “turn on the radio,” whereas Lisa Loeb recounts how, habitually, “I turn the radio on, I turn the radio up.”) We really want to support both. So we check to see if the first part of the verb might possibly be a phrasal verb: if the first word in the verb is LOOK, we check to see if there’s an IN or AT later in the command, and if there is, we rearrange the command so it puts the two parts of the phrasal verb together. This might produce a command that a native speaker wouldn’t think to produce naturally, be we don’t display the intermediate stages of parsing to the user anyway, so it doesn’t matter. (Side note: action-dispatch methods on
Noun
descendants use underscores to represent the spaces between words in a phrasal verb, and the parsing routines massage this as a late step, so Noun
and descendants have a .look_in()
method that’s a synonym for .search()
, and so forth.)
- Once we’ve pulled out any prepositions that are actually part of phrasal verbs, we locate all other prepositions in the parts of the command that we haven’t yet parsed. Then we break the command into the phrases in between the prepositions.
- Then, for each of those phrases in between the propositions, we track what the preposition preceding it is, and mach each noun phrase to an object in scope if possible. The noun phrase that’s not preceded by a preposition is the direct object, the other noun phrases are indirect objects, and the preposition used indicates what their role in the sentence is. So for the phrase PUT THE BIRTHDAY CAKE ON THE BED WITH THE SHOVEL, we wind up tracking that the direct object is BiRTHDAY CAKE, the verb is PUT, and the indirect objects are
{'using': shovel, 'on': bed}
. Identifying the objects in scope is handled by another helper function, get_scope()
, which is complex and not shown here.
- If any noun phrase can’t be matched to an object in scope, the whole parsing process fails and a message along the lines of YOU CAN’T SEE ANY BIRTHDAY CAKE HERE or THE TINY SHOVEL MADE OF PINK PLASTIC IS TOO SMALL TO SUPPORT THE BIRTHDAY CAKE is printed. Currently, there is no handling of partial correction of erroneous commands, which you get for free with Inform et al.; the player has to retype the whole command on the next turn. (Fixing this is going to require adding a whole other level of abstraction to the parser.)
Some subtleties have been glossed over here. One is that multiple direct (but not indirect) objects are supported provided that the word AND occurs between them. (Inform et al. supports comma-separated lists of direct objects; this parser doesn’t. Commas always always always mean someone is being given a command.) There is also some support for pronouns; this is provided by massaging during preprocessing. I also haven’t talked about disambiguation at all, which is a whole other kettle of fish.
Once the command has been broken down and all of its parts have been identified, we have a list of direct objects, a verb, and a dictionary of indirect objects. The actual work of dispatching is done by iterating over the list of direct objects, looking up the relevant method for them using getattr()
, and expanding the list of keywords into a parameter list by using double-star expansion. Doing this looks like:
for the_item in direct_objects:
getattr(the_item, the_verb)(**call_parameters)
The command PUT THE BIRTHDAY CAKE ON THE BED WITH THE SHOVEL gets translated into a direct_objects
list holding one object, the birthday cake object, presumably an instance of Food
or a subclass; the verb becomes the .put()
method of that object, and the call that’s actually made becomes [the birthday cake object].put(using=[the shovel object], on=[the bed object]), because double-star expansion translates a dictionary into keyword parameters. Then it’s the job of the Food
class’s .put()
method to handle those parameters and that object. (Or perhaps a higher-level superclass: there’s no particular reason why Food
would need to override the .put()
method from the Thing
class that I can think of offhand.)
So this works! Sort of. Mostly. For many common cases. Provided the player understands the system deeply and is cooperative and competent. It gets you handling of things things like SHOOT RICK WITH THE SHOTGUN, finding the Rick object and the shotgun object, if they’re in scope, and calling the Rick object’s .shoot()
method and passing the shotgun object to the Rick object’s .shoot()
method as a using=
parameter. Or you can type LILLIAN, PLAY PIANO and, assuming both Lillian and a piano are visible, it will invoke that piano’s .play()
method while passing the Lillian object to the method’s actor=
parameter. Or you can type MOM, SLAP ME AND RICK and, if your mother and Rick are both visible, and if the persuasion approval rules (which we haven’t discussed) succeed, she’ll go ahead and slap first you, and then Rick. Similarly, you can DRAG COUCH TO DOOR to construct a barricade, SNIFF THE PIZZA, etc. etc. etc. and, as long as a handler for the appropriate action has been written for the relevant object’s class, or for one of its superclasses, there’ll be a message printed in response. Perhaps it will be “Yup, that smells just like a pizza,” if one of the generic, default handlers way up the chain winds up getting invoked; and if I want to write a more specific response for the pizza object, I can write a custom response by defining a .smell()
method on the Pizza
class that says overrides the default to print something like “Of all of the many smells God created, surely pizza is one of the finest.” It’s easy to customize items by attaching overriding methods to the class that the object in question is a direct instance of, and it’s easy to override a message for a whole class of items by writing a method for a common superclass that prints a custom message for all descendant classes. Because Python supports multiple inheritance, it’s even easy to write mix-in classes that override certain types of behavior for certain subclasses that are not direct descendants of each other in their primary line of descent, provided you understand the complex nitty-gritty details of how inheritance works in Python. (This is another case of “I told you you’d learn a lot about Python by doing this.”) You can even monkey-patch an object to change its class in the middle of a run, if you really need to; this is very much like trying to change an oil filter while your engine is running, but it’s possible and comes in handy if, for instance, an NPC is bitten and you want them to now be a member of class ZombieHuman
instead of Cynic
. Making substitutions like that can change whole swaths of object behavior all at once: the previously human character now gets all of the default Zombie
behaviors.
The burning question then becomes “how do you enforce basic requirements for the grammar of various commands?” Because you want to both avoid nonsensical commands (EAT BIRTHDAY CAKE USING SHOTGUN) and commands that contain a verb and direct object, but not enough information to fully specify the action required (BARRICADE DOOR isn’t good enough; we need to BARRICADE DOOR WITH SOFA – remember that one of the ways in which our parser is suboptimal compared to Inform or ZIL is that it doesn’t do partial parsing at all; it just prints an error message saying what’s wrong and tells the user to try typing the necessary command again, only right this time). The underlying problem is one of interfaces to methods of objects, which specify what they need in their declarations. For instance, the declaration for Door.barricade()
looks roughly like this:
class Door(Thing):
def barricade(self, actor, using):
[...]
So if the player just types BARRICADE DOOR, the parser will happily fill in the self
parameter for the door, disambiguate if there’s more than one door in scope (“Do you mean the door to the living room or the bathroom door?”), and it will fill in the actor
parameter with the object referring to the protagonist, because it always already does that anyway; these are common enough tasks that the parser accounts for them. But it can’t fill in the using
parameter, because that’s where I’ve drawn the line: parameters other than the direct object and the actor
need to be specified manually, or the parser would balloon out of control. My personal boundary on this issue was “the direct parsing routines only supply values that must be supplied in EVERY action; it doesn’t try to figure out values for parameters that are specified in indirect objects or other less-common grammar situations.”
Your mileage may vary and your priorities may be different, of course. Perhaps you want to bloat the multi_parse()
routine to a thousand lines: it’s not an inherently evil way to approach the problem, just one that introduces new complexities of its own. For my own part, I prefer to handle the “you must supply additional parameters in your command” issue in other, smaller chunks of code outside of multi_parse()
. Because if we’re not spitting off code that validates that all necessary information has been supplied into smaller chunks of code that we can write elsewhere, we’re back to having big tables of verbs and what each verb requires: OPEN doesn’t require anything special, but BARRICADE requires a using
parameter; for UNLOCK, you can optionally specify the relevant key with using
, and …
This is all kind of ugly; worse, it’s hard to keep the tables of which verbs require which parameters in sync with the code that handles the actions themselves, and letting them get out of sync introduces crashes and other errors. There’s also the issue that the same English word can mean different things and be handled in different ways depending on context: SCREW BOLT WITH SCREWDRIVER requires a using
parameter, but the Person.screw()
method doesn’t (and just prints a rejection message. It’s not that kind of game. Not that there’s anything wrong with that). This is currently handled rather easily simply by defining the relevant action-handling methods differently on the different object classes: Bolt.screw
requires a using
parameter, Person.screw()
does not. But this would get complex if we had to draw up a grammar table for each verb: we’d have to account for different situations in that table itself. Boo! Plus, having to maintain a separate set of big tables is one of the things that we’ve successfully avoided doing so far, and it would be a shame to have to give up on that now.
So far we’ve been successful at keeping all of the information about handling actions at the level of the action-handling code itself and relying on Python’s introspection facilities to deal with the rest. (Well, ALMOST all. There’s a list of verbs that might be phrasal, and a list of verbs that aren’t allowed multiple direct objects. These are small enough lists that eliminating them would be more work than maintaining them, though.) What we really want is to keep it that way, not to throw our hands up and start writing a big set of tables that are inevitably going to get out of sync from time to time during development.
Here’s the problem more specifically: as the system has been described up to this point, if a user just types BARRICADE DOOR, the program will crash, because the .barricade()
method on the door class requires three arguments: the Door
instance (which is mapped to the self
parameter because that’s how we’ve set up our system, and because the first parameter to a method call is always the self
instance in Python); and the actor
parameter, which is supplied to every action method by the parser itself; but nothing supplies the using=
parameter to the Door
's .barricade()
method if the user doesn’t remember to add USING KITCHEN TABLE to BARRICADE DOOR, so it won’t be filled in in the keyword-arguments dictionary that gets expanded with the double-star notation in getattr(the_item, the_verb)(**call_parameters)
, and the game will crash with a message like TypeError: barricade() missing 1 required positional argument: 'using'
. I think that we can all probably agree that a game that crashes because the user was insufficiently specific in typing their command is not a very well-written game.
So the question then becomes “How do we add logic that steps in right before the method is called on the direct object and make sure that everything is specified that should be specified, before we get to the point where we actually try to call the direct object’s method and the game crashes?” This is a classic validate-the-data-before-passing-it-to-the-function problem, and Python has a really good advanced feature that can do exactly that: decorators.
Decorators are a Python feature that allow functions or class methods (classes, too, though that’s not relevant here) to have additional logic added to them without having to re-write the function or class method itself. You can use them for a lot of things, including validation, and they’re a way to separate out the validation logic from the method that’s being validated. There’s no reason why you couldn’t just put the validation logic at the top of every single method that needs to have it; but applying a decorator only takes one line of code, and, once the decorator’s been written, applying it is easier, and easier to remember to do, than inserting several lines of boilerplate code at the beginning of each method that needs to be validated. (It also makes the syntax clearer, as it turns out.) They also help to make it clear at a glance which rules apply to which object methods.
Decorators are (usually, and most naturally) applied with the @
sign, above a method. So the declaration for the .barricade()
method on the Door
object looks like this:
class Door(Thing):
[ ... more definitions applying to Door ...]
@MustSpecifyWith
def barricade(self, actor, using):
[ ... the code handling the BARRICADE command ...]
[ ... more definitions applying to Door ...]
This applies a decorator called MustSpecifyWith
to the Door
's .barricade()
method. MustSpecifyWith
is a function that runs before the .barricade()
method, calls the .barricade()
method (or any other method or function that it decorates), then continues running after the .barricade()
method is done. This means that it can intervene to manage what’s passed to the .barricade()
method; can avoid calling it entirely; can massage the results passed back from the method, if it wants to.
What the MustSpecifyWith
function does is simple: it checks to see if the using
parameter was passed in to the .barricade()
method. If it was, it goes ahead and calls the .barricade()
method. If using
wasn’t passed in, instead of calling .barricade()
with too few parameters and letting the game crash, it raises ParseError
. That ParseError
that it raises bubbles back up through the call stack, out of the decorator, out of multi_parse()
, and back to the try:
statement in the parse()
method, which called multi_parse()
, which called the Door.barricade()
method, in which the @MustSpecifyWith
decorator intervened. The try/except
prints a message that boils down to “You need to say what you want to barricade the bedroom door with,” and the handler at that level lets the outer scope – the game’s main loop – know that nothing happened this turn, and the process begins again: the user is prompted for another command, the command is broken down and parsed, and if special cases aren’t handled, the whole process of trying to match noun phrases to objects in scope, determine a verb, determine if an order is being given to an NPC, determining action parameters, and dispatching to the action-handling methods of the direct object(s) that was/were located, possibly validated by decorators, happens again.
So all the @MustSpecifyWith
decorator really does is step in right before the action-handling method is called and safely abort if everything necessary isn’t there, jumping out of the whole parsing and action-handling loop and explaining why the door didn’t get barricaded.
The MustSpecifyWith
function is written like so:
def MustSpecifyWith(func):
def when_called(*args, **kwargs):
if 'using' not in kwargs:
raise ParseError("Please try again, and specify what you want to %s with." % func.__name__)
if isinstance(kwargs['using'], nope.Nope):
raise SilentParseError(su._decode("It doesn't look like {[spec]} will help {[spec]} to {[str]}.",
kwargs['using'], kwargs['actor'], func.__name__))
return func(*args, **kwargs)
return when_called
This is a bit of a simplification to illustrate the point, and it omits some of the implementation details that help to support introspection by other code. It’s a closure-based decorator, one of the basic Python decorator patterns: when it’s executed, after the method it’s decorating has been defined, the function when_called
, defined insie the decorator itself, is substituted for the method being decorated, and the function func
is stored as the function that’s going to be called. When something tries to call the original method, it instead (unknowingly) winds up calling the when_called
function that was returned by the MustSpecifyWith
decorator. That when_called
function executes, checking that the using
parameter was included in the kwargs
argument parameters dictionary. Once it’s verified that the keyword arguments include a using
parameter, it calls the function that was stored in the func
variable when the decorator was applied. That func
variable holds a reference to the original method that was decorated, which is the .barricade()
method of the Door
class. The upshot is that:
- When the
.barricade()
method is defined, the decorator replaces it with the decorator’s own when_called()
function, and it stores a reference to the original function being replaced – the .barricade()
method of the Door
class – as the decorator’s func
attribute.
- When other code tries to call the
.barricade()
method, it instead winds up calling that when_called()
function that was substituted for it. when_called()
, when it’s called, checks that the parameters that were passed to it include a using
parameter, then it goes ahead and dispatches to the original .barricade()
method of the Door
class, which it had previously stored.
If all of this is totally new, there’s a pretty good and fairly in-depth primer on Python decorators here.
There are of course other decorators to enforce other rules, including …
-
@MustSpecifyTopic
, which is applied to the handlers for ASK and TELL to enforce the need to specify a topic of conversation;
-
@MustSpecifySource
, which is applied to verbs like FILL to enforce the FILL TANK FROM PUMP syntax;
-
@MustSpecifyDest
, which ensures that a phrase like PUT DONUT is followed by a phrase like ON TABLE,
-
@DestMustBeContainer
ensures that indirect object onto/into/under which the player is trying to place the direct object is in fact a Container
.
There’s also another decorator that’s automatically applied to almost every method of every single descendant of Noun
, a decorator called NoExtraParameters
. Predictably, this decorator simply raises a ParseError
if any parameters are passed to a function other than those that are specified in the function header.
How does that decorator get applied to several thousand methods throughout the code base automatically? That’s the role of the StandardGrammar
metaclass that was mentioned briefly in the initial discussion of the Noun
abstract class, way up above. A metaclass is an abstraction that’s responsible for controlling how classes – not objects, but classes – get created. (What a class is to objects, a metaclass is to classes. What’s an object an instance of? A class. What’s a class an instance of? A metaclass. What’s a metaclass an instance of? Also a metaclass. That’s the top of the conceptual hierarchy.) So the StandardGrammar
metaclass intervenes in the in the creation of Noun
and all of its descendant classes, automatically applying the @NoExtraParameters
decorator to most of the action-handling methods that each class defines.
StandardGrammar
looks like this:
class StandardGrammar(type):
"""A metaclass for nouns.Noun. For Noun and descendants, it decorates verb
parameters appropriately with decorators to enforce a standard grammar.
Note that this is only one of many places in the code that assumes that in-game
nouns obey the rule that any of their method whose name does not begin with an
underscore is an in-game verb performed on that object.
Adapted from Mark Lutz's *Learning Python*, p. 1402.
Standard Grammar currently means that verb methods are wrapped with ...
* @NoExtraParameters (unless the method's arguments list allow **kwargs.)
* Nothing else, for now.
"""
def __new__(meta, classname, supers, classdict):
for attr, attrval in classdict.items():
if type(attrval) is types.FunctionType and not attr.startswith('_'):
if not inspect.getfullargspec(_unwrap_function(attrval)).varkw:
classdict[attr] = NoExtraParameters(attrval)
return type.__new__(meta, classname, supers, classdict)
I’ll forego digging into the details of exactly how that works, except to say that it intercepts the type()
call that normally happens automatically when a class is being created and adds some extra logic around it to apply the decorator automatically.
So there you have it: a data ontology and a parser that understands it, interpreting commands and dispatching to action-handling methods defined on the classes to which in-game objects belong. There’s a system for dealing with more than a simple verb-noun parser, and a system for enforcing grammatical rules that apply to commands. It’s a reasonably flexible parsing system that’s tied into a world model and leverages Python’s class system to make things easy to introspect. Action-handling code is grouped together with the objects it operates on, and it’s easy to specify default behavior high up in the class tree and then override it for certain types of objects lower down. All in all, it’s a decent parser system, I think.
But – and here I’m going to beat that horse again (even though hoses are beautiful and noble creatures) – it’s still not a great parser system. It’s missing a lot, and it’s not flexible in ways that it should be. There’s no current way to get processing of ALL (as in TAKE ALL), which is something players expect to have, for instance. And it makes no attempt to store the results of partially completed parsing and ask for clarification, which gets annoying if you make many typos. Its system of having to dispatch an action to a single direct object makes it awkward to deal with multiple direct objects, and there are probably ways that this could be exploited to do things that would likely make purists cry “unfair!” in at least some circumstances. (The current system tries to avoid this by maintaining a list of verbs that aren’t allowed to be applied to multiple direct objects, in a single turn, and this is one of several ways in which verb information is stored in tables or lists instead of being grouped on an action-handling method.)
Less obviously, it brute-forces the parsing problem and isn’t flexible with the kinds of grammar it can parse. Everything it can understand is a fairly small set of variations on a single basic pattern. It can’t deal with alternative basic sentence constructions at all; it doesn’t try to match objects to descriptions based on a set of flexible grammar-declaration string patterns as in, say, BNF; it just has a hardcoded notion of where in the sentence various things will happen to fall, based on a set of rough heuristics hard-coding informal knowledge about how certain things in English tend to work. If that basic pattern fials, it doesn’t have any way of trying alternative “readings” of the command to try to extract sense (and the thing that’s most likely to trip it up is misreading a preposition as part of a phrasal verb, which there’s currently no way to correct for without re-engineering the whole system).
This also means it’s useless for parsing languages other than English, if that ever becomes something the game or its underlying engine wants to do.
More abstractly, there’s no good way to override processing in particular circumstances without ripping into the whole parser engine to account for the exception. If I wanted to add a magic ring that makes it possible to pass through locked doors, I’d have to modify several parts of the code base to check whether the player is wearing the magic ring; in Inform, I could simply declare something along the lines of The can't pass through locked doors rule does nothing when the player wears the glowing ring.
How much all of that matters depends on how restrictive it is for the story you want to write. The system I’ve written is mostly adequate for a story that revolves around objects. It’s less satisfying for a story that turns on relationships and conversation, or that otherwise needs to work at more abstract levels. And it’s always going to be more work – substantially more work – to write a piece of parser IF in Python under this system than in a domain-specific language like ZIL or Dialog or TADS. The end result is almost certainly going to be more polished, too, though how much more polished depends on how much work I want to put into polishing it.