Entry Wagner:1998:EFI 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{Wagner:1998:EFI,
  author =       "Tim A. Wagner and Susan L. Graham",
  title =        "Efficient and Flexible Incremental Parsing",
  journal =      j-TOPLAS,
  volume =       "20",
  number =       "5",
  pages =        "980--1013",
  month =        sep,
  year =         "1998",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Mon Mar 1 10:04:11 MST 1999",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  URL =          "http://www.acm.org:80/pubs/citations/journals/toplas/1998-20-5/p980-wagner/",
  abstract =     "Previously published algorithms for LR ($k$)
                 incremental parsing are inefficient, unnecessarily
                 restrictive, and in some cases incorrect. We present a
                 simple algorithm based on parsing LR($k$) sentential
                 forms that can incrementally parse an arbitrary number
                 of textual and/or structural modifications in optimal
                 time and with no storage overhead. The central role of
                 {\em balanced sequences\/} in achieving truly
                 incremental behavior from analysis algorithms is
                 described, along with automated methods to support
                 balancing during parse table generation and parsing.
                 Our approach extends the theory of sentential-form
                 parsing to allow for {\em ambiguity\/} in the grammar,
                 exploiting it for notational convenience, to denote
                 sequences, and to construct compact (``abstract'')
                 syntax trees directly. Combined, these techniques make
                 the use of automatically generated incremental parsers
                 in interactive software development environments both
                 practical and effective. In addition, we address {\em
                 information preservation\/} in these environments:
                 Optimal node reuse is defined; previous definitions are
                 shown to be insufficient; and a method for detecting
                 node reuse is provided that is both simpler and faster
                 than existing techniques. A program representation
                 based on {\em self-versioning documents\/} is used to
                 detect changes in the program, generate efficient
                 change reports for subsequent analyses, and allow the
                 parsing transformation itself to be treated as a
                 reversible modification in the edit log.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; languages; performance; theory",
  subject =      "{\bf D.2.6} Software, SOFTWARE ENGINEERING,
                 Programming Environments, Interactive environments.
                 {\bf D.2.7} Software, SOFTWARE ENGINEERING,
                 Distribution, Maintenance, and Enhancement, Version
                 control. {\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 E.1}
                 Data, DATA STRUCTURES, Trees.",
}

Related entries