Status Update + IPG
Not much happened on this blog and c3wife's blog lately because I was back at work at Beenox for 3 months. They urgently needed someone for a specific task and I was happy to get back to work for a short time, giving me time to think about the next steps for C3. My sabbatical will be extended to December 2011, making it a complete year as scheduled.
Since my return at home, I worked on IPG and I decided that I would complete this project before continuing work on C3. I think the best thing to do now is to get things rolling as soon as possible. I hope to get experience with the dynamics of releasing open source software and hopefully accepting patches and interacting with users and collaborators.
IPG stands for "Incremental Parser Generator". The basic idea is to create a parser generator (such as Yacc or Bison) but with a few twists:
- Its input is a PEG (Parsing Expression Grammar) instead of a CFG (Context-Free Grammar).
- It generates a Recursive Descent Parser that is easy to read, understand, and debug instead of a bunch of compressed tables (See "Understanding C parsers generated by GNU Bison")
- No semantic actions are embedded in the grammar. Instead, an interface is provided to traverse the parse tree. It may seem to waste memory but in fact the parse tree is kept in a minimalist data structure that I need to keep around anyway for Packrat Parsing.
- If the input text changes, the parse tree is locally updated instead of reparsing the whole text. This is the "Incremental" part.
IPG was created to implement the following design choices for C3:
- Have a single grammar for multiple purposes: easily modifiy the syntax, generate the parser (potentially in many languages), learn the syntax
- Have a single code path for all parsing needs: compilation, syntax-highlighting, refactoring, etc.
- Have a completely incremental process from code to execution (that can happen on the fly)
The current implementation generates C++ code. One interesting property is that the interface to traverse the parse tree is an STL-style iterator, making the client code very clean and terse. I will continue to work improving the interface and implementation but I will soon make a real first release.
