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.