docs/BIBLIOGRAPHY

   1
   2 I want Gazelle to be state-of-the-art, so I've read a lot of literature that
   3 pertains to parsing.  Here is a list of the books and papers that influenced
   4 me the most as I was writing Gazelle.
   5
   6 Gries, David:  Describing an Algorithm by Hopcroft, 1972
   7    Acta Informatica, 2(2):97-109
   8
   9    This article is a bit more digestible presentation of Hopcroft's algorithm.
  10    It was useful in actually implementing the minimization algorithm in minimize.lua.
  11
  12
  13 Grune, Dick and Jacobs, Ceriel J. H.  Parsing Techniques, second edition, 2007
  14    ISBN: 9780387202488
  15
  16    This is a fabulous book that puts the whole field of parsing in perspective
  17    through its broad coverage and fantastic comparisons of parsing techniques.
  18    I didn't truly understand the difference between LL, Simple-LL and Strong-LL
  19    until I read this book.
  20
  21
  22 Hopcroft, John E.  An n log n algorithm for minimizing states in a finite automaton, 1971
  23    Available online at: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf
  24
  25    This algorithm, published in 1971, is still the best known algorithm for DFA
  26    minimization.  It is O(n log n), where all other algorithms are at least O(n^2).
  27    I use this algorithm in minimize.lua.
  28
  29
  30 Norvell, Theodore:  Parsing Expressions by Recursive Descent, 1999-2001
  31    http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
  32
  33    This article gave a good description of two specialized algorithms for doing
  34    expression parsing (operator-precedence parsing): Dijkstra's "Shunting Yard"
  35    algorithm (which I ultimately used) and another algorithm known as
  36    "Precedence Climbing."  Between this and the Wikipedia article about
  37    operator-precedence parsing, I came to the happy realization that it was
  38    possible to combine top-down and expression parsing into a single parser.
  39
  40
  41 Parr, Terence.  The Definitive ANTLR Reference, 2007
  42    ISBN: 0978739256
  43
  44    It would be foolish to embark on a project like this without learning from
  45    what came before.  I read this book and realized that Terence Parr reached
  46    a lot of the same conclusions I did about how to do practical LL parsing.
  47    I was especially keen on observing his design choices related to syntactic
  48    and semantic predicates.
  49
  50
  51 Parr, Terence.  ANTLR 3.0 Lookahead Analysis
  52    Available online at http://www.antlr.org/blog/antlr3/lookahead.tml
  53
  54    ANTLR's algorithm for calculating LL(*) lookahead turns out to be quite
  55    useful for calculating both LL(k) and LL(*).  It takes what is technically a
  56    O(2^k) problem and exploits the fact that actual lookahead is nearly always
  57    extremely sparse, and thus best found through search.
  58
  59    Before I really understood this algorithm, I devised a similar search-based
  60    algorithm, but Terence's algorithm is simpler, so I rewrote my lookahead
  61    calculation to use it.
  62
  63
  64 Scott, Michael L.  Programming Language Pragmatics, second edition, 2006
  65    ISBN: 0126339511
  66
  67    This is a textbook about programming language implementation and design.
  68    I used its NFA construction in nfa_construct.lua.
  69
  70
  71 Visser, Eelco.  Scannerless Generalized-LR Parsing, 1997
  72    Available online at: http://www.program-transformation.org/Transform/ScannerlessGeneralizedLRParsing
  73
  74    This paper introduced me to the idea of integrating lexing and parsing and
  75    the associated benefits of doing that.  Few of the details applied to my
  76    project though, since he was using GLR parsing instead of LL.
  77