DSL for parsing bas tag:client title:magic

[gaborbernat]

I am trying to parse a text where keys can have fields attached to it: bas tag:client title:magic, but I am getting NotAllInputParsedException: Redundant input, expecting EOF but found: title:

import { CstParser, Lexer, createToken } from "chevrotain";
const WhiteSpace = createToken({ name: "WhiteSpace", pattern: /\s+/, group: Lexer.SKIPPED });
const Value = createToken({ name: "Identifier", pattern: /[-a-zA-Z0-9]+/ });
const FieldSpecifier = createToken({ name: "Identifier", pattern: /(tag|title):/ });
const allTokens = [WhiteSpace, Value, FieldSpecifier];
const lexer = new Lexer([FieldSpecifier, Value, WhiteSpace]);

class SelectParser extends CstParser {
  constructor() {
    super(allTokens);
    // biome-ignore lint/complexity/noUselessThisAlias: required for chevrotain
    const $ = this;

    $.RULE("element", () => {
      $.OPTION(() => {
        $.CONSUME(FieldSpecifier);
      });
      $.CONSUME2(Value);
    });

    $.RULE("search", () => {
      $.MANY_SEP({
        SEP: WhiteSpace,
        DEF: () => {
          $.SUBRULE($.element);
        },
      });
    });

    this.performSelfAnalysis();
  }
}

const parser = new SelectParser();

export function parse(text: string) {
  const lexingResult = lexer.tokenize(text);
  // "input" is a setter which will reset the parser's state.
  parser.input = lexingResult.tokens;
  parser.search();
  if (parser.errors.length > 0) {
    throw parser.errors[0];
  }
}

Ideas?

[msujew]

Hey @gaborbernat,

I tried reproducing this in the playground and noticed that you're using Lexer.SKIPPED for the WhiteSpace token. This will completely discard the token from the token stream and prevents you from actually consuming it. After removing the group, everything seems to parse correctly :)

[gaborbernat]

Now I am trying to extend that to support and and or with parenthesis:

describe.concurrent("Parse", () => {
  test.each([
    ["test", {}],
    ["tag:bas", {}],
    ["title:bas", {}],
    ["test title:bas", {}],
    ["test\ttitle:bas", {}],
    ["test|title:bas", {}],
    ["test&title:bas", {}],
    ["test|title:bas", {}],
    ["test&(tag:bas|tag:magic & tag:alpha)", {}],
  ])("%s", (text, result) => {
    expect(parse(text)).toEqual(result);
  });
});

I got to <CONSUME> argument is invalid expecting a TokenType reference but got: <undefined> 🤔 was following https://raw.githubusercontent.com/Chevrotain/chevrotain/master/examples/grammars/calculator/calculator_pure_grammar.js

Works now:

import type { IToken } from "@chevrotain/types";
import { type CstNode, CstParser, Lexer, createToken } from "chevrotain";

/*
bas tag:client title:magic
*/
const WhiteSpace = createToken({ name: "WhiteSpace", pattern: /\s+/ });
const LeftParen = createToken({ name: "LeftParen", pattern: /\(/ });
const RightParen = createToken({ name: "RightParen", pattern: /\)/ });
const CombineOperator = createToken({ name: "CombineOperator", pattern: Lexer.NA });
const Or = createToken({ name: "Or", pattern: /\|/, categories: CombineOperator });
const And = createToken({ name: "And", pattern: /&/, categories: CombineOperator });
const Field = createToken({ name: "Field", pattern: /(name|tag|title)/ });
const FieldSep = createToken({ name: "Field", pattern: /:/ });
const Value = createToken({ name: "Value", pattern: /(['"]).*\1|[-a-zA-Z0-9]+/ });
const allTokens = [WhiteSpace, LeftParen, RightParen, CombineOperator, Or, And, Field, FieldSep, Value];

class SearchParser extends CstParser {
  constructor() {
    super(allTokens);
    // biome-ignore lint/complexity/noUselessThisAlias: required for chevrotain
    const $ = this;

    $.RULE("expression", () => {
      // biome-ignore lint/style/useNamingConvention: LABEL
      $.SUBRULE($.atomicExpression, { LABEL: "lhs" });
      $.MANY(() => {
        $.OPTION(() => {
          $.CONSUME(CombineOperator);
        });
        // biome-ignore lint/style/useNamingConvention: LABEL
        $.SUBRULE2($.atomicExpression, { LABEL: "rhs" });
      });
    });

    $.RULE("parenthesisExpression", () => {
      $.CONSUME(LeftParen);
      $.SUBRULE($.expression);
      $.CONSUME(RightParen);
    });

    $.RULE("atomicExpression", () => {
      // biome-ignore lint/style/useNamingConvention: ALT
      $.OR([{ ALT: () => $.SUBRULE($.parenthesisExpression) }, { ALT: () => $.SUBRULE($.element) }]);
    });

    $.RULE("element", () => {
      $.OPTION(() => {
        $.CONSUME(WhiteSpace);
      });
      $.OPTION1(() => {
        $.CONSUME1(Field);
        $.CONSUME5(FieldSep);
      });
      $.CONSUME4(Value);
      $.OPTION3(() => {
        $.CONSUME3(WhiteSpace);
      });
    });

    this.performSelfAnalysis();
  }
}

const lexer = new Lexer(allTokens);
const parser = new SearchParser();

const BaseCstVisitor = parser.getBaseCstVisitorConstructor();

class SearchInterpreter extends BaseCstVisitor {
  constructor() {
    super();
    this.validateVisitor();
  }

  expression(ctx: { lhs: CstNode; rhs: CstNode[] }) {
    const result = [this.visit(ctx.lhs)];
    if (ctx.rhs) {
      ctx.rhs.forEach((rhs: CstNode, index: number) => {
        result.push(ctx.CombineOperator ? ctx.CombineOperator[index].tokenType.name : "And");
        result.push(this.visit(rhs));
      });
    }
    return result;
  }

  parenthesisExpression(ctx: { expression: CstNode | CstNode[] }) {
    // visiting an array is equivalent to visiting its first element.
    return this.visit(ctx.expression);
  }
  atomicExpression(ctx: { parenthesisExpression: CstNode | CstNode[]; element: CstNode | CstNode[] }) {
    if (ctx.parenthesisExpression) {
      return this.visit(ctx.parenthesisExpression);
    }
    if (ctx.element) {
      return this.visit(ctx.element);
    }
  }
  // biome-ignore lint/style/useNamingConvention: Capital case tokens
  element(ctx: { Field: IToken[]; Value: IToken[] }) {
    const value = ctx.Value[0].image;
    if (ctx.Field) {
      return [ctx.Field[0].image, value];
    }
    return value;
  }
}

const interpreter = new SearchInterpreter();
export function parse(text: string) {
  parser.input = lexer.tokenize(text).tokens;
  const cst = parser.expression();
  if (parser.errors.length > 0) {
    throw parser.errors[0];
  }
  return interpreter.visit(cst);
}