A Bottom-Up Algorithm for Parsing and Generation

Gregor Erbach

CLAUS-Report Universität des Saarlandes 5 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.

Weitere Links

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence