Regex to DFA parser in Dart

Question

I've created a Regex to DFA parser, using Thompson's construction algorithm and epsilon-reduction. Here is the code:

builtins.dart:

bool setEquals(Set a, Set b) {
  List temp_a = a.toList();
  List temp_b = b.toList();

  return listEquals(temp_a, temp_b);
}

bool listEquals(List a, List b) {
  a.sort();
  b.sort();

  for (int c = 0; c < a.length; c++) {
    if (a[c] != b[c])
      return false;
  }

  return true;
}

Node.dart:

/// A node - required for the NFA and DFA.
class Node {
  int ident;
  List paths;

  Node(int ident) {
    this.ident = ident;
    this.paths = [];
  }

  void addPath(String char, Node node) {
    this.paths.add([char, node.ident]);
  }

  void removePath(int node_ident) {
    for (int a = 0; a < this.paths.length; a++) {
      int destination = this.paths[a][1];

      if (node_ident == destination) {
        this.paths.removeAt(a);
        return;
      }
    }
  }
}

NondeterministicFA.dart:

import "Node.dart";

String EPSILON = "";

/// The main class for the non-determinstic automaton
/// generated by Thompson's algorithm.
class NondeterministicFA {
  String regex;
  List<Node> nodes;
  int node_index;

  /// Checks if a string has balanced parentheses.
  bool _isBalanced(String str) {
    int index = 0;

    for (int a = 0; a < str.length; a++) {
      if (str[a] == "(")
        index++;
      else if (str[a] == ")")
        index--;
    }

    return index == 0;
  }

  /// Turns the regex into something easier to parse
  /// for the NFA.
  List _regexToGroups(String regex) {
    List regex_groups = [];
    Map quantifiers = {
      "*": "STAR",
      "+": "PLUS",
      "?": "QMARK"
    };

    while (regex.length > 0) {
      if (regex[0] == "(") {
        int paren_count = 1;
        int paren_index = 1;

        while (paren_count != 0) {
          if (regex[paren_index] == "(")
            paren_count += 1;
          else if (regex[paren_index] == ")")
            paren_count -= 1;

          paren_index += 1;
        }

        List<String> inside_parens = regex.substring(1, paren_index - 1).split("|");
        List temp = [];

        if (this._isBalanced(inside_parens[0])) {
          temp.add("OR");
        } else {
          inside_parens = [inside_parens.join("|")];
        }

        List other = inside_parens.map((str) => ["GROUP", this._regexToGroups(str)]).toList();

        if (other.length == 1) {
          temp.addAll(other[0]);
        } else {
          temp.addAll(other);
        }

        if (quantifiers.containsKey(regex[paren_index])) {
          regex_groups.add([quantifiers[regex[paren_index]], temp]);
          regex = regex.substring(paren_index + 1);
        } else {
          regex_groups.add(temp);
          regex = regex.substring(paren_index);
        }
      } else {
        if (regex.length > 1 && quantifiers.containsKey(regex[1])) {
          regex_groups.add([quantifiers[regex[1]], ["CHAR", regex[0]]]);
          regex = regex.substring(2);
        } else {
          regex_groups.add(["CHAR", regex[0]]);
          regex = regex.substring(1);
        }
      }
    }

    return regex_groups;
  }

