Traditional Parsing Methods
One parsing technique that I sometimes use is Top Down Operator Precedence Parsing (TDOP). TDOP parsers have been discussed in many other places as well. Unfortunately, I have not seen TDOP described in terms of left-corner parsing (except for a passing comment in this thesis).
The purpose of this post is to set the stage for a later discussion about TDOP parsing. This post will introduce top-down and bottom-up parsing, then combine the two methods to introduce left-corner parsing. Also, the top-down parsing language (TDPL) will be briefly mentioned as its semantics relate to TDOP.
Symbolic Interpretation
Recently I worked on a project for my Optimizing Compilers course. The purpose of this project was to implement Loop-invariant Code Motion and any other compiler optimizations that we choose. The project is competitive because one's mark is based on how one's compiler improves the mean execution time on a small set of static, pre-determined test cases. Given that the test cases do not change, it is natural to specialize one's optimizations to the code being tested. Realistically, this might not be the best approach as code tends to change and compiler optimizations are not always transparent.
Dr. Sheng Yu
It is with great sadness that I report the passing of my friend, colleague, and mentor: Dr. Sheng Yu. I knew Sheng in the past three and a half years of his life. Sheng was twice my professor, twice my employer, and my undergraduate thesis supervisor.
Often I would pop in to Sheng's office on the third floor of Middlesex College at The University of Western Ontario. On his desks were towers of books and papers; it baffled me that they never fell. In his office, we would talk--sometimes for hours--about his past students and what they were up to, about parsing techniques, finite automata, regular languages and their operations, and object-oriented programming.
I prefaced each of our e-mail correspondences with the far too formal "Prof. Sheng Yu". Goodbye Prof. Sheng Yu; you will be missed.
Comment System Now Working Again
It turns out that the comment system hasn't been working since I allowed for HTML in comments. I have now fixed the commenting system.
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.