Lindsey Kuper (lindseykuper) wrote,
Lindsey Kuper

Invertible parsing and pretty-printing

At my job last summer, I'd occasionally hear people say that pretty-printing is the opposite of parsing. They were probably referring specifically to the opposite of parsing-assembly-instructions-to-ASTs, but they could have meant parsing in the more general sense of going from concrete syntax to abstract syntax.

I'd forgotten about the opposite-of-parsing thing until today, when I noticed this paper that just turned up on Lambda the Ultimate. The paper points out that parsing and pretty-printing aren't quite inverses, because several concrete representations can map onto the same abstract representation, but you typically don't want your pretty-printer to spit out all the possible concrete representations, so you have to pick one (the "nicest", whatever that means).1 But the paper's clever idea is that even though they aren't inverses, we don't have to throw up our hands in defeat and implement a language's parser and pretty-printer entirely separately; instead, we can just implement one thing -- which the paper calls a "syntax description" -- and then put a different interface on it to get a parser or pretty-printer as desired.

For the world's five logic programmers, who would read that and say, "Oh, yeah, sure, I do that sometimes; I call it programming," the authors get in a special dig; in section 4.3, they write, "in contrast to logic programming[, our model of] invertibility can actually be made to work in practice." Burn!

  1. I guess this would mean that the parser and pretty-printer for a language together comprise a Galois connection. As so often. But, as so often, I'm not sure what knowing that something is a Galois connection is good for.

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded