Re: Tree Parsing

Haibing Ma wrote:


> I'm looking for some program for tree parsing. BURG is good, but the
> only problem is it's restricted to binary tree. Does anybody know any
> tree parsing program which has no such restriction?


I'd hesitate to say RTFM, because I've found this subject to be
relatively tricky, and I wrote one of the useful papers in the field.
But, if you study how this is done (e.g., some of O'Donnell's papers,
maybe Equational Logic as a Programming Language) you could probably
extend the algorithms to higher arity.


Also, Todd Proebsting (*) and a gradual student developed something, I
think more or less as an exercise, called "jburg" that I've looked at
(it's written in Java, of course). It just does dynamic cost
computations from the bottom, but doesn't restrict you to binary
patterns. It's got some unusual quirks (uses the Java type system for
its node labels, and if you have an inheritance relationship between
the nodes in your grammar, you can get some relatively non-intuitive
results; my advice is to avoid this "feature") but it gets the job
done.


(*) Todd's with Microsoft now.


David Chase
NaturalBridge LLC
--

Return to the comp.compilers page.
Search the comp.compilers archives again.