MudBytes
» MUDBytes Community » Coding Discussions » Coding and Design » Parser and Object Binder Desi...
Pages: << prev 1, 2 next >>
Parser and Object Binder Design Questions
Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
* #1 id:29571 Posted Jul 23, 2009, 12:03 pm

I've been toying around with my own codebase for a while now, just trying various things and getting a feel for the scope of the problem.  I'm finally getting around to trying to improve the parser to something that is more flexible, and seem to be running around in circles.  Let me describe what I was doing, and what I'm trying to do, and see if anyone has past experience that they're willing to share that might help nudge me along in the right direction.

Right now, the parser uses a very basic expression-based command table and substring-based object binder that works something like this:

  • Use first word of input string to locate command in the dictionary

  • Split remaining input string based on the command's defined pattern (i.e., "take * from *")

  • Split each part of the resulting strings into tokens around whitespace. (so "take blue rock from chest" becomes "blue rock","chest", which becomes ["blue","rock"]["chest"])

  • Search the environment for items whose name fields contain all of the words in a group.  Example: The previous input line might match the "blue shiny rock" and the "blue rock statue" inside the "forgotten pirate's chest"



Obviously, that was a quick and dirty hack for getting something I could play around with.  Now that I've come back to the parser, I've been exploring some more complex parsing options.  I'd like to end up with a parser that can successfully bind expressions like:
"hit the king with the third rock"
"take five monkies from the cage"
"put the sword of ice into my backpack"
"dance with the monkey from madagascar"

I've gotten very close by using a vocabulary that auto-generates from my entities' name and adjective fields to parse the input lines into a tree structure that holds information about the part of speech that each token in the input stream maps to.  My problem is that I keep running down rabbit holes when I try and resolve ambiguity introduced by allowing prepositions to modify the nouns as well as the verbs.  "the king with a beard", for example, causes massive issues with a command like "hit <living> with <weapon>".  If the player types "hit the king with a beard with my sword", should we hit "the king" with "a beard with my sword", or should we hit "the king with a beard" with "my sword"?

So, finally to my question:  Has anyone here played with NLP-style parsers in their own work, and if so, where do you draw the line on the breadth of the grammar that's accepted by your parser?  Should I discard the idea of allowing arbitrary prepositional phrases in the input, and restrict the grammar to only allowing prepositions to be part of a command definition, or is there a middle ground that is generally accepted?  Or am I completely missing the boat somewhere along the line and just don't see it?

Any ideas or commentary would be appreciated.  Thanks!

(EDIT: Added example of why "king with a beard" poses a parsing problem for me.)

Last edited Jul 23, 2009, 12:06 pm by Kintar
Idealiad
Wizard




Group: Members
Posts: 903
Joined: Jan 28, 2007

Go to the bottom of the page Go to the top of the page
#2 id:29577 Posted Jul 23, 2009, 5:37 pm

I don't have great experience writing parsers, but I'm just curious if in your system you use disambiguation questions to the player so that they can refine their input, or if you're shooting for everything to be resolved by the parser?

My only suggestion is to look at the parsers for IF languages, such as Inform and Tads 3. They by far have the most sophisticated parser implementations for NLP in games. For muds though, I would suggest looking at the original MUD (or it might be MUD2, whichever is more developed).

David Haley
Wizard






Group: Members
Posts: 7,841
Joined: Jun 30, 2007

Go to the bottom of the page Go to the top of the page
#3 id:29578 Posted Jul 23, 2009, 6:09 pm

I posted my thoughts/initial prototype to Nick Gammon's forums some time ago; here is the post.

If you read the accompanying documentation, you'll see that I certainly don't allow arbitrary English (which is completely unnecessary given the limited scope) but I do allow somewhat "complex" sentence structure, in that you can attach clauses to other clauses. Work still needs to be done, as I noted, for instance in understanding the difference between "from" and "to" when it comes to generating the logical form. For example, it should not generate several logical forms for the sentence "give the sword in the bag to Fred"; I think that fairly unambiguously should mean give <the sword <in the bag>> <to Fred>. But, since it has no knowledge of the semantics of prepositions, it can't figure that out.

