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:
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. ;)