Tutorial: LR(1) Parser Generator HYACC

Tutorial at the International Symposium on Code Generation and Optimization (CGO 2012)
Xin Chen
March 31, 2012
San Jose, California

About HYACC

The space and time cost of Knuth’s canonical LR parser generation is high and has long been a myth since 1965. Robust and effective LR(1) parser generators are rare to find. Started in 2006 and towards most recently, we employed the Knuth canonical algorithm, Pager’s practical general method, lane-tracing algorithm, and other relevant algorithms, implemented an efficient, practical and open-source parser generator Hyacc (http://hyacc.sourceforge.net), which supports full LR(0)/LALR(1)/LR(1) and partial LR(k). Hyacc is compatible with Yacc and Bison in command line interface and input/output format. Hyacc is more advanced than Yacc and Bison in that it employs the more powerful LR(1) algorithm instead of LALR(1) algorithm. Hyacc is implemented in ANSI C, is highly efficient, can be easily ported to unix/linux, mac, windows and many other platforms, and can be easily picked up by anyone familiar with Yacc or Bison. We believe Hyacc is a very useful tool and should benefit the parser generation community.

Tutorial Objective

This tutorial introduces the LR(1) Parser Generator Hyacc. The audience will gain an in-depth knowledge of both the practical usage and internal workings of Hyacc.

Target Audience

• Compiler generator writers and practitioners.
• Researchers and educators in compiler theory and practice, especially those interested in front-end parser generation.
• Students interested in compiler theory and/or who are taking compiler courses.

Tutorial Schedule

Morning: the practical side of Hyacc.

• 08:30 - 09:15 : Introduction [PPT]
  • Overview
  • Problem and Motivation
  • Literature Review
  • Approach and Results
  • Related work
  • Contributions and Limitations
• 09:15 - 10:00 : Implementation [PPT]
  • Architecture
  • Parse engine
  • Storing the parsing table
  • Handling precedence and associativity
  • Error handling
  • Data structures
  • Future work
  • Discussion
• 10:00 - 10:30 : Coffee break
• 10:30 - 12:00 : Usage [PPT]
  • The Project website: http://hyacc.sourceforge.net
  • What is Hyacc, and why it is special
  • Features
  • Download
  • Readme.PDF
  • Hyaccmanpage.html
  • License
  • History
  • References
  • Example
  • Discussion

Afternoon: the internal workings of Hyacc.

• 12:00 - 01:00 : Lunch break
• 01:00 - 03:00 : Theory [PPT]
  • Knuth Canonical LR(1) Algorithm
  • Pager's LR(1) Practical General Method
  • Pager's LR(1) Lane-tracing Algorithm
  • Pager's Unit Production Elimination Algorithm
  • Edge-pushing LR(k) algorithm
  • Discussion
• 03:00 - 03:30 : Afternoon break
• 03:30 - 04:30 : Theory, and wrap up

Presenter Bio

Xin Chen is a PanSTARRS PSPS Software Engineer at the Institute for Astronomy at the University of Hawaii, where the PanSTARRS project aims to find asteroids and comets that possibly can pose danger to the earth. Xin received his PhD in Computer Science from the University of Hawaii in 2009, concentrated on reduced-space LR compiler generation theory and practice. HYACC is a software released from his PhD work. Before this, Xin earned his MS in Computer Science from the University of Hawaii in 2003, and BS in Biology from Tsinghua University in Beijing in 1998.

Further reading

1. Donald Knuth. On the translation of languages from left to right. Information and Control, 8(6):607–639, 1965.
2. David Pager. The lane tracing algorithm for constructing LR(k) parsers. In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 172 – 181, Austin, Texas, United States, 1973.
3. David Pager. The lane-tracing algorithm for constructing LR(k) parsers and ways of enhancing its efficiency. Information Sciences, 12:19–42, 1977.
4. David Pager. A practical general method for constructing LR(k) parsers. Acta Informatica, 7:249 – 268, 1977.
5. Xin Chen. LR(1) Parser Generator Hyacc. Available: http://hyacc.sourceforge.net
6. Xin Chen, David Pager. LR(1) Parser Generator Hyacc. In Proceedings of the 2011 International Conference on Software Engineering Research and Practice, p.471-477. Las Vegas, July 18-21, 2011. Available:
7. Xin Chen, David Pager. The Edge-Pushing LR(k) Algorithm. In Proceedings of the 2011 International Conference on Software Engineering Research and Practice, p.490-495. Las Vegas, July 18-21, 2011. Available:
8. Xin Chen, David Pager. Full LR(1) Parser Generator Hyacc And Study On The Performance of LR(1) Algorithms. In Proceedings of The Fourth International C* Conference on Computer Science & Software Engineering, p.83-92. Montreal, Canada, May 16-18, 2011. Available: ACM digital library or