Entry Bates:1994:RSL from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Bates:1994:RSL,
  author =       "Joseph Bates and Alon Lavie",
  title =        "Recognizing Substrings of {LR$(k)$} Languages in
                 Linear Time",
  journal =      j-TOPLAS,
  volume =       "16",
  number =       "3",
  pages =        "1051--1077",
  month =        may,
  year =         "1994",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Fri Jan 5 07:58:42 MST 1996",
  bibsource =    "Compiler/TOPLAS.bib;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/0164-0925/177768.html",
  abstract =     "LR parsing techniques have long been studied as being
                 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 substrings of a
                 context-free language is at least as hard as
                 recognizing full strings of the language, since the
                 latter problem easily reduces to the former. In this
                 article we present a linear-time algorithm for
                 recognizing substrings of LR(k) languages, thus showing
                 that the substring recognition problem for these
                 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.",
  acknowledgement = ack-nhfb # " and " # ack-pb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; languages",
  subject =      "{\bf F.4.2}: Theory of Computation, MATHEMATICAL LOGIC
                 AND FORMAL LANGUAGES, Grammars and Other Rewriting
                 Systems, Parsing. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors, Parsing.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Translator writing systems and compiler
                 generators. {\bf F.4.2}: Theory of Computation,
                 MATHEMATICAL LOGIC AND FORMAL LANGUAGES, Grammars and
                 Other Rewriting Systems, Grammar types. {\bf F.4.3}:
                 Theory of Computation, MATHEMATICAL LOGIC AND FORMAL
                 LANGUAGES, Formal Languages, Classes defined by
                 grammars or automata.",
}

Related entries