Can abstract syntax trees be unparsed in subexponential time?

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?

The question has been posted on StackOverflow and Computer Science without any answers.

• To avoid redundancy, you could have had your question migrated. Aug 20 '12 at 22:31
• I also hate redundancy. cs.stackexchange.com/questions/3233/… Aug 21 '12 at 0:17
• true, wanted to give the beta a shot after the comment. Imho, this is more an algorithmic, theoretical CSP than programming question. Aug 21 '12 at 2:42
• where do you guys think this question belongs? SO, CS, CS-Theory? Aug 21 '12 at 2:47
• It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). Aug 21 '12 at 14:56