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.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ To avoid redundancy, you could have had your question migrated. $\endgroup$
    – Tyson Williams
    Commented Aug 20, 2012 at 22:31
  • 2
    $\begingroup$ I also hate redundancy. cs.stackexchange.com/questions/3233/… $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 21, 2012 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.
    Commented Aug 21, 2012 at 2:42
  • $\begingroup$ where do you guys think this question belongs? SO, CS, CS-Theory? $\endgroup$
    – Stefan K.
    Commented Aug 21, 2012 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
    Commented Aug 21, 2012 at 14:56

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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