On parsing and condensing substrings of LR languages in linear time

AbstractLR 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. [-4pt