  /// Connects two nodes together, according to the rules of
  /// Thompson's Construction Algorithm.
  void _connectNode(List group, Node start, Node end) {
    int temp_index = this.node_index;

    if (group[0] == "STAR") {
      this.node_index += 2;
      Node left = new Node(temp_index);
      Node right = new Node(temp_index + 1);

      start.addPath(EPSILON, left);
      start.addPath(EPSILON, end);
      right.addPath(EPSILON, left);
      right.addPath(EPSILON, end);

      this._connectNode(group[1], left, right);
      this.nodes.addAll([left, right]);
    } else if (group[0] == "PLUS") {
      this.node_index += 2;
      Node left = new Node(temp_index);
      Node right = new Node(temp_index + 1);

      start.addPath(EPSILON, left);
      right.addPath(EPSILON, left);
      right.addPath(EPSILON, end);

      this._connectNode(group[1], left, right);
      this.nodes.addAll([left, right]);
    } else if (group[0] == "QMARK") {
      start.addPath(EPSILON, end);

      this._connectNode(group[1], start, end);
    } else if (group[0] == "OR") {
      List connected_groups = group.sublist(1);
      this.node_index += connected_groups.length * 2;

      for (int a = 0; a < connected_groups.length; a++) {
        Node group_start = new Node(temp_index + (2 * a));
        Node group_end = new Node(temp_index + (2 * a) + 1);

        start.addPath(EPSILON, group_start);
        group_end.addPath(EPSILON, end);

        this._connectNode(connected_groups[a], group_start, group_end);
        this.nodes.addAll([group_start, group_end]);
      }
    } else if (group[0] == "GROUP") {
      List items = group[1];
      List<Node> group_nodes = [start];
      this.node_index += items.length - 1;

      for (int a = 0; a < items.length - 1; a++) {
        Node new_node = new Node(temp_index + a);

        this._connectNode(items[a], group_nodes[a], new_node);

        group_nodes.add(new_node);
      }

      this._connectNode(items[items.length - 1], group_nodes[group_nodes.length - 1], end);
      this.nodes.addAll(group_nodes.sublist(1));
    } else if (group[0] == "CHAR") {
      start.addPath(group[1], end);
    }
  }

  /// Parses the final regex.
  void _parseRegex() {
    List regex_groups = this._regexToGroups(this.regex);
    int starting_index = 0;

    for (int a = 0; a < regex_groups.length; a++) {
      List current_group = regex_groups[a];

      Node temp_node = new Node(this.node_index);
      this.node_index += 1;

      this._connectNode(current_group, this.nodes[starting_index], temp_node);

      this.nodes.add(temp_node);
      starting_index = this.nodes.length - 1;
    }

    this.nodes.sort((first, second) => first.ident - second.ident);
  }

  NondeterministicFA(String regex) {
    this.regex = regex;
    this.nodes = [new Node(0)];
    this.node_index = 1;

    this._parseRegex();
  }
}

DeterminsticFA.dart:

import "Node.dart";
import "NondeterministicFA.dart";

String EPSILON = "";

class DeterministicFA {
  List<Node> nodes;
  List test;

  List _movements(List<Node> nodes) {
    List moves = [];

    for (int a = 0; a < nodes.length; a++) {
      List move_paths = nodes[a].paths.where((path) => path[0] != EPSILON);

      moves.addAll(move_paths);
    }

    return moves;
  }

  List<int> _epsilonClosure(Node starting_node) {
    Set<int> accessible = new Set();

    for (List path in starting_node.paths) {
      String connect_item = path[0];
      int connect_node = path[1];

      if (connect_item == EPSILON) {
        accessible.add(connect_node);
      }
    }

    Set<int> new_elements = new Set();

    for (int a in accessible) {
      new_elements.addAll(this._epsilonClosure(this.nodes[a]));
      new_elements = new_elements.where((n) => !accessible.contains(n)).toSet();
    }

    if (new_elements.length == 0) {
      List<int> accessible_ls = accessible.toList();
      accessible_ls.insert(0, starting_node.ident);
      return accessible_ls;
    }

    accessible.addAll(new_elements);
    List<int> accessible_ls = accessible.toList();
    accessible_ls.insert(0, starting_node.ident);

    return accessible_ls;
  }

  List<Node> _toDeterministic() {
    List<Node> nfa_nodes = this.nodes;

    List<List<int>> new_nodes = [[0]];
    List<List> node_paths = [];
    Set<int> used_nodes = new Set();
    int ending_index;

    for (int a = 0; a < nfa_nodes.length; a++) {
      if (nfa_nodes[a].paths.length == 0)
        ending_index = a;
        break;
    }

    while (used_nodes.length < nfa_nodes.length || new_nodes.length > node_paths.length) {
      Set<int> connected_nodes = new Set();

      for (int a = new_nodes.length - node_paths.length; a > 0; a--) {
        List<int> starting_node = this._epsilonClosure(this.nodes[new_nodes[new_nodes.length - a][0]]);
        List connections = this._movements(starting_node.map((n) => this.nodes[n]).toList());
        print(starting_node);

        new_nodes[new_nodes.length - a] = starting_node;
        node_paths.add(connections);
        used_nodes.addAll(starting_node);
        connected_nodes.addAll(connections.map((n) => n[1]));
      }

      List<int> first_items = new_nodes.map((ls) => ls[0]);
      connected_nodes = connected_nodes.where((n) => !first_items.contains(n));

      new_nodes.addAll(connected_nodes.map((n) => [n]));
    }

    List<Node> actual_nodes = [];

    for (int a = 0; a < new_nodes.length; a++) {
      List paths = node_paths[a];
      Node temp_node = new Node(new_nodes[a][0]);

      for (int b = 0; b < paths.length; b++) {
        temp_node.addPath(paths[b][0], nodes[paths[b][1]]);
      }

      actual_nodes.add(temp_node);
    }

    this.nodes = actual_nodes;
  }