In general, I think it is useful to write a grammar that is limited but feels natural. You cannot match normal English using a simple top-down parser, however you could write such a parser that matched very many sentences that people are likely to type into your command prompt. Basically, you have domain knowledge of the kind of things people are likely to want to do, and so you should exploit that when designing the grammar.
.........................
-- d.c.h --
BabbleMUD Project (custom codebase)
Legends of the Darkstone (head coder)
http://david.the-haleys.org
.........................

Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
#4 id:29579 Posted Jul 23, 2009, 6:51 pm

Thanks for the responses!

Idealiad: I've grabbed the source for Tads 3, but haven't had time to dig into it yet.  About a week ago I read an article series by Richard Bartlett about the way MUD2 parses commands.  He's gone a bit overboard for my needs, though, and was very vague on certain details, like prepositional clauses attached to noun groups.

David Haley:  Thanks!  Your CLIP Parser is almost exactly what my first pass at a new parser turned out, so it's good to know the basics are sound. ;)

Unless someone else has extra input, I'm probably going to go with a tactic that limits the prepositions to a certain well-defined subset of English, and limits which ones can be used in connection with verbs, and which can be used in connection with nouns, and tweak it until it feels right.  As much as I'd like to be able to parse something like "hit the oldest king of Paravel with a beard with the monkey wearing the dented amulet of Ra", I think that's a tad overzealous. :rolleyes:  I'll be happy with a grammar that understands "of" as a prepositional phrase that joins on another adjective ("old king of Paravel" = n: "king", adj: "paravel, old"), and that "with" and "at" (and similar) are used to join noun phrases together for a verb.

Again, thanks for the feedback, guys.  I've been working on this on my own, and was starting to think I'd lost perspective.  Looks like I was right. :biggrin:

Last edited Jul 23, 2009, 6:54 pm by Kintar
David Haley
Wizard






Group: Members
Posts: 7,841
Joined: Jun 30, 2007

Go to the bottom of the page Go to the top of the page
#5 id:29582 Posted Jul 23, 2009, 7:33 pm

Please keep us posted on your progress: I'm very curious to hear more. :smile: I'm reaching the point where I'll need smart command parsing as well, so I might have something more to post as well at some point.
.........................
-- d.c.h --
BabbleMUD Project (custom codebase)
Legends of the Darkstone (head coder)
http://david.the-haleys.org
.........................

Silenus
Sorcerer




Group: Members
Posts: 281
Joined: Feb 26, 2008

Go to the bottom of the page Go to the top of the page
#6 id:29610 Posted Jul 23, 2009, 10:19 pm

The LPC world has some examples of command parsers which vary in sophistication and generality. Maybe these might help you w.r.t. designing something. The FluffOS/MudOS distribution comes with a contrib parser package (the ZorkMud parser ported into the driver), DW lib comes with one written in LPC which arguably has more options and I think Tublib also has a parser built in. DGD comes with a tool parse_string() which allows you to sketch out a context free grammar and returns the various ambiguous parses(Ihesitate at this point to call this GLR because after skimming over the source I am not sure if it is).

To get fuller parsing of English probably requires more sophisticated grammar formalism like unification grammars but this may or may not be overkill depending on what you are doing.

Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
#7 id:29630 Posted Jul 24, 2009, 6:02 am

Thanks again for all the input, everyone.  I had an epiphany last night, triggered by an unrelated comment from my wife.  (Thanks, hon! :biggrin:)

The mud codebase I'm working on is component-based, so it's very simple to tell the class of a given object.  The parse is greatly simplified if we resolve which of the available set of items is valid for the command before we attempt to parse the input line.  Something like this;  Say you're in a room with Spock and his evil twin from the antimatter universe.  You want to hit the evil twin with a chair, but the only way to tell the difference is that #### goatee.  (And no, I'm not writing a Star Trek MUD, it was just the first example that came to mind. *LOL*)

