summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--chapter-2/2.2-regular-expressions.scm65
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