Paper: Parsing Non-Recursive CFGs

ACL ID P02-1015
Title Parsing Non-Recursive CFGs
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2002

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.