regexp-tree - npm Package Compare versions

Comparing version 0.0.79 to 0.0.80

dist/bin/regexp-tree.js

@@ -103,3 +103,6 @@ /**
       var dfa = fa.toDFA(expression);
-      dfa.printTransitionTable();
+      dfa.printTransitionTable('\nDFA: Original transition table:\n');
+
+      dfa.minimize();
+      dfa.printTransitionTable('\nDFA: Minimized transition table:\n');
     }
@@ -106,0 +109,0 @@

dist/interpreter/finite-automaton/dfa/dfa-minimizer.js

@@ -109,3 +109,3 @@ /**
                 // just append this state to the same set.
-                if (areEquivalent(state, handledState, alphabet)) {
+                if (areEquivalent(state, handledState, table, alphabet)) {
                   handledStates[handledState].add(state);
@@ -257,9 +257,34 @@ handledStates[state] = handledStates[handledState];
 
-          // All states in a set are equivalent, so take the first one
-          // to see where it goes on symbol.
-          var originalState = set.values().next().value;
           updateAcceptingStates(set, _idx);
 
-          var originalTransition = table[originalState][symbol];
+          // Determine original transition for this symbol from the set.
+          var originalTransition = void 0;
+          var _iteratorNormalCompletion7 = true;
+          var _didIteratorError7 = false;
+          var _iteratorError7 = undefined;
 
+          try {
+            for (var _iterator7 = set[Symbol.iterator](), _step7; !(_iteratorNormalCompletion7 = (_step7 = _iterator7.next()).done); _iteratorNormalCompletion7 = true) {
+              var originalState = _step7.value;
+
+              originalTransition = table[originalState][symbol];
+              if (originalTransition) {
+                break;
+              }
+            }
+          } catch (err) {
+            _didIteratorError7 = true;
+            _iteratorError7 = err;
+          } finally {
+            try {
+              if (!_iteratorNormalCompletion7 && _iterator7.return) {
+                _iterator7.return();
+              }
+            } finally {
+              if (_didIteratorError7) {
+                throw _iteratorError7;
+              }
+            }
+          }
+
           if (originalTransition) {
@@ -336,12 +361,12 @@ minimizedTable[_idx][symbol] = remaped.get(currentTransitionMap[originalTransition]);
  */
-function areEquivalent(s1, s2, alphabet) {
-  var _iteratorNormalCompletion7 = true;
-  var _didIteratorError7 = false;
-  var _iteratorError7 = undefined;
+function areEquivalent(s1, s2, table, alphabet) {
+  var _iteratorNormalCompletion8 = true;
+  var _didIteratorError8 = false;
+  var _iteratorError8 = undefined;
 
   try {
-    for (var _iterator7 = alphabet[Symbol.iterator](), _step7; !(_iteratorNormalCompletion7 = (_step7 = _iterator7.next()).done); _iteratorNormalCompletion7 = true) {
-      var symbol = _step7.value;
+    for (var _iterator8 = alphabet[Symbol.iterator](), _step8; !(_iteratorNormalCompletion8 = (_step8 = _iterator8.next()).done); _iteratorNormalCompletion8 = true) {
+      var symbol = _step8.value;
 
-      if (!goToSameSet(s1, s2, symbol)) {
+      if (!goToSameSet(s1, s2, table, symbol)) {
         return false;
@@ -351,12 +376,12 @@ }
   } catch (err) {
-    _didIteratorError7 = true;
-    _iteratorError7 = err;
+    _didIteratorError8 = true;
+    _iteratorError8 = err;
   } finally {
     try {
-      if (!_iteratorNormalCompletion7 && _iterator7.return) {
-        _iterator7.return();
+      if (!_iteratorNormalCompletion8 && _iterator8.return) {
+        _iterator8.return();
       }
     } finally {
-      if (_didIteratorError7) {
-        throw _iteratorError7;
+      if (_didIteratorError8) {
+        throw _iteratorError8;
       }
@@ -372,7 +397,17 @@ }
  */
-function goToSameSet(s1, s2, symbol) {
+function goToSameSet(s1, s2, table, symbol) {
   if (!currentTransitionMap[s1] || !currentTransitionMap[s2]) {
     return false;
   }
-  return currentTransitionMap[s1][symbol] === currentTransitionMap[s2][symbol];
+
+  var originalTransitionS1 = table[s1][symbol];
+  var originalTransitionS2 = table[s2][symbol];
+
+  // If no actual transition on this symbol, treat it as positive.
+  if (!originalTransitionS1 && !originalTransitionS2) {
+    return true;
+  }
+
+  // Otherwise, check if they are in the same sets.
+  return currentTransitionMap[s1].has(originalTransitionS1) && currentTransitionMap[s2].has(originalTransitionS2);
 }
@@ -379,0 +414,0 @@

package.json

 {
   "name": "regexp-tree",
-  "version": "0.0.79",
+  "version": "0.0.80",
   "license": "MIT",
@@ -5,0 +5,0 @@ "description": "Regular Expressions parser in JavaScript",

README.md

@@ -31,2 +31,3 @@ # regexp-tree
 - [Using interpreter API](#using-interpreter-api)
+  - [Printing NFA/DFA tables](#printing-nfa-dfa-tables)
 - [AST nodes specification](#ast-nodes-specification)
@@ -120,40 +121,2 @@
 
-The `--table` option allows displaying NFA/DFA transition table:
-
-```
-./bin/regexp-tree -e '/ab/' --table all
-```
-
-Result:
-
-```
-> - starting
-✓ - accepting
-
-NFA transition table:
-
-┌─────┬───┬─────────┐
-│     │ a │ ε*      │
-├─────┼───┼─────────┤
-│ 1 > │   │ {1,2,4} │
-├─────┼───┼─────────┤
-│ 2   │ 3 │ 2       │
-├─────┼───┼─────────┤
-│ 3   │   │ {3,4,2} │
-├─────┼───┼─────────┤
-│ 4 ✓ │   │ {4,2}   │
-└─────┴───┴─────────┘
-
-
-DFA transition table:
-
-┌───────┬───┐
-│       │ a │
-├───────┼───┤
-│ 1 ✓ > │ 2 │
-├───────┼───┤
-│ 2 ✓   │ 2 │
-└───────┴───┘
-```
-
 > NOTE: the format of a regexp is `/ Body / OptionalFlags`.
@@ -689,2 +652,71 @@
 
+#### 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 -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 ✓ │   │   │   │
+└─────┴───┴───┴───┘
+```
+
 ### AST nodes specification
@@ -691,0 +723,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

255004

increased by1.47%

Lines of code

5783

increased by0.56%

Number of lines in readme file

1962

increased by1.66%

No dependency changes