4 ms·

I'd love for a post on reproducible, incremental parse trees. Roslyn, Rust Analyzer, et al use them to provide good language server facilities. Basically their

I'd love for a post on reproducible, incremental parse trees. Roslyn, Rust Analyzer, et al use them to provide good language server facilities. Basically their parse trees are immutable and can recover the entire source file, comments and all. These allow for fast parsing that can be used to do code modification and good semantic analysis. Another area that should be mentioned is purposefully messy grammars. A common addition to languages these days are arrow functions: (a, b, c) => { ... These are really nice for defining functions, but they usually cause unbounded lookahead. For instance in JavaScript, the arguments list can also be parsed as a comma expression inside parentheses. In my language they can be parsed as a tuple expression. There might be some tricky way of doing this with an LR parser, but I can't figure it out. Therefore I needed to parse arrow functions/tuples by basically assuming they're an arrow function, then if I'm mistaken, I convert my parameters list into a tuple expression and continue parsing. For instance: (a, b, 10) When we hit the 10, my parser goes "ah shoot, this is a tuple" and converts the (a, b to be expressions in a tuple. Some may argue that grammars should just stay within LR/LALR/LL, but I do think adding a little bit of parsing complexity for ease of use is a worthy tradeoff.

DylanSp 6y ago
To your first point, I've got a couple of bookmarks: - Query-based compiler architecture: https://ollef.github.io/blog/posts/query-based-compilers.html https://ollef.github.io/blog/posts/query-based-compilers.htm... - Lezer [a parsing system used by CodeMirror]: https://marijnhaverbeke.nl/blog/lezer.html https://marijnhaverbeke.nl/blog/lezer.html - Anders Hejlsberg on Modern Compiler Construction: https://www.youtube.com/watch?v=wSdV1M7n4gQ https://www.youtube.com/watch?v=wSdV1M7n4gQ
- hardwaregeek 6y ago
  I'm familiar with the first and last link. I'd love for there to be a centralized resource or even working group on these ideas. More and more people are learning and implementing them but they're still limited to the cutting edge compiler authors and the CS equivalent of mathematical folklore.
mathgladiator 6y ago
What do you mean by incremental? I recently hand-wrote my own parser so I could achieve some these results. Having used parser generators in the past, I realize now that hand writing a parser is SO much more flexible.
- hardwaregeek 6y ago
  Lots of these parsers figure out what changed and only reparse the difference. This is pretty important if the parser is powering a language server, as reparsing needs to happen while the user is typing, so that autocomplete and other features work.
drakmaniso 6y ago
I believe the way it's usually done is to always parse a tuple, then parse the arrow as a binary operator applied to the two surrounding expressions. This potentially produce a syntactically incorrect AST (e.g. if there is an arrow following a tuple containing numbers), so you need to detect those in another pass and produce the corresponding error.
- tgv 6y ago
  Can be done in one go: just check the type of the left and right operand at the end of X -> expr "=>" expr, or assign "=>" the highest priority when following a tuple, X -> tuple ("=>" "{" body "}")?.
- hardwaregeek 6y ago
  What's subtly tricky about my language is that not all function arguments are valid expressions. For instance I allow: (a: int, b: float, c) => { .... which is not a valid tuple expression. Just had to make my life harder haha
UncleEntity 6y ago
Something like: expr ::= <all the other expressions> | '(' [ expr { ',' expr } ] ')' | '{' { expr } '}' | expr '=>' expr | identifer '(' expr { ',' expr } ')' | literal Tried adding it to the javascript grammar I play with and the parser generator (Coco/R) didn't complain about conflicts -- though it doesn't have tuples so YMMV. --edit-- Played with it a bit more and added tuples (as a replacement for '(' expr ')' grouping expression (exactly like the now-edited example above) and it still seems happy. If I were to add this to the grammar for real I'd have to monkey around with it some more to ensure there was an actual '(' ... ')' expression before the => but seems easily doable by transforming the grammar a bit.

DylanSp 6y ago

To your first point, I've got a couple of bookmarks: - Query-based compiler architecture: https://ollef.github.io/blog/posts/query-based-compilers.html https://ollef.github.io/blog/posts/query-based-compilers.htm... - Lezer [a parsing system used by CodeMirror]: https://marijnhaverbeke.nl/blog/lezer.html https://marijnhaverbeke.nl/blog/lezer.html - Anders Hejlsberg on Modern Compiler Construction: https://www.youtube.com/watch?v=wSdV1M7n4gQ https://www.youtube.com/watch?v=wSdV1M7n4gQ

hardwaregeek 6y ago
I'm familiar with the first and last link. I'd love for there to be a centralized resource or even working group on these ideas. More and more people are learning and implementing them but they're still limited to the cutting edge compiler authors and the CS equivalent of mathematical folklore.

mathgladiator 6y ago

What do you mean by incremental? I recently hand-wrote my own parser so I could achieve some these results. Having used parser generators in the past, I realize now that hand writing a parser is SO much more flexible.

hardwaregeek 6y ago
Lots of these parsers figure out what changed and only reparse the difference. This is pretty important if the parser is powering a language server, as reparsing needs to happen while the user is typing, so that autocomplete and other features work.

drakmaniso 6y ago

I believe the way it's usually done is to always parse a tuple, then parse the arrow as a binary operator applied to the two surrounding expressions. This potentially produce a syntactically incorrect AST (e.g. if there is an arrow following a tuple containing numbers), so you need to detect those in another pass and produce the corresponding error.

tgv 6y ago
Can be done in one go: just check the type of the left and right operand at the end of X -> expr "=>" expr, or assign "=>" the highest priority when following a tuple, X -> tuple ("=>" "{" body "}")?.
hardwaregeek 6y ago
What's subtly tricky about my language is that not all function arguments are valid expressions. For instance I allow: (a: int, b: float, c) => { .... which is not a valid tuple expression. Just had to make my life harder haha

UncleEntity 6y ago

Something like: expr ::= <all the other expressions> | '(' [ expr { ',' expr } ] ')' | '{' { expr } '}' | expr '=>' expr | identifer '(' expr { ',' expr } ')' | literal Tried adding it to the javascript grammar I play with and the parser generator (Coco/R) didn't complain about conflicts -- though it doesn't have tuples so YMMV. --edit-- Played with it a bit more and added tuples (as a replacement for '(' expr ')' grouping expression (exactly like the now-edited example above) and it still seems happy. If I were to add this to the grammar for real I'd have to monkey around with it some more to ensure there was an actual '(' ... ')' expression before the => but seems easily doable by transforming the grammar a bit.