Регулярни изрази

18.11.2013

История

• Разработени са като чисто теоритичен модел около 1950г.
• В езикът SNOBOL присъстват понятия като pattern matching през 1962г.
• Кен Томпсън ги имплементира в QED за CTSS
• Денис Ричи ги имплементира в QED за GE-TSS
• Двамата по-късно създават UNIX и ги вкарват там
• От 1970 насам има ed, sed, grep, egrep, awk, and lex...
• В PERL се стандартизират като PCRE

Проблемна област

най-общо: работа с текстови низове

• Търсене на по-сложна последователност от символи в низ
• Заместване на такива последователности с нещо друго
• Проверка дали даден низ отговаря на определени условия (валидация)

Call me maybe?

Искаме да проверим дали даден низ е валиден мобилен номер.
Това означава:

• Трябва да съдържа само цифри
• Трябва да започва с код на някой от местните мобилни оператори(087, 088, 089)
• Първата цифра след кода не може да е 0 или 1
• След това, дължината му трябва да е 6 (шест) цифри

Пф. Тривиално

func isValidMobilePhone(number string) bool {
    code := number[:3]
    if code != "087" && code != "088" && code != "089" {
        return false
    }

    if number[3] == '0' || number[3] == '1' {
        return false
    }

    return len(number[4:]) == 6
}

Пф. Тривиално и адекватно

func isValidMobilePhone(number string) bool {
    return regexp.MustCompile(`^08[789][2-9]\d{6}$`).MatchString(number)
}

Nice, a?

Понятия и терминология

• „шаблон“, още „регулярен израз“ (pattern)
• Специални символи (meta characters)
• Екраниране на специалните символи (escape-ване)
• Повторители и повторение (quantifiers and repetition)
• Класове от символи (character classes)
• Групи
• Флагове (modifiers) на шаблона

Регулярните изрази в контекста на Go

• Имплементирани са в пакета regexp
• Всеки регулярен израз е от типa regexp.Regexp
• Всеки регулярен израз се дефинира с ` около себе си
• Той има 16 метода за търсене на даден израз в стринг
• Find(All)?(String)?(Submatch)?(Index)?

godoc regexp/syntax

Задаване на шаблон

Всеки символ, освен някои специални, означава себе си.

Цялата магия е в специалните символи:
. \| ( ) [ ] { } + \ ^ $ * ?

Някои символи са специални само в определен контекст (например символът -)

Компилация на регулярен израз

• Преди да можем да използваме нашия регулярен израз, той трябва да бъде компилиран
• В някои езици тази стъпка може да бъде изпусната от програмиста и се изпълнява имплицитно
• В Go това може да се направи с метода Compile() или MustCompile()

re, err := regexp.Compile(`Hello`)
re := regexp.MustCompile(`Hello`)

Второто изпада в паника, ако регулярният израз не е валиден

Пример

re := regexp.MustCompile(`Hello`)

if re.MatchString("Hello Regular Expression.") {
    fmt.Printf("Match ")
} else {
    fmt.Printf("No match ")
}

func matcher(pattern, text string) string

• Примерите ще демонстрираме чрез нея
• Не е част от стандартната библиотека
• Ще ви покажем 7-те й реда код по-късно.

matcher(`pat`, "Find a pattern.") // Find a (pat)tern.
matcher(`#`, "What the ###?")     // What the (#)##?

Магия от level 1 -- Повторения (quantifiers)

• Важат за непосредствено предхождащия ги символ/клас/група; ще го означим със s
• s* означава нула или повече повторения на s
• s+ търси едно или повече повторения на s
• s? съвпада с нула или едно повторение на s
• s{m,n} означава между m и n повторения на s

В последното можем да пропуснем m или n:

• s{,n} има смисъл на нула до n повторения, а s{m,} — поне m повторения
• s{n} означава точно n повторения

func matcher(pattern, text string) string

• Примерите ще демонстрираме чрез нея
• Не е част от стандартната библиотека
• Ще ви покажем 7-те й реда код по-късно.

matcher(`pat`, "Find a pattern.") // Find a (pat)tern.
matcher(`#`, "What the ###?")     // What the (#)##?

Алчност (greedy)

• По подразбиране повторителите са "алчни", т.е. изяждат колкото се може повече от низа
• Това поведение може да се контролира с ? след квантора
• Например .*? кара повторителя * да се държи не-лакомо

matcher(`[hH]o+`, "Hoooooohohooo...")  // (Hoooooo)hohooo...
matcher(`[hH]o+?`, "Hoooooohohooo...") // (Ho)ooooohohooo...

Примери

matcher(`o+`, "Goooooooogle")                  // G(oooooooo)gle

