Which Parsing Approach?

Re:Which Parsing Approach? by hardwaregeek on Tuesday September 15, 2020 @01:23PM (#24483924)

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.

[ Parent | on HN ]

Re:Which Parsing Approach? by DylanSp on Tuesday September 15, 2020 @01:42PM (#24484187)

To your first point, I've got a couple of bookmarks:

- Query-based compiler architecture: https://ollef.github.io/blog/posts/query-based-compilers.htm...

- Lezer [a parsing system used by CodeMirror]: https://marijnhaverbeke.nl/blog/lezer.html

- Anders Hejlsberg on Modern Compiler Construction: https://www.youtube.com/watch?v=wSdV1M7n4gQ

[ Parent | on HN ]

Re:Which Parsing Approach? by hardwaregeek on Tuesday September 15, 2020 @01:58PM (#24484403)

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.

[ Parent | on HN ]

Re:Which Parsing Approach? by drakmaniso on Tuesday September 15, 2020 @02:33PM (#24484922)

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.

[ Parent | on HN ]

Re:Which Parsing Approach? by tgv on Tuesday September 15, 2020 @04:28PM (#24486342)

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 "}")?.

[ Parent | on HN ]

Re:Which Parsing Approach? by hardwaregeek on Tuesday September 15, 2020 @04:32PM (#24486380)

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

[ Parent | on HN ]

Re:Which Parsing Approach? by UncleEntity on Tuesday September 15, 2020 @03:54PM (#24485995)

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.

[ Parent | on HN ]

Re:Which Parsing Approach? by mathgladiator on Tuesday September 15, 2020 @01:51PM (#24484303)

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.

[ Parent | on HN ]

Re:Which Parsing Approach? by hardwaregeek on Tuesday September 15, 2020 @01:57PM (#24484383)

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.

[ Parent | on HN ]