Empty Alternative inside Nested Repetitions causes infinite loops on Parser initilization

[matthew-dean]

I'm sure this was a grammar error on my part, but just wanted to let you know it's possible to get into a loop state while performing self-analysis.

The loop is like this:

 at possiblePathsFrom (/git/chevrotain/src/parse/grammar/interpreter.ts:287:14)
    at getAlternativesForProd (/git/chevrotain/src/parse/grammar/interpreter.ts:265:24)
    at possiblePathsFrom (/git/chevrotain/src/parse/grammar/interpreter.ts:322:16)
    at getAlternativesForProd (/git/chevrotain/src/parse/grammar/interpreter.ts:265:24)
    at possiblePathsFrom (/git/chevrotain/src/parse/grammar/interpreter.ts:322:16)
    at getAlternativesForProd (/git/chevrotain/src/parse/grammar/interpreter.ts:265:24)

[bd82]

Thanks for reporting this @matthew-dean

Do you have a small grammar that reproduces the issue?
Otherwise I'm not sure how to resolve it.

• did your grammar include some infinite loop, e.g some empty alternative inside a loop?
• How did you fix the issue ? (Changing the grammar?)

Maybe another check for invalid grammars could be added, but I need to reproduce the scenario first...

[matthew-dean]

@bd82 Sorry for the incomplete information.

Yes, it was fixable by changing grammar. I'm trying to think of the scenarios where I encountered this. It's happened to me a few times. Each time, there was a clearer way to express the grammar that didn't trigger this, but unfortunately, no, I don't have a simple grammar to trigger it. I just wanted to raise the issue that these loops are not detected by analysis. Sorry there's not more to go on!

[matthew-dean]

@bd82 IIRC, I do have a commit somewhere for Less grammar where this was happening... but it wouldn't be a simple reproduction. Hmm, I can look for it. If it happens again, I'll definitely make a branch and commit it.

[bd82]

o.k. if you can reproduce in the future even with a more complex example I will try to debug.

reopen this issue if/when you have a reproducible case.

[matthew-dean]

@bd82 Just had this happen again! So I immediately pushed the commit. This rule customValue works in most circumstances, but in this line, causes the looping error: https://github.com/matthew-dean/less.js/blob/4.x-WIP/packages/parser/src/productions/mixin.ts#L18

[matthew-dean]

customValue is defined here, although I already notice a problem. Still, this might help you diagnose detecting the error.

[matthew-dean]

If I change the block in mixin to:

    $.MANY(() => {
      $.OR([
        { ALT: () => $.SUBRULE($.expressionList) },
        { ALT: () => $.SUBRULE($.curlyBlock) }
      ])
      
      $.OPTION(() => {
        $.CONSUME($.T.SemiColon)
        $.isSemiColonSeparated = true
      })
    })

I get, Ambiguous alternatives: <1 ,2> due to common lookahead prefix in <OR> inside <testMixin> Rule, <> may appears as a prefix path in all these alternatives.

However, this is false. The curlyBlock must start with a {. But I think Chevrotain gets confused inside this MANY, because an expressionList can be empty?

(The mixin test was basically working except for accepting curly blocks. If I remove the OR and leave expressionList, it works.)

[matthew-dean]

Oh wait! If I flip the order (put curlyBlock first), it works!

EDIT: No wait, it doesn't..... or does it? Anyway, curious that it doesn't have the same error if it's ambiguous.

[bd82]

I'll try to play with this on the weekend

[bd82]

This may be related to: #855
Also may be related to the empty alternative.

Debugging such a large example is complicated and I am not making much headway, I may try to resolve the issue linked above (which includes a small reproducible case) instead and see if also resolves this issue.

[bd82]

I can reproduce the issue with this small example:

const { CstParser, createToken, EMPTY_ALT } = require("chevrotain")

// ----------------- lexer -----------------
const Comma = createToken({ name: "Comma", pattern: /,/ })

const allTokens = [
  Comma
]

class NestedManyEmptyAltBugParser extends CstParser {
  constructor() {
    super(allTokens)

    const $ = this

    // the parsing methods
    $.RULE("A", () => {
      $.MANY(() => {
        $.SUBRULE($.B)
      });
    });

    $.RULE("B", () => {
      $.MANY(() => {
        $.SUBRULE($.C)
      });
    });

    $.RULE("C", () => {
      $.OR([
        { ALT: () => $.CONSUME(Comma) },
        { ALT: () => EMPTY_ALT }
      ]);
    });

    this.performSelfAnalysis()
  }
}

const parser = new NestedManyEmptyAltBugParser()

[bd82]

In the meanwhile I suggest you try to refactor your grammar to avoid the empty alternative or avoid the MANY inside MANY. (even if it means duplicated grammar parts).

[matthew-dean]

@bd82 So you think it's the EMPTY_ALT inside of a nested MANY?

I think the problem in my case is the use of GATEs, which may produce an EMPTY_ALT. But it's good to know. I'll see if I can rethink it when I circle back around.

[bd82]

The phase that causes the infinite loop does not take into account the GATEs at all.
I hope to have time on the weekend to debug the reproduce-able example farther.