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: https://github.com/pgoodman/Grail-Plus.
© 2011, 2012 Peter Goodman, all rights reserved.