making a dynamic parser

Continuing a discussion from here.

Inform 7 allows a game to understand things by properties–you can say that a block can have a color (red, green, or blue), say “Understand the color property as describing a block” and then the game will understand “RED BLOCK” as a red block if and only if the color of the block is red–so when the color changes the way it can be understood changes.

But what about dynamically generated descriptions that go beyond colors? My “game” Garbage Collection generates a series of random descriptions of garbage:

Not every word generated here is a property of the piece of garbage in a straightforward way (source code is here) and in any case it might be nice to just have the parser automatically understand the string generated for the piece of garbage as referring to it. So if these five pieces of garbage were generated, it would understand the difference between “x purple film” and “x cracked metal” and “x smooth metal” etc.

This might, for instance, help us simulate a gigantic heap of garbage with only a few objects–have a few objects representing pieces of object defined in the code, and assign them new descriptions as new pieces of garbage are drawn from the pile while old ones are returned to it.

The virtual machines that Inform compiles to don’t do this easily (as far as I know)–they rely on dictionary words that are generated at compile time, which are assigned to objects… well, somehow (won’t pretend I understand the parser)… there’s a sort of pre-parser or something that resolves a command into dictionary words and non-dictionary text, and as the parser processes dictionary words it looks around to see what objects the words might match.

How might we make a system that’s more friendly to dynamic parsing in this way? Well, it seems to me that one way might be to flip the order. Instead of having the parser understand words and find objects to match them, have the underlying machine assign words to objects. Then a pre-parser could figure out what objects are available for reference at any given time, and what words refer to them, and the parser could check if the words in the command match the words that refer to the available objects.

That would make it easier to the sort of generation I described–just change the list of words associated with an object. It could even happen with words that themselves were generated, so you could generate random names like “huwikaz” and “zucimut” and assign them to objects.

I mentioned some of these ideas here, but the context was “How can I actually do this?” rather than “How can I describe a system I’d like someone else to write?” :wink:

The VM’s dictionary is really just a way of giving each input word a canonical integer. For the Z-Machine it’s part of the VM’s design, which means it has more limitations, namely that it needs to be sorted. Possibly in Glulx it would be possible to have a dynamically growing dictionary so that you could add randomly generated or user entered words at run time. Or another possibility would be to make it hash the words it can’t find in the dictionary between the tokenising and parsing stage. The same hashed value could be added to the object tree.

It’s definitely possible in theory to do a lot more. It just depends on what exactly needs to be supported, and then how that should be programmed most simply and/or efficiently.

Also, the dictionary is just an optimization to do string comparisons (in Glulx using a binary search of fixed-length values) against a list of pre-sorted words. The parser could use string arrays directly, comparing words the user typed against property values of in-scope objects, character-by-character.

The Z-Machine has a built-in @tokenise opcode, but if you look at the parser Tokenise__ function for Glulx (I’m only familiar with the I6 version) you’ll see how it does the word-splitting and dictionary lookup much as in any other language.

The pname.h extension shows how one could override the default parser behavior (looking at the standard name property) to provide alternate object resolution.

“How can I describe a system I’d like someone else to write?”

Heh heh, now that’s the hard part!

~Jesse

Regardless of any specific authoring system, here are my thoughts on dynamic parsing.

I see two things in dynamic parsing:

  1. creating dynamic object descriptions, like in matt w’s opening post;
  2. mapping user input text to objects and actions dynamically.

There are several definitions of parser or interpreter. When I started building mine, I used the following definitions:

Parser: translates a string of characters entered by the user to objects and actions that exist in the game. E.g. the char string “ancient sword” is translated or mapped to object 4567.
Interpreter: interprets the parser’s output: the interpreter knows how to perform the actions on the objects by changing states, printing text, etc.

I’m not saying these definitions are correct, but this is where I’m coming from.

Normal (static) parsing:
Each object has one or more textual descriptions. The parser maps the user input by only looking at these textual descriptions, or at least a part of it.

