A Bottom-Up Algorithm for Parsing and Generation
Gregor Erbach · 2000
We present a bottom-up algorithm for parsing and generation. The algorithm is a bottom-up chart parser, whose lexical lookup phase has been modified for generation. An analysis of the algorithm offers interesting insights into the relationship between parsing and generation, summarized by the statement that parsing is a very constrained form of generation. The use of the generation algorithm as a component of a grammar development environment is discussed. 1 Parsing and Generation In this paper, we present a chart-based algorithm for parsing and generation. We will not consider generation from a semantic representation, for which the usual head-driven algorithms [Shieber et al. 1990] are better suited, but rather the generation of large sets of sentences. This functionality is needed in grammar development systems for exploring the coverage of a given grammar, and for checking whether a grammar overgenerates, which is particularly useful if grammars are developed not only for analy...