Yary

I think of text, grammars that parse the text, and the syntax trees (data) generated by a parser as a triangle. Most of the time in computerland, people doing something with this triangle are interested in converting a text into a tree using a parser.

Every once in a while I need to write a parser. My first serious parser was in the late 90's, for a radio station that needed each week to convert a large plain-text weekly email to tables of venues and shows. For that, I used a version of Bison (yacc) that allowed me to write actions in Perl.

These days, I'm excited to get my hands dirty in Perl6 grammars. Writing a correct parser is never easy, so a clean, well-thought-out "featureful" parser language means less effort spent on fighting the tool, more on attacking the problem.

And Perl6's grammar-to-syntax-tree is so nicely defined, it's moving me to explore an idea I've had kicking around for a while: reversible grammars. I'd like to be able to write a grammar, and then annotate and/or subclass it in such a way that it can deparse an abstract syntax tree. That's basically the reverse of what a grammar normally does. It takes the "tree" and "parser" points of the triangle to generate a "text."

For example, given a grammar that can parse simple RPN mathematical expressions, you could feed it the text "4 2 − 5 ×" and get a tree that looks like "(4 => - <= 2) => × <= 5", and reversing it would give you back the original text. Or, feeding that tree into a grammar that parses & deparses infix expressions would return something like "(4-2)×5".

I'll be working on this as I get the tuits, which means, it could be quite a while. Dear readers, do you care to recommend any reading on the subject of reversible grammars, deparsing, or decompiling? I have little theory and would like to understand the problem better, before diving into it.

And- outside the scope of what I want to work on- there's the idea of using the "tree" and "text" points of the triangle to generate a "grammar." If you already had a grammar for RPN, and were given examples of the same expression in both RPN and infix notation, you could take the tree from parsing the RPN, apply that tree to the text from the infix notation, and generate a grammar for infix. What's the name for that, and does such a beast exist?