Grail+

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.

Tools

Grail+ supports the following tools:

cfg-parse
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.
cfg-remove-lr
Transform a CFG so as to remove all (in)direct left recursion.
cfg-stack-lang
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.
cfg-to-cnf
Convert a CFG into Chomsky Normal Form.
cfg-to-gnf
Convert a CFG into Greibach Normal Form.
cfg-to-pda
Convert a CFG into an ε-PDA accepting the same language of the inputted CFG.
cfg-to-ll1
Output the basic structure of an LL(1) parser for the inputted CFG. The output language is the C programming language.
nfa-dominators
Output the dominator tree of an NFA as another NFA.
nfa-to-dot
Output an NFA as a DOT digraph. This is suitable for visualization of NFAs using tools like GraphViz.
pda-intersect-nfa
Output an NFA that accepts the intersection of the languages accepted by the inputted PDA and NFA.
pda-to-cfg
Convert a PDA into a CFG that generates the same language accepted by the PDA.

About

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.