Journal of the Association for Computing Machinery, Vol. 43, No. 3, May 1996, pp. 524–554.

Linear-Time Suffix Parsing for Deterministic Languages

MARK-JAN NEDERHOF

AND

EBERHARD BERTSCH

Abstract. We present a linear-time algorithm to decide for any fixed deterministic contextfree language L and input string w whether w is a suffix of some string in L. In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to process incorrect input in linear time.

Categories and Subject Descriptors. D.3.4 [Programming Languages]: Processors— parsing; F.4.2 [Mathematical Logic and Formal Languages]: Grammars and Other Rewriting Systems—parsing

General Terms. Theory, Verification

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.