> hit spock with goatee with chair

First, we look up the trigger word in our command dictionary.  We find that the definition for "hit" is  "hit <damageable> with <weapon>".  The first thing we do is collect all damageable items and all weapon items that are available to the thing that is performing the action.  Say we get the following objects back:

damageable: [spock1, spock2, playerKintar, breakableDoor52]
weapon: [phaser42, scalpel12, chair9]

Next we look at the input to the verb.  Much in the same way MudOS does their NL parser, there is a literal separator ("with") in the command definition, so we know we have to group our item references around the literal.  If we make the parser smart enough to know that literals might appear in noun phrases, too, we can see that there are two situations we have to account for:

hit (spock) with (goatee with chair)
and
hit (spock with goatee) with (chair)

We now use a dictionary-based AST parser to parse each noun phrase in the first option.  We end up with:

object: [n: spock]
indObj: [n: goatee [prep: with [chair]]]

We check for available Spocks in our collection of damageable items and know we've got at least one.  Next we check for goatees in our list of weapons and find that there aren't any.  The parser now backtracks and tries other groupings for the nouns:

object: [n: spock [prep: with [goatee]]]
indObj: [n: chair]

We try to find a Spock again, and get two.  Now, however, we've got a prepositional modifier on the noun, so we use the object's predefined modifiers and find that one of them matches the prepositional clause "with goatee".  That's our selected Object.  We now look through our possible list of weapons for a chair, and find exactly one.  Bingo!  Binding succeeded, so we call our command handler with spock2 as the object and chair9 as the indirect object.

I think this will work for 99% of situations, if the core mud object has the proper data structures to hold descriptive clauses.  What do you guys think?

Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
#8 id:29633 Posted Jul 24, 2009, 6:13 am

By the way, this parsing strategy will also work for command definitions that don't have a literal separator, as long as we keep a good dictionary of parts of speech based on the items in our mud.  Our grammar can look like:  (I'm using ANTLR's implementation of BNF grammar because I'm familiar with it.  ? means match zero or once, * = zero or more, no modifier means match exactly once, | is an OR statement, parentheses group rules together like mathematical expressions.)

Code (text):
command  :    verb verbLiteral? freeText?
          |    verb freeText (verbLiteral freeText)?


This will solve commands like "take box", "take box from bag", "take box bag", and "take off armor".  We can then pass the "freeText" blocks, if any, to a separate noun parser that uses the set of potential matches to derive its vocabulary.  The grammar for that would look like:

Code (text):
noun  :  article? (adjective (conjunction adjective)*)? noun (nounPrep nounDescriptor (conjunction nounDescriptor)*)?

I think this will work! =)

shasarak
Sorcerer






Group: Members
Posts: 421
Joined: Nov 28, 2007

Go to the bottom of the page Go to the top of the page
#9 id:29634 Posted Jul 24, 2009, 6:18 am

This sounds very interesting!

My one comment is that if you want this to be clever, you will need to include some knowledge about the player character's environment within the parsing routine.

It's not difficult to come up with an instruction that is genuinely ambiguous. For example: "put the key in the hat on the treestump". Are we saying "take the key that is currently in the hat out of the hat and put it on the treestump instead"? Or are we saying "there is an empty hat on a treestump here; place the key in that hat"? There's no way that any parser that only looks at the words typed can resolve that ambiguity - even a human reading those words out of context has no way of telling which was meant, because the English language itself isn't that precise. The only way you can distinguish between them is to know something about the context in which the command was issued.

In the room where the player currently is, is there an empty hat sitting on a treestump? And is there a key present elsewhere in the room or in the player's inventory? If so then the player clearly meant "put the key into the hat".

If there isn't a hat on a treestump, but there is a hat somewhere else with a key in it, and there is a treestump present, then clearly the player meant "take the key out of the hat and put it on the stump".

So, ideally the first stage of the parser should actually come up with multiple possible interpretations, and the second stage of the parsing process should then examine which of those possibilities actually makes sense within the context that the command is typed.

