[Haskell-cafe] How to do reversible parsing?

Askar Safin safinaskar at mail.ru
Wed Jan 6 23:08:25 UTC 2021

Hi. How to do reversible converting between parse tree and AST?

My final task can be thought as the following reversible computation:

stream of chars <---> stream of tokens <---> parse tree <---> AST

On first piece (chars <---> tokens): I will probably just give up on
reversible lexing, so the problem is gone. :) I will write separate lexer and

On second piece (tokens <---> parse tree): printing is easy. For parsing I will
use package "Earley" from Hackage. And I will use brute force to ensure

On third piece (parse tree <---> AST): it seems to be last remaining piece. I don't
know how to get both translators in the same time.

Consider usual arithmetic language, i. e. a * (b + c). This is how parse tree may look:

data Term = Id Id | Braces LBrace Expr RBrace
data Product = Term Term | Times Product Times Term
data Expr = Product Product | Plus Expr Plus Product

As you can see this data types are direct mapping of grammar.

And this is how corresponding AST looks:

data AExpr = AId Id | ATimes AExpr AExpr | APlus AExpr AExpr

Is there some way to simultaneously write translators in both directions?

Askar Safin

More information about the Haskell-Cafe mailing list