What is Hyacc | Features | Example | Download | License | References | Contact

What is Hyacc, and why it is special

Many people have used Yacc. It is a LALR(1) parser generator, often used with the lexical analyzer Lex to create compilers. There are many variations of Yacc, most famous ones are like Bison and Byacc (Berkely yacc). The problem with LALR(1) parser generators is that they contain "mysterious" reduce/reduce conflicts even for deterministic and unambiguous grammars, and these require the language designer to tweak the grammar which is often a time-consuming and painful process, and the resulted grammar may not be the same as before modification.

Hyacc is similar to Yacc in that it is a parser generator. It is different from yacc in that it is a LR(1) parser generator, which means it can accept all LR(1) grammars. This is more powerful than LALR(1) algorithm. A LR(1) parser generator also does not have the "mysterious reduce/reduce conflict" problem.

The general problem of LR(1) parser generation is that the original Knuth's canonical LR(k) algorithm was too expensive in time and space to be practical. Pager's algorithm [1] in 1977 based on the concept of "weak compatibility" reduces the size of the parsing table and makes canonical LR(1) parser generation practical. Hyacc shows that, with Pager's algorithm and proper use of data structures, the performance of a LR(1) parser generator can be close to LALR(1) parser generators.

Hyacc is pronounced as "HiYacc", means Hawaii Yacc.

Specifically, based on the original Knuth LR(1) algorithm, three optimizations are used:

  1. Combine compatible states. [1]
  2. Remove unit productions. [2]
  3. Further remove repeated states after the previous step.

Hyacc tries the best to be compatible with Yacc and Bison in the format of input file and command line switches. So anyone used Yacc or Bison before should be able to start using Hyacc immediately.

Hyacc is ANSI C compliant, which makes it extremely easy to port to any platform.


Current features: What's not working and to be implemented:


Here is a yacc input file calc.y for an infix notation calculator, modified from an example from Bison's online document.

Type the command: hyacc calc.y -v -t -g -D0
-v asks for the generation of y.output
-D0 asks for printing all the relevant information into y.output
-t asks for generating y.parse that contains all the parsing details when the generated parser parses an input.
-g asks for generating y.gviz that can be used as input file to graphviz.

The generated files are:, y.output and y.gviz.
Using graphviz, based on the genereated file y.gviz, this is the graphviz-generated parsing machine.
Now compile with a C compiler, which gives calc.exe.
Use the input file input.txt (don't forget the newline at the end), type: calc < input.txt
The answer is given in the standard output as:
# 25
and a y.parse file is generated, which shows the parsing process for the formular in input.txt.


Hyacc can be compiled and used in Unix, Linux and Windows, or any system that supports ANSI C.

Documentations (included in the source packages): readme.pdf, hyaccmanpage

Source package: Hyacc project page. Or directly go to the download page.

If you used Hyacc on a complex grammar, you can help me by providing these information.


Hyacc source code is released under the GPL license.

The only exception is the parser engine file "hyaccpar", which is released under the BSD license. This guarantees that the generated parser can be used in both open source and commercial softwares. A similar situation was addressed by Richard Stallman in the release notes of Bison 1.23 and 1.24.


  1. Pager, D., A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977)
  2. Pager, D., Eliminating Unit Productions from LR Parsers. Acta Informatica 9, 31 - 59 (1977)
Other implementations of [1].
  1. Implementation in Forthan: LR. By C. Wetherell and A. Shannon (1981)
  2. Implementation in Objective Caml: Menhir. By François Pottier and Yann Régis-Gianas (2004 ~ 2007)
  3. Implementation in Python. By Jason Evans (2007)


Please contact chenx AT hawaii DOT edu for any comments or bug report.

This page is also hosted at

Copyrighted (2007, 2008) @
X.C. Created on: 8/26/2007, Last modified: 2/9/2008