DFKI-LT - A Bottom-Up Algorithm for Parsing and Generation

Gregor Erbach
A Bottom-Up Algorithm for Parsing and Generation
1 volume 5,
CLAUS-Report, Universität des Saarlandes, Saarbrücken, 2/1991

We present a bottom-up algorithm for parsing and for the generation of language samples. A language sample is a subset of the language generated by a grammar which is restricted to avoid uninteresting variation. We discuss the use of the generation of language samples for grammar development, where inspection of a language sample can help to detect overgeneration in a grammar. The algorithm is a bottom-up chart parser, whose lexical lookup phase has been modified for generation of language samples. An analysis of the algorithm offers interesting insights into the relationship between parsing and generation, summarized by the statement that parsing is a constrained form of generation.
Files: BibTeX, Erbach:1991:BAP.pdf