How to handle left-recursive grammar with parser-ts
- Dominant language
- TypeScript
- Stars
- 196
- Forks
- 19
- PR merge metrics
- No merged PRs in 30d
Description
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,
```typescript
export const BinaryExprParser: P.Parser = 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`?
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.