regexp-tree-cli

Regular expressions processor in JavaScript

The regexp-tree-cli is a command line utility fo the regexp-tree package.

Table of Contents

• Installation
• Development
• Usage as a CLI
• Parsing and printing AST
• Capturing locations
• Using optimizer API
• Using compat-transpiler API
• Printing NFA/DFA tables

Installation

The CLI can be installed as an npm module:

npm install -g regexp-tree-cli

regexp-tree-cli --help

Development

1. Fork https://github.com/DmitrySoshnikov/regexp-tree-cli repo
2. If there is an actual issue from the issues list you'd like to work on, feel free to assign it yourself, or comment on it to avoid collisions (open a new issue if needed)
3. Make your changes
4. Submit a PR

Usage as a CLI

Check the options available from CLI:

regexp-tree-cli --help

Usage: regexp-tree-cli [options]

Options:
  --help, -h        Show help                                          [boolean]
  --version, -v     Show version number                                [boolean]
  --expression, -e  A regular expression to be parsed                 [required]
  --loc, -l         Whether to capture AST node locations
  --optimize, -o    Apply optimizer on the passed expression
  --compat, -c      Apply compat-transpiler on the passed expression
  --table, -t       Print NFA/DFA transition tables (nfa/dfa/all)
                                                  [choices: "nfa", "dfa", "all"]

Parsing and printing AST

To parse a regular expression, pass -e option:

regexp-tree-cli -e '/a|b/i'

Which produces an AST node corresponding to this regular expression:

1{
2  type: 'RegExp',
3  body: {
4    type: 'Disjunction',
5    left: {
6      type: 'Char',
7      value: 'a',
8      symbol: 'a',
9      kind: 'simple',
10      codePoint: 97
11    },
12    right: {
13      type: 'Char',
14      value: 'b',
15      symbol: 'b',
16      kind: 'simple',
17      codePoint: 98
18    }
19  },
20  flags: 'i',
21}

NOTE: the format of a regexp is / Body / OptionalFlags.

Capturing locations

For source code transformation tools it might be useful also to capture locations of the AST nodes. From the command line it's controlled via the -l option:

regexp-tree-cli -e '/ab/' -l

This attaches loc object to each AST node:

1{
2  type: 'RegExp',
3  body: {
4    type: 'Alternative',
5    expressions: [
6      {
7        type: 'Char',
8        value: 'a',
9        symbol: 'a',
10        kind: 'simple',
11        codePoint: 97,
12        loc: {
13          start: {
14            line: 1,
15            column: 1,
16            offset: 1,
17          },
18          end: {
19            line: 1,
20            column: 2,
21            offset: 2,
22          },
23        }
24      },
25      {
26        type: 'Char',
27        value: 'b',
28        symbol: 'b',
29        kind: 'simple',
30        codePoint: 98,
31        loc: {
32          start: {
33            line: 1,
34            column: 2,
35            offset: 2,
36          },
37          end: {
38            line: 1,
39            column: 3,
40            offset: 3,
41          },
42        }
43      }
44    ],
45    loc: {
46      start: {
47        line: 1,
48        column: 1,
49        offset: 1,
50      },
51      end: {
52        line: 1,
53        column: 3,
54        offset: 3,
55      },
56    }
57  },
58  flags: '',
59  loc: {
60    start: {
61      line: 1,
62      column: 0,
63      offset: 0,
64    },
65    end: {
66      line: 1,
67      column: 4,
68      offset: 4,
69    },
70  }
71}

Using optimizer API

Optimizer transforms your regexp into an optimized version, replacing some sub-expressions with their idiomatic patterns. This might be good for different kinds of minifiers, as well as for regexp machines.

NOTE: the Optimizer is implemented as a set of regexp-tree plugins.

From CLI the optimizer is available via --optimize (-o) option:

regexp-tree-cli -e '/[a-zA-Z_0-9][A-Z_\da-z]*\e{1,}/' -o

Result:

Optimized: /\w+e+/

See the optimizer README for more details.

Using compat-transpiler API

The compat-transpiler module translates your regexp in new format or in new syntax, into an equivalent regexp in a legacy representation, so it can be used in engines which don't yet implement the new syntax.

NOTE: the compat-transpiler is implemented as a set of regexp-tree plugins.

Example, "dotAll" s flag:

1/./s

Is translated into:

1/[\0-\uFFFF]/

Or named capturing groups:

1/(?<value>a)\k<value>\1/

Becomes:

1/(a)\1\1/

From CLI the compat-transpiler is available via --compat (-c) option:

regexp-tree-cli -e '/(?<all>.)\k<all>/s' -c

Result:

Compat: /([\0-\uFFFF])\1/

Printing NFA/DFA tables

The --table option allows displaying NFA/DFA transition tables. RegExp Tree also applies DFA minimization (using N-equivalence algorithm), and produces the minimal transition table as its final result.

In the example below for the /a|b|c/ regexp, we first obtain the NFA transition table, which is further converted to the original DFA transition table (down from the 10 non-deterministic states to 4 deterministic states), and eventually minimized to the final DFA table (from 4 to only 2 states).

./bin/regexp-tree-cli -e '/a|b|c/' --table all

Result:

> - starting
✓ - accepting

NFA transition table:

┌─────┬───┬───┬────┬─────────────┐
│     │ a │ b │ c  │ ε*          │
├─────┼───┼───┼────┼─────────────┤
│ 1 > │   │   │    │ {1,2,3,7,9} │
├─────┼───┼───┼────┼─────────────┤
│ 2   │   │   │    │ {2,3,7}     │
├─────┼───┼───┼────┼─────────────┤
│ 3   │ 4 │   │    │ 3           │
├─────┼───┼───┼────┼─────────────┤
│ 4   │   │   │    │ {4,5,6}     │
├─────┼───┼───┼────┼─────────────┤
│ 5   │   │   │    │ {5,6}       │
├─────┼───┼───┼────┼─────────────┤
│ 6 ✓ │   │   │    │ 6           │
├─────┼───┼───┼────┼─────────────┤
│ 7   │   │ 8 │    │ 7           │
├─────┼───┼───┼────┼─────────────┤
│ 8   │   │   │    │ {8,5,6}     │
├─────┼───┼───┼────┼─────────────┤
│ 9   │   │   │ 10 │ 9           │
├─────┼───┼───┼────┼─────────────┤
│ 10  │   │   │    │ {10,6}      │
└─────┴───┴───┴────┴─────────────┘


DFA: Original transition table:

┌─────┬───┬───┬───┐
│     │ a │ b │ c │
├─────┼───┼───┼───┤
│ 1 > │ 4 │ 3 │ 2 │
├─────┼───┼───┼───┤
│ 2 ✓ │   │   │   │
├─────┼───┼───┼───┤
│ 3 ✓ │   │   │   │
├─────┼───┼───┼───┤
│ 4 ✓ │   │   │   │
└─────┴───┴───┴───┘


DFA: Minimized transition table:

┌─────┬───┬───┬───┐
│     │ a │ b │ c │
├─────┼───┼───┼───┤
│ 1 > │ 2 │ 2 │ 2 │
├─────┼───┼───┼───┤
│ 2 ✓ │   │   │   │
└─────┴───┴───┴───┘