zbMATH — the first resource for mathematics

On parsing and condensing substrings of LR languages in linear time. (English) Zbl 0984.68093
Summary: LR parsers have long been known as being an efficient algorithm for recognizing deterministic context-free grammars. In this article, we present a linear-time method for parsing substrings of LR languages. The algorithm depends on the LR automaton which is used for the usual parsing of complete sentences. We prove the correctness and linear complexity of our algorithm and present an interesting extension of our substring parser that allows to condense the input string, which increases the speed when reparsing that string for a second time.

68Q42 Grammars and rewriting systems
Full Text: DOI
[1] Aho, A.V.; Ullman, J.D., The theory of parsing, translation and compiling, vol. 1, parsing, (1972), Prentice-Hall Englewood Cliffs, NJ · Zbl 0264.68032
[2] Bates, J.; Lavie, A., Recognizing substrings of LR\((k)\) languages in linear time, ACM trans. program. languages systems, 16, 3, 1051-1077, (1994)
[3] Clarke, G.; Barnard, D.T., An LR substring parser applied in a parallel environment, J. parallel distributed comput., 35, 2-17, (1996) · Zbl 0855.68054
[4] Cormack, G.V., An LR substring parser for noncorrecting syntax error recovery, ACM sigplan, 24, 7, 161-169, (1989)
[5] Richter, H., Noncorrecting syntax error recovery, ACM trans. program. languages systems, 7, 3, 478-489, (1985) · Zbl 0604.68099
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.