Examples: “sword” maps to “ancient sword” and to “elvish sword” “ancient” maps to “ancient sword” and to “ancient map” “ancient map” maps to “ancient map”’ but not to “ancient sword”
With static parsing, you can run into ambiguities when objects have identical words in their static descriptions and the user input doesn’t make it clear (like with the 2nd example above).

Dynamic parsing:
I think dynamic parsing can help in resolving ambiguities (mapping user text to the right object/action) without having to ask the user what he means.

Some thoughts on how to do this:

look at attributes/properties, like the red block example in the opening post. If the block can change color, the color cannot be in the static description. We should learn the parser to take properties into account when it cannot uniquely map the user input to 1 object. There’s some things to think about, like should it only try to map adjectives to properties or also nouns/prepositions etc. Should it only consider properties when static parsing doesn’t yield a unique match? Etc

look at the action involved. For example, if “take box” maps to more than 1 box, try to limit the search space to only boxes that are not already held by the player. Similar situations are for drop, open, lock etc. I actually implemented this in my parser and it works pretty well.

look at relations between objects. Let’s take the “contains” relation: an object can contain or be contained in another object. The containment can be “in”’, “on”, ‘under”, etc etc.
Now, if the user would enter “examine the box on the table” it would be nice if the parser could deduce something like: there are red box and blue box objects, there is a table object, the red box has a contained relation with the table described as “on”, so the user wants to examine the red box.

But… looking at relations introduces new possible ambiguities. Consider the following

[code]You see an old man, a young man and a grey stone here. The old man picks up the grey stone.

hit man with stone[/code]
Depending on the parser’s mapping, the interpreter can have several outcomes:

[code]

hit man with stone

You make a fist and hit the old man right on his nose! The young man runs off.[/code]
Or

[code]> hit man with stone

Which man do you mean? The old man or the young man?

young

you take the grey stone from the old man and hit the young man with it.[/code]

Both responses are valid. There is IMO no way the parser can predict what the user means here, so it needs a priority order in how to try to map things.

Something like:
First try static mapping
Then consider the action involved
Then take into account the properties/attributes
Then try the relations
If that still doesn’t give a unique mapping, ask the user.

Just my thoughts, hope this contributes.

What you’re referring to here is non context free parsing as opposed to context free parsing whereby the meaning is independent of the situation. I was assuming that by “dynamic” parsing, we mean the ability to change the grammar rules at runtime, or at at least perform some kind of dictionary reassignment.

Dynamically creating objects is, i think, yet another problem. Referring to “matt w”'s “garbage” problem, this reminds me of what i call the “sandy beach” problem;

You’re on a beautiful sandy beach stretching far both to the east and west. On the beach, the sand is almost pure white and behind, a few palm trees wave softly in the breeze.

> put sand in bucket with spade

You can already see the problem; next thing, the whole game is filled with “some sand here” after i take the bucket and empty it in every game location and into every container!

Just make the sand a scenery item! Good idea, but what if the story requires me to dig at a specific beach location to find some mystery buried item. No doubt i can manipulate the sand then?

So this problem, ie how to deal with the fact that you can keep getting “some sand” or “some gravel” or “some water” etc. is similar to Matt’s garbage problem, except here, the object is the same and does not require a property change (which is a separate problem).

Oh, then there’s this; “Which sand, the sand or the sand?”

Because they are all the same.

Now some systems support this by allowing objects to be in multiple places at once. This can work providing you are not able to change the property of the item. For example, if the sand can be either wet or dry, then having the same “sand” in multiple locations fails to distinguish the dryness.

Another idea is to have a predefined “pool” of sand objects (eg 3 instances) and find a convenient excuse to prevent the player from taking more than the pool. This can work but leads to the “which sand?” problem.

The most common solution is to create a plot device to prevent the player from removing any sand from the beach. Let the player get the sand and drop the sand, but only when at the beach locations which are all (conveniently) adjacent. If you get some sand in the bucket and try to get more, it can say, “but you’ve already got some sand”, or something like that. Whenever you drop some sand, there’s a hook that resets the beach sand state.

