Parsing with Typed Feature Structures is an issue that has raised many concerns among researchers in Computational Linguistics. When TFSs are used in formalisms such as HPSG, the parsing problem is generated by two aspects [van Noord1997]: the complex and large structure of the lexical entries, and the small number of grammar rules. The following paragraphs present a motivation for the choice of bottom-up, all-paths, parsing algorithms as suitable for TFSGs.
While the size of lexical entries in TFSGs is a concern from the perspective of increased unification times, the grammar rules are related directly to the parsing algorithm. As mentioned in [Oepen and Carroll2000], strictly top-down parsing algorithms are not suitable for TFSGs (a complete comparison between bottom-up and top-down parsers can be found in [Jurafsky and Martin2000]).
The motivation for using bottom-up parsers for TFSGs does not lie solely in the structure of the grammar. As van Noord noord-head-corner observes, a top-down parser may encounter termination problems. Using enhanced top-down parsing techniques, such as restricted top-down predictions, avoids the termination issues, but generally results in degraded performance.
Finally, bottom-up parsing is suitable for TFSGs due to the lexicalist nature of such formalisms [van Noord1997]. Since bottom-up parses ``never suggest trees that are not at least locally grounded in the actual input'' [Jurafsky and Martin2000], this class of parsing algorithms seems more adequate for a grammar formalism where the syntactic and semantic information is heavily concentrated in the lexical entries.
Another important aspect when parsing TFSGs (and UBGs in general) is the need for an all-paths parser. The reason behind this need is given in [Penn and Munteanu2003]:
While there have been great advances in probabilistic parsing methods in the last five years, which find one or a few most probable parses for a string relative to some grammar, all-paths parsing is still widely used in grammar development, and as a means of verifying the accuracy of syntactically more precise grammars, given a corpus or test suite.