EDIT: Bah, took way too long to type this and was anticipated by the two previous posts. Oh well. :(
.........................
Hand over the chocolate and nobody gets hurt.

Last edited Jul 24, 2009, 6:20 am by shasarak
flumpy
Wizard






Group: Members
Posts: 624
Joined: Mar 27, 2009

Go to the bottom of the page Go to the top of the page
#10 id:29636 Posted Jul 24, 2009, 6:29 am

@Kintar

I started out in exactly the opposite way to you. I initially started using something called "antlr" which does what your tree implementation seems to do. After all, any "language" from programming to natural language follows some rules. The trouble is, the more complicated your phrase the more complex the tree needs to be.

I quickly realised I was actually over-complicating things, and I should work back to a more simple regex based model. I realised too that I wanted to achieve what you started out with. My main reasoning was this: there are many exceptional phrase structures that can occur in natural language, and I could be there forever trying to guess what the user meant if I didnt ask them explicitly. Either that or I might end up having to generate very many spurious tree structures with far too many branches for an average user to remember.

For example, in one of the examples you gave about the bearded man, I would either have to ask which "with" meant "using" or have the user remember a spurious rule that if they have a sentence with "with" in it, they need to specify "using" instead. On its own this is not too bad, but with all the other rules it could become too much.

I suggest that you would have to keep in mind your user here. Like any other user interface, a player can become bogged down with choice, or annoyed that they cannot do simple things easily. If you are constantly asking them for prompts, or trying to get them to remember rules, they will quickly get bored.

Not that you shouldnt try to do this for fun of course ;)

.........................

GroovyMud - a mud engine written in Java and Groovy

try it out! telnet://zeno.biyg.org:2223


Disclaimer: this project is in alpha, and therefore in heavy development.

Last edited Jul 24, 2009, 6:35 am by flumpy
Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
#11 id:29638 Posted Jul 24, 2009, 6:46 am

@flumpy

A very good point; That's actually the issue I was posting about in the message that started this thread.  I'm pretty sure that the two-stage parse will resolve that issue most of the time, however.  In the bearded man example:

>hit king with beard with axe

Let's assume you've got the following rules for the verb "hit":

hit <thing>
hit <woundable> with|using <weapon>

Attempting the first rule, we end up with the following parse tree for "king with beard with axe":
Code (text):
noun: king [
  prep: with [
    descriptor: beard ]
  prep: with [
    descriptor: axe ]
  ]


The parser will discard this as an invalid structure, since the grammar says you're not allowed to specify two prepositional phrases on the same noun.  It will then move on to the next rule, which yields the following possible noun groups:

"king", "beard with axe"
"king with beard", "axe"

Parsing the first group yields:
Code (text):
noun1: king

noun2: beard [
  prep: with [
    descriptor: axe ]
  ]


This will fail to bind, because there are no beards in the room that have the phrase "with axe" assigned to them.  It then tries to bind the second form:
Code (text):
noun1: king [
  prep: with [
    descriptor: beard ]
  ]

noun2: axe


This will bind, since there is a king with a beard, and an axe.

The only case where this would be ambiguous is if the description of the king contained an axe, and the player is using an axe. This means we have to introduce one slightly abstruse grammar rule about prepositional phrases on nouns.  The proper form would be something liek "hit king with beard and axe with axe", but I think that's fairly likely to be the way the player would enter the command anyway.  ...  Well, assuming the builders are annoying enough to put the player in a situation where that many noun descriptors are required!  Typically, "hit king with axe" should be enough. =)

( EDIT: My kings keep having "bears" instead of "beards". :P )

Last edited Jul 24, 2009, 6:51 am by Kintar
flumpy
Wizard






Group: Members
Posts: 624
Joined: Mar 27, 2009

Go to the bottom of the page Go to the top of the page
#12 id:29639 Posted Jul 24, 2009, 6:53 am

Kintar said:
Thanks again for all the input, everyone.  I had an epiphany last night, triggered by an unrelated comment from my wife.  (Thanks, hon! :biggrin:)

