Debugging notes

If there are infinite recursion error, these are possible problems.

With any of these problems, if you're stuck, don't be afraid to ask for help!

Infinite recursion of parsers

Suspect codes: src/parser-lib.ts, src/lexer.ts, or src/ast-parser.ts.

Some parsers are recursive, some are mutually recursive. Break the infinite recursion by making use of the lazy combinator.

A good example is the many combinator:

export function many<T, U>(parser: Parser<T, U>): Parser<T, Array<U>> {
  return choice(
    sequence(parser, many(parser))
      .map(([first, rest]) => [first, ...rest]),
    nothing().map(() => []),
  );
}

It makes sense for many to be recursive since we want parser to be parsed multiple times. In fact, this is considerably elegant in functional programming. However, if we look closely, this function never returns because it always calls itself!

We need to use the lazy combinator.

export function many<T, U>(parser: Parser<T, U>): Parser<T, Array<U>> {
  return choice(
    sequence(parser, lazy(() => many(parser)))
      .map(([first, rest]) => [first, ...rest]),
    nothing().map(() => []),
  );
}

Now the many inside is only called when needed. At most cases, just adding lazy is enough. Although there are cases where this is not enough but I don't think this can happen. I'll let you figure it out how it can happen if you're curious.

Parsers can be mutually recursive in a complicated way however. Sadly, we have to draw a dependency graph of all functions and put lazy on cycles.

There could be a tool that automatically makes call graph that allows us to hide nodes so we can focus only on parsers. Again sadly, I can't find a good one at least in VSCode. So far, what I've find doesn't allow us to hide nodes. TODO links

Parsing many nothing

Suspect codes: src/parser-lib.ts, src/lexer.ts, or src/ast-parser.ts

Considering many(parser) or all(parser), if parser can parse nothing, then the two constructions will result in infinite recursion. I'll let you figure it out why that's the case. This happens in the derivative combinators as well: manyAtLeastOnce and allAtLeastOnce.

If you figure out this is the problem, you have to figure out how to remedy this however. Don't be afraid to ask for help however 😊.