[DGD] Algorithm for Parsing Commands

[Par Winzell]

> First, a question; for a long time, the paradigm has been to have a 
> basic command parser determine which verb to use, and then call that 
> verb function, which would parse the command further.  What is the 
> reasoning behind this?

Well, no. As I recall, by 1994, it was well established among those who 
spent their time thinking about such things that a global, static list 
of verbs is much more intuitive than e.g. LPMud's notion that rooms can 
add a verb that doesn't work elsewhere, or works differently elsewhere.

The Skotos mudlib, my only hands-on experience with a modern mudlib, 
makes a very clear distinction between grammatical constructs, which are 
part of the 'text-based player interface' module, and 'actions' which 
belong in the 'virtual world' module.

The code that deals with grammatical constructs (i.e. parses verb 
phrases) is preoccupied with the nearly-infinitely complicated task of 
unravelling the vagueries of the English language and produce useful 
error output when something's off. The code that deals with actions 
needs know nothing about language.

As a simple example, 'light light'. Chances are the TextInterface module 
would turn this into either ACT_FLIP(light_switch) or ACT_IGNITE(torch). 
  The actions are never ambiguous, and they could be generated by NPC 
scripting code just as easily as they are generated by the parser.

Anyway, that wasn't your main question. :)

> Assumption:  Articles are treated as whitespace

This assumption isn't necessary; adding article support is one of the 
simpler extensions. If you get 'the', you require that the noun resolves 
to a single object. If you get 'one' or 'a'/'an', you pick a random one. 
If you get 'six' you return six random ones. If you get 'sixth' you pick 
the sixth... etc.

> 2)  Determine which words are verbs, by comparing them to a list of 
> suitable verbs (this takes into account synonyms for verbs)
>      a) If there is no suitable verb, produce error output

Yes, verbs are terminals in our grammar as well.

> I know that this, so far, is still relatively simple; it can handle 
> "verb adjective noun preposition adjective noun" sentences all day 
> long.  I would like to make it more robust, to handle sentences such as;

I think you've pretty much got the essentials down. Parsers do double in 
complexity every time you try to make them smarter, but the examples 
below seem like fairly minor additions:

> "cast gnusto at spellbook" - gnusto is a noun, but would forever be 
> missed because it doesn't exist in the player's environment

SkotOS splits a sentence down by verbs, prepositions and articles. Those 
are grammatical constructs, as opposed to nouns and adjectives which are 
more or less free form. Since we allow any number of prepositions in our 
sentences, you can no longer usefully talk of 'the noun' or even 'the 
direct vs the indirect noun'. We had to come up with a new term, 'role', 
a single word label to describe the purpose of a noun in a sentence.

Thus:

   'wave my sword at the sky'
and
   'wave at the sword with my sky'

will resolve to the same thing; when parsing is done, the sword will be 
stored under one label, the sky under another. This remapping of grammar 
construct to logical construct makes it a lot easier to write scripts -- 
the sword should obviously be able to respond identically to be shaken 
at the sky regardless of which method players use to shake it.

To handle the 'gnusto' case, SkotOS introduced 'raw roles', where the 
parser would return the raw words rather than attempt noun resolution on 
a subset of the sentence, once it had finished chopping it up into 
roles. Thus the 'cast' verb could have two roles defined, 'spell' and 
'target' perhaps. The 'to' preposition would be configured to map to the 
'target' role for that verb, and the 'spell' role would be configured as 
a direct noun. The 'spell' role is then marked 'raw', to stop the parser 
from trying to interpret it, and "gnusto" will be sent on uninterpreted 
for some other code to deal with.


> "wear red cloak from burlap sack" - Would only work if there was 
> preposition/adjective/noun checking in "wear".

SkotOS by default will search the player's environment and inventory for 
  noun resolution, but before it does the search it looks to see if 
there is a Merry script defined on the verb object (each verb's 
configuration is stored in a separate object) that wishes to replace the 
normal search operation for the current role. If there is, the script 
may return an array of objects whose inventories to seek. This is needed 
for something as trivial as 'take cup from bag'.

> "read newspaper by candlelight" - another sentence that would just fail.
> "check settings on dial" - and another sentence that would just fail.

Both these would be handled by 'raw roles'. The only problem is that it 
is sometimes unpleasant to have to give up all noun parsing for a role 
in a verb. For the 'check' example, you'd sort of like 'check my sword' 
to still perform basic noun lookup, but if you mark the direct object 
role of check as 'raw', it's always going to be raw. That remains an 
unsolved irritation. Many other designs are no doubt possible.

Zell

_________________________________________________________________
List config page:  http://list.imaginary.com/mailman/listinfo/dgd