- 著者
- Joseph Bates, Alon Lavie
- タイトル
- Recognizing Substring of LR(k) Languages in Linear Time
- 日時
- October 1991
- 概要
- 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.
- カテゴリ
- CMUTR

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