<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift) --> <!--X-From-R13: X Q Znjerapr <pynjNhaqre.rate.ftv.pbz> --> <!--X-Date: Tue, 7 Jul 1998 11:14:52 -0700 --> <!--X-Message-Id: 199807071814.LAA02580#under,engr.sgi.com --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] (fwd) Re: command parsers: a modest proposal (with a</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:claw#under,engr.sgi.com"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00060.html">Previous</a> | <a href="msg00062.html">Next</a> ] Thread: [ <a href="msg00095.html">Previous</a> | <a href="msg00057.html">Next</a> ] Index: [ <A HREF="author.html#00061">Author</A> | <A HREF="#00061">Date</A> | <A HREF="thread.html#00061">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</LI> <LI><em>From</em>: J C Lawrence <<A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A>></LI> <LI><em>Date</em>: Tue, 7 Jul 1998 11:14:17 -0700 (PDT)</LI> <LI><em>Cc</em>: <A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A></LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> From: Richard Bartle <76703.3042#CompuServe,COM> Subject: Re: command parsers: a modest proposal (with apologies to J. Swift) Newsgroups: rec.games.mud.admin Date: Sat, 04 Jul 1998 18:48:44 -0400 "Ilya, SCC, Game Commandos" <ilya#gamecommandos,com> wrote: >But you never mentioned how it was that MUD2 handled the >idea of the forgiving parser. Well OK, I'm happy to explain. It could be MORE forgiving, I hasten to add, but it's better than most of what's out there. >Do you implement any aspect of this? I implement all aspects that I described in my earlier post. >Are several likely synonyms of command words all functional (or all >suggesting the proper alternative syntax)? Or do similar words do vastly >different things such? I have two approaches. The first is the straight synonym, or abbreviation. Example: if someone can't be bothered to type GET, they can type G. In that case, G is a vocabulary item which points at the same (command) object that GET does. Similarly, DROP, DR, GIVE, GI and INSERT are all synonyms for the action of transferring an object from the person carrying it to some other container (or person, or room - they're just specialisations of the class CONTAINER). The second is through the class hierarchy. Example: in most cases if you TOSS an object, it should execute the same code that THROW does (which in turn normally behaves like DROP does) except in the special case where the object being tossed is a subclass of COIN. So I can define: { drop object }: <default code for DROP OBJECT here> { throw firework }: <something telling you not to throw fireworks here> { toss coin }: <something telling you whether it came up heads or tails here> Thus, if someone does TOSS COIN they get the message about heads or tails; if they do TOSS FIREWORK they get the message about not throwing fireworks; if they do TOSS BANANA they get the default code for DROP BANANA. However, if they typed DROP COIN then it would just drop it, without the message. >Example: if a character wants to start a fight with herman, >another character, what happens with these various commands: >hit herman, kick herman, slap herman, poke herman, punch >herman, chop herman, attack herman, kill herman, murder >herman, combat herman, fight herman, etc.? OK, well I implement HIT as a one-time hit, and KILL as initiating a fight. This distinction only makes sense for players and mobiles, though, so for ordinary objects like doors and boxes they behave the same. I therefore make HIT a subclass of KILL and define: { KILL OBJECT }: <damages the object> { KILL CREATURE }: <initiate round-based combat routines> { HIT CREATURE }: <damage the creature once, but don't start combat> For the other commands you mentioned, ATTACK, MURDER, COMBAT and FIGHT are all direct synonyms of KILL. I make KICK, SLAP, PUNCH and CHOP be subclasses of HIT, so I can tell the person who receives the blow what kind of blow it was. POKE is a implemented as a separate command which tells the person who was poked that they were poked, but does no damage; you might use it to wake someone up, for example. >(I mention these because some games implement kick as >a combat command, some implement it as a 'social;' some >games require murder for player-vs-player combat, others >do not; some use attack, some kill, and so forth) Well that's not really a parser issue, then; it's just a matter of how each particular implementor chooses to do it. >Example: if a character wants to pick up a stick off >of the ground, what happens with these commands: get stick, >take stick, obtain stick, grab stick, pick up stick, get >stick from ground, grab stick off of ground, etc.? GET, TAKE, OBTAIN and GRAB are direct synonyms. PICK followed by the adverb UP is folded to give an internal command object, PICKUP, which is a subclass of GET; this is so I can trap various other interpretations of "pick up" on specific objects (eg. players) before I let it through to the default GET; I could bind PICK UP directly to GET if I chose. GET STICK FROM GROUND I'll have to check, but off the top of my head I think it does the same as GET STICK except it complains if there is no ground, eg. you're falling off a cliff or you're at sea in a boat. I'm not sure, though - it's ages since I wrote that code. GRAB STICK OFF OF GROUND would, I believe, fail to parse, complaining that OFF is a preposition and it's being followed by another preposition when it was expecting maybe a noun. It would take me maybe a minute to get it to parse (by declaring OFF to be an adverb as well as a preposition, and recompiling). >Not to mention the simple variations with 'a,' 'an,' or 'the' >articles included or not (get the stick, take the stick, >take a stick, obtain the stick, grab the stick, etc.) My parser has a weak spot with plurals, in that I treat every object as if it were plural. Thus, GET STICK in a room with 3 sticks in it would pick them all up. If you just wanted one, then GET A STICK or GET 1 STICK would work, as would use of a discriminating adjective like GET LIT STICK or GET HEAVIEST STICK. >(Again, none of these is an unreasonable guess on the part >of the player. But implementations abound where they have >vastly different meanings. Yes, I know, although I'm not sure whether all of these are parser issues: some are just issues of choice on the part of the implementer for dealing with genuinely ambiguous words. >'Pick up x' is often interpreted as 'use lockpicking skills to pick the >lock named 'up''; Well if they implemented a class hierarchy for commands, that wouldn't happen. If PICK is a subclass of GET then: { PICK LOCK }: <code for lockpicking> { PICK FLOWER }: <code for picking a flower> { GET OBJECT }: <code for picking up something> What's more, if the parser actually pays attention to the adverbs, PICK LOCK and PICK UP LOCK need not amount to the same thing. >grab may be a social, not a synonym for take; Sigh... { GRAB PLAYER }: <socialisation code here> { GRAB OBJECT }: call drop(object) >Please note that I do not necessarily espouse that all >potential synonyms always be active -- only that every effort >be made to reduce the pain required on the part of the >player to guess the proper command I really must process that copy of Roget's Thesaurus I downloaded a couple of years ago! I've added many synonyms and subclasses for commands over the years, but not exhaustively. Still, it's pretty good: if someone types GENUFLECT instead of BOW, it works... >So, since you've entered into the exchange, Mr. Bartle, Hmm, well if you're going to be formal it's Dr Bartle..! >do complete your answer with a description of your venerable >MUD2's way of implementing anything along the lines of a >forgiving parser. I get the feeling you may have the impression that I don't know what I'm talking about... Oh well, here goes! There are several stages to parsing in a MUD. Ideally, they should all be interconnected so you can backtrack from one to the other, but in practice they tend to be dealt with by different processes, perhaps even on different machines, so it's never going to be as good as it might be. Here's how MUD2 does it, with reference to its forgivingness. I've simplified things a little (it allows certain verbs to enquote the rest of the sentence, for example, which is a pain to implement), but this is roughly what it does: Stage 1: tokenising The input line is split into tokens, ie. collections of symbols which are potentially meaningful. Whitespace and garbage characters are stripped away. Unforgiving parsers might complain about "GET BOX" with two spaces after "GET", or the fact that "GET" is in upper case. Stage 2: dictionary lookup The symbols in the tokenised command line are looked up in the the game's dictionary/vocabulary. If they're not there, then they must either be ignored, guessed at, or the parsing process must stop. Unforgiving parsers will bomb out with an error message. As it happens, MUD2 does that, too. In MUD1, the words were ignored, but I found that most problems of this nature were due to players' typing mistakes. In MUD2, I added synonyms for most of the common errors ("teh" for "the" and so on), but stopped short of trying to guess what people meant because there were potential dangers if the wrong guess was made. If someone types KI JIM meaning KISS JIM, and the game decides that KILL JIM is more likely, well, you get the picture... People seem to prefer to have the error pointed out so they can use line-editing and correct it. This may not be the case on other MUDs, with different player cultures. Stage 3: parsing The dictionary entry for each symbol returns a set of parts of speech which this symbol can take. Many English words have different meanings depending on where they are in a sentence (eg. PLANT can be a verb, adjective or noun), and in a MUD this is compounded by abbreviations (eg. F is short for the verb FLEE and the preposition FROM). The job of the parser is to determine which parts of speech apply for each command line. For MUD2, I use an implicit, backtracking grammar so arranged as to find the most common forms first (eg. VERB NOUN before ADVERB VERB). I parse the whole input line, and as a result will get either a failed parse or a successful parse. There's not much I can do about a failed parse: if someone types DOOR THE OPEN KEY WITH then a human may be able to figure out what's meant, but it would bloat a parser to give it that capacity. What I do, therefore, is tell the players what the parser DID understand, and what it was expecting the symbol it failed on to be. Players can then attempt to rephrase what they typed so as to fit what the parser can cope with. It beats "I don't understand that, please try saying it a different way". Since my parser knows about verbs, nouns, adjectives, adverbs, prepositions, definite/indefinite objects, pronouns, superlatives, numbers, conjunctions and punctuation, it can handle a reasonable range of imperative sentences. DROP THE BIGGEST OF THE LIT STICKS IN THE BOAT THEN DROP IT AND THE LEAST BEST WEAPON IN THE RIVER would parse (and be successfully executed, not that people often bother typing stuff in with that kind of complexity). For synonyms, this is the stage where they are reconciled with their main meaning. The parts of speech returned by a successful parse of GET LONGSWORD are identical to those returned by G LS. Stage 4: binding The result of the parse is a set of sentences/commands. These are handled one at a time. A command consists of a verb, followed by a list of verb qualifiers (adverbs and prepositions) followed by a list of noun groups. Noun groups are a noun, followed by a list of noun qualifiers (adjectives, definite/indefinite objects etc.). The binder's job is to associate a word with a real object. If I say GET KEY, then the binder has to find which key(s) I mean, in the context of the verb; DROP KEY would bind to a different key (one I'm holding, rather than one on the floor). OK, so first I apply all the modifiers to the verb, to get a new verb. Most modifiers do nothing, but some are important - THROW KNIFE AT MARY is not the same as THROW KNIFE TO MARY. Once I have the modified verb, this determines the point at which the search for objects begins (eg. the player for DROP, the room for GET). The search traverses all opened, accessible containers from the search point, and finds all objects which are instances of the class implied by the noun. DROP GOLD would bind a list of all objects of class GOLD that you were carrying to the first noun slot. Once this set of noun bindings has been created, it is filtered by the noun qualifier list. If you said GET GOLDEN FORK and there were three forks in the room, then these three would be the initial set, but applying the adjective (function) GOLDEN to each element would produce a new set with only golden forks in it. A similar process works for superlatives, and for excluding prepositions (DROP EVERYTHING BUT MY SWORD). Some nouns are dynamic, and have to be bound on the fly. There are no objects of class FOE, for example, but if I were fighting an invisible player I may want to reference them as the target for a spell, say. If I don't know their name, what can I do? Well, using the word FOE will bind to all creatures with whom you are currently engaged in combat. I could thus BLIND FOE to try cast a BLIND spell at them. Pronouns are handled in a similar fashion. At the end of the parse, I have a verb, and an optional number of sets of objects. If any of these sets are empty, then the player has referenced an object that they have no access to: that, therefore, is what I tell them. KILL OX. "You don't see any ox.". HIT BILL WITH CARROT. "You don't see any carrot.". There ARE carrots and oxen in the game, just not where you are. Stage 5: despatching At this stage, I have a verb, and 0 or more non-empty sets of nouns (in fact, the way MUD2 does it, it's limited to 0, 1 or 2 sets of nouns: it can't handle stuff like PUT THE EGG IN THE PAN WITH THE SPOON, but a day's work would enable it to do so). I now have to decide what actual functions to call. As I mentioned earlier, functions are legitimate objects in MUD2, so rather than going through all the objects telling them to invoke the function on them, I simply tell the function to invoke itself with each objects as a parameter, in turn. Example: verb=GET, first noun set=[KEY1, KEY2, KEY3] Invoke: GET(KEY1) GET(KEY2) GET(KEY3) I've used the traditional syntax for calling functions, there; it's really more like: call(GET, KEY1) call(GET, KEY2) call(GET, KEY3) If there are no noun groups, it's trivial to call the verb with no parameters. There is something of an issue, though, if there are two sets of nouns, eg. GET INSECTS WITH NETS when there are 3 insects and 2 nets. What does it mean? It's not exactly clear what it means in English, let alone in a MUD! The solution I adopt is fairly arbitrary, but then any solution will be arbitrary in some respect. I call GET three times, one for each insect, and use the first net only. If, however, the net is somehow destroyed by getting one of the insects (eg. it breaks), I would switch to the second net. Also, binding would cease if the player were to die as a result of executing a command. Unforgiving parsers may not be able to despatch on functions, which means that the same verb cannot affect radically different objects in different ways. What's appropriate for C++ isn't necessarily appropriate for MUDs. Stage 6: executing Execution takes place a function call at a time. Here, the function call is matched in an hierarchical fashion against function definition templates, until a match is found. A match is ALWAYS found, because I have a top-level template which matches everything that hasn't been matched elsewhere. When the match is found, the code is executed. Originally, I had an option to rematch, but I found that I never used it. PROLOG has a cut operator to prevent rematching, and my operator was like an inverse of this (ie. default was to cut, explicit operator causes the search to continue). Given that I didn't find I needed it, and that it added a significant overhead to the matching process, I removed it. For absolutely purity, though, I should have left it in. The execution of the command actually effects changes in the game world. It also tests conditions of applicability: if you want to hit someone with an axe, and injury has left you too weak to wield the axe, then the command should fail with an appropriate error message. Similarly, if you want to open a door and it's already open, you should be told that it's already open, not that you've opened it. It's at this point that the final stage of forgivingness takes place, by making intelligent assumptions. If someone says OPEN DOOR, and the door is locked but they have a key which fits, then they should be able to open the door. However, if they say OPEN DOOR WITH SMALL KEY and the small key doesn't fit, they should be told it doesn't fit, of course, but what if they had another key which does fit? I decided not to open the door, as they actually specified which key to use, however other MUD designers might prefer it to open in their game. There's therefore some debate as to how far to go with this; I tend to err on the side of convenience. If someone says OPEN then I could search for a closed door, search for a matching key, and open it. However, in MUD2 there are other things people can open, some of which are deadly, and therefore I tell them I need to know what it is they wish to open. It's within the parser's capacity to say "What do you want me to open? (chest, door) but I try to avoid doing that. It always annoyed me as a player, and it's not exactly hard for them to use a line editing command to pull back the OPEN and then add CHEST or whatever anyway. I realise that there are certain Zork-hardened players who would advocate the answer-the-question approach, though. Hmm, I think that's about it! I hope that helps answers your question. Richard -- J C Lawrence Internet: claw#null,net (Contractor) Internet: coder#ibm,net ---------(*) Internet: claw#under,engr.sgi.com ...Honourary Member of Clan McFud -- Teamer's Avenging Monolith... </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00060.html">[MUD-Dev] Re: WIRED: Kilers have more fun</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00062.html">[MUD-Dev] Re: Affordances and social method (Was: Re: Wired Magazine...)</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00095.html">[MUD-Dev] Re: (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00057.html">[MUD-Dev] Re: Ubiquity Scope & Requirements</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00061"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00061"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><STRONG>[MUD-Dev] Re: (fwd) Re: command parsers: a modest proposal(with apologies to J. Swift)</STRONG>, <EM>(continued)</EM> <ul compact> <ul compact> <LI><strong><A NAME="00085" HREF="msg00085.html">[MUD-Dev] Re: (fwd) Re: command parsers: a modest proposal(with apologies to J. Swift)</A></strong>, Ross Nicoll <a href="mailto:rnicoll#calmar-mud,com">rnicoll#calmar-mud,com</a>, Wed 08 Jul 1998, 17:35 GMT </LI> <LI><strong><A NAME="00087" HREF="msg00087.html">[MUD-Dev] Re: (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</A></strong>, Richard Woolcock <a href="mailto:KaVir#dial,pipex.com">KaVir#dial,pipex.com</a>, Wed 08 Jul 1998, 18:19 GMT </LI> <LI><strong><A NAME="00091" HREF="msg00091.html">[MUD-Dev] Re: (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</A></strong>, Adam Wiggins <a href="mailto:adam#angel,com">adam#angel,com</a>, Wed 08 Jul 1998, 18:43 GMT </LI> </ul> <LI><strong><A NAME="00095" HREF="msg00095.html">[MUD-Dev] Re: (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Thu 09 Jul 1998, 00:56 GMT </LI> </ul> </LI> <LI><strong><A NAME="00061" HREF="msg00061.html">[MUD-Dev] (fwd) Re: command parsers: a modest proposal (with apologies to J. Swift)</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 07 Jul 1998, 18:14 GMT <LI><strong><A NAME="00057" HREF="msg00057.html">[MUD-Dev] Re: Ubiquity Scope & Requirements</A></strong>, Greg Munt <a href="mailto:greg#uni-corn,demon.co.uk">greg#uni-corn,demon.co.uk</a>, Tue 07 Jul 1998, 06:39 GMT <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="00058" HREF="msg00058.html">[MUD-Dev] Re: Ubiquity Scope & Requirements</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Tue 07 Jul 1998, 14:18 GMT <UL> <LI><strong><A NAME="00070" HREF="msg00070.html">[MUD-Dev] Re: Ubiquity Scope & Requirements</A></strong>, Vadim Tkachenko <a href="mailto:vt#freehold,crocodile.org">vt#freehold,crocodile.org</a>, Wed 08 Jul 1998, 02:30 GMT </LI> </UL> </LI> </UL> </LI> <LI><strong><A NAME="00053" HREF="msg00053.html">[MUD-Dev] Development of a Smart Compiler</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 07 Jul 1998, 01:28 GMT </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>