chapter-2: Update regular expressions file.

1 files changed, 65 insertions, 0 deletions

diff --git a/chapter-2/2.2-regular-expressions.scm b/chapter-2/2.2-regular-expressions.scm
index fa92120..236d778 100644
--- a/chapter-2/2.2-regular-expressions.scm
+++ b/chapter-2/2.2-regular-expressions.scm
@@ -151,4 +151,69 @@
 (grep-test (r:seq (r:quote "foo") (r:+ (r:quote "bar")))
            '(not "foo") "foobar" "foobarbar")
 
+
 ;; Exercise 2.7: A bug, one bad joke, two tweaks, and a revelation
+
+;; Helpful context: The POSIX standard chapter on regular expressions:
+;; https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html
+
+;; a
+
+;; Unbounded recursion!
+
+;; b
+
+;; Eva's proposal runs in linear time and produces a relatively
+;; concise regular expression.  Alyssa's proposal would produce a
+;; massively long expression that specifies, in full detail, all of
+;; the permutations that should match.  Passing #f for the max
+;; argument would result in unbounded recursion.  Leaving that issue
+;; aside, the time complexity also suffers.  In addition to looping (-
+;; max min) times, each iteration of this outer loop would need an
+;; additional inner loop requiring min, min + 1, min + 2, ..., max
+;; iterations.
+
+;; c
+
+;; Ben's propsoal of using interval expression has numerous
+;; advantages. Interval expressions are a feature of the underlying
+;; language so the combinator implementation is straightforward,
+;; produces small expression strings, and is constant time rather than
+;; linear time.  Eva's proposal requires targeting the ERE language
+;; rather than BRE, which is incompatible with BRE, so other aspects
+;; of the implemenation would likely have to be changed.
+
+;; d
+
+(define (r:repeat min max expr)
+  (cond
+   ((not max)
+    (string-append expr "\\{" (number->string min) ",\\}"))
+   ((= max min)
+    (string-append expr "\\{" (number->string min) "\\}"))
+   (else
+    (string-append expr "\\{" (number->string min) ","
+                   (number->string max) "\\}"))))
+
+(grep-test (r:repeat 3 5 (r:alt (r:quote "cat") (r:quote "dog")))
+           "catdogcat"
+           "catcatdogdog"
+           "dogdogcatdogdog"
+           '(not "catdogfrog"))
+(grep-test (r:repeat 2 #f (r:alt (r:quote "cat") (r:quote "dog")))
+           "catdog"
+           "catdogdog"
+           '(not "cat")
+           '(not "dog")
+           '(not "dogfrog"))
+(grep-test (r:repeat 2 2 (r:alt (r:quote "cat") (r:quote "dog")))
+           "catdog"
+           "catcat"
+           "dogdog"
+           '(not "catfrogdog")
+           '(not "cat")
+           '(not "dog")
+           '(not "dogfrog"))
+
+
+;; Exercise 2.8: Too much nesting