Entry Ancona:1991:ECL 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{Ancona:1991:ECL,
  author =       "M. Ancona and G. Dodero and V. Gianuzzi and M.
                 Morgavi",
  title =        "Efficient Construction of {LR$(k)$} States and
                 Tables",
  journal =      j-TOPLAS,
  volume =       "13",
  number =       "1",
  pages =        "150--178",
  month =        jan,
  year =         "1991",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Fri Jan 5 07:58:42 MST 1996",
  bibsource =    "Compiler/Compiler.Lins.bib; Compiler/TOPLAS.bib;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib;
                 Misc/IMMD_IV.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/0164-0925/102809.html",
  abstract =     "A new method for building LR($k$) states and parsing
                 tables is presented. The method aims at giving a
                 feasible construction of a collection of LR($k$)
                 parsing tables, especially when $k > 1$. for nontrivial
                 grammars. To this purpose, the algorithm first attempts
                 to build a set of {\em normal states\/} for the given
                 grammar, each one associated to a single parsing action
                 in {\em accept, reduce, shift}. When such an action
                 cannot be uniquely determined, that is, when up to $k$
                 input symbols have to be examined (inadequacy), further
                 states, belonging to a new type, called {\em
                 look-ahead\/} states, are computed. The action
                 associated with inadequate states is a new parsing
                 action, {\em look}. States are built without actual
                 computation of the FIRST${}_k$ and EFF${}_k$ functions;
                 that is, nonterminals are kept in the context string of
                 items composing each state, and their expansion to
                 terminals is deferred until indispensable to solve
                 inadequacy. The aforementioned method is illustrated;
                 then the canonical collection of states and the
                 canonical tables are compared with those obtained from
                 the proposed method. A sufficient condition is stated,
                 by which the size of parsing tables, obtained by
                 applying this new method, is smaller than that of
                 canonical tables. Experimental results show that such a
                 condition is verified by the grammars of several
                 programming languages and that significant speed is
                 gained by avoiding the computation of the FIRST${}_k$
                 function.",
  acknowledgement = ack-nhfb # " and " # ack-pb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; experimentation; languages; theory;
                 verification",
  subject =      "{\bf F.4.2}: Theory of Computation, MATHEMATICAL LOGIC
                 AND FORMAL LANGUAGES, Grammars and Other Rewriting
                 Systems, Parsing. {\bf F.4.2}: Theory of Computation,
                 MATHEMATICAL LOGIC AND FORMAL LANGUAGES, Grammars and
                 Other Rewriting Systems, Grammar types.",
}

Related entries