I/O Reader

RSS Feed

Peter Goodman's blog about PHP, Parsing Theory, Applications, Javascript, Functional Programming,

Undergraduate Thesis Report Finished!

Update: Grail+ is now on GitHub at https://github.com/pgoodman/Grail-Plus.

Well, I've finally submitted my undergraduate thesis project's final report. My project was to develop the newest version of Grail+. Grail+ is a set of command line tools for manipulating non-deterministic finite automata (ε-NFAs), non-deterministic pushdown automata (ε-NPDAs), and context-free grammars (CFGs). Grail+ is built on top of the Formal Language Template Library (FLTL), a library that I developed for representing and symbolically manipulating CFGs, ε-NFAs, and ε-NPDAs. Over the past several months I've worked hard and built Grail+ and the FLTL from the ground up. Together, they represent around 12,000 lines of C++.

My report can be found here. The report is 49 pages long. For anyone reading this blog, the most interesting part of the report is the implementation discussion. Unfortunately, I had to leave a lot out of the report as it is already quite long. As such, the API described in the report is incomplete and some of the interesting discussions were cut short.

I have licensed Grail+ under the MIT License. I am interested in collaborating with others to continue the development of the project. The source code of Grail+ can be found here.