Grammar problem - two rules, same separator

[maral]

I have a grammar with a structure like this:
R1:

• R2 (',' R2)*

R2:

• 'print' Number (',' Number)* |
• 'print'

Example inputs:

• print 3, 4, 5, print 2, 3
• print
• print, print 1, 23, print 3, 5, 2

The problem is, this grammar doesn't work properly. The problem seems to be caused by using the same separator (comma) in both rules. After a 'print' and a Number, the analyzer sees a comma and expects another Number, following (2). So if it meets 'print' instead, it throws MismatchedTokenException. Is there any way around this? I tried different workarounds with rewritten grammars, nothing seems to work.

I made a simplified minimal working example in the playground, source code is attached below. Here is the diagram.

(function jsonGrammarOnlyExample() {
  // ----------------- Lexer -----------------
  const createToken = chevrotain.createToken;
  const Lexer = chevrotain.Lexer;

  const A = createToken({ name: "A", pattern: /print/ });
  const B = createToken({ name: "B", pattern: /\d+/ });
  const X = createToken({
    name: "X",
    pattern: /,/,
  });
  const Space = createToken({
    name: "Space",
    pattern: / +/,
    group: Lexer.SKIPPED,
  });
  
  X.LABEL = "','";

  const smdTokens = [A, B, X, Space];

  const JsonLexer = new Lexer(smdTokens, {
    // Less position info tracked, reduces verbosity of the playground output.
    positionTracking: "onlyStart"
  });


  // ----------------- parser -----------------
  const CstParser = chevrotain.CstParser;

  class JsonParser extends CstParser {
    constructor() {
      super(smdTokens);

      const $ = this;

      $.RULE("r1", () => {
        $.AT_LEAST_ONE_SEP({
          SEP: X,
          DEF: () => {
            $.SUBRULE($.r2);
          },
        });
      });

      $.RULE("r2", () => {
        $.CONSUME(A),
          $.MANY_SEP({
            SEP: X,
            DEF: () => {
              $.CONSUME(B);
            },
          });
      });
  
      this.performSelfAnalysis();
    }
  }

  // for the playground to work the returned object must contain these fields
  return {
    lexer: JsonLexer,
    parser: JsonParser,
    defaultRule: "r1"
  };
}())

[msujew]

Hey @maral,

so the main issue is that Chevrotain does not look into the outer context of a rule to determine its lookahead. In that sense, you need some way to explain to Chevrotain that it has to take more context into account when determining whether to continue parsing the MANY_SEP inside of r2. Usually you would do this by using a GATE (see the docs) on the MANY_SEP call, but only MANY supports GATE properties, so you'd have to rewrite the grammar slightly:

$.RULE("r2", () => {
  $.CONSUME(A);
  // unwrap MANY_SEP as a combination of OPTION+MANY
  $.OPTION(() => {
    $.CONSUME(B);
    $.MANY({
      // If the gate returns false, the `DEF` won't be executed
      GATE: () => $.LA(2).tokenType === B,
      DEF: () => {
        $.CONSUME(X);
        $.CONSUME(B);
      }
    });
  });
});

[maral]

Thank you very much, this is exactly what I needed. I even spent some time reading about gates and look ahead functions, but couldn't find how to use them together in my case.

[Korporal]

I was curious about this, I looked at it with Antlr4 and this grammar seems to handle the test inputs:

grammar print;

print_text
    : print_group* EOF
    ;

print_group
    : print_set (COMMA print_set)* 
    ;

print_set
    : PRINT (NUMBER (COMMA NUMBER)*)? 
    ;

PRINT: 'print';
NUMBER: [0-9]+;
COMMA:  ',';
SPACE:  (' ')+ -> skip;
NL:     [\r\n]+ -> skip;

Giving this parse:

For this input:

print 3, 4, 5, print 2, 3
print
print, print 1, 23, print 3, 5, 2
print 2

Given Chevrotain uses the same kind of parsing algorithm as Antlr4, can this not be done the same way?

[msujew]

Given Chevrotain uses the same kind of parsing algorithm as Antlr4

It uses the same theoretical basis (LL), but the actual lookahead implementations are wildly different. ANTLR4 is - as you found out - capable of handling outer context during lookahead, since lookahead computation is done at runtime instead of "compile time" (Chevrotain precomputes lookahead tables). Their original paper (section 3.1) goes into more depth on this. In literature, you would call Chevrotain an SLL (Strong LL) parser, while ANTLR4 is a "true" LL parser.