Using nodes from AT_LEAST_ONE_SEP

[Zuruckt]

I'm creating a tool to evaluate user defined expressions and I've stumbled upon some issues when creating the visitor for the AT_LEAST_ONE_SEP rule.

The input I'm giving is 40 >= 40 and 30 >= 30 and 20 >= 20 and with the implementation I made it returns the diferrent rules grouped by type in arrays

How should I keep track of the order which each comparasionExpression appeared in the tree?

My Diagram:

parsers.js:

import { CstParser } from "chevrotain";
import { ComparasionOperator, Identifier, IntegerLiteral, LogicalOperator, StringLiteral, tokens } from "./tokens.js";

export class ExpressionParser extends CstParser {
  constructor() {
    super(tokens);

    const $ = this; 

    $.RULE("expression", () => {
        $.AT_LEAST_ONE_SEP({
          SEP: LogicalOperator,
          DEF: () => {
            $.SUBRULE($.comparasionExpression);
          }
        });
    });

    $.RULE("comparasionExpression", () => {
      $.SUBRULE($.atomicExpression, {LABEL: "lhs"});
      $.CONSUME(ComparasionOperator);
      $.SUBRULE2($.atomicExpression, {LABEL: "rhs"});
    });

    $.RULE("logicalOperator", () => {
      $.CONSUME(LogicalOperator);
    })

    $.RULE("atomicExpression", () => {
      $.OR([
        { ALT: () => $.CONSUME(StringLiteral) },
        { ALT: () => $.CONSUME(IntegerLiteral) },
      ]);
    });

    $.RULE("comparasionOperator", () => {
      $.CONSUME(ComparasionOperator);
    })

    $.RULE("identifier", () => {
      $.CONSUME(Identifier);
    })

    $.performSelfAnalysis();
  }
}

[bd82]

Hello @Zuruckt

The CST as a low level data structure representing the syntax.
In theory you may want to transform it to higher level data structures (AST / IR) for evaluating the semantics of your language.

The order of insertion to these arrays is in the order they were encountered in the input text.
So in theory you could evaluate it as:
(comparasionExpression[0] logicalOperator[0] comparasionExpression[1]) logicalOperator[1] comparasionExpression[2]

except different logical operators (and vs or) often have different precedence, so we are back to either:

1. Model the logicalOperator precedence in your grammar.
2. Perform a post-parsing processing phase to "digest" your CST to something which is easier to evaluate.

I prefer the 2nd option due to performance reasons and keeping the grammar "pure" (only dealing with syntax)

• chevrotain/examples/grammars/ecma5/ecma5_parser.js

  Lines 41 to 48 in 4a68802

  	// A.3 Expressions
  	// Note that the binary expression operators are treated as a flat list
  	// instead of using a new rule for each precedence level.
  	// This is both faster and less verbose but it means additional logic must be used to re-order the flat list
  	// into a precedence tree.
  	// This approach was used in the swift compiler.
  	// https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Expressions.html#//apple_ref/doc/uid/TP40014097-CH32-ID383
  	// (scroll down to the note on binary expressions)

• chevrotain/examples/grammars/ecma5/ecma5_parser.js

  Lines 257 to 283 in 4a68802

  	$.RULE("BinaryExpression", () => {
  	$.SUBRULE($.UnaryExpression);
  	$.MANY(() => {
  	$.OR(
  	$.c3 ||
  	($.c3 = [
  	// flat list of binary operators
  	{ ALT: () => $.CONSUME(t.AbsAssignmentOperator) },
  	{ ALT: () => $.CONSUME(t.VerticalBarVerticalBar) },
  	{ ALT: () => $.CONSUME(t.AmpersandAmpersand) },
  	{ ALT: () => $.CONSUME(t.VerticalBar) },
  	{ ALT: () => $.CONSUME(t.Circumflex) },
  	{ ALT: () => $.CONSUME(t.Ampersand) },
  	{ ALT: () => $.CONSUME(t.AbsEqualityOperator) },
  	{ ALT: () => $.CONSUME(t.AbsRelationalOperator) },
  	{ ALT: () => $.CONSUME(t.InstanceOfTok) },
  	{ ALT: () => $.CONSUME(t.InTok) },
  	{ ALT: () => $.CONSUME(t.AbsShiftOperator) },
  	{
  	ALT: () => $.CONSUME(t.AbsMultiplicativeOperator),
  	},
  	{ ALT: () => $.CONSUME(t.AbsAdditiveOperator) },
  	]),
  	);
  	$.SUBRULE2($.UnaryExpression);
  	});
  	});