Sunday, September 20, 2015

Parsing in ZILF, part 1: The ideal sentence

This is the first in a series of posts describing ZILF's parser. Read part 2 here.

Writing one's own interactive fiction language is a popular pastime, but people who attempt it quickly find that the language itself is the easy part. The hard part is fleshing out the parser and world model to the standards that players have come to expect.

We've come a long way since Colossal Cave and its two-word sentences ("get lamp", "throw axe"). Most modern games understand things like:
  • Prepositions (the "up" in "pick up lamp")
  • Different actions for the same verb word ("look at" vs. "look in" vs. "look under")
  • Commands with two or more noun phrases ("put coin in slot")
  • Complex noun phrases ("take key, lamp, and all cubes except the red cube")
  • Multiple commands per line ("north. west. open door then go in.")
  • Ordering ("watson, take the prints to the crime lab")
  • Disambiguation ("take polish" => "Which do you mean, the shoe polish or the Polish sausage?")
  • Implied nouns ("take" by itself when there's only one thing to pick up)
  • Correcting mistakes ("oops") and repeating commands ("again")
In fact, even in the 80s, Infocom's games understood those, so ZILF really should as well.

In this series, I'll explain how ZILF deals with all of the above, but for now let's look at a simple command like "pick up lamp". Here's the source code that defines the syntax for that command:
<SYNTAX PICK UP OBJECT (FIND TAKEBIT) (MANY ON-GROUND IN-ROOM) = V-TAKE>
Look at the parts in turn:
  • PICK: The verb word. For this syntax to take effect, the verb in the player's command has to be "pick" (or one of its synonyms, if it had any). The compiler assigns a new verb number to "pick", which is given the constant name ACT?PICK; this would also become the verb number of any synonyms.
  • UP: A preposition. The compiler assigns a preposition number to "up", the constant PR?UP.
  • OBJECT: Shows how many objects the command wants. OBJECT can appear zero, one, or two times in the syntax line; since it appears once here, this is a one-object command.
  • (FIND TAKEBIT): The "find flag", hinting at what kind of objects the command prefers.
  • (MANY ON-GROUND IN-ROOM): The "search options", hinting at where and how the command prefers to find its objects.
  • V-TAKE: The name of the action routine, which contains the code that implements taking. The compiler assigns an action number based (mostly) on the name of the action routine, in this case the constant V?TAKE; the action number identifies what the player wants to do. There might be many different syntaxes — "get lamp", "take lamp" — that all use different verbs to represent the same action. (And yes, unfortunately, V for action numbers and ACT for verb numbers is the opposite of what you'd expect.)
Notice that nothing in that line says exactly which words have to appear in which order, and in fact the parser will accept "lamp pick up"! Unlike Inform, ZILF doesn't define a precise grammar for each command; it has a general idea of what makes a sentence, and it uses its rudimentary knowledge of English to extract the parts of a command and fit them into a pattern.

So, what makes a sentence? A verb, a preposition, a noun phrase, another preposition, and another noun phrase. Everything except the verb is optional, but there are a few rules: you can't have a second noun phrase without a first noun phrase, each preposition needs a corresponding noun phrase, and two or more prepositions in a row collapse into one (so "look up in air" becomes "look up air").

The parser looks for a verb, extracts the prepositions and noun phrases from the player's command to fit them into the ideal sentence pattern, then searches through all the syntax lines for that verb, hoping to find one that has the same prepositions and number of noun phrases that the player typed. If it finds one, it can move on to identifying which "lamp" the player is talking about.

If that doesn't work, the parser may still be able to find a syntax line that can be made to work with more information, in which case it'll ask a clarifying question ("What do you want to pick up?") and orphan the command, keeping it around just long enough to see if the next input gives more information. Or it may decide that none of the syntaxes can possibly match and issue an error.

[Update: Corrected the name of the preposition number constant.]

4 comments:

  1. I've seen some parsers that define verb+preposition as just a verb (for example 'pick up' and 'pick' would have two verb definitions). Did you weigh the pro/cons of that at some point?

    ReplyDelete
    Replies
    1. Not really - that part of the design was constrained for compatibility reasons.

      Specifically, ZILF generates several parser tables in the same format that Infocom games used, including the action syntaxes. which are accessed through a master table indexed by verb number.

      Delete
    2. Strictly from a grammar point of view, "pick up" is what is known as a phrasal verb. Prepositions relate nouns to each other. So, "up" isn't functioning as a noun in this example because there is only one noun; it is part of the verb. See https://en.oxforddictionaries.com/grammar/phrasal-verbs for more information.

      Delete