Реализация простого сканера / токенизатора с использованием регулярного выражения в clojure

Question

Я пытаюсь написать функцию с именем scan-for, которая, принимая в качестве входных данных набор строк («токены»), возвращает функцию «токенизатор», которая, принимая в качестве входных данных строку, возвращает (предпочтительно ленивый)последовательность строк, состоящая из «токенов», содержащихся во входных данных, распознаваемых жадным способом, и непустых подстрок между ними, в начале и конце, в порядке их появления на входе.

Например, ((scan-for ["an" "ban" "banal" "d"]) "ban bananas and banalities") должно выдать:

("ban" " " "ban" "an" "as " "an" "d" " " "banal" "ities")

В моей первой попытке я использую регулярное выражение, чтобы сопоставить "токены" (с re-seq) и найти промежуточные подстроки(с split) и затем чередуйте получающиеся последовательности.Проблема состоит в том, что входная строка анализируется дважды с помощью построенного регулярного выражения и что результирующая последовательность не является ленивой из-за split.

[В определении scan-for я использую молчаливый / point-free style (исключая лямбды и их замаскированные маскировки), которые я нахожу элегантными и полезными в целом ( Джон Бэкус, вероятно, согласится ).В ближайшем будущем это требует расширенного использования partial, чтобы заботиться о неиспользованных функциях.Если вам это не нравится, вы можете добавить лямбда-выражения, макросы потоков и т. Д.]

(defn rpartial
  "a 'right' version of clojure.core/partial"
  [f & args] #(apply f (concat %& args)))

(defn interleave*
  "a 'continuing' version of clojure.core/interleave"
  [& seqs]
  (lazy-seq
    (when-let [seqs (seq (remove empty? seqs))]
      (concat
        (map first seqs)
        (apply interleave* (map rest seqs))))))

(defn make-fn
  "makes a function from a symbol and an (optional) arity"
  ([sym arity]
   (let [args (repeatedly arity gensym)]
     (eval (list `fn (vec args) (cons sym args)))))
  ([sym] (make-fn sym 1)))

(def scan-for
  (comp
    (partial comp
      (partial remove empty?)
      (partial apply interleave*))
    (partial apply juxt)
    (juxt
      (partial rpartial clojure.string/split)
      (partial partial re-seq))
    re-pattern
    (partial clojure.string/join \|)
    (partial map (make-fn 'java.util.regex.Pattern/quote))
    (partial sort (comp not neg? compare))))

Во второй попытке я использую регулярное выражение для сопоставления "токенов" и промежуточных одиночных символов, а затемсгруппировать эти отдельные символы.Здесь мне не нравится объем обработки, выполняемый вне соответствия регулярному выражению.

(defn scan-for [tokens]
  (comp
    (partial remove empty?)
    (fn group [s]
      (lazy-seq
        (if-let [[sf & sr] s]
          (if (or (get sf 1)
                  (some (partial = sf) tokens))
            (list* "" sf (group sr))
            (let [[gf & gr] (group sr)]
              (cons (str sf gf) gr)))
          (cons "" nil))))
    (->> tokens
         (sort (comp not neg? compare))
         (map #(java.util.regex.Pattern/quote %))
         (clojure.string/join \|)
         (#(str % "|(?s)."))
         (re-pattern)
         (partial re-seq))))

Так есть ли способ сделать это, используя некоторое подходящее регулярное выражение для однократного анализа ввода и выполняя минимальную обработку вне этого анализа?

(Ленивая версия split, которая также возвращает совпадения с регулярным выражением, была бы полезна ... если бы она существовала.)

Answer 1

Я нашел решение, которое выглядит приемлемым.Он основан на использовании групп захвата и квантификатора *?, неохотно-жадной версии *.

. Вот она:

(defn scan-for [tokens]
  (comp
    (partial remove empty?)
    flatten
    (partial map rest)
    (->> tokens
         (sort (comp not neg? compare)) ;alternatively, we can short by decreasing length
         (map #(java.util.regex.Pattern/quote %))
         (clojure.string/join \|)
         (#(str "((?s).*?)(" % "|\\z)"))
         (re-pattern)
         (partial re-seq))))

И вмолчаливый стиль:

(def scan-for
  (comp
    (partial comp
      (partial remove empty?)
      flatten
      (partial map rest))
    (partial partial re-seq)
    re-pattern
    (partial str "((?s).*?)(")
    (rpartial str "|\\z)")
    (partial clojure.string/join \|)
    (partial map (make-fn 'java.util.regex.Pattern/quote))
    (partial sort (comp not neg? compare))))

Answer 2

Вот быстрая и грязная версия, которая не ленивая, но я думаю, что ее можно превратить в ленивую, используя lazy-seq в нескольких местах, как вы делали в своей версии:

(defn scan-for
  ([tokens text unmatched xs]
   (if (empty? text)
     (concat xs [unmatched])
     (let [matching (filter #(clojure.string/starts-with? text %) tokens)]
       (if (empty? matching)
         (recur tokens (subs text 1) (str unmatched (subs text 0 1)) xs)
         (let [matched (first matching)]
           (recur tokens
                  (subs text (count matched))
                  ""
                  (concat xs
                          (when-not (empty? unmatched) [unmatched])
                          [matched])))))))
  ([tokens text]
   (scan-for tokens text "" [])))


;; (scan-for ["an" "ban" "banal" "d"] "ban bananas and banalities")
;; => ("ban" " " "ban" "an" "as " "an" "d" " " "ban" "alities")

Edit:

Это было очень интересно, поэтому мне пришлось попробовать. Я обнаружил, что clojure.string/split также принимает необязательный параметр с ограничением на количество разбиений, которые он будет производить. Предполагая, что достижение предела не отсканирует остальную часть ввода, вы можете реализовать его на основе ваших первоначальных предложений:

(defn create-regex [xs]
  (->> xs (interpose "|") (apply str) re-pattern))

(defn split-lazy [s re]
  (when-not (empty? s)
    (let [[part remaining] (clojure.string/split s re 2)]
      (lazy-seq (cons part (split-lazy remaining re))))))

(defn scan-lazy [xs s]
  (let [re         (create-regex xs)
        no-matches (split-lazy s re)
        matches    (concat (re-seq re s) (repeat nil))]
    (remove empty?
            (interleave no-matches matches))))

(defn scan-for [xs] (partial scan-lazy xs))

;; ((scan-for ["an" "ban" "banal" "d"]) "ban bananas and banalities")
;; => ("ban" " " "ban" "an" "as " "an" "d" " " "ban" "alities")

В приведенном выше коде я использую трюк, в котором matches дополняется nil s, так что interleave может использовать обе коллекции, в противном случае он остановится, когда одна из них закончится.

Вы также можете проверить, что он ленивый:

bananas.core> (def bananas ((scan-for ["an" "ban" "banal" "d"]) "ban bananas and banalities"))
#'bananas.core/bananas
bananas.core> (realized? bananas)
false
bananas.core> bananas
("ban" " " "ban" "an" "as " "an" "d" " " "ban" "alities")
bananas.core> (realized? bananas)
true

Редактировать 2:

Если вы сортируете токены по уменьшенной длине, вы получите «жадную» версию, которую вы ожидали:

(defn create-regex [xs]
  (->> xs (sort-by count) reverse (interpose "|") (apply str) re-pattern))

;; ((scan-for ["an" "ban" "banal" "d"]) "ban bananas and banalities")
;; => ("ban" " " "ban" "an" "as " "an" "d" " " "banal" "ities")