Grail+ is a set of command line tools for manipulating non-deterministic finite automata (NFAs), non-deterministic pushdown automata (PDAs), and context-free grammars (CFGs). Grail+ is built on top of the Formal Language Template Library (FLTL), a library for representing and symbolically manipulating CFGs, NFAs, and PDAs.


Grail+ supports the following tools:

Parse some text according to an arbitrary CFG. Grail+ implements an Earley parser. Notably, variable terminals are automatically unified with tokens that cannot be resolved to any terminals.
Transform a CFG so as to remove all (in)direct left recursion.
Construct an NFA representing the language of all of the configurations of the stack that a top-down parser could generate by parsing according to the inputted CFG.
Convert a CFG into Chomsky Normal Form.
Convert a CFG into Greibach Normal Form.
Convert a CFG into an ε-PDA accepting the same language of the inputted CFG.
Output the basic structure of an LL(1) parser for the inputted CFG. The output language is the C programming language.
Output the dominator tree of an NFA as another NFA.
Output an NFA as a DOT digraph. This is suitable for visualization of NFAs using tools like GraphViz.
Output an NFA that accepts the intersection of the languages accepted by the inputted PDA and NFA.
Convert a PDA into a CFG that generates the same language accepted by the PDA.


The current version of Grail+ was developed by Peter Goodman as his undergraduate thesis under the supervision of the late Dr. Sheng Yu.

Grail+ is currently being used as a basis for research into greedy left corner parsers.

License and Download

Grail+ is licensed under the MIT License. The source code of Grail+ can be found at GitHub:

© 2011, 2012 Peter Goodman, all rights reserved.