I suppose it depends how complex you want it to be. Simple pa**ers would just check for things like 'go north', 'take the ball', etc., while more complex ones would allow things like 'drop the ball down the well', etc.

I *think* that all commands the user can give would start with a verb (Apart from abbreviated movement commands such as 'north'), so a good starting point might be to write something to seperate the verb from the rest of the command. Unless you can think of a generic way of describing commands that the computer can use, e.g. 'go <room>', 'drop <object> [(in|down|onto) <object>]', it's probably best to write seperate pa**ers for each verb the player can use. Obviously you'd be able to reuse functions, e.g. a function to work out which object the player is talking about.

2) Apply grammar.
This is the tricky part I think.
First, I'd try to check that the instruction was 'well formed'. To be honest my education has failed me here, I don't have enough explicit understanding of grammar.
But basically, just apply a list of rules.
If the player wants to take something, he must have mentioned what it is that he wants. So 'Pick up X' is acceptable, but 'Pick up' by itself us not. (Note that 'pick up' is an atomic unit - the word spotter can't just separate words at spaces.
Similarly "Pick up North" is not acceptable.
The complexity here is not that significant, but the rules may be extensive, especially if complex instructions are required.
"Tie X to Y" is OK, but to be fair to the player one would also have to detect "tie together X and Y with the String", "Tie X and Y together with string", "Use string to tie X to Y"

Now imagine "Tie one end of the rope to the tree, and the other to the dog's collar"

This brings me to state. If the player has just referred to one thing, they may use 'it' to refer to it again. Thus the most recently used object in several areas must be matched against 'it'.

3) Finally, one should check the game universe to check it permits the instruction given.
"Pick up clock"
There are no clocks around here.

Or something.

Yeah, it's the scripting, you probably wrote a semi colon followed by a close bracket which the board tends to interpret as a smiley.

Yeah, that'll be it. Now the question is why I put a semi-colon there...

To get back to the topic, to be honest I'd be tempted to attack the problem from the other end.

Give the player a list of options of valid commands, and let her create an instruction from them.

To start with the options would be
Go, Pick up, Put down, Examine, Use (and so on)

When one of these was selected, you'd get a list of appropriate, grammatically correct options.

I think this would simplify things immensely, and it also has the advantage that the user will never be stuck because she can't guess the word.

Or at least look at the library code to see how their pa**er works - briefly:

* It splits the users command up into a series of words
* It then compares each word against a dictionary, and so replaces each word with a number to represent the dictionary word, if found
* It then compares it against a series of 'grammar lines', e.g.

'take' noun

Where 'take' would be the literal word take and noun would be an object in sight, or

'say' text 'to' creature

where 'creature' would be an object in sight which has the 'life' attribute, etc.

* It then sets the appropriate variables for the best matching (well, first matching) grammar line and calls the appropriate function

Having a read through the DM4 might be a good idea if you're interested in learning Inform or about its pa**er.

Of course writing a pa**er/game world as complex/flexible as the inform one would take some time - in the end it's up to what you want.