How to do proper recursion in Pyparsing?

Question

I'm currently parsing a custom programming language, and, when creating the "expression" rule for parsing, I'm struggling to find a way that's not painfully slow with recursion. My problem is that a function call can be in an expression, and an expression can be in a function call (parameters). So what I end up with is a terrible system based on Forward(), that takes seconds on func1(var1+1) + 1 and minutes on func1(func1(var1+1)+1) + 1, which is for sure not acceptable. Here's my current bad approach:

    expression = Forward()
    functionCall = Forward()
    value = literal ^ identifier ^ Group(functionCall)
    expression << Group(infixNotation(value, [
        (memberOP, 2, opAssoc.LEFT),
        ...
    ]))
    arguments = ZeroOrMore(delimitedList(expression))

    ...

    functionCall << identifier + Literal("(").suppress() + Group(arguments) + Literal(")").suppress()

@MisterMiyagi Wow, this was instantaneous ! Now I feel dumbfounded, but I guess that's how you learn. Feel free to add an answer I would validate. — Maxime, Jun 08 '20 at 12:04
More performance tips here: https://github.com/pyparsing/pyparsing/wiki/Performance-Tips — PaulMcG, Jun 08 '20 at 12:07

score 4 · Accepted Answer · answered Jun 08 '20 at 12:20

PyParsing can remember previous parse results and re-use them using the Packrat optimisation. This is provides a performance benefit for recursive grammars or generally if an element may apply in different contexts.

Packrat must be manually enabled, since it might conflict with parsers that have side-effects (e.g. a parse action that modifies global state).

import pyparsing
pyparsing.ParserElement.enablePackrat()

How to do proper recursion in Pyparsing?

1 Answers1