progs/catastrophic/catastrophic.dart
author Christian Urban <christian.urban@kcl.ac.uk>
Mon, 14 Dec 2020 19:22:12 +0000
changeset 818 6928a677d26f
parent 777 a10430cb797c
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
777
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     1
/// A case of catastrophic backtracking in Dart
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     2
///---------------------------------------------
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     3
/// example provided by Martin Todorov
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     4
///
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     5
/// regex: (a*)*b
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     6
/// strings: aa...a
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     7
///
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     8
/// run with
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
     9
///
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    10
///    dart catastrophic.dart n
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    11
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    12
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    13
main(List<String> args) {
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    14
  final n = int.parse(args[0]);
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    15
  final evilRegex = RegExp("(a*)*b");
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    16
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    17
  for(int i = 1; i <= n; i++) {
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    18
    final toMatch = "a" * i;
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    19
    final stopwatch = Stopwatch()..start();
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    20
    evilRegex.hasMatch(toMatch);
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    21
    print("$i a's matched in ${stopwatch.elapsed}");
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    22
  }
a10430cb797c updated
Christian Urban <christian.urban@kcl.ac.uk>
parents:
diff changeset
    23
}