regexp.bnf

/**
 * BNF grammar for Regular Expressions.
 *
 * Based on RegExp grammar from ECMAScript:
 * http://www.ecma-international.org/ecma-262/7.0/#sec-patterns
 *
 * Parser generated by Syntax tool (npm: syntax-cli)
 *
 * Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
 *
 * MIT Style License.
 */

// --------------------------------------------
// 1. Lexical grammar.

%lex

CHAR                    [^*?+\[()\\|]
ESC                     \\
U                       [0-9a-fA-F]
U_LEAD_SURROGATE        [dD][89abAB][0-9a-fA-F]{2}
U_TRAIL_SURROGATE       [dD][c-fC-F][0-9a-fA-F]{2}

GROUP_NAME              ([\w$]|\\'u'[0-9a-fA-F]{4}|\\'u{'[0-9a-fA-F]{1,}'}')+

/**
 * Lexer state for character class.
 *
 * Some meta symbols inside a character class are treated as simple
 * symbols, so we return different token types for them.
 *
 * E.g. `(` yields L_PAREN token by default, however in a character
 * class it's  a simple symbol:
 *
 *   '('          return 'L_PAREN'
 *   <class>'('   return 'CHAR'
 *
 * This allows making BNF grammar simpler with less productions, and states.
 *
 * <u_class> is the same but with unicode flag.
 */
%s class
%s u_class

/**
 * State for "extended" regexp, enabled by `x` flag.
 *
 * In this state whitespace are ignored, and expressions can
 * use #-comments.
 *
 * <xu> is the same but with unicode flag.
 */
%s x
%s xu

/**
 * State for "unicode" regexp, enabled by `u` flag.
 *
 * In this state surrogate pairs are treated as codepoints and
 * \u{} syntax is understood.
 */
%s u

%%

<x,xu>'#'[^\n]*(?=\n|\/\w*)          /* skip comments */
<x,xu>\s+                            /* skip whitespace */

<class,u_class>{ESC}'-'              return 'ESC_CHAR'
<class,u_class>'-'                   return 'DASH'
<class,u_class>'/'                   return 'CHAR'
<class,u_class>'#'                   return 'CHAR'
<class,u_class>'|'                   return 'CHAR'
<class,u_class>'.'                   return 'CHAR'

<class,u_class>'{'                   return 'CHAR'

'{'\d+'}'                            return 'RANGE_EXACT'
'{'\d+',}'                           return 'RANGE_OPEN'
'{'\d+','\d+'}'                      return 'RANGE_CLOSED'

{ESC}'k<'{GROUP_NAME}'>'             {
                                       const groupName = yytext.slice(3, -1);
                                       validateUnicodeGroupName(groupName, this.getCurrentState());
                                       return 'NAMED_GROUP_REF';
                                     }

{ESC}'b'                             return 'ESC_b'
{ESC}'B'                             return 'ESC_B'

{ESC}'c'[a-zA-Z]                     return 'CTRL_CH'

{ESC}'0'\d{1,2}                      return 'OCT_CODE'
{ESC}'0'                             return 'DEC_CODE'
{ESC}\d{1,3}                         return 'DEC_CODE'

<u,xu,u_class>{ESC}'u'{U_LEAD_SURROGATE}{ESC}'u'{U_TRAIL_SURROGATE} return 'U_CODE_SURROGATE'

<u,xu,u_class>{ESC}'u{'{U}{1,}'}'   return 'U_CODE'

{ESC}'u'{U}{4}                      return 'U_CODE'

{ESC}'x'{U}{2}                      return 'HEX_CODE'

{ESC}[tnrdDsSwWvf]                  return 'META_CHAR'

{ESC}'/'                            return 'ESC_CHAR'

<xu>{ESC}[ #]                       return 'ESC_CHAR'

{ESC}{CHAR}                         {
                                      const s = this.getCurrentState();
                                      if (s === 'u' || s === 'xu' || s === 'u_class') {
                                        throw new SyntaxError(`invalid Unicode escape ${yytext}`);
                                      }
                                      return 'ESC_CHAR';
                                    }

{ESC}[*?+\[()\\|]                   return 'ESC_CHAR'

<class,u_class>'('                  return 'CHAR'
<class,u_class>')'                  return 'CHAR'

'(?='                               return 'POS_LA_ASSERT'
'(?!'                               return 'NEG_LA_ASSERT'

'(?<='                              return 'POS_LB_ASSERT'
'(?<!'                              return 'NEG_LB_ASSERT'

'(?:'                               return 'NON_CAPTURE_GROUP'

'(?<'{GROUP_NAME}'>'                {
                                      yytext = yytext.slice(3, -1);
                                      validateUnicodeGroupName(yytext, this.getCurrentState());
                                      return 'NAMED_CAPTURE_GROUP';
                                    }

'('                                 return 'L_PAREN'
')'                                 return 'R_PAREN'

<class,u_class>[*?+[^$]             return 'CHAR'
<class,u_class>{ESC}']'             return 'ESC_CHAR'

<class,u_class>']'                  { this.popState(); return 'R_BRACKET' }

'^'                                 return 'BOS'
'$'                                 return 'EOS'

'*'                                 return 'STAR'
'?'                                 return 'Q_MARK'
'+'                                 return 'PLUS'

'|'                                 return 'BAR'

'.'                                 return 'ANY'

'/'                                 return 'SLASH'

{CHAR}                              return 'CHAR'

'[^'                                { const s = this.getCurrentState(); this.pushState(s === 'u' || s === 'xu' ? 'u_class' : 'class'); return 'NEG_CLASS' }
'['                                 { const s = this.getCurrentState(); this.pushState(s === 'u' || s === 'xu' ? 'u_class' : 'class'); return 'L_BRACKET' }

/lex

// --------------------------------------------
// 2. Syntactic grammar.

%{

/**
 * Lower group boundary:
 *
 *   /(((a)b)c)(d)(e)/
 *
 * The first paren in (((a)b)c) has lower bound 0, but when
 * we reach the (d), it already 4.
 */
let capturingGroupsCurrentLower = 0;

/**
 * Group number to assign to a group.
 */
let currentCapturingGroup = 0;

/**
 * Tracks capturing groups.
 */
let capturingGroupsCount = 0;

/**
 * Tracks named groups.
 */
let namedGroups = {};

/**
 * Parsing string.
 */
let parsingString = '';

yyparse.onParseBegin = (string, lexer) => {
  parsingString = string;
  capturingGroupsCurrentLower = 0;
  currentCapturingGroup = 0;
  capturingGroupsCount = 0;
  namedGroups = {};

  const lastSlash = string.lastIndexOf('/');
  const flags = string.slice(lastSlash);

  if (flags.includes('x') && flags.includes('u')) {
    lexer.pushState('xu');
  } else {
    if (flags.includes('x')) {
      lexer.pushState('x');
    }
    if (flags.includes('u')) {
      lexer.pushState('u');
    }
  }
};

yyparse.onShift = token => {
  if (token.type === 'L_PAREN' || token.type === 'NAMED_CAPTURE_GROUP') {
    currentCapturingGroup++;
    capturingGroupsCount++;
  }
  return token;
};

/**
 * Updates the capturing groups counts.
 */
function updateCapturingGroupTracking() {
  // Go up.
  currentCapturingGroup--;

  // We reached the top level, reset the current group:
  if (currentCapturingGroup === capturingGroupsCurrentLower) {
    currentCapturingGroup = capturingGroupsCount;
    capturingGroupsCurrentLower = capturingGroupsCount;
  }
}

/**
 * Extracts ranges from the range string.
 */
function getRange(text) {
  const range = text.match(/\d+/g).map(Number);

  if (Number.isFinite(range[1]) && range[1] < range[0]) {
    throw new SyntaxError(`Numbers out of order in ${text} quantifier`);
  }

  return range;
}

/**
 * Checks class range
 */
function checkClassRange(from, to) {
  if (from.kind === 'control' || to.kind === 'control' || (!isNaN(from.codePoint) && !isNaN(to.codePoint) && from.codePoint > to.codePoint)) {
    throw new SyntaxError(`Range ${from.value}-${to.value} out of order in character class`);
  }
}

/**
 * Creates a character node.
 */
function Char(value, kind, loc) {
  let symbol;
  let codePoint;

  switch (kind) {
    case 'decimal': {
      codePoint = Number(value.slice(1));
      symbol = String.fromCodePoint(codePoint);
      break;
    }
    case 'oct': {
      codePoint = parseInt(value.slice(1), 8);
      symbol = String.fromCodePoint(codePoint);
      break;
    }
    case 'hex':
    case 'unicode': {
      if (value.lastIndexOf('\\u') > 0) {
        let [lead, trail] = value.split('\\u').slice(1);
        lead = parseInt(lead, 16);
        trail = parseInt(trail, 16);
        codePoint = (lead - 0xd800) * 0x400 + (trail - 0xdc00) + 0x10000;

        symbol = String.fromCodePoint(codePoint);
      } else {
        const hex = value.slice(2).replace('{', '');
        codePoint = parseInt(hex, 16);
        if (codePoint > 0x10ffff) {
          throw new SyntaxError(`Bad character escape sequence: ${value}`);
        }

        symbol = String.fromCodePoint(codePoint);
      }
      break;
    }
    case 'meta': {
      switch (value) {
        case '\\t':
          symbol = '\t';
          codePoint = symbol.codePointAt(0);
          break;
        case '\\n':
          symbol = '\n';
          codePoint = symbol.codePointAt(0);
          break;
        case '\\r':
          symbol = '\r';
          codePoint = symbol.codePointAt(0);
          break;
        case '\\v':
          symbol = '\v';
          codePoint = symbol.codePointAt(0);
          break;
        case '\\f':
          symbol = '\f';
          codePoint = symbol.codePointAt(0);
          break;
        case '\\b':
          symbol = '\b';
          codePoint = symbol.codePointAt(0);
        case '\\0':
          symbol = '\0';
          codePoint = 0;
        case '.':
          symbol = '.';
          codePoint = NaN;
          break;
        default:
          codePoint = NaN;
      }
      break;
    }
    case 'simple': {
      symbol = value;
      codePoint = symbol.codePointAt(0);
      break;
    }
  }

  return Node({
    type: 'Char',
    value,
    kind,
    symbol,
    codePoint,
  }, loc);
}

/**
 * Valid flags per current ECMAScript spec and
 * stage 3+ proposals.
 */
const validFlags = 'gimsuxy';

/**
 * Checks the flags are valid, and that
 * we don't duplicate flags.
 */
function checkFlags(flags) {
  const seen = new Set();

  for (const flag of flags) {
    if (seen.has(flag) || !validFlags.includes(flag)) {
      throw new SyntaxError(`Invalid flags: ${flags}`);
    }
    seen.add(flag);
  }

  return flags.split('').sort().join('');
}

/**
 * Parses patterns like \1, \2, etc. either as a backreference
 * to a group, or a deciaml char code.
 */
function GroupRefOrDecChar(text, textLoc) {
  const reference = Number(text.slice(1));

  if (reference > 0 && reference <= capturingGroupsCount) {
    return Node({
      type: 'Backreference',
      kind: 'number',
      number: reference,
      reference,
    }, textLoc);
  }

  return Char(text, 'decimal', textLoc);
}

/**
 * Unicode names.
 */
const uRe = /^\\u[0-9a-fA-F]{4}/;
const ucpRe = /^\\u\{[0-9a-fA-F]{1,}\}/;

/**
 * Validates Unicode group name.
 */
function validateUnicodeGroupName(name, state) {
  const isUnicodeName = uRe.test(name) || ucpRe.test(name);
  const isUnicodeState = (state === 'u' || state === 'xu' || state === 'u_class');

  if (isUnicodeName && !isUnicodeState) {
    throw new SyntaxError(`invalid group Unicode name "${name}", use \`u\` flag.`);
  }
}

/**
 * Extracts from `\k<foo>` pattern either a backreference
 * to a named capturing group (if it presents), or parses it
 * as a list of char: `\k`, `<`, `f`, etc.
 */
function NamedGroupRefOrChars(text, textLoc) {
  const groupName = text.slice(3, -1);

  if (namedGroups.hasOwnProperty(groupName)) {
    return Node({
      type: 'Backreference',
      kind: 'name',
      number: namedGroups[groupName],
      reference: groupName,
    }, textLoc);
  }

  // Else `\k<foo>` should be parsed as a list of `Char`s.
  // This is really a 0.01% edge case, but we should handle it.

  let startOffset = null;
  let startLine = null;
  let endLine = null;
  let startColumn = null;

  if (textLoc) {
    startOffset = textLoc.startOffset;
    startLine = textLoc.startLine;
    endLine = textLoc.endLine;
    startColumn = textLoc.startColumn;
  }

  const charRe = /^[\w$<>]/;
  let loc;

  const chars = [
    // Init to first \k, taking 2 symbols.
    Char(
      text.slice(1, 2),
      'simple',
      startOffset
        ? {
          startLine,
          endLine,
          startColumn,
          startOffset,
          endOffset: startOffset += 2,
          endColumn: startColumn += 2,
        }
        : null
    ),
  ];

  // For \k
  chars[0].escaped = true;

  // Other symbols.
  text = text.slice(2);

  while (text.length > 0) {
    let matched = null;

    // Unicode, \u003B or \u{003B}
    if ((matched = text.match(uRe)) || (matched = text.match(ucpRe))) {
      if (startOffset) {
        loc = {
          startLine,
          endLine,
          startColumn,
          startOffset,
          endOffset: (startOffset += matched[0].length),
          endColumn: (startColumn += matched[0].length),
        };
      }
      chars.push(Char(matched[0], 'unicode', loc));
      text = text.slice(matched[0].length);
    }

    // Simple char.
    else if ((matched = text.match(charRe))) {
      if (startOffset) {
        loc = {
          startLine,
          endLine,
          startColumn,
          startOffset,
          endOffset: ++startOffset,
          endColumn: ++startColumn,
        };
      }
      chars.push(Char(matched[0], 'simple', loc));
      text = text.slice(1);
    }
  }

  return chars;
}

/**
 * Creates an AST node with a location.
 */
function Node(node, loc) {
  if (yy.options.captureLocations) {
    node.loc = {
      source: parsingString.slice(loc.startOffset, loc.endOffset),
      start: {
        line: loc.startLine,
        column: loc.startColumn,
        offset: loc.startOffset,
      },
      end: {
        line: loc.endLine,
        column: loc.endColumn,
        offset: loc.endOffset,
      },
    };
  }
  return node;
}

/**
 * Creates location node.
 */
function loc(start, end) {
  if (!yy.options.captureLocations) {
    return null;
  }

  return {
    startOffset: start.startOffset,
    endOffset: end.endOffset,
    startLine: start.startLine,
    endLine: end.endLine,
    startColumn: start.startColumn,
    endColumn: end.endColumn,
  };
}

%}

%%

RegExp
  : SLASH Pattern SLASH OptFlags
    {
      $$ = Node({
        type: 'RegExp',
        body: $2,
        flags: checkFlags($4),
      }, loc(@1, @4 || @3))
    }
  ;

OptFlags
  : Flags
  | /* empty */ { $$ = '' }
  ;

Flags
  : CHAR
  | Flags CHAR { $$ = $1 + $2 }
  ;

Pattern
  : Disjunction
  ;

Disjunction
  : Alternative

  | Disjunction BAR Alternative
    {
      // Location for empty disjunction: /|/
      let _loc = null;

      if (@2) {
        _loc = loc(@1 || @2, @3 || @2);
      };

      $$ = Node({
        type: 'Disjunction',
        left: $1,
        right: $3,
      }, _loc)
    }
  ;

Alternative
  : AlternativeEntries
    {
      if ($1.length === 0) {
        $$ = null;
        return;
      }

      if ($1.length === 1) {
        $$ = Node($1[0], @$);
      } else {
        $$ = Node({
          type: 'Alternative',
          expressions: $1,
        }, @$)
      }
    }
  ;

AlternativeEntries
  : /* empty */
    { $$ = [] }

  | AlternativeEntries Term
    { $$ = $1.concat($2) }
  ;

Term
  : Assertion
    { $$ = Node(Object.assign({type: 'Assertion'}, $1), @$) }

  | Atom OptQuantifier
    {
      $$ = $1;

      if ($2) {
        $$ = Node({
          type: 'Repetition',
          expression: $1,
          quantifier: $2,
        }, @$)
      }
    }
  ;

Assertion
  : BOS       { $$ = { kind: '^' } }
  | EOS       { $$ = { kind: '$' } }
  | ESC_b     { $$ = { kind: '\\b' } }
  | ESC_B     { $$ = { kind: '\\B' } }

  | POS_LA_ASSERT Disjunction R_PAREN
    {
      $$ = {
        kind: 'Lookahead',
        assertion: $2,
      }
    }

  | NEG_LA_ASSERT Disjunction R_PAREN
    {
      $$ = {
        kind: 'Lookahead',
        negative: true,
        assertion: $2,
      }
    }

  | POS_LB_ASSERT Disjunction R_PAREN
    {
      $$ = {
        kind: 'Lookbehind',
        assertion: $2,
      }
    }

  | NEG_LB_ASSERT Disjunction R_PAREN
    {
      $$ = {
        kind: 'Lookbehind',
        negative: true,
        assertion: $2,
      }
    }
  ;

Atom
  : SourceCharacter
  | CharacterClass
  | Group
  ;

SourceCharacter
  : CHAR
    { $$ = Char($1, 'simple', @$) }

  | ESC_CHAR
    { $$ = Char($1.slice(1), 'simple', @$); $$.escaped = true; }

  | U_CODE_SURROGATE
    { $$ = Char($1, 'unicode', @$); $$.isSurrogatePair = true; }

  | U_CODE
    { $$ = Char($1, 'unicode', @$) }

  | CTRL_CH
    { $$ = Char($1, 'control', @$) }

  | HEX_CODE
    { $$ = Char($1, 'hex', @$) }

  | OCT_CODE
    { $$ = Char($1, 'oct', @$) }

  | DEC_CODE
    { $$ = GroupRefOrDecChar($1, @$) }

  | META_CHAR
    { $$ = Char($1, 'meta', @$) }

  | ANY
    { $$ = Char($1, 'meta', @$) }

  | NAMED_GROUP_REF
    { $$ = NamedGroupRefOrChars($1, @1) }

  ;

OptQuantifier
  : Quantifier
  | /* empty */
  ;

Quantifier
  : QuantifierPrefix
  | QuantifierPrefix Q_MARK
    {
      $1.greedy = false;
      $$ = $1;
    }
  ;

QuantifierPrefix
  : STAR
    {
      $$ = Node({
        type: 'Quantifier',
        kind: $1,
        greedy: true,
      }, @$)
    }

  | PLUS
    {
      $$ = Node({
        type: 'Quantifier',
        kind: $1,
        greedy: true,
      }, @$)
    }

  | Q_MARK
    {
      $$ = Node({
        type: 'Quantifier',
        kind: $1,
        greedy: true,
      }, @$)
    }

  | RANGE_EXACT
    {
      const range = getRange($1);
      $$ = Node({
        type: 'Quantifier',
        kind: 'Range',
        from: range[0],
        to: range[0],
        greedy: true,
      }, @$)
    }

  | RANGE_OPEN
    {
      $$ = Node({
        type: 'Quantifier',
        kind: 'Range',
        from: getRange($1)[0],
        greedy: true,
      }, @$)
    }

  | RANGE_CLOSED
    {
      const range = getRange($1);
      $$ = Node({
        type: 'Quantifier',
        kind: 'Range',
        from: range[0],
        to: range[1],
        greedy: true,
      }, @$)
    }
  ;

Group
  : CapturingGroup
  | NonCapturingGroup
  ;

CapturingGroup
  : NAMED_CAPTURE_GROUP Disjunction R_PAREN
    {
      if (namedGroups.hasOwnProperty($1)) {
        throw new SyntaxError(`Duplicate of the named group "${$1}".`);
      }

      namedGroups[$1] = currentCapturingGroup;

      $$ = Node({
        type: 'Group',
        capturing: true,
        name: $1,
        number: currentCapturingGroup,
        expression: $2,
      }, @$);

      updateCapturingGroupTracking();
    }

  | L_PAREN Disjunction R_PAREN
    {
      $$ = Node({
        type: 'Group',
        capturing: true,
        number: currentCapturingGroup,
        expression: $2,
      }, @$);

     updateCapturingGroupTracking();
    }
  ;

NonCapturingGroup
  : NON_CAPTURE_GROUP Disjunction R_PAREN
    {
      $$ = Node({
        type: 'Group',
        capturing: false,
        expression: $2,
      }, @$)
    }
  ;

CharacterClass
  : NEG_CLASS ClassRanges R_BRACKET
    {
      $$ = Node({
        type: 'CharacterClass',
        negative: true,
        expressions: $2,
      }, @$)
    }
  | L_BRACKET ClassRanges R_BRACKET
    {
      $$ = Node({
        type: 'CharacterClass',
        expressions: $2,
      }, @$)
    }
  ;

ClassRanges
  : /* empty */
    { $$ = [] }

  | NonemptyClassRanges
  ;

NonemptyClassRanges
  : ClassAtom
    { $$ = [$1] }

  | ClassAtom NonemptyClassRangesNoDash
    { $$ = [$1].concat($2) }

  | ClassAtom DASH ClassAtom ClassRanges
    {
      checkClassRange($1, $3);

      $$ = [
        Node({
          type: 'ClassRange',
          from: $1,
          to: $3,
        }, loc(@1, @3))
      ];

      if ($4) {
        $$ = $$.concat($4);
      }
    }
  ;

NonemptyClassRangesNoDash
  : ClassAtom
  | ClassAtomNoDash NonemptyClassRangesNoDash
    { $$ = [$1].concat($2) }

  | ClassAtomNoDash DASH ClassAtom ClassRanges
    {
      checkClassRange($1, $3);

      $$ = [
        Node({
          type: 'ClassRange',
          from: $1,
          to: $3,
        }, loc(@1, @3)),
      ];

      if ($4) {
        $$ = $$.concat($4);
      }
    }
  ;

ClassAtom
  : DASH
    { $$ = Char($1, 'simple', @$) }

  | ClassAtomNoDash
  ;

ClassAtomNoDash
  : SourceCharacter

  | ESC_b
    { $$ = Char($1, 'meta', @$) }
  ;