How to program a text adventure in C

13. The parser

Every text adventure has a parser. But there are parsers and parsers. A simple ‘verb-noun’ parser (like the one we have been using ever since chapter 2) could be sufficient for a carefully designed adventure game. However, Infocom has proven that a more advanced parser really helps to make an enjoyable game. It does not have to pass the Turing test; but it should enable the player to express his intentions in a more or less natural way.

Our parser mainly consists of two lines of code, tucked away in main.c:

Alright, plus the sequence of strcmp calls to match verbs to commands, and a few functions in misc.c to translate nouns to objects (parseObject, nounIsInTags). But that's it. This system has served us well for the past 10 chapters, but it has some major flaws.

• It only accepts simple commands of the form ‘verb noun’; it does not understand sentences with both a direct object and an indirect object, like put coin in box.
• It does accept multi-word objects (like silver coin), but the whitespace between the words must be spot-on. Our game rejects a double space between silver and coin.
• It is case-sensitive; the command “Go north” is not recognized because of the capital ‘G’.

Writing a good parser is no trivial task, but here I will give you a relatively simple approach. We will define a grammar that consists of a list of patterns, similar to (but much simpler than) regular expressions. Examples of patterns:

To parse the user's input, we will traverse the list from top to bottom, trying to match the user's input with each pattern in turn. We will stop at the first match found. We will not make use of backtracking, though this could be added later.

Uppercase letters are the nonterminal symbols in our grammar; they match any object's tag, and they capture the properties of the associated object. For each nonterminal, the properties are stored in a struct:

A brief explanation of the struct's members:

• tag: the tag to match the player's input
• object: the closest matching object (shortest distance to the player); if more than one object qualifies, one is picked arbitrarily (typically the first one in the array of objects)
• distance: the ‘distance’ between object and player; see chapter 7 for a detailed explanation
• count: the number of objects that qualify as ‘closest match’ (typically 1, but could be more)

This struct could then be passed as a parameter to the function that takes care of execution of the command.

For simplicity, I will use a global variable instead of parameters (despite the bad reputation of global variables). The global variable will be an array of aforementioned struct.

params[0] (the first array element) captures nonterminal ‘A’, params[1] captures ‘B’, and so forth. The total number of elements in the array does not really matter. 26 is sufficient when every uppercase letter qualifies as a nonterminal. In practice, the upper bound can be a lot smaller, but please do some bounds checking to prevent a buffer overrun in case of a malformed pattern.

Now we have to think of a way to handle missing or unrecognized objects. For example, if the user enters “go kave”, none of the patterns will match (not even “go A” because “kave” is not a known tag), and a generic error message (“I don't know how to go kave”) would be returned. This takes away every opportunity to improve these ‘negative responses.’ It would be better to maintain all replies concerning command go inside function executeGo. There are a few ways to achieve this, but the easiest one is to introduce special nonterminals “A?”, “B?” etc. that match anything (including total gibberish). Capturing will be as follows.

• tag: the remaining input stream (in the example: “kave”)
• object: NULL
• distance: distUnknownObject, or distNoObjectSpecified if the end of the input stream has already been reached
• count: 0

In practice, we will use these ‘loose’ nonterminals only at the very end of a pattern. Examples:

• Pattern “go A?” will match not only go cave (capturing location ‘cave’), but go kave as well.
• Pattern “put A in B?” matches put coin in box and put coin in boox, but not put koin in box.
• To handle put koin in box, we need an additional pattern “put A?”; A? will capture koin in box as being an unknown item, and the response would be something like “I don't understand what you want to put.” Of course, the same pattern will also catch a command like put coin (which should yield “I don't understand where to put it”).

You saw us create two patterns for command put. This applies to every command that requires two or more parameters. With n parameters, you need n patterns to handle all possible mismatches. An example with three parameters:

1. “paint A on B with C?”
2. “paint A on B?”
3. “paint A?”

The following module contains a list of patterns that should be able to match every command we have implemented so far (plus a few extras such as look at and go to to demonstrate the correct order of patterns). Each pattern is tied to a function that executes the appropriate command.

TODO: also 'get A from B' and 'put A in B' and 'give A to B' and 'ask B for A'

The hardest part is the implementation of function matchCommand.

Now we can remove the original implementation of function parseAndExecute from main.c:

The amount of code in misc.c can be reduced as well, since the new parser makes functions parseObject and nounIsInTags obsolete. This is what is left.

We still need to make some minor adjustments to the existing command-implementing functions. We immediately grab the opportunity to make a check on ambiguous nouns.

TODO: location.*

TODO: inventory.*

TODO: still no 'drop all', 'drop coin and key', 'get key and go east'; yacc might be better

Next chapter: 14. Light and dark