Регулярные выражения
Как можно использовать регулярные выражения?
Регулярные выражения не являются частью стандарта CL, а реализуются в виде отдельных библиотек. CLisp имеет свой небольшой пакет regexp, обеспечивающий элементарную работу с регулярными выражениями (в рамках POSIX-стандарта). Список некоторых библиотек, посвященных регулярным выражениям, можно посмотреть в соответствующем разделе cliki. Наиболее популярной и мощной можно назвать библиотеку cl-ppcre, она оптимизирована по скорости и позволяет использовать регулярные выражения примерно так, как они используются в Perl. Её мы и рассмотрим.
CL-PPCRE
CL-PPCRE ("Common Lisp Portable Perl Compatible Regular Expression") отличают следующие свойства:
- Сами регулярные выражения совместимы с Перл-овыми (точнее с Perl 5.8) 1).
- Библиотека работает для разных ANSI реализаций CL.
- Есть альтернативная запись регулярных выражений в виде s-выражений.
- Работает быстро, как было сказано.
- Библиотека свободна и распространяется на основе BSD-лицензии.
Установка
- Ручная установка с помощью ASDF
Библиотека свободна от зависимостей (для необязательных тестов используется flexi-streams), нужно скачать архив http://weitz.de/files/cl-ppcre.tar.gz, распаковать в удобное место, и использовать систему ASDF для загрузки (есть несколько вариантов, читайте про них в части про ASDF).
- С помощью asdf-install
(asdf-install:install :cl-ppcre)
- Порты и пакеты
Для систем Gentoo, Debian и FreeBSD имеются установочные пакеты.
Основная концепция
Основой этой библиотеки является концепция сканеров как замыканий (closure), предназначенных для сканирования строк и возвращения соответствующих значений для совпадений (matching, в этом смысле не-совпадение - разновидность совпадения). Эти сканеры можно различным образом использовать - присваивать переменным, объявлять их в блоке let и так далее.
Методы create-scaner являются полиморфными методами в смысле CLOS, то есть они определены для разных типов и возвращают такие замыкания для сканирования. Всего определено три метода create-scaner - для строк, деревьев и функций.
;;; [Method]
;;; create-scanner (string string) &key case-insensitive-mode multi-line-mode single-line-mode extended-mode destructive => scanner, register-names
Этот метод принимает строку, которая представляет собой регулярные выражения в синтаксисе Perl и возвращает замыкание, т.е. лямбда-функцию ссылающуюся на свое лексическое окружение и служащую для сканирования строк.
;;; [Method]
;;; create-scanner (function function) &key case-insensitive-mode multi-line-mode single-line-mode extended-mode destructive => scanner
Способ создать замыкание-сканер для готовой сканирующей функции.
;;; [Method]
;;; create-scanner (parse-tree t)&key case-insensitive-mode multi-line-mode single-line-mode extended-mode destructive => scanner, register-names
То же, что и метод для строк, но в этом случае для определения регулярного выражения вместо "перловых" строк используются специальные s-выражения, то есть это просто другой способ их записи, например:
(parse-string "(ab)*")
(:GREEDY-REPETITION 0 NIL (:REGISTER "ab"))
(parse-string "(a(b))")
(:REGISTER (:SEQUENCE #\a (:REGISTER #\b)))
(parse-string "(?:abc){3,5}")
(:GREEDY-REPETITION 3 5 (:GROUP "abc"))
;; (:GREEDY-REPETITION 3 5 "abc") тоже подходит
(parse-string "a(?i)b(?-i)c")
(:SEQUENCE #\a
(:SEQUENCE (:FLAGS :CASE-INSENSITIVE-P)
(:SEQUENCE #\b (:SEQUENCE (:FLAGS :CASE-SENSITIVE-P) #\c))))
;; тоже что (:SEQUENCE #\a :CASE-INSENSITIVE-P #\b :CASE-SENSITIVE-P #\c)
(parse-string "(?=a)b")
(:SEQUENCE (:POSITIVE-LOOKAHEAD #\a) #\b)
Функции сканирования
Теперь переходим к общей (generic) функции scan - функция scan сканирует второй аргумент-строку начиная с индекса :start и до индекса :end на предмет совпадения с регулярным выражением, определённым в первом аргументы, который может быть обычной строкой, деревом разбора в s-нотации, или подготовленным сканером:
;;;[Generic Function]
;;;scan regex target-string &key start end => match-start, match-end, reg-starts, reg-ends
(scan "(a)*b" "xaaabd")
1
5
#(3)
#(4)
(scan "(a)*b" "xaaabd" :start 1)
1
5
#(3)
#(4)
(scan "(a)*b" "xaaabd" :end 4)
NIL
(scan "b.r" "foo bar baz bur" :start 5)
12
15
#()
#()
(scan "b.r" "foo bar baz bur" :start 5 :end 13)
NIL
(scan '(:greedy-repetition 0 nil #\b) "bbbc")
0
3
#()
#()
(scan '(:greedy-repetition 4 6 #\b) "bbbc")
NIL
(let ((s (create-scanner "(([a-c])+)x")))
(scan s "abcxy"))
0
4
#(0 2)
#(3 3)
возвращает она индексы начала и конца первого совпадения, при отсутствии совпадений возвращает NIL. Третье и четвёртое возвращаемые значения это индексы начала и конца регистровой ("запоминаемой", той что в скобках) переменной.
Функция scan-to-strings похожа на scan, но не возвращает индексы, а записывает первое совпадение в строку (и, при наличии, регистровую переменную во вторую строку):
;;; [Function]
;;; scan-to-strings regex target-string &key start end sharedp => match, regs
(scan-to-strings "[^b]*b" "aaabd")
"aaab"
#()
(scan-to-strings "([^b])*b" "aaabd")
"aaab"
#("a")
(scan-to-strings "(([^b])*)b" "aaabd")
"aaab"
#("aaa" "a")
Вспомогательные макросы
Макрос register-groups-bind связывает регистровые переменные с обозначенными переменными, например:
;;; [Macro]
;;; register-groups-bind var-list (regex target-string &key start end sharedp) declaration* statement* => result*
(register-groups-bind (first second third fourth)
("((a)|(b)|(c))+" "abababc" :sharedp t)
(list first second third fourth))
("c" "a" "b" "c")
(register-groups-bind (nil second third fourth)
;; note that we don't bind the first and fifth register group
("((a)|(b)|(c))()+" "abababc" :start 6)
(list second third fourth))
(NIL NIL "c")
(register-groups-bind (first)
("(a|b)+" "accc" :start 1)
(format t "This will not be printed: ~A" first))
NIL
(register-groups-bind (fname lname (#'parse-integer date month year))
("(\\w+)\\s+(\\w+)\\s+(\\d{1,2})\\.(\\d{1,2})\\.(\\d{4})" "Frank Zappa 21.12.1940")
(list fname lname (encode-universal-time 0 0 0 date month year 0)))
("Frank" "Zappa" 1292889600)
Макрос do-scans, основанный на scan, служит для перебора различных совпадений в строке, на нём основаны следующие макросы : DO-MATCHES, ALL-MATCHES, SPLIT, REGEX-REPLACE-ALL.
;;; [Macro]
;;; do-scans (match-start match-end reg-starts reg-ends regex target-string &optional result-form &key start end) declaration* statement* => result*
Макрос do-matches делает то же, но не работает с регистровыми переменными:
;;; [Macro]
;;; do-matches (match-start match-end regex target-string &optional result-form &key start end) declaration* statement* => result*
(defun foo (regex target-string &key (start 0) (end (length target-string)))
(let ((sum 0))
(do-matches (s e regex target-string nil :start start :end end)
(incf sum (- e s)))
(format t "~,2F% of the string was inside of a match~%"
(float (* 100 (/ sum (- end start)))))))
FOO
(foo "a" "abcabcabc")
33.33% of the string was inside of a match
NIL
(foo "aa|b" "aacabcbbc")
55.56% of the string was inside of a match
NIL
Макрос do-matches-as-strings отличается тем, что при каждом совпадении связывает match-var с совпавшей подстрокой:
;;; [Macro]
;;; do-matches-as-strings (match-var regex target-string &optional result-form &key start end sharedp) declaration* statement* => result*
(defun crossfoot (target-string &key (start 0) (end (length target-string)))
"Тут мы собираем только числовые знаки в строке,
и переводить их в числа с помощью parse-integer."
(let ((sum 0))
(do-matches-as-strings (m :digit-class
target-string nil
:start start :end end)
(incf sum (parse-integer m)))
(if (< sum 10)
sum
(crossfoot (format nil "~A" sum)))))
CROSSFOOT
(crossfoot "bar")
0
(crossfoot "a3x")
3
(crossfoot "12345")
6
Макрос do-register-groups может помочь в итерации по всем совпадениям вместе со связыванием регистровых переменных:
;;; [Macro]
;;; do-register-groups var-list (regex target-string &optional result-form &key start end sharedp) declaration* statement* => result*
(do-register-groups (first second third fourth)
("((a)|(b)|(c))" "abababc" nil :start 2 :sharedp t)
(print (list first second third fourth)))
("a" "a" NIL NIL)
("b" NIL "b" NIL)
("a" "a" NIL NIL)
("b" NIL "b" NIL)
("c" NIL NIL "c")
NIL
(let (result)
(do-register-groups ((#'parse-integer n) (#'intern sign) whitespace)
("(\\d+)|(\\+|-|\\*|/)|(\\s+)" "12*15 - 42/3")
(unless whitespace
(push (or n sign) result)))
(nreverse result))
(12 * 15 - 42 / 3)
Функция all-matches просто возвращает список всех индексов совпадений:
;;; [Function]
;;; all-matches regex target-string &key start end => list
(all-matches "a" "foo bar baz")
(5 6 9 10)
(all-matches "\\w*" "foo bar baz")
(0 3 3 3 4 7 7 7 8 11 11 11)
А функция all-matches-as-strings, соответственно, возвращает список всех совпавших подстрок:
;;; [Function]
;;; all-matches-as-strings regex target-string &key start end sharedp => list
(all-matches-as-strings "a" "foo bar baz")
("a" "a")
(all-matches-as-strings "\\w*" "foo bar baz")
("foo" "" "bar" "" "baz" "")
Разбиение строк на части
Итак, функция split служит для разбиения строк на основе регулярных выражений:
(split "\\s+" "foo bar baz frob")
("foo" "bar" "baz" "frob")
(split "\\s*" "foo bar baz")
("f" "o" "o" "b" "a" "r" "b" "a" "z")
(split "(\\s+)" "foo bar baz")
("foo" "bar" "baz")
(split "(\\s+)" "foo bar baz" :with-registers-p t)
("foo" " " "bar" " " "baz")
(split "(\\s)(\\s*)" "foo bar baz" :with-registers-p t)
("foo" " " "" "bar" " " " " "baz")
(split "(,)|(;)" "foo,bar;baz" :with-registers-p t)
("foo" "," NIL "bar" NIL ";" "baz")
(split "(,)|(;)" "foo,bar;baz" :with-registers-p t :omit-unmatched-p t)
("foo" "," "bar" ";" "baz")
(split ":" "a:b:c:d:e:f:g::")
("a" "b" "c" "d" "e" "f" "g")
(split ":" "a:b:c:d:e:f:g::" :limit 1)
("a:b:c:d:e:f:g::")
(split ":" "a:b:c:d:e:f:g::" :limit 2)
("a" "b:c:d:e:f:g::")
(split ":" "a:b:c:d:e:f:g::" :limit 3)
("a" "b" "c:d:e:f:g::")
(split ":" "a:b:c:d:e:f:g::" :limit 1000)
("a" "b" "c" "d" "e" "f" "g" "" "")
Замены в строках
Функция regex-replace заменяет только первое совпадение:
(regex-replace "fo+" "foo bar" "frob")
"frob bar"
T
(regex-replace "fo+" "FOO bar" "frob")
"FOO bar"
NIL
(regex-replace "(?i)fo+" "FOO bar" "frob")
"frob bar"
T
(regex-replace "(?i)fo+" "FOO bar" "frob" :preserve-case t)
"FROB bar"
T
(regex-replace "(?i)fo+" "Foo bar" "frob" :preserve-case t)
"Frob bar"
T
(regex-replace "bar" "foo bar baz" "[frob (was '\\&' between '\\`' and '\\'')]")
"foo [frob (was 'bar' between 'foo ' and ' baz')] baz"
T
(regex-replace "bar" "foo bar baz"
'("[frob (was '" :match "' between '" :before-match "' and '" :after-match "')]"))
"foo [frob (was 'bar' between 'foo ' and ' baz')] baz"
T
вариант с созданием нужного сканера "на ходу":
(regex-replace "(be)(nev)(o)(lent)"
"benevolent: adj. generous, kind"
#'(lambda (match &rest registers)
(format nil "~A [~{~A~^.~}]" match registers))
:simple-calls t)
"benevolent [be.nev.o.lent]: adj. generous, kind"
T
Замены всех вхождений встроках
Функция regex-replace-all, в отличии от regex-replace, обрабатывает все вхождения:
(regex-replace-all "(?i)fo+" "foo Fooo FOOOO bar" "frob" :preserve-case t)
"frob Frob FROB bar"
T
(regex-replace-all "(?i)f(o+)" "foo Fooo FOOOO bar" "fr\\1b" :preserve-case t)
"froob Frooob FROOOOB bar"
T
(let ((qp-regex (create-scanner "[\\x80-\\xff]")))
(defun encode-quoted-printable (string)
"Converts 8-bit string to quoted-printable representation."
;; won't work for Corman Lisp because non-ASCII characters aren't 8-bit there
(flet ((convert (target-string start end match-start match-end reg-starts reg-ends)
(declare (ignore start end match-end reg-starts reg-ends))
(format nil "=~2,'0x" (char-code (char target-string match-start)))))
(regex-replace-all qp-regex string #'convert))))
Converted ENCODE-QUOTED-PRINTABLE.
ENCODE-QUOTED-PRINTABLE
(encode-quoted-printable "Fête Sørensen naïve Hühner Straße")
"F=EAte S=F8rensen na=EFve H=FChner Stra=DFe"
T
(let ((url-regex (create-scanner "[^a-zA-Z0-9_\\-.]")))
(defun url-encode (string)
"URL-encodes a string."
;; won't work for Corman Lisp because non-ASCII characters aren't 8-bit there
(flet ((convert (target-string start end match-start match-end reg-starts reg-ends)
(declare (ignore start end match-end reg-starts reg-ends))
(format nil "%~2,'0x" (char-code (char target-string match-start)))))
(regex-replace-all url-regex string #'convert))))
Converted URL-ENCODE.
URL-ENCODE
(url-encode "Fête Sørensen naïve Hühner Straße")
"F%EAte%20S%F8rensen%20na%EFve%20H%FChner%20Stra%DFe"
T
(defun how-many (target-string start end match-start match-end reg-starts reg-ends)
(declare (ignore start end match-start match-end))
(format nil "~A" (- (svref reg-ends 0)
(svref reg-starts 0))))
HOW-MANY
(regex-replace-all "{(.+?)}"
"foo{...}bar{.....}{..}baz{....}frob"
(list "[" 'how-many " dots]"))
"foo[3 dots]bar[5 dots][2 dots]baz[4 dots]frob"
T
(let ((qp-regex (create-scanner "[\\x80-\\xff]")))
(defun encode-quoted-printable (string)
"Converts 8-bit string to quoted-printable representation.
Version using SIMPLE-CALLS keyword argument."
;; ;; won't work for Corman Lisp because non-ASCII characters aren't 8-bit there
(flet ((convert (match)
(format nil "=~2,'0x" (char-code (char match 0)))))
(regex-replace-all qp-regex string #'convert
:simple-calls t))))
Converted ENCODE-QUOTED-PRINTABLE.
ENCODE-QUOTED-PRINTABLE
(encode-quoted-printable "Fête Sørensen naïve Hühner Straße")
"F=EAte S=F8rensen na=EFve H=FChner Stra=DFe"
T
(defun how-many (match first-register)
(declare (ignore match))
(format nil "~A" (length first-register)))
HOW-MANY
(regex-replace-all "{(.+?)}"
"foo{...}bar{.....}{..}baz{....}frob"
(list "[" 'how-many " dots]")
:simple-calls t)
"foo[3 dots]bar[5 dots][2 dots]baz[4 dots]frob"
T
Примеры
Элементарные html-тэги
Допустим стоит задача переводить текст между \=\=\=\=, \=\=\= и \=\= в html заголовки h1, h2 и h3 соответственно. Этого можно достичь трёмя строчка - по одной на каждую задачу:
(setf *str* (regex-replace-all "\=\=\=\=(.*)=\=\=\=\=" *str* "<h1>\\1</h1>" :preserve-case t))
(setf *str* (regex-replace-all "\=\=\=(.*)\=\=\=" *str* "<h2>\\1</h2>" :preserve-case t))
(setf *str* (regex-replace-all "\=\=(.*)\=\=" *str* "<h3>\\1</h3>" :preserve-case t))
3)
Как видим, перловые $1, $2, $3, ... для запоминания паттернов в скобках () заменяются переменными
1,
2,
3, ...