<p>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.</p>

<p>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. </p>

<p>See Norman Ramsey, <a href="http://www.cs.tufts.edu/~nr/pubs/unparse-abstract.html" rel="nofollow"><em>Unparsing Expressions With Prefix and Postfix Operators</em></a>. Software—Practice and Experience, 28(12):1327–1356, October 1998. </p>

CC BY-SA 3.0
2012-08-21T12:59:26.550Z
2012-08-21T12:59:26.550Z
Neel Krishnaswami
<h3>Abstract problem description</h3>

<p>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. <code>parse(unparse(AST)) = AST</code> should hold.  </p>

<p>This is the equal to finding a valid parse tree which would produce the same AST. </p>

<p>The language is described by a context free S-attributed grammar using a eBNF variant. </p>

<p>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)$. </p>

<p>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. </p>

<h3>Questions</h3>

<ol>
<li>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?</li>
<li>I've got the feeling this problem isn't $O(e^n)$ in general -- could some genius help me with this?</li>
</ol>

<hr>

<p>The question has been posted on <a href="https://stackoverflow.com/questions/11918961/unparse-ast-oexpn">StackOverflow</a> and <a href="https://cs.stackexchange.com/questions/3233/can-abstract-syntax-trees-be-unparsed-in-subexponential-time">Computer Science</a> without any answers.</p>

CC BY-SA 3.0
2012-08-20T22:31:52.830Z
To avoid redundancy, you could have had your question migrated.
Tyson Williams
CC BY-SA 3.0
2012-08-21T00:17:44.680Z
I also hate redundancy.  http://cs.stackexchange.com/questions/3233/can-abstract-syntax-trees-be-unparsed-in-subexponential-time
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-21T02:42:15.393Z
true, wanted to give the beta a shot after the comment. Imho, this is more an algorithmic, theoretical CSP than programming question.
Stefan K.
CC BY-SA 3.0
2012-08-21T02:47:49.910Z
where do you guys think this question belongs? SO, CS, CS-Theory?
Stefan K.
CC BY-SA 3.0
2012-08-21T14:56:07.627Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) 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).
Kaveh
CC BY-SA 3.0
2012-08-21T15:25:25.653Z
how much is sufficient time? I've postet this question on Stackoverflow, offered a bounty on the question which expired unanswered. I also added the question, as suggested to CS, which is without an reply after 3 days probably because it's a *beta*.
Stefan K.
CC BY-SA 3.0
2012-09-06T21:19:03.920Z
I reopened the question. Next time wait a week before reposting, include links in all directions, and summerize any relevant information from other posts. Also asking to answer your question on another site is not a real question but an advertisement, you should not use cstheory question to advertise your questions on other sites, therefore I am removing that part of the question. If you don't like redundancy, then next time please ask the moderators on the original site to migrate your question in place of reposting it.
Kaveh
<ds.algorithms><graph-algorithms><fl.formal-languages><parsing>
Can abstract syntax trees be unparsed in subexponential time?
Stefan K.
# Can abstract syntax trees be unparsed in subexponential time?

(Asked by: username_0 on 2012-08-20)

### 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](https://stackoverflow.com/questions/11918961/unparse-ast-oexpn) and [Computer Science](https://cs.stackexchange.com/questions/3233/can-abstract-syntax-trees-be-unparsed-in-subexponential-time) without any answers.

**Tags:** ds.algorithms, graph-algorithms, fl.formal-languages, parsing
> **Comments:**
> **username_1**: To avoid redundancy, you could have had your question migrated.  
> **username_2**: I also hate redundancy.  http://cs.stackexchange.com/questions/3233/can-abstract-syntax-trees-be-unparsed-in-subexponential-time  
> **username_0**: true, wanted to give the beta a shot after the comment. Imho, this is more an algorithmic, theoretical CSP than programming question.  
> **username_0**: where do you guys think this question belongs? SO, CS, CS-Theory?  
> **username_3**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being reposted, our [site policy](http://meta.cstheory.stackexchange.com/a/231/) 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).  
> **username_0**: how much is sufficient time? I've postet this question on Stackoverflow, offered a bounty on the question which expired unanswered. I also added the question, as suggested to CS, which is without an reply after 3 days probably because it's a *beta*.  
> **username_3**: I reopened the question. Next time wait a week before reposting, include links in all directions, and summerize any relevant information from other posts. Also asking to answer your question on another site is not a real question but an advertisement, you should not use cstheory question to advertise your questions on other sites, therefore I am removing that part of the question. If you don't like redundancy, then next time please ask the moderators on the original site to migrate your question in place of reposting it.  

---

## 1 answers

### Answer by username_4 on 2012-08-21. Score: 3

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*](http://www.cs.tufts.edu/~nr/pubs/unparse-abstract.html). Software—Practice and Experience, 28(12):1327–1356, October 1998.


---

