AbstractWe present a linear-time algorithm to decide for any fixed deterministic context-free 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.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
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
Selected references
- A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Time and tape complexity of pushdown automaton languages. Information and Control, 13(3):186-206, September 1968.
- Joseph Bates and Alon Lavie. Recognizing substrings of LR(k) languages in linear time. ACM Transactions on Programming Languages and Systems, 16(3):1051-1077, May 1994.
- J. Earley. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94-102, February 1970.
- Charles N. Fischer and Jon Mauney. A simple, fast, and effective LL(1) error repair algorithm. Acta Informatica, 29(2):109-120, 1992.
- Susan L. Graham, Michael A. Harrison, and Walter L. Ruzzo. An improved context-free recognizer. ACM Transactions on Programming Languages and Systems, 2(3):415-462, July 1980.
- René Leermakers. Recursive ascent parsing: from Earley to Marcus. Theoretical Computer Science, 104(2):299-312, 12 October 1992. Note.
- Hans Leiss. On Kilbury's modification of Earley's algorithm. ACM Transactions on Programming Languages and Systems, 12(4):610-640, October 1990.
- Helmut Richter. Noncorrecting syntax error recovery. ACM Transactions on Programming Languages and Systems, 7(3):478-489, July 1985.