So this is similar to Matt’s garbage problem because it asks for the dynamic proliferation of objects; a bit like generating a new object from the “garbage” heap. It is different because the garbage problem generates random unique objects; from which you can still fill up the game with junk should you be so inclined. Additionally, the generator would have to be careful not to repeat itself otherwise you might get the “which old rag, the old rag or the old rag?” problem.

So moving away from the “sandy beach” problem, there’s the problem of whether systems can support the dynamic creation of objects - even if there’s only one such object. Naturally, if there’s a fixed amount of such objects (eg 1), perhaps there could be some mechanism to have a pre-allocated “blank” object, which at runtime could be assigned a description and properties, including parser “noun” and “adjective”.

First consequence; saved games!

Dynamically created or modified objects would have to go into the saved game. This would include any new words added to the dictionary etc. If objects were truly dynamic, ie not re-assigned “blank” ones, the save game (and object tables) would increase in size and may eventually (or even soon) exceed limits. So there’d have to be non-story related checks for this.

Earlier on, i talked about changing the grammar rules at runtime. Why would you want to do this? Actually you don’t within any given game, but is common to require new grammatical forms for different styles of game. Pirate slang anyone?

Two pirates aboard ship:
Mate: “There be ships on the horizon, captn’!”
Captain: “arrrrre!”

Changing grammar rules isn’t the re-assignment of adjectives or being context sensitive, these are all part of a given grammar set. New grammars are often required for new games and not within a game. consider;

"put sand in bucket with spade" "get sand with bucket" "get sand with bucket and spade" "fill bucket with sand using spade" "use spade to get sand" "use spade to put sand in bucket" "use spade to fill bucket with sand" "dig sand with spade and put it in the bucket" "dig up sand with bucket and spade" "shovel sand into bucket with spade"

There are many more and these are mostly all slightly different grammatical constructions.

Changing adjectives is a dictionary update problem constrained by making sure you do not accidentally create identical (ie indistinguishable) objects.

Being context sensitive is part of clause resolution with regard to the world state. This is mostly performed eagerly within the parser, but can lead to problems;

[code]> put some sand in the bucket"
OK

put some sand in the bucket"
into what?[/code]

I can think of an example where a modifiable parser in-game would be desirable:

You are tasked with building a translator to talk to Yoda and have to assemble electronic components that are essentially parts of speech. Later, you have to reassemble the pieces in a different order to talk to a different alien. You want the game to allow the player to assemble the pieces in any order and produce bad output if they fail in the task.

https://www.theatlantic.com/entertainment/archive/2015/12/hmmmmm/420798/

I’m totally loving all the examples people are giving. Keep them coming.

1 Like

This is not a serious difficulty for the kind of dynamic parsing you’re talking about. It’s true that dictionary words have to be known at compile time, but if you’re setting up a space of objects, you’re defining lists of dictionary words.

Words are normally assigned to objects at compile time, but these mappings can be made or changed at runtime. Admittedly this is easier in I6 than in I7, which has a slightly overbearing approach to object naming.

Prepositional phrases are the interesting next step, but a tricky one, for the reasons people have already outlined. I think a reasonable parser would have to accumulate a list of parsings (“hit (man with stone)”, “hit (man) with (stone)”) and then apply weightings according to a bunch of heuristics – including recent history and game salience. (Is this a game about hitting people, do people commonly carry stones, etc.)

This is unfortunately where Z-code and Glulx add a lot of friction. (As opposed to the dict word handling, which is straightforward.) You want to represent these possible parsings with bags of complex data structures. This is trivial in Perl or Python – and I assume it’s trivial in TADS3 also – but the Inform VMs weren’t built for that sort of work and it’s clunky.

Well, besides the huwikaz/zucimut issue where the words are themselves generated (that’s from something where I wrote a simplistic name generator that randomly alternates consonants and verbs), this would in theory require figuring out every word I wrote in quoted text strings that could possibly apply to an object and seeding the dictionary with it, wouldn’t it? Including if I have a verb “stain” I’d have to add “stain” and “stained” to the dictionary?

