4 ms·

Roslyn's parser and syntax tree is pretty amazing. You can recreate the precise source text from the parse tree up to whitespace. This sort of "bijective parsin

Roslyn's parser and syntax tree is pretty amazing. You can recreate the precise source text from the parse tree up to whitespace. This sort of "bijective parsing" is truly incredible and probably one of the cooler innovations I've seen in parsing technology. I can see a bunch of really interesting ideas that you could do with bijective parsing. For instance, imagine Rails style boilerplate generation but done at a semantics aware, within file basis. You could conceivably have a code generator that finds a class, introspects if it has the corresponding method, then generates it if not. Or imagine syntax reformatting but purely locally. Or semantically aware git diffs that can actually compare the underlying parse trees instead of just raw text. There's so much cool stuff you can do. I wish every language had a parser like this.

munificent 7y ago
Dart's parser can do this too. The formatter (dartfmt) takes advantage of this in order to preserve comments and use the original formatting as a hint to the output in some cases.
Sharlin 7y ago
Pardon me if I'm missing something, but doesn't just about any AST implementation allow recovering the source text up to whitespace – or indeed including whitespace, given that most real-world parsers have to retain lexical information in order to support reasonable diagnostic messages anyway.
- _hardwaregeek 7y ago
  I'm not sure to be honest. I suspect most parse trees preserve most of the info but not up to bijection. For instance, Ruby has ways of taking the Ripper output and generating source text but there's no guarantee that this output will be precisely the original source text. After all, the parser would need to distinguish between spaces and tabs and store them as tokens to reproduce the text fully.
- fierarul 7y ago
  > doesn't just about any AST implementation allow recovering the source text up to whitespace That's correct. Especially for parsers used in IDEs you most definitely care about exact locations of everything, including whitespace.
- Karliss 7y ago
  There is reason AST is called abstract syntax tree not just syntax tree. Many syntax details like parentheses or choice between alternative syntax forms are there only to avoid syntactic ambiguity, improve readability or historical reasons and don't affect the semantics or even error messages. It's not surprising for compiler authors to choose discarding some of the unnecessary information as early as possible to save memory.
  - ygra 7y ago
    Notable a lot of JavaScript AST libraries at least a while back omitted comments and whitespace, which is fine for writing a minifier, but horrible when trying to implement source code transformations. What I really like about Roslyn's AST (and I guess TypeScript's looks about the same) is that all those details are put into Trivia; ignoring those is just passing one flag to the visitor; you don't have to be aware of how many different types of AST nodes there are that might be ignorable. It also means that each and every whitespace and comment belongs to a syntax token instead of being other nodes interleaved with the normal nodes. This helps keeping comments where they belong even after re-arranging code in the AST – something that, e.g. ReSharper is atrociously bad at.
  - lonelappde 7y ago
    It's called abstract syntax tree because the concrete syntax is not a tree, it's an list of characters. Not because it makes semantic-invariant transformations.
    - yatac42 7y ago
      > It's called abstract syntax tree because the concrete syntax is not a tree, it's an list of characters. It's called abstract syntax tree to distinguish it from parse trees (a.k.a. concrete syntax trees).
- cf 7y ago
  Many times things like comments are dropped and names are disambiguated. Printing the tree back out would yield an equivalent program but the source code would look way different.
- Rusky 7y ago
  Many (if not most) ASTs, especially in batch compilers, do not preserve comments, whitespace, or even all of the actual syntax. Even the diagnostics information you're referring to are insufficient to reproduce the whitespace. Further, what Roslyn does is quite interesting even on top of preserving all of that. It does so in a way that lets it incrementally re-parse parts of the program without touching the rest- including position information for the rest of the file after the change, which has all shifted to match. None of this was standard practice anywhere when Roslyn was designed, though it's starting to be picked up in other projects since.
throwaway8941 7y ago
>Or imagine syntax reformatting but purely locally. You don't have to imagine it, this has been supported by IDEA for about a decade now at least for some languages (it works for Kotlin at least, I just re-checked before posting this). > Or semantically aware git diffs that can actually compare the underlying parse trees instead of just raw text. http://semanticmerge.com/ http://semanticmerge.com/

munificent 7y ago

Dart's parser can do this too. The formatter (dartfmt) takes advantage of this in order to preserve comments and use the original formatting as a hint to the output in some cases.

Sharlin 7y ago

Pardon me if I'm missing something, but doesn't just about any AST implementation allow recovering the source text up to whitespace – or indeed including whitespace, given that most real-world parsers have to retain lexical information in order to support reasonable diagnostic messages anyway.

_hardwaregeek 7y ago
I'm not sure to be honest. I suspect most parse trees preserve most of the info but not up to bijection. For instance, Ruby has ways of taking the Ripper output and generating source text but there's no guarantee that this output will be precisely the original source text. After all, the parser would need to distinguish between spaces and tabs and store them as tokens to reproduce the text fully.
fierarul 7y ago
> doesn't just about any AST implementation allow recovering the source text up to whitespace That's correct. Especially for parsers used in IDEs you most definitely care about exact locations of everything, including whitespace.
Karliss 7y ago
There is reason AST is called abstract syntax tree not just syntax tree. Many syntax details like parentheses or choice between alternative syntax forms are there only to avoid syntactic ambiguity, improve readability or historical reasons and don't affect the semantics or even error messages. It's not surprising for compiler authors to choose discarding some of the unnecessary information as early as possible to save memory.
- ygra 7y ago
  Notable a lot of JavaScript AST libraries at least a while back omitted comments and whitespace, which is fine for writing a minifier, but horrible when trying to implement source code transformations. What I really like about Roslyn's AST (and I guess TypeScript's looks about the same) is that all those details are put into Trivia; ignoring those is just passing one flag to the visitor; you don't have to be aware of how many different types of AST nodes there are that might be ignorable. It also means that each and every whitespace and comment belongs to a syntax token instead of being other nodes interleaved with the normal nodes. This helps keeping comments where they belong even after re-arranging code in the AST – something that, e.g. ReSharper is atrociously bad at.
- lonelappde 7y ago
  It's called abstract syntax tree because the concrete syntax is not a tree, it's an list of characters. Not because it makes semantic-invariant transformations.
  - yatac42 7y ago
    > It's called abstract syntax tree because the concrete syntax is not a tree, it's an list of characters. It's called abstract syntax tree to distinguish it from parse trees (a.k.a. concrete syntax trees).
cf 7y ago
Many times things like comments are dropped and names are disambiguated. Printing the tree back out would yield an equivalent program but the source code would look way different.
Rusky 7y ago
Many (if not most) ASTs, especially in batch compilers, do not preserve comments, whitespace, or even all of the actual syntax. Even the diagnostics information you're referring to are insufficient to reproduce the whitespace. Further, what Roslyn does is quite interesting even on top of preserving all of that. It does so in a way that lets it incrementally re-parse parts of the program without touching the rest- including position information for the rest of the file after the change, which has all shifted to match. None of this was standard practice anywhere when Roslyn was designed, though it's starting to be picked up in other projects since.

throwaway8941 7y ago

>Or imagine syntax reformatting but purely locally. You don't have to imagine it, this has been supported by IDEA for about a decade now at least for some languages (it works for Kotlin at least, I just re-checked before posting this). > Or semantically aware git diffs that can actually compare the underlying parse trees instead of just raw text. http://semanticmerge.com/ http://semanticmerge.com/