2
\$\begingroup\$

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).
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ How would a shunting yard algorithm work in this scenario? The "or" function can be applied to multiple elements, and most functions are monadic (e.g. "*" is the Kleene star, and only works on one character or group). How would I process through capturing groups in this scenario? \$\endgroup\$ – Qwerp-Derp Jun 29 '17 at 8:52
  • \$\begingroup\$ @Qwerp-Derp Oh right, forgot that * and ? binds tighter than concat. You can instead insert an imaginary infix concat operator between every 2 non-operators and process it like normal. The | issue is solved by setting whether it's left or right associative. Doesn't really matter in this case because | is associative anyway a|b|c is equal to (a|b)|c is equal to a|(b|c). \$\endgroup\$ – ratchet freak Jun 29 '17 at 9:06
  • \$\begingroup\$ Also, how would a DFA be more complex than an NFA via epsilon-reduction? There are less overall nodes, and less paths between nodes - I don't see how a DFA would be more complicated. \$\endgroup\$ – Qwerp-Derp Jun 30 '17 at 10:21
  • \$\begingroup\$ @Qwerp-Derp the equivalent DFA of a n-state NFA can have up to 2^n states. Adversarial users will use that to blow up your algorithm (like how you can use catastrophic backtracking in most regex engines to kill performance). \$\endgroup\$ – ratchet freak Jun 30 '17 at 11:09
  • \$\begingroup\$ I understand this sounds like "gimme teh codez", but could you provide some code examples with your thing? I'm barely wrapping my head around much of this. Also, I'm not sure if this covers my main concerns of "reducing code size" and "improving readability". \$\endgroup\$ – Qwerp-Derp Jun 30 '17 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.