Student application for Bison

[Valentin Tolmer]

Google Summer of Code Application

Name: Valentin Tolmer

E-mail: address@hidden

Project: Bison – Improve precedence and associativity declaration with partial orders

Summary: Provide a way to declare precedence and associativity of symbols with a partial order to detect unwanted conflict resolutions. Unify the precedence declaration system with the %dprec rule.

Benefits:
    The aim is to clarify the precedence and associativity declarations. With the new system, only used precedence relationships will be declared, so every relationship will be exposed to scrutiny, thus limiting the risk of unwanted conflict resolution. This is true especially when a new symbol is added to a grammar : new conflicts may arise and be resolved silently with the former system, and it is hard to detect them and check if they are correct.
    Furthermore, the same system would be applied to the GLR's %dprec rule, allowing for more complex (and yet clearer) precedence relationships.

Deliverables:
    A new syntax (backward-compatible) for the precedence system, for both the symbol declarations and the GLR rules %dprec declarations.

Details:
    For now, the precedence information is declared with a total order, by the order in which the tokens are given precedence (and associativity). The new system will allow for partial order in the precedence relationships, through an extension of the existing syntax.
    For example, the arithmetical operators (+, -, *, /) could be defined in one part, and the logical ones (&&, ||, !) in another. Each group would have internal precedence relationships, but none in between the group. A conflict between elements of different groups would appear as an unresolved shift/reduce conflict. For now, we are forced to have a total order, so an unwanted conflict between && and + would pass unnoticed, even if the language described should not arrive at such a comparison.
    The same system could be applied to GLR parsers. Currently, at the time of the merge, if several branches are in a similar state, the merging is decided with numerical precedence and no associativity, with the %dprec rule. This could be improved by allowing the user to define labels and provide the precedence information in a declaration part (details are still to be worked out), similar to the rule precedence declarations. Then the declarations would be harmonized for both precedence systems.

Timeline:
May 27 : student selections
June : discussion with the community about the details of the new syntax, both for the symbol declarations and replacement for %dprec rules.
June 28 – July 29 (Mid-term evaluation) : Coding period. Most features of the new syntax are implemented, and basic grammars using that syntax can be interpreted.
July 30 – August 15 : Coding period. The syntax is completed, and works on the most complex grammars.
August 16 – August 31 : Testing, bugfixing, documentation. A few real-life grammars are translated to the new syntax and tested.
August 31 : Project is handed over.

Communication:
    Communication will be done via e-mail, IRC, and maybe Skype meetings with the mentor. I already talked with Akim Demaille, a co-maintainer of Bison, and he has agreed to be my mentor.
    Consultation of the community will be done via the mailing list.
    A weekly meeting with the mentor is proposed, as an occasion for direct feedback and code review. All the code will be committed on a github repository on a regular basis.

My experience:
    I am currently a student of EPITA, in Paris. I am finishing my second year, and next year I will be in the first year of the engineering cycle (3rd year after graduation). I am currently in Prague, in the Czech Technical University for a semester abroad. I already have had a good deal of programming experience, starting in the freshman year of high school, with languages such as PHP, C, C++, Visual Basic, Java, and Ocaml.
    Most of my programming experience was on my own, but I had to lead a project (developing an OCR in Ocaml with a team of 4) in the second semester of 2012. I am also creator and maintainer of the plugin CreeperHeal for the game Minecraft, an ongoing project for the past 2 years, that required me to react to customer demands and cooperate with other plugin authors.

    Furthermore, I have already worked on Bison, as an intern in the LRDE (EPITA's research lab), under the supervision of Akim Demaille. I am thus familiar with the Bison project, and the area I will be working on, as well as the open-source mentality and the way to contribute. There I learned the benefits of the commit early commit often philosophy, as well as the importance of tests.
    During this internship, I was already working on precedence and associativity, and I created a warning message for useless precedence/associativity that is now part of Bison. I also did some work to create a graph of used precedence relationships and present it in a readable way, but I did not have time to complete it. I hope to have time to finish that part before starting of my GSOC project, as it would be a useful tool to visualize the changes in the grammar, and to give ideas as to how the syntax of the new precedence system should look like.