Formal Grammars
A Journal of Mathematical Research on Formal and Natural Languages

Editor-in-chief: Carlos Martín-Vide
Special issues
Introduction
Volume 7(2004)
Volume 8(2005)
Editorial board
Aims and Scope
Subscription to the Hardcopy Edition
Submission procedure

Gap Parsing with LL(1) Grammars

EBERHARD BERTSCH
Faculty of Mathematics, Ruhr University
Universitätsstraße 150, D-44780 Bochum, Germany
e-mail: bertsch AT lpi.rub.de

 MARK-JAN NEDERHOF
Faculty of Arts, University of Groningen
P.O. Box 716, 9700 AS Groningen, The Netherlands
e-mail: markjan AT let.rug.nl

Abstract

We study the time complexity of the parsing problem for input strings that contain gaps. For context-free languages the time requirement is cubic. For restricted classes of languages given by LL(1), bidirectional LL(1), and a specific kind of XML grammars, the time requirement is bounded linearly or quadratically depending on the number of separate gaps.

 Download:
 PS file
PDF file
Copyright © 2004 GRLMC. All rights reserved.
Research Group on Mathematical Linguistics - Rovira i Virgili University
Webmaster