partial parsing?

Dave Abrahams abrahams at mediaone.net
Sun Apr 23 23:37:57 CEST 2000


in article 8dvilp$88s$1 at slb6.atl.mindspring.net, Andrew Dalke at
dalke at acm.org wrote on 4/23/00 2:27 PM:

> Can anyone here provide pointers to relevant programs or papers?

You might think about looking at chart parsing technology, sometimes used in
natural language processing.

You can use a chart parser to extract all parseable sub-regions from a
sequence of tokens. Just turn off the grammar rules you're not interested in
and you should be all set (provided the grammar rules you care about don't
generate false positives due to the lack of contextual information that
would be neccessary for a complete parse). Depending on how self-similar
your grammar is, this technique may well end up doing more work than you'd
like. Whether it will work for you sort of depends on your goals and the
problem domain.

Just a caveat: in typical program parsers much more time is spent in lexical
analysis than in actual parsing. This tends to indicate that using YACC is
probably about as well as you'll do for speed and trying to optimize away
parsing time is misguided.

Good luck,
Dave




More information about the Python-list mailing list