Parsing

When doing my own research into LR parser generation all of the sources I reviewed presented only a limited slice of the information required to get all the way to a working implementation.

So what I'm hoping to do is to provide a reference with every detail necessary to go from nothing all the way to a complete LR parser.

Specifically I'm going to describe how to get to a LALR(1) parser using the algorithm created by DeRemer and Pennello [3].

Then later I'm going to build up to a IELR(1) parser generation algorithm which expands on LALR to be able to parse all LR grammars [7].

Chapters

To build up even to LALR(1) however we need to lay some groundwork first. The content is thus split into the following chapters:

1. Definitions

Some basic definitions of terms and notation used throughout the subsequence chapters.

2. LR(0)

The process of constructing a LR(0) parser from a grammar.

Also covered:

  • Definitions of parse tables and parser items
  • The Closure of a set of items
3. LALR(1)

The process of constructing a LALR(1) parser from the LR(0) parser.

Also covered:

  • The Digraph algorithm
4. Parse Table Compression (Coming Soon)

The base/check algorithm for producing a more dense representation of the tables defining the state transitions of LR parsers.

5. IELR(1) (Coming Soon)

The process of constructing a IELR(1) parser from the LALR(0) parser.

Each chapter does very much build on the ones before it. So if you ever find yourself wondering "but what does [term]" mean, either it is defined in a previous chapter or I've made a mistake and would be happy to receive a bug report about it.

Additional Reading

Throughout the process of writing these I pulled a lot of general information from the following sources. They are well worth a read if you want to learn more.

  • On the translation of languages from left to right by Donald E. Knuth [1].

    The foundational paper on the topic.

  • Efficient LR (1) Parsers by Anderson, Eve, and Horning [2].

    This provides a great overview of everything known at the time about LR parsing, including being the earliest published source for LALR. As the original conference proceedings that proposed that algorithm are not widely available.

  • Compilers: Principles, Techniques, & Tools by Aho, Lam, Sethi, and Ullman [4].

    The "Purple Dragon" book. The textbook on compilers.

  • Practical LR(k) Parser Construction by David R. Tribble [5].

    A slightly incomplete article on the same topic. Works through examples in exceptional detail. Note that the Honalee Algorithm described here unfortunately has some flaws discussed in [7]. It is very clean and simple compared to most alternatives, so this is a shame.

  • The bison parser generator.

    If you are working through this yourself I highly recommend reviewing the generated parser states for various example grammars using a tool like bison.

    The task of generating states for even a tiny parser is daunting for a human, and the states for such small examples are often too large to easily publish. Viewing those states provides essential context for most articles on the topic, my work included.

References

  1. D. E. Knuth, "On the translation of languages from left to right," Information and Control, vol. 8, no. 6, pp. 607-639, Jun. 1965, doi: https://doi.org/10.1016/S0019-9958(65)90426-2.
  2. T. Anderson, J. Eve, and J. J. Horning, "Efficient LR (1) parsers," Acta Informatica, vol. 2, no. 1, pp. 12-39, 1973, doi: https://doi.org/10.1007/bf00571461.
  3. F. DeRemer and T. Pennello, "Efficient Computation of LALR(1) Look-Ahead sets," ACM Transactions on Programming Languages and Systems, vol. 4, no. 4, pp. 615-649, Oct. 1982, doi: https://doi.org/10.1145/69622.357187.
  4. A. V. Aho, M. S. Lam, Ravi Sethi, and J. D. Ullman, Compilers: Principles, Techniques, & Tools, 2nd ed. Boston, MA, USA: Pearson, 2007.
  5. D. R. Tribble, "Practical LR(k) Parser Construction", Dec, 12, 2004, [Online]. Available: http://david.tribble.com/text/lrk_parsing.html
  6. J. Gregg. (2021). Shift-Reduce Parsers [Online]. Available: https://www2.lawrence.edu/fast/GREGGJ/CMSC515/Parsing/LR.html
  7. J. E. Denny and B. A. Malloy, "IELR(1): practical LR(1) parser tables for non-LR(1) grammars with conflict resolution," in ACM symposium on Applied computing, 2008, pp. 240-245, doi: https://doi.org/10.1145/1363686.1363747.
  8. Bison, the GNU Compiler Compiler. (v3.8.2). GNU Project. [Online]. Available: https://savannah.gnu.org/projects/bison.