The mud codebase I'm working on is component-based, so it's very simple to tell the class of a given object.  The parse is greatly simplified if we resolve which of the available set of items is valid for the command before we attempt to parse the input line.  Something like this;  Say you're in a room with Spock and his evil twin from the antimatter universe.  You want to hit the evil twin with a chair, but the only way to tell the difference is that #### goatee.  (And no, I'm not writing a Star Trek MUD, it was just the first example that came to mind. *LOL*)

> hit spock with goatee with chair

First, we look up the trigger word in our command dictionary.  We find that the definition for "hit" is  "hit <damageable> with <weapon>".  The first thing we do is collect all damageable items and all weapon items that are available to the thing that is performing the action.  Say we get the following objects back:

damageable: [spock1, spock2, playerKintar, breakableDoor52]
weapon: [phaser42, scalpel12, chair9]

Next we look at the input to the verb.  Much in the same way MudOS does their NL parser, there is a literal separator ("with") in the command definition, so we know we have to group our item references around the literal.  If we make the parser smart enough to know that literals might appear in noun phrases, too, we can see that there are two situations we have to account for:

hit (spock) with (goatee with chair)
and
hit (spock with goatee) with (chair)

We now use a dictionary-based AST parser to parse each noun phrase in the first option.  We end up with:

object: [n: spock]
indObj: [n: goatee [prep: with [chair]]]

We check for available Spocks in our collection of damageable items and know we've got at least one.  Next we check for goatees in our list of weapons and find that there aren't any.  The parser now backtracks and tries other groupings for the nouns:

object: [n: spock [prep: with [goatee]]]
indObj: [n: chair]

We try to find a Spock again, and get two.  Now, however, we've got a prepositional modifier on the noun, so we use the object's predefined modifiers and find that one of them matches the prepositional clause "with goatee".  That's our selected Object.  We now look through our possible list of weapons for a chair, and find exactly one.  Bingo!  Binding succeeded, so we call our command handler with spock2 as the object and chair9 as the indirect object.

I think this will work for 99% of situations, if the core mud object has the proper data structures to hold descriptive clauses.  What do you guys think?


Hah I didn't read this thread fully before I replied :D

This sounds like a very good way to do things. However, how would you make sure the spock you select has a goaty? Or that indeed the chair has not (silly i know)?  *EDIT ok you answered my question in the previous post :)*

These kind of hints would not want to be provided by the user, so if you can devise some way to do this I would be very interested in seeing your AST :D

*EDIT 2: This is making me want to go back and revisit my ANTLR implimentation again. I'm getting all excited thinking about it. Man I'm such a geek... My main problem was with generating all those trees, and figuring out the grammars. You seem like you know more about the subject than me, I was just dabbling, so if you can get something half decent I'd be /very/ interested to see.*
.........................

GroovyMud - a mud engine written in Java and Groovy

try it out! telnet://zeno.biyg.org:2223


Disclaimer: this project is in alpha, and therefore in heavy development.

Last edited Jul 24, 2009, 6:58 am by flumpy
shasarak
Sorcerer






Group: Members
Posts: 421
Joined: Nov 28, 2007

Go to the bottom of the page Go to the top of the page
#13 id:29640 Posted Jul 24, 2009, 6:55 am

Kintar, if one issues the command "hit goblin with knife", how does your proposed system decide whether the player means "use the knife I'm holding to hit the goblin" or "punch the goblin who is holding a knife"? I don't think you can assume that if the word "with" appears at least once that there must be a mention of the weapon.

It's also worth mentioning that there can be three possible interpretations of an example grammatically similar to your spock/goatee example, not two. Consider "hit goblin with dagger with ebony blade". That could mean "punch the goblin who is holding an ebony-bladed dagger", "use my ebony-bladed sword to hit the goblin who is holding a dagger" or "use my ebony-bladed dagger to hit the goblin".

In the spock/goatee example, a human would be able to tell fairly easily which one is meant, partly from the grammar and partly from the semantics. A human knows that you cannot use a goatee as a weapon, and knows that a goatee cannot be armed with a chair - maybe your parser should be given knowledge like this?

