How to handle left-recursive grammar with parser-ts

[lujiajing1126]

I would like to use parser-ts to parse PromQL of which formal definition may be found below,

1. https://github.com/prometheus/prometheus/blob/main/promql/parser/generated_parser.y.go
2. https://github.com/prometheus/lezer-promql/blob/main/src/promql.grammar

You may notice that the BinaryExpr will recursively check Expr where BinaryExpr is also listed with a high priority.

But with the following code,

export const BinaryExprParser: P.Parser<C.Char, BinaryExpr> = pipe(
  ExprParser,
  P.bindTo('l'),
  P.apFirst(S.spaces),
  P.bind('op', () => binaryOpParser),
  P.apFirst(S.spaces),
  P.bind('r', () => ExprParser),
  P.map(a => ({ _tag: 'binary_expr', left: a.l, right: a.r, op: a.op })),
);

we will encounter "Maximum call stack size exceeded error".

As is suggested from https://stackoverflow.com/questions/29158248/parser-combinators-and-left-recursion, we may "memorize" the (position, parser) tuple to avoid this issue. So is that possible to do this with parser-ts?

[IMax153]

Hey @lujiajing1126 - sorry for the delay in my response. In general, left recursive grammars post a particularly difficult problem for parser combinator libraries. However, it will be difficult to help you solve the issue without seeing more of the code (so I can examine how other parsers are being constructed).

Is it possible to share a larger snippet or a gist with the code you are using?

In reference to your question, there is nothing built into parser-ts that would allow for memoization, but it certainly seems possible to build a memoization layer on top of parser-ts.

[lujiajing1126]

Hey @lujiajing1126 - sorry for the delay in my response. In general, left recursive grammars post a particularly difficult problem for parser combinator libraries. However, it will be difficult to help you solve the issue without seeing more of the code (so I can examine how other parsers are being constructed).

Is it possible to share a larger snippet or a gist with the code you are using?

In reference to your question, there is nothing built into parser-ts that would allow for memoization, but it certainly seems possible to build a memoization layer on top of parser-ts.

Thanks for your reply.

I've uploaded the main file which you may find here https://gist.github.com/lujiajing1126/1f13bd5d9a68df634ccc63da2e353297

On L233, I've defined a binary expression parser. The so-called binary expression consists of two operands on the left and right of the operator.

In the original goyacc version, the left and right are both Expression. However, with parser-ts I am not able to do this due to the left-recursion problem.