I guess this wouldn’t necessarily be a VM issue, because you could have something that compiled to the VM that generated these things as dict words… but it seems like it’d be clunky to do with existing tools.

The main reason I’d be interested in the dict words is that I’m told that doing string comparisons on the player’s command is computationally expensive. If I try to whip up an example sometime I probably just won’t worry about computational expense.

What kind of contextual clause resolution does I6/7 have out of the box. For example, if i say;

> put key in bag on table

Does it correctly resolve,

1 put (key in bag) on table
2 put key in (bag on table)

Where in (1) the key is in the bag and (2) where the bag is on the table. The hit man with stone is similar to this.

More complex resolutions, might need story hooks,

> ask the butler about the man

Assuming the butler is male and only one other “man” were, so far, encountered by the player, this could resolve to a specific “man”, otherwise it would need qualification, eg “old man” etc.

Ask abouts are tricky because the object asked about does not have to be local, consequently it’s difficult to prompt resolution without accidental spoilers;

“which man the delivery man or the old man?” (bad idea!)

Suppose, as yet, you’d seen no “old man”. Additionally, suppose you had seen the old man but some time ago and the “delivery man” was just mentioned by the game;

eg.

> ask butler about cheese
The butler says, it's very cheesy.

At that moment, a van pulls up outside, stops and out steps a delivery man who proceeds to drop off a parcel near the door. He then gets back in the van and immediately drives off.

> ask butler about the man
"which man?"

This particular one is easy in Inform 7. The Epistemology extension is something that marks a thing as known when it’s seen. You can make your conversation action apply only to known things, and then only unknown things will show up in the disambiguation:

[code]Include Epistemology by Eric Eve.

Quizzing it about is an action applying to one thing and one visible thing. Understand “ask [someone] about [any known thing]” as quizzing it about.

Report quizzing: say “[The noun] does not know about [the second noun].”

Lab is a room. Gold Room is south of Lab. Silver room is south of Gold Room. Bronze room is south of Silver room.

A gold coin is in Gold Room. A silver coin is in Silver room. A bronze coin is in bronze room.

Marvin is a person in Lab.[/code]

That’s really neat!

Presumably you can’t ask about something you haven’t seen even if you fully specify it, eg “ask marvin about the gold coin” before seeing it.

Sometimes you might want the latter to work (eg for replays), but if it doesn’t do that, that’s also fair enough.

Yep, this applies even to fully specified nouns.

