0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ To avoid redundancy, you could have had your question migrated. $\endgroup$ – Tyson Williams Aug 20 '12 at 22:31
  • 2
    $\begingroup$ I also hate redundancy. cs.stackexchange.com/questions/3233/… $\endgroup$ – Tsuyoshi Ito Aug 21 '12 at 0:17
  • $\begingroup$ true, wanted to give the beta a shot after the comment. Imho, this is more an algorithmic, theoretical CSP than programming question. $\endgroup$ – Stefan K. Aug 21 '12 at 2:42
  • $\begingroup$ where do you guys think this question belongs? SO, CS, CS-Theory? $\endgroup$ – Stefan K. Aug 21 '12 at 2:47
  • $\begingroup$ 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). $\endgroup$ – Kaveh Aug 21 '12 at 14:56
3
$\begingroup$

If the synthesized attributes compute a parse tree, then unparsing can be done in time linear in the size of the parse tree, assuming that string concatenation happens in constant time -- the obvious recursive algorithm on the parse tree will do the job.

I would guess XText is doing backtracking in order to minimize the number of parentheses in arithmetic expressions, line breaks, or some other pretty-printing criteria. However, for most languages it's possible to do that in linear time, as well.

See Norman Ramsey, Unparsing Expressions With Prefix and Postfix Operators. Software—Practice and Experience, 28(12):1327–1356, October 1998.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.