Category: CMUTR
Institution: Department of Computer Science, Carnegie
        Mellon University
Abstract: LR parsing techniques have long been studied as efficient and 
        powerful methods for processing context free languages. A linear
        time algorithm for recognizing languages representable by LR(k) 
        grammars has long been known. Recognizing substings of a context
        -free language is at least as hard as recognizing full strings 
        of the languages, as the latter problem easily reduces to the 
        former. In this paper we present a linear time algorithm for 
        recognizing substrings of LR(k) languages, thus showing that 
        the substring recognition problem for theses languages is no 
        harder than the full string recognition problem. An interesting 
        data structure, the Forest Structured Stack, allows the 
        algorithm to track all possible parses of a substring without 
        loosing the efficiency of the original LR parser. We present the
        algorithm, prove its correctness, analyze its complexity, and 
        mention several applications that have been constructed.
        
        
Number: CMU-CS-91-188
Bibtype: TechReport
Month: oct
Author: Joseph Bates
        Alon Lavie
Title: Recognizing Substring of LR(k) Languages in Linear Time
Year: 1991
Address: Pittsburgh, PA
Super: @CMUTR