Is there any example on handleing (left) recursive for complex grammars?

[myrfy001]

Hi, I'm using Chumsky to parse a functional-style programming language (which is called Bluespec SsytemVerilog), which means the expression type can be very complex and there are a lot of left recursive grammars. The full grammar can be find at https://github.com/B-Lang-org/bsc/releases/download/2023.07/BSV_lang_ref_guide.pdf and I have extracted all the grammar defs to a gist: https://gist.github.com/myrfy001/f4621cba938fa8d9577181a0c06ac666

for example, the following is a slice of the grammar:

expression                  ::= condExpr
                            |   operatorExpr
                            |   exprPrimary
exprPrimary                 ::= identifier
                            |   exprPrimary . identifier
                            |   functionCall
                            |   methodCall
                            |   bitSelect

condExpr                    ::= condPredicate ? expression : expression

operatorExpr                ::= unop expression
                            | expression binop expression
functionCall                ::= exprPrimary [ ( [ expression { , expression } ] ) ]
methodCall                  ::= exprPrimary . identifier [ ( [ expression { , expression } ] ) ]
bitSelect                   ::= exprPrimary [ expression [ : expression ] ]

From the Chumsky's toturial, it provides simple example for handling left recursive by using repeat and fold, but it seems to work only for simple case, when the expression being complex, is there any other way to handle the left recursive? Because the grammar is so complex that it's not possible to rewrite to remove the left recusrive. Also, I'm not an expert on Writing Parsers.

In the 1.0 alpha version, I can see it has an memorized paraer and it says can be used to handle left recursive, but I'm not sure whether it can handle such a complex case, and it doesn't has an example either.

I wish to get some advise on those problems, thanks!

[zesterer]

Hello,

From the Chumsky's toturial, it provides simple example for handling left recursive by using repeat and fold

Those cases are actually just restated as right-recursive patterns.

Because the grammar is so complex that it's not possible to rewrite to remove the left recusrive

It is, I believe, always possible in general to rewrite as right-recursive. That said, I agree that it can sometimes be rather annoying to do. I think in your case, however, the rewrite shouldn't be too hard. Take this sub-grammar:

exprPrimary                 ::= ...
                            |   exprPrimary . identifier
                            ...

This can be restated as right-recursive with a technique called precedence climbing, which would express this as something more akin to:

exprAtom ::= ...
exprField ::= exprAtom + (. identifier)*

You can see this approach for parsing operators taken in several of the example parsers, and in the tutorial. I don't see anything in the BNF that you provide that is fundamentally more complex than these cases.

Incidentally, if you're using version 1.0 (I would recommend doing so, 0.9 is effectively in maintenance mode and will be considered legacy once a stable 1.0 is released) you can use the pratt combinator to make writing operator parsers substantially less annoying.

Let me know if I can help further.

[myrfy001]

This is my first time to write a praser so I still have some questions. It would be very appreciate to have some examples on complex grammars.

The grammar is not as simple as

exprPrimary                 ::=    exprPrimary . identifier

There are also indirect left recursive. for example, there are two recursive loop:

1. expression -> condExpr -> condPredicate -> exprOrCondPattern -> expression
2. exprPrimary -> bitSelect | functionCall | methodCall -> exprPrimary

So how to deal with those indirect left recursions?

expression                  ::= condExpr
                            |   operatorExpr
                            |   exprPrimary

condExpr                    ::= condPredicate ? expression : expression

condPredicate               ::= exprOrCondPattern { &&& exprOrCondPattern }

exprOrCondPattern           ::= expression
                            |   expression matches pattern

operatorExpr                ::= unop expression
                            | expression binop expression

exprPrimary                 ::= exprPrimary . identifier
                            |   bitSelect
                            |   functionCall
                            |   methodCall

bitSelect                   ::= exprPrimary [ expression [ : expression ] ]

functionCall                ::= exprPrimary [ ( [ expression { , expression } ] ) ]

methodCall                  ::= exprPrimary . identifier [ ( [ expression { , expression } ] ) ]

[Zij-IT]

Sure! You can find an example that is roughly up-to-date here. I will warn you, that this is my code, so I don't know how readable it's going to be 😅 For your particular issue, these lines are likely going to be of use, as they are how you would handle bitSelect, functionCall and methodCall. I will let you know now that the pratt operators handling have changed since this code was written, so for that you will have to read the current documentation for 1.0.0-alpha.6.

I hope this helps!