Modifying Lark script parsing Excel formulas using Earley to LALR(1)

[onatyap]

I am trying to parse formulas written in Excel using LALR(1)

I did:

• Write the first version in Earley, which takes too much time to parse.
• There is a collision between functions using symbols and what I call an expr, but I couldn't figure out a way to avoid this. I am using symbol functions inside each other for the calculation precedence. I also thought about priorities but couldn't think of a way. I don't know if Excel formulas could create unambiguous trees and if that is the reason.

I would appreciate any suggestions to make it faster as well.

Here is the MWE lark script I have:
excel.lark.txt

An example formula I want to parse:
=SUM(A2:A5) / 2 + IF(A1=B1, SUM(B2:B5), SUM(C2:C5))

[MegaIng]

You currently have an infinite recursion comp_sym -> conc_sym -> sym2 -> sym1 -> expr -> comp_sym. I think just removing the first branch of expr should fix this. You probably also want to avoid the empty branch of expr (i.e. the | | thing you have there), and you probably want comp_sym inside of parentheses.

expr: NUMBER | ESCAPED_STRING | CELL_RANGE | CELL_REF | _function | "(" comp_sym ")" |  "-" expr

[onatyap]

Hi @MegaIng, thanks for the reply. Sorry, I somehow put the wrong version of the file.

?start: "=" comp_sym
comp_sym: (conc_sym ("="))* conc_sym
conc_sym: (sym2 "&")* sym2
sym2: (sym1 ("+"|"-"))* sym1
sym1: (expr ("*"|"/"))* expr
expr: NUMBER | ESCAPED_STRING | CELL_RANGE | CELL_REF | _function | "(" expr ")" |  "-" expr | comp_sym

_function: _sum | _if

_if: "IF" "("  expr ","  expr ","  expr ")"
_sum: "SUM" "("  expr (","  expr)* ")"

CELL_REF: /\$?[A-Z]{1,3}\$?\d+/
CELL_RANGE: CELL_REF ":" CELL_REF
NUMBER: SIGNED_NUMBER

%import common.ESCAPED_STRING
%import common.SIGNED_NUMBER
%import common.WS
%ignore WS

This is a version that parses =SUM(A2:A5) / 2 + IF(A1=B1, SUM(B2:B5), SUM(C2:C5)) correctly. (Checking from Lark IDE)

I was aware of that infinite recursion but couldn't remove it without breaking the example above.
If I understand you correctly, you are suggesting:
expr: NUMBER | ESCAPED_STRING | CELL_RANGE | CELL_REF | _function | "(" comp_sym ")" | "-" expr

But wouldn't this cause comp_sym and other symbolic functions to not be parsed unless they are inside parentheses?
I couldn't get the example above to work with the new expr you defined. I would appreciate if you could explain what I should change.

[MegaIng]

Then name expr is misleading for that you have. I would call it atom. Your normal expr is actually your comp_sym, since that includes all binary operations. So inside of the various _function, you need to use comp_sym as the arguments

[onatyap]

Yes, I agree and changed, and I figured it out now, thanks to you. I was having trouble thinking about how using expr in function wouldn't cause a recursion, but if I understand correctly, the function names act as constraints that help avoid ambiguity and recursion.

[MegaIng]

The problem with the recursion I was pointing out is that those were unqualified. I.e. You could have a repeated nesting of those without actually progressing in the input text. You basically have rules of the form comp_sym: conc_sym | comp_sym, which allows for arbitrary many repeats of comp_sym before actually going into conc_sym. LALR(1) does not like this (and neither does earley, but that will cope with it). if you have expr: "(" comp_sym ")" you can only have as meany repeats as there are (, which is not a problem.

[onatyap]

The version I have that works for LALR(1) is below. I don't think this has unqualified recursion, but if you have any other suggestions to make this more performant, I would gladly modify it accordingly.

?start: "=" expr

_function: _sum | _if

_if: "IF" "("  expr ","  expr ","  expr ")"
_sum: "SUM" "("  expr (","  expr)* ")"

expr: (conc_sym ("="))* conc_sym
conc_sym: (sym2 "&")* sym2
sym2: (sym1 ("+"|"-"))* sym1
sym1: (atom ("*"|"/"))* atom

atom: NUMBER | ESCAPED_STRING | CELL_RANGE | CELL_REF | _function | "(" atom ")" |  "-" atom

CELL_REF: /\$?[A-Z]{1,3}\$?\d+/
CELL_RANGE: CELL_REF ":" CELL_REF
NUMBER: SIGNED_NUMBER