Matching templates against a tree - any ideas?

Jon Fernquest ferni at loxinfo.co.th
Thu Sep 23 00:36:05 EDT 1999


>...traverse the tree attempting to
>match each subtree in the tree against the template, however this would
>be inefficient (there could be many trees, each if which may be large,
>and many templates).

Seems like overkill for parsing equations, ...but if you were 
parsing natural language...Tree Adjoining Grammars (TAG's)
are very reminiscent of what you're describing.
They consist of large collections of tree template patterns
(possible parses) the individual constituents of which are 
made more complicated/refined through an operation called
tree adjunction, which is basically splitting a tree apart 
at a certain point and inserting another tree.
(Perl hierarchical hashes are great for this!)

They belong to the "mildly context sensitive" class of grammars.
They're  just a little bit more powerful than CFG's, just powerful
enough to deal with natural languages according to Aravind
Joshi who has a research project devoted to them at the University 
of Pennsylvania. TAG's can be parsed in O(n**4) time.
They've been used to parse newspaper text and for translating 
across languages (Synchronous TAG's,Prof Shieber at Harvard).
They can also be implemented as finite state machines
where tree adjunction is defined as a union of finite state
transducers (Roche and Schabes, 1997, 273)
Most TAG code seems to be written in LISP.
I'm writing basic tree adjunction operators now in Perl. 
(Eventually, I'd like to 
move to Python because I really don't believe in the philosophy
of writing obfuscated code that almost all seem to have in 
the Perl community. I feel embarassed to even show Perl code that
hasn't been refined down to some 
head-scratching-arabesque-of-a-one-liner)

TAG Links:
http://www.cis.upenn.edu/~xtag/
http://www.cis.upenn.edu/~joshi/

A paper describing tree templates for natural language:
ftp://ftp.cis.upenn.edu/pub/ircs/tr/95-03.ps.Z

 

Reference:
Roche and Schabes (1997). Finite State Language Processing. MIT Press. 


Jon Fernquest
ferni at loxinfo.co.th
bayinnaung at hotmail.com
http://www.geocities.com/SoHo/Square/3472/index.html

 

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/19990923/7a4b0f2e/attachment.html>


More information about the Python-list mailing list