Mastodawn

Joshua Barretto

@janriemer Recursion couldn't be easier!

let a = recursive(|a| /* definition of a */);

Make sure you don't end up with accidental left recursion though. Check out the docs for the new pratt parser combinator if you want a really neat way to do complex expression parsing.

https://docs.rs/chumsky/1.0.0-alpha.6/chumsky/trait.Parser.html#method.memoized

@jsbarretto This looks very easy indeed - thank you!

Yes, thank you for the hint regarding left recursion (see little anecdote in second toot). 👍

If I understand correctly, `memoized` should be used for left recursive grammars in general, no!?

I always thought pratt parsing was only for parsing expressions (like 1+2*5 etc.), but not general left recursive parsing, but this is more an intuition, so I might be wrong.😇

1/2

Parser in chumsky - Rust

A trait implemented by parsers.

@jsbarretto here comes the anecdote (if you are interested):

The grammar I have to parse is left-recursive. When I started the project I painfully run into it by experiencing exponential parsing time (took me quite a while to figure out what was going on).

So I decided to transform the grammar into a right-recursive one. However, this can result into some "ugly" AST structure, so after parsing I transform the AST back into something that resembles the "left-recursive" structure.

2/3

@jsbarretto Now, using chumsky, I'll probably don't need that extra transformation step, but can parse the left recursive grammar directly, which is really nice!

(first, I'll leave the transformation step and right-recursive parsing as is to not have too much refactoring going on at the same time😬)

3/3

Joshua Barretto Feb 25, 2024

@janriemer So... Yes, `memoized` does exist, and does allow the parsing of left-recursive grammars. However, it does come with some overhead: if you can rewrite your grammar to be right-recursive, you'll almost certainly be happier in the long run (this goes for pretty much any top-down approach to parsing out there FWIW).

I'd be interested to know what the right-recursive section of your grammar looks like: the pratt parser can almost certainly handle it, whatever it is.

@jsbarretto Thank you for all the tips, Joshua! 🤗

So two places in the grammar might be interesting:

1. Conditional Expressions:
Think of something like this:
foo && (bar || baz)

So this might not be very different from math expressions and so pratt parsing should be possible, right!?🤔

Here is a direct link to the parsing code and line (⚠️ nom macros ahead!)
https://gitlab.com/seloxidate/selector/-/blob/e6a7aa290c6027c9fd595ed89bebc4d3c1de4773/src/parsers/conditional_expression.rs#L43

1/2

src/parsers/conditional_expression.rs · e6a7aa290c6027c9fd595ed89bebc4d3c1de4773 · seloxidate / selector · GitLab

A parser for inline select statements in X++. Written in Rust. 🦀

GitLab

2. Eval Name:
Basically method calls - think of something like this to parse:
myClass.myMethod(foo.bar())

I can imagine that this might not be suitable for pratt parsing (it's not a classical math expression), but I haven't really put much thought into it yet, so maybe it's perfecty fine to apply pratt parsing!?

Here is a direct link to the parsing code and line (⚠️ nom macros ahead!)
https://gitlab.com/seloxidate/selector/-/blob/e6a7aa290c6027c9fd595ed89bebc4d3c1de4773/src/parsers/eval_name.rs#L16

2/2

src/parsers/eval_name.rs · e6a7aa290c6027c9fd595ed89bebc4d3c1de4773 · seloxidate / selector · GitLab

A parser for inline select statements in X++. Written in Rust. 🦀

GitLab

https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html

@jsbarretto Currently reading matklads article "Simple but Powerful #Pratt Parsing" 🤓

#Parser #Algorithm #Compiler #PrattParsing

Simple but Powerful Pratt Parsing

Welcome to my article about Pratt parsing --- the monad tutorial of syntactic analysis. The number of Pratt parsing articles is so large that there exists a survey post :)

Joshua Barretto Feb 25, 2024

@janriemer Both of these cases can definitely be handled by a pratt parser! The first cases (&& and ||) are just regular binary expressions. The second case (method calls) is just a postfix unary expression, but where the 'operator' is `.method(<expr>)`. Remember that 'operator' doesn't need to be just a single token, it just needs to be 'self-delimiting' (i.e: outside the precedence hierarchy)!