How to program a text adventure in C

by Ruud Helderman <r.helderman@hccnet.nl>

Licensed under MIT License

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; remember, it’s only a game. But the parser should enable the player to express his intentions in a more or less natural way.

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

Alright, plus the sequence of strcmp calls to map verbs to commands, and the functions in noun.c to map nouns to objects. But that’s it. This system has served us well for the past 11 chapters, but it has its 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 of patterns from top to bottom, trying to match the user’s input with each pattern in turn. We will stop at the first match found. For the sake of simplicity, 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 tag (of any object). Matching is greedy; when the parser has a choice between two different tags (for example ‘silver coin’ and ‘silver’), the longer tag will take precedence.

The matching tag can then be passed as parameter noun to one of the execute functions. For commands with more than one noun (introduced in the next chapter), parameter passing becomes a bit unpractical. For simplicity, I will use a global variable instead of parameters (despite the bad reputation of global variables). The variable will be an array of string pointers.

The array has 26 elements; one for each (uppercase) letter in the alphabet. That is sufficient for upto 26 different nonterminals in a single pattern. For every nonterminal in a (matching) pattern, a matching tag will be ‘captured’ by filling the nonterminal’s array element with a pointer to that particular tag. params[0] (the first array element) captures nonterminal ‘A’, params[1] captures ‘B’, and so forth. A simple macro can be used to find the array element that belongs to a given nonterminal.

Note: you may find the array length of 26 a bit over the top, but it does save me the trouble of writing some bounds checking code to prevent a buffer overflow in case of a malformed pattern.

Now we have to think of a way to handle missing or unrecognized nouns. Suppose the user makes a typo and enters “go kave”. Question is, should this command match the pattern “go A” or not? If we don’t, then the command will fail to match any pattern and end up in a generic error handler, which will probably reply with something like “I don’t know how to go kave”. This takes away every opportunity to improve these ‘negative responses’; a reply “I don’t understand where you want to go” already feels a lot more natural. It would be best to maintain all replies concerning command go inside function executeGo.

There are a few ways to achieve this, but the easiest one is to allow nonterminals to match anything; so not just a valid tag, but also total gibberish, blanks or just nothing. This ‘invalid’ input will be captured as an empty string (“”).

Having such a ‘loose’ nonterminal in the middle of a pattern does complicate the pattern matching process; it would require backtracking to properly align the word ‘in’ when matching input “put foo in in box” with pattern “put A in B”.

To keep things simple, we will only enable this loose matching for nonterminals that occur at the very end of a pattern. To be able to properly match the example above, we need two separate patterns:

• Pattern “put A in B” will match the valid command put coin in box, as well as the invalid commands put coin in booox and put coin in. Note that the nonterminal A only matches valid tags (in this case coin).
• Pattern “put A” matches all remaining invalid commands: put coin, put koin, put koin in box, put koin in booox and a bare put. And also the initial example (put foo in in box).

The order of the patterns is vital here: if “put A” would be on top (meaning it will be tried first), then it would consume every put command; a valid “put coin in box” would be considered invalid because there is no tag “coin in box.”

The same goes for commands that appear in multiple forms, such as look.

• “look around”
• “look” (as an abbreviation of look around)
• “look A”

The first two patterns can be in any order, but the third one must come last.

Time to put this into action. We will discard the existing contents of module parsexec.c, and replace it by a new implementation of function parseAndExecute using a list of patterns that should be able to match every command we have implemented so far. Each pattern is tied to a function that executes the appropriate command.

The hardest part is the implementation of function matchCommand. But as you can see below, that too can be done in less than 100 lines of code.

We adjust the implementations of the various commands to make use of the new array params.

Same thing for the module we added in the previous chapter.

In location.c, the command look around is given its own function, separate from the look command to inspect specific objects (see lines 7-12).

Our game still accepts simple verb-noun commands only, but the new parser does have the potential to accept commands with more than one noun like ‘put coin in box’; this will be demonstrated in the next chapter.

The new parser is a huge improvement over the original one, but by today’s standards, it is still far from perfect. For example, there is no structural way to manipulate multiple objects with a single command (‘get coin, key and lamp’) or execute two or more commands in a row (‘get key then go east’).

In the true sense of the word, my parser is not even a parser. It is just a simple pattern matcher. IMHO, it does its job sufficiently well for a simple adventure game. Some of its flaws can be mitigated by adding more patterns. But eventually, you will run into its limitations, and you may want to move on to something more mature. In that case, I would recommend a decent parser generator (e.g. Yacc). Please be aware that this is not an easy thing to do. For now, this is outside the scope of this tutorial.

Next chapter: 14. Multiple nouns