Abstract problem descriptionThe 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. QuestionsIs 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?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. 
Can abstract syntax trees be unparsed in subexponential time?
algorithms;compilers;parsers;attribute grammars