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.

Click Here to View the Paper In XML Format