Can abstract syntax trees be unparsed in subexponential time?
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.