@hackage / partage

The library implements an Earley-style, bottom-up parser for tree adjoining grammars (TAGs) with special focus on structure (and, hence, computation) sharing.

Two particular flavours of structure sharing are currently implemented:

• Subtrees common to different elementary trees are shared amongst them. The input TAG, which can be seen as a set of elementary (initial and auxiliary) grammar trees, is in fact transformed into an equivalent DAG.

• Flat production grammar rules representing the individual parts of the DAG are then compressed in the form of a minimal FSA. Other forms of compression are also provided by the library (e.g. prefix tree).