matcher(`[hH]o+`, "Hohohoho...")               // (Ho)hohoho...

Хм. Не искахме точно това. По-скоро:

matcher(`([hH]o)+`, "Hohohoho...")             // (Hohohoho)...

matcher(`([hH]o){2,3}`, "Hohohoho...")         // (Hohoho)ho...

Скоби и групиране

Символите ( и ) се използват за логическо групиране на части от шаблона с цел:

• Контролиране областта на влияние на дадена операция
• Възможност за референция към "ограденото" в скобите
• Задаване на по-специални (и не толкова често употребявани) конструкции

Повече за тях -- след малко

Значение на специалните символи

Символът | има смисъла на "или"

matcher(`day|nice`, "A nice dance-day.")  // A (nice) dance-day.
matcher(`da(y|n)ce`, "A nice dance-day.") // A nice (dance)-day.

NB! Единствено | се прилага не над непосредствените му
символи/класове, а на целия низ отляво/отдясно:

matcher(`ab|c|e`, "abcdef")   // (ab)cdef
matcher(`am|c|e`, "abcdef")   // ab(c)def
matcher(`a(m)|c|e`, "abcdef") // ab(c)def

Символни класове

Набор от символи, заграден от [ и ], например [aeoui].
Съвпадат с точно един от символите, описани в класа:

matcher(`[aeoui]`, "Google") // G(o)ogle

Отрицание на символен клас -- ^ в началото на класа:

matcher(`[^CBL][aeoui]`, "Cobol") // 'Co(bo)l'

Диапазон от символи -- - между два символа в символен клас:

matcher(`[0-9]{1,3}-[a-z]`, "Figure 42-b") // Figure (42-b)
matcher(`[^a-zA-Z-]`, "Figure-42-b")       // Figure-(4)2-b

Групи и прихващане

Символите ( и ) се използват за логическо групиране на части от шаблона с цел:

• Контролиране областта на влияние на дадена операция
• Например, следното ще match-ва низове, съдържащи думите day или dance: \bda(y|nce)\b
• Възможност за референция към „ограденото“ в скобите
• Задаване на по-специални (и не толкова често употребявани) конструкции

re := regexp.MustCompile(`.at`)
res := re.FindAllStringSubmatch("The cat sat on the mat.", -1)
fmt.Printf("%v", res)
// [[cat] [sat] [mat]]

Find and replace

Можем да разменим местата на две думи

re := regexp.MustCompile("([a-z]+) ([a-z]+)")
re.ReplaceAllString("foo bar", "$2 $1")

или да имаме по-сложна логикa, върху всяко от съвпаденията

re.ReplaceAllStringFunc("foo with bar", func(match string) string {
        if len(match) > 3 {
                return match + "!!!"
        }
        return match
})
// foo with!!! bar

или ...

re := regexp.MustCompile("a(x*)b")
fmt.Println(re.ReplaceAllLiteralString("-ab-axxb-", "Щ"))
// -Щ-Щ-

Обяснете последното :)

Split

Често strings.Split() е крайно недостатъчен.

re := regexp.MustCompile("[0-9]")
re.Split("Помощ1не2ми3работи4space5клавиша!", -1)
// []string{"Помощ" "не" "ми" "работи" "space" "клавиша!"}

Вторият аргумент указва максималната дължина на върнатия слайс.

re := regexp.MustCompile("[0-9]")
re.Split("Помощ1не2ми3работи4space5клавиша!", 3)
// []string{"Помощ" "не" "ми3работи4space5клавиша!"}

Флагове

• i case-insensitive
• m multi-line mode: ^ и $ хващат И начало на ред и край на ред
• s Позволяват на . да хваща \n
• U ungreedy: обръщат значението на x* и x*?, x+ и x+?, ...

regexp.Compile(`(?i)n`)

Кодът на matcher()

func matcher(pattern, text string) string {
    match := regexp.MustCompile(pattern).FindStringIndex(text)
    if match == nil {
        return ""
    }

    begin := match[0]
    end := match[1]
    return fmt.Sprintf("%s(%s)%s\n", text[:begin], text[begin:end], text[end:])
}

След като вече всички сме наясно, че са мега яки...

Encouraging regular expressions as a panacea for all text processing
problems is not only lazy and poor engineering, it also reinforces
their use by people who shouldn't be using them at all.

-- Rob Pike

commandcenter.blogspot.ch/2011/08/regular-expressions-in-lexing-and.html

Regular Expression Matching Can Be Simple And Fast

but is slow in Java, Perl, PHP, Python, Ruby, ...

Russ Cox
rsc@swtch.com
January 2007

swtch.com/~rsc/regexp/regexp1.html

Въпроси?