Re: Tree Parsing

David Chase <>
22 Sep 1998 01:15:05 -0400

          From comp.compilers

Related articles
Tree Parsing (Haibing Ma) (1998-09-13)
Re: Tree Parsing (Vladimir Makarov) (1998-09-18)
Re: Tree Parsing (David Chase) (1998-09-22)
| List of all articles for this month |

From: David Chase <>
Newsgroups: comp.compilers
Date: 22 Sep 1998 01:15:05 -0400
Organization: NaturalBridge LLC
References: 98-09-036
Keywords: parse

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

(*) Todd's with Microsoft now.

David Chase
NaturalBridge LLC

Post a followup to this message

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