Can abstract syntax trees be unparsed in subexponential time?

Question

Abstract problem description

The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. parse(unparse(AST)) = AST should hold.

This is the equal to finding a valid parse tree which would produce the same AST.

The language is described by a context free S-attributed grammar using a eBNF variant.

So the unparser has to find a valid 'path' through the traversed nodes in which all grammar constraints hold. This bascially means to find a valid allocation of AST nodes to grammar production rules. This is a constraint satisfaction problem (CSP) in general and could be solved, like parsing, by backtracking in $O(e^n)$.

Fortunately for parsing, this can be done in $O(n^3)$ using GLR (or better restricting the grammar). Because the AST structure is so close to the grammar production rule structure, I was really surprised seeing an implementation where the runtime is worse than parsing: XText uses ANTLR for parsing and backtracking for unparsing.

Questions

1. Is a context free S-attribute grammar everything a parser and unparser need to share or are there further constraints, e.g. on the parsing technique / parser implementation?
2. I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?

I didn't receive an answer for this question on StackOverflow. It was suggested to ask here, but I hate redundancy, so I hope you forgive me for asking you to answer here.

Answer 1

There is a version of your question for which unparsing is easy and can be done in linear time. However, I'm not entirely sure if your question pertains to this specific version of unparsing, so I'll look at that first.

You say in your question over at StackOverflow that your AST looks like "AnyObject -> AnyObject -> Vehicle [name="Car"]". Your question would be a lot easier if your AST looks like "Area -> Highway -> Car", that is, that we know which productions were taken when your AST was constructed/parsed. In ordinary context-free parsers, you (almost) always get this information: you might decide to throw it away, but (nearly) all parsing algorithms can also give you this information.

If you don't have this information, I'm pretty sure exponential time is the best you can do, unless you know something about your S-expressions. The problem then is simply recovering the "Area -> Highway -> Car" AST, the unparsing after that is the easy part.

If you do have this information, then we can just look at context-free grammars and try to unparse them. Consider this grammar:

1: $S \to a$
2: $S \to a S a$

An AST for this grammar may look like $S \to a (S \to a) a$, on input "aaa". Unparsing this AST is easy: perform a postorder walk of the tree and output all terminals found in this walk. The result is "aaa" again.

Things become a bit more complicated when you look at ambiguous context-free grammars. On one hand, things are still easy: you just pick any parse tree of your input and do the above: you can reconstruct all other parse trees from the result.

However, in the presence of disambiguation rules, you have to do something clever. In particular, the input "(1+2)*3" may be unparsed as "1+2*3", which is different from the original. It is possible to do this in linear time on $LR(1)$ grammars (where precedence and associativity are enforced like in Yacc) by doing a reverse $LR$ parse at unparse time. I'll skip the details, as this was not part of your question, but it can be done.