With the best will in the world, you will eventually come across ambiguous situations (e.g. "hit goblin with knife" issued when both the player and the goblin are wielding knives) so you have to be willing for the parser to give up and ask for clarification too. :)

EDIT: crossed in the post again, I'm bowing out of this! :)
.........................
Hand over the chocolate and nobody gets hurt.

Last edited Jul 24, 2009, 6:58 am by shasarak
Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
#14 id:29647 Posted Jul 24, 2009, 7:26 am

@flumpy:  I'll definitely share whatever I come up with.  I've been researching this for quite a while now, and Richard Bartlett's articles from almost 10 years ago are the only detailed discussions I can find, so I definitely want to open the discussion up a little more. :)

shasarak said:
EDIT: crossed in the post again, I'm bowing out of this! :)


Don't bow out!  You're bringing up very good points, and anything that can be done to further clarify them is awesome. :)  Your last example, especially, needs to be thought about:

> hit goblin with knife

If there is a "goblin with knife", then we either need a rule stating that social commands (hit <thing>) take precedence over potentially deadly commands (kill|hit <killable> with|using <weapon>), or the parser needs to stop and ask:

> hit goblin with knife
Did you mean you want to:
  (social command)"hit 'goblin with knife'"
Or do you want to:
  (combat command)"kill 'goblin' using 'my knife'"?

Kintar
Magician




Group: Members
Posts: 56
Joined: Jul 23, 2009

Go to the bottom of the page Go to the top of the page
#15 id:29648 Posted Jul 24, 2009, 7:59 am

shasarak said:
For example: "put the key in the hat on the treestump"


I meant to directly address this, too, but forgot. :)

The grammar I'm outlining is simple enough that "in" probably won't be one of the allowed prepositions for nouns.  BUT, if we did want to do this kind of detailed parsing, the following might work:

Definitions:
  put <thing> in <container>
  put <thing> on <surface>

We'd end up with the following potential parses:
  put (the key) in (the hat on the treestump)
  put (the key in the hat) on (the treestump)

Binding will once again save the day, albeit with a very complex set of rules about noun prepositions.

Preposition rule:  <thing> on <surface>
Preposition rule:  <thing> in <container>

This now turns our two-phase parser into a three-phase parser.

Case 1: [n: key], [n: hat [prep: on [ treestump ]]]

For this case to succeed, the third phase parser (the prepParser) would have to locate a "treesump" surface object in the actor's location, and find an object named "hat" that passes the "on" preposition rule.  The second phase parser would then verify that the "hat" object is ALSO a surface object.  If not, the bind fails, and the next rule is considered.

Case 2: [n: key in hat], [n: treestump]

For this case to succeed, the prepParser would have to find an accessible container object named "hat" that passes the prepositional test for "key in", and also locate a "treestump" that is a surface object.

Hmm...I like the sound of this.  So, maybe:

Phase 1: Verb binding.  Locate all verbs that match the input's trigger word.
Phase 2: For each verb, parse the input according to its prepositional phrases to obtain one or more lists of noun phrases.
Phase 3: For each noun phrase, attempt binding.  If the noun phrase contains a prepositional phrase, look up the rule for that prepositional phrase and parse.
Phase 3a - Preposition parsing: Split the input tokens around the preposition and run Phase 3 for each resultant noun phrase.

If any phase fails to produce viable results, the parser stores the tokens it successfully bound and then backtracks to the previous phase.  Once the complete parsing/binding algorithm completes, that completed parse is stored.  After all options are parsed, if only one completed parse exists, that's the target.  If no completed parses exist, the failed parse results are presented to the player so they can disambiguate their input.  If more than one parse produced a successful result, these are presented to the player and they're asked to choose.

This was typed in about 10 minutes between meetings at work.  PLEASE tell me what I've missed, 'cause there's bound to be something. ;)

Pages:<< prev 1, 2 next >>

Valid XHTML 1.1! Valid CSS!