  DeterministicFA(NondeterministicFA nfa) {
    this.nodes = nfa.nodes;

    this._toDeterministic();
  }
}

(I apologise in advance for the lack of comments.)

Here are my main concerns with the code:

• There is definitely a lot of fluff in the code. A lot of the code felt like it was hacked on, and some unnecessary elements can definitely get removed.
• Readability is also a problem - I can hardly read the code myself. Is there any way to separate a larger function into a bunch of smaller functions?
• Speed may be an issue as well, since I'm designing this to rival Dart's native regex library, which uses JavaScript's regex flavour (which is awful).

Answer 1

There is no real reason to build the DFA upfront (which can be exponentially larger than the NFA). Instead you can create its nodes dynamically during simulation. Though a pass to squash the epsilon transitions would help simulation speed.

Your parsing method is a bit odd, you seem to go top down, first splitting the outer group into tokens and then creating the NFA out of that.

I think it would be more intuitive to use a stack based approach like shunting yard.

When you pop operator you pop 2 nodes from the value stack and combine them using the Thompson's Construction Algorithm based on the popped operator and push the resulting node back on the value stack.

When you see a non-operator you insert a concat operator in front of it and process that first if it isn't the first char or after an opening parenthesis.

bool seenChar = false;
foreach(char c in regex){
    if(isChar(c)){
        if(seenChar) pushOperator(Concat);
        pushValue(c);
        seenChar = true;
        continue;
    }

    if(c=='('){
        if(seenChar) pushOperator(Concat);
        pushOperator(OpenParen);
        seenChar = false;
    } else if(c==')'){
        pushOperator(CloseParen); 
        //will actually result in popping operators off the stack 
        //up until the top most OpenParen is popped
    } else if(c=='|'){
        pushOperator(Or);
        seenChar = false;
    } else if(c=='*'){
        pushOperator(KleineStar);
    } else if(c=='?'){
        pushOperator(Optional);
    }
}

Capturing groups can be handled my marking some states as starting or ending captures. During simulation you then have a list per NFA state of captured substring indices that you propagate along. If the current DFA state contains S1 with a capture with an outgoing connection with a to S2 and it sees an a then the new state of the DFA will contain S2 with those same captures.

If 2 paths with captures lead to the same NFA state then you discard one of them based on a priority rule that is filled in based on the greedyness of the operator that led to the merge.

states = {start};//each state can also contain auxiliary data about capturing groups.

foreach(c in input){

    newStates = {};

    foreach(state in states){
        newStates.addAll(state.nextStatesFor(c));
    }
    states = newStates;
    if(states.contains(finalState))return true;
}

Answer 2

Just about the built-ins, which it doesn't seem like you are even using, the set equality is terribly expensive, and assumes that the elements are Comparable (so that the list of them can be sorted).

In practice, you only use values that are integers (likely in a limited range of non-negative numbers). You can probably create an efficient bit set for that, but even without that, I'd write the set-equals as:

bool setEquals(Set<int> a, Set<int> b) => 
    a.length == b.length && a.containsAll(b);

While it's possible to create sets that would not work correctly with this, it takes actual work and using a different equality relation on integers than the default. That doesn't apply here.

Creating copies of all the elements of both sets, then sorting them, and then iterating them, is far too much work. (Also, it doesn't even check that the lists have the same length, so there's an IndexError waiting to happen if the first set differ from the second only by containing more elements that are larger than the rest of the elements.)