To be clear there isn’t anything special about something’s having been seen here; the extension just sets the “known” property when you see something (I think it gets set the first time the name is printed, and then the “[any known thing]” token means that only things with the “known” property can be understood in that spot. (“Any” means that it totally ignores scope, so the things don’t have to be currently visible.) I think what the parser does is loop over possible matches–so the known things–and check word by by word whether the words used do match those things.

Getting something where disambiguation only listed known things but you could fully specify an unknown thing seems like it’d be pretty challenging in Inform.

None at all, out of the box. It doesn’t understand modifiers to nouns like that at all. You can add them, but it’s not particularly smart about them.

I was curious, so I added parsing of “on [supporter]” and “in [container]” and tried this out, with a box on the table and a key in the box.

So it didn’t get the ambiguity right. It considered only the cases “put (key) in (box on table)” and “put (key in (box on table))”, decided the first was unlikely because the key was already in the box, chose the second, realized it didn’t have a second noun specified, and grabbed one effectively at random.

I’m not sure why it didn’t consider “put (key in box) on table”, which would have been the best option. But I assume it has to do with the internal workings of the parser.

It shouldn’t, in theory, be too difficult to replace the Glulx parser in toto and build a new one from the ground up (using Earley, for instance). In practice, all sorts of things might break, and I’m not comfortable enough with the internals of the library to try this.

What “understand” lines did you write exactly? Shouldn’t relations be used instead?

Understand "in [something related by reversed containment]" as a thing. Understand "on [something related by reversed support]" as a thing.
Maybe Inform would parse better like that (especially if there are multiple identical things, not all inside a container), but I haven’t tested.

Ah, yep, that’s basically what I did (though I used “containment” rather than “support” for “on”, since they’re the same under the hood).

The Lab is a room. There is a table in the Lab. There is a rock on the table. There is a box on the table. There is a key in the box. There is a bag on the table. The bag is a container.

Understand "on [something related by reversed containment]" as a thing. Understand "in [something related by reversed containment]" as a thing.

It looks to me as though this fails even on a less complicated construction:

I’d guess that when the parser is trying to parse “key” as a noun, it focuses exclusively on the noun place and does it greedily. That is, when it’s trying to match “key” to the [something] spot in the grammar line, it processes every word that could possibly match the key without considering that it ought to be saving “in” to match the preposition in the grammar line, if possible. Then it’s matched the key and used all the words, and it acts as though the command was “put key,” and then goes and auto-chooses an object to put the key in, preferring the only thing that’s directly in the room.

By the way, if you put another thing at the same level, you get a disambiguation loop. The parser asks “What do you want to put the key in,” and if you answer “box,” it decides that the new command is “put key in box in box,” which is just three ways of referring to the key (“key,” “in box,” “in box” again), so it asks again, and the new answer tacks on another “in box,” ad infinitum.

…so, minimal test case:

[code]The Lab is a room. There is a box in the Lab. There is a key in the box. There is a rock in the Lab.

Understand “in [something related by reversed containment]” as a thing.[/code]

With stuff like PUT KEY IN BAG ON TABLE that’s tricky for the parser, but that’s tricky for the brain to parse as well. It’s an “eats shoots and leaves” type strange-loop meta phrasing.

One helpful thing is to ensure every specific thing has a unique adjective. I know that sounds pedantic but what I’m suggesting is an author can teach the player they don’t need to come up with input that requires a descriptive infinitive such as “on the table”. It’s PUT KEY IN BLUE CLOTH BAG. [the bag which happens to be supported by the table but it doesn’t matter]. If there are several bags and several supporters they could be resting on, you’d only run into problems if you’re making lots of automatic kinds-of-kinds that don’t get hand-named uniquely. I struggled with similar disambiguation extensively implementing kinds of working light switches in Transparent

Yeah, in natural language you’d say “put the key that’s in the bag on the table” or “put the key in the bag that’s on the table.”

This reminds me of the old chestnut “The horse raced past the barn fell”; it’s supposed to be a grammatical sentence that’s impossible to parse, meaning “the horse that was raced past the barn fell,” but I don’t think it’s grammatical; you can’t use “the horse raced past the barn” as a noun phrase in other contexts either. For instance, you can’t say “I’m going to ride the horse raced past the barn.” (Other similar phrases can be used that way–you can say “Follow the man dressed in black!” but you can also say “The man dressed in black fell” and be understood more easily.) OK that’s a pet peeve of mine that is not really related to IF.

You could solve the original issue by changing the understand statement to “that’s in…” or “that is in…”, but then you’d have to communicate that to the player.

Also I think most of this discussion is pretty theoretical–I can’t think of too many cases where it’s really important to let the player distinguish the key in the box from the key on the table, as such. But it’s of interest to parser nerds!

1 Like

The case that led me to implement “in [container]” and “on [supporter]” in Scroll Thief was actually originally intended for rooms! When the player can see multiple rooms at once, players would try to disambiguate with “examine the door in the living room” or “examine the door in the kitchen”. Unfortunately, this turns out to be a fundamental limitation of Inform 7: you can never understand a thing by the room it’s currently in.

Yeah, I encountered that when I was trying to do something for the poster with the striped cat–turned out that you can’t understand by relations that aren’t related to things.

I guess in this case you could make dummy things offstage with the same name as the room, define a relation that relates a thing to the associated dummy thing of its room, and understand by that. Overly elaborate though.