Parsing non-recursive CFGs

Parsing Non-Recursive Context-Free Grammars Mark-Jan Nederhof � Faculty of Arts University of Groningen P.O. Box 716 NL-9700 AS Groningen, The Netherlands markjan@let.rug.nl Giorgio Satta Dip. di Elettronica e Informatica Universit`a di Padova via Gradenigo, 6/A I-35131 Padova, Italy satta@dei.unipd.it Abstract We consider the problem of parsing non-recursive context-free grammars, i.e., context-free grammars that generate finite languages. In natural language process- ing, this problem arises in several areas of application, including natural language generation, speech recognition and ma- chine translation. We present two tabu- lar algorithms for parsing of non-recursive context-free grammars, and show that they perform well in practical settings, despite the fact that this problem is PSPACE- complete. 1 Introduction Several applications in natural language processing require “parsing” of a large but finite set of candidate strings. Here parsing means some computation that selects those strings out of the finite set that are well- formed according to some grammar, or that are most likely according to some language model. In these applications, the finite set is typically encoded in a compact way as a context-free grammar (CFG) that is non-recursive. This is motivated by the fact that non-recursive CFGs allow very compact represen- tations for finite languages, since the strings deriv- able from single nonterminals may be substrings of many different strings in the language. Unfolding such a grammar and parsing the generated strings � Secondary affiliation is the German Research Center for Artificial Intelligence (DFKI). one by one then leads to an unnecessary duplica- tion of subcomputations, since each occurrence of a repeated substring has to be independently parsed. As this approach may be prohibitively expensive, it is preferable to find a parsing algorithm that shares subcomputations among different strings by work- ing directly on the nonterminals and the rules of the non-recursive CFG. In this way, “parsing” a nonter- minal of the grammar amounts to shared parsing of all the substrings encoded by that nonterminal. To give a few examples, in some natural lan- guage generation systems (Langkilde, 2000) non- recursive CFGs are used to encode very large sets of candidate sentences realizing some input con- ceptual representation (Langkilde calls such gram- mars forests). Each CFG is later “parsed” using a language model, in order to rank the sentences in the set according to their likelyhood. Similarly, in some approaches to automatic speech understand- ing (Corazza and Lavelli, 1994) the � -best sen- tences obtained from the speech recognition module are “compressed” into a non-recursive CFG gram- mar, which is later provided as input to a parser. Fi- nally, in some machine translation applications re- lated techniques are exploited to obtain sentences that simultaneously realize two different conceptual representations (Knight and Langkilde, 2000). This is done in order to produce translations that preserve syntactic or semantic ambiguity in cases where the ambiguity could not be resolved when processing the source sentence. To be able to describe the above applications in an abstract way, let us first fix some terminology. The term “recognition” refers to the process of …

Content truncated to 500 words