module to parse "pseudo natural" language?

[Andrew E]

Hi all

I've written a python program that adds orders into our order routing
simulation system. It works well, and has a syntax along these lines:

./neworder --instrument NOKIA --size 23 --price MARKET --repeats 20

etc

However, I'd like to add a mode that will handle, say:

./neworder buy 23 NOKIA at MKT x 20

I could enter several orders either by running multiple times, or use a
comma-separated approach, like:

./neworder buy 23 NOKIA at MKT on helsinki, sell 20 NOKIA at market on
helsinki

The thing about this is that its a "tolerant" parser, so all of these
should also work:

# omit words like "at", "on"
./neworder buy 23 NOKIA mkt helsinki

# take any symbol for helsinki
./neworder buy 23 mkt helsinki

# figure out that market=helsinki
./neworder buy 23 NOKIA at market price


I've started writing a simple state-based parser, usage like:

class NaturalLanguage InsructionBuild er:

def parse( self, arglist ):
"""Given a sequence of args, return an Instruction object"""
...
return Instruction( instrument, size, price, ... )


class Instruction:
"""encapsul ate a single instruction to buy, sell, etc"""

def __init__( self, instrument, size, price, ... ):
...


This doesn't work yet, but I know with time I'll get there.

Question is - is there a module out there that will already handle this
approach?

Thanks for any suggestions :)

Andrew

[Diez B. Roggisch]

Re: module to parse "pseudo natural" language?

>[color=blue]
> Question is - is there a module out there that will already handle this
> approach?[/color]

Try the python nltk. I haven't done stuff with it so far, but I'd certainly
give it a try when I need natural language support.

http://nltk.sourceforge.net/

--
Regards,

Diez B. Roggisch

[F. Petitjean]

Re: module to parse "pseudo natural" language?

Le Sun, 17 Apr 2005 13:38:09 +0200, Andrew E a écrit :[color=blue]
> Hi all
>
> I've written a python program that adds orders into our order routing
> simulation system. It works well, and has a syntax along these lines:
>
> ./neworder --instrument NOKIA --size 23 --price MARKET --repeats 20
>
> etc
>
> However, I'd like to add a mode that will handle, say:
>
> ./neworder buy 23 NOKIA at MKT x 20
>
> I could enter several orders either by running multiple times, or use a
> comma-separated approach, like:
>
> ./neworder buy 23 NOKIA at MKT on helsinki, sell 20 NOKIA at market on
> helsinki[/color]
It would be simpler to have the rule : one line == one order, action,
command wahtever.[color=blue]
>
> The thing about this is that its a "tolerant" parser, so all of these
> should also work:
>
> # omit words like "at", "on"
> ./neworder buy 23 NOKIA mkt helsinki
>
> # take any symbol for helsinki
> ./neworder buy 23 mkt helsinki
>
> # figure out that market=helsinki
> ./neworder buy 23 NOKIA at market price[/color]
You have some variation of the same « buy » order. If you want to detail
the semantics : you arrive to determine the different parameter of a
BuyCommand : what, where, how (many) ...
This semantic is expressed differently in english, US-english, french
...
If you base your parser on regex you see that the same BuyOrder is
represented by a number of variant :
Please, buy 23 NOKIA at market Helsinki
Acheter 40 actions Bouygues à la Bouse de Paris

So you have for a given environment (orders management module) a number
of commands expressed in pseudo-natural languages. Each command has a
certain number of attributes
name, module_name, parameters, variants(list of regexps for instance),
description, short description, sample sentence (to be presented
to the user in an interactive session if requested).
An important attribute is naturally the action taken when the
parser/interpreter matches the current line.

So you group the description of the Commands in an easy to parse file
and write an interpreter which on startup read such a file for the
Commands it understands : command to load a module, to list the commands
in the currently loaded module or in the interpreter, command to display
the sample, short or long description (help about cmd or how to spell
cmd)., command to stop the interpreter (and the program) ...
command to read/include a file containings commands to parse and
execute.
Python is dynamic, with setattr() you can easily construct a Command
object from its description.

Here is what could be the description of a command to compute the
equilibrium position in a stability module (using a «here» shell like
syntax ):
command equilibre << eoc
description << eod
La commande « equilibre » permet de lancer le calcul de la position
d'équilibre du flotteur couramment décrit.
position equilibre en partant de pqr 0.0/0.0/1.0 et h=8.500
les mots-clés sont equilibre pqr et h[=]
eod
sample <<eos
equilibre pqr 0.0/0.0/1.0 avec h=8.500
eos
# name of function to call
action compute_equi
# parameters of the command (a dictionary of parameters could be in
# action's arguments
parameters << eop
pqr
h
eop[color=blue]
>[/color]
# The regexpes
variants << eov
# the following regexp is with re.I (ignore case flag) :
variant I << eovi
equilibrer?\spq r\s+(?P<pqr>\d* \.\d*/\d*\.\d*/\d*\.\d*)\s+(?P <h>\d*\.\d*)
eovvi
# syntax of regexp untested :-)
variant << eovi
equilibrium\spq r\s+(?P<pqr>\d* \.\d*/\d*\.\d*/\d*\.\d*)\s+(?P <h>\d*\.\d*)
eovvi
eov
eoc
[color=blue]
> Thanks for any suggestions :)
>
> Andrew[/color]

[John Roth]

Re: module to parse &quot;pseudo natural&quot; language?

"Andrew E" <andrew@nospam. com> wrote in message
news:d3thql$4rh $1@news.hispeed .ch...[color=blue]
> Hi all
>
> I've written a python program that adds orders into our order routing
> simulation system. It works well, and has a syntax along these lines:
>
> ./neworder --instrument NOKIA --size 23 --price MARKET --repeats 20
>
> etc
>
> However, I'd like to add a mode that will handle, say:
>
> ./neworder buy 23 NOKIA at MKT x 20
>
> I could enter several orders either by running multiple times, or use a
> comma-separated approach, like:
>
> ./neworder buy 23 NOKIA at MKT on helsinki, sell 20 NOKIA at market on
> helsinki
>
> The thing about this is that its a "tolerant" parser, so all of these
> should also work:
>
> # omit words like "at", "on"
> ./neworder buy 23 NOKIA mkt helsinki
>
> # take any symbol for helsinki
> ./neworder buy 23 mkt helsinki
>
> # figure out that market=helsinki
> ./neworder buy 23 NOKIA at market price
>
>
> I've started writing a simple state-based parser, usage like:
>
> class NaturalLanguage InsructionBuild er:
>
> def parse( self, arglist ):
> """Given a sequence of args, return an Instruction object"""
> ...
> return Instruction( instrument, size, price, ... )
>
>
> class Instruction:
> """encapsul ate a single instruction to buy, sell, etc"""
>
> def __init__( self, instrument, size, price, ... ):
> ...
>
>
> This doesn't work yet, but I know with time I'll get there.
>
> Question is - is there a module out there that will already handle this
> approach?
>
> Thanks for any suggestions :)[/color]

There's NLTK (on Sourceforge) which has already been mentioned.
However, it's a teaching tool, not a real production natural language
parser.

I'd suggest you step back from the problem and take a wider
view. Parsing natural language, in all its variations, is an unsolved
research problem that is part of what has given Artificial Intelligence
somewhat of a black eye.

Your problem is, however, much simpler than the general one:
you've got a limited number of commands which pretty much
all follow the VO (verb operands) pattern.

You've also got a lot of words from limited and disjunct
vocabularies that can be used to drive the parse. In your example,
at least one of 'buy' and 'sell' is required to start a clause,
MKT is one of maybe a half dozen
qualifiers that specify other information that must be present,
there are a limited number of exchanges, and the number of
shares seems to be the only number present.

I'd also take a bit of advice from the XP community: don't
write the library first, wait until you've got at least three
working examples so you know the services that the
library really needs to support.

John Roth[color=blue]
>
> Andrew[/color]

[bytecolor]

Re: module to parse &quot;pseudo natural&quot; language?

Andrew E wrote:[color=blue]
> Hi all
>
> I've written a python program that adds orders into our order routing
> simulation system. It works well, and has a syntax along these lines:
>
> ./neworder --instrument NOKIA --size 23 --price MARKET --repeats 20
>
> etc
>
> However, I'd like to add a mode that will handle, say:
>
> ./neworder buy 23 NOKIA at MKT x 20
>
> I could enter several orders either by running multiple times, or use[/color]
a[color=blue]
> comma-separated approach, like:
>
> ./neworder buy 23 NOKIA at MKT on helsinki, sell 20 NOKIA at market[/color]
on[color=blue]
> helsinki[/color]

You could add a string option instead:
$ neworder -c 'buy 23 NOKIA at MKT on helsinki, sell 20 NOKIA at market
on helsinki'

This would leave your current option parsing in tact. Then just
split on the comma.

Another suggestion would be to drop into an interactive mode if
no arguments are passed:
$ neworder
->? buy 23 NOKIA at MKT on helsinki
->? sell 20 NOKIA at market on helsinki
->? ^d
[color=blue]
> The thing about this is that its a "tolerant" parser, so all of these
> should also work:
>
> # omit words like "at", "on"
> ./neworder buy 23 NOKIA mkt helsinki
>
> # take any symbol for helsinki
> ./neworder buy 23 mkt helsinki
>
> # figure out that market=helsinki
> ./neworder buy 23 NOKIA at market price
>
>
> I've started writing a simple state-based parser, usage like:
>
> class NaturalLanguage InsructionBuild er:
>
> def parse( self, arglist ):
> """Given a sequence of args, return an Instruction object"""
> ...
> return Instruction( instrument, size, price, ... )
>
>
> class Instruction:
> """encapsul ate a single instruction to buy, sell, etc"""
>
> def __init__( self, instrument, size, price, ... ):
> ...
>
>
> This doesn't work yet, but I know with time I'll get there.
>
> Question is - is there a module out there that will already handle[/color]
this[color=blue]
> approach?
>
> Thanks for any suggestions :)
>
> Andrew[/color]

If I were in your situation, I'd probably write a BNF for the
tiny-language. This would help wrap my brain around the problem.
The BNF would help show what kind of regular expression you are
looking at creating as well.

--
bytecolor