Regular Expressions

About Regular Expressions

Záznam z prednášky

Motivácia

(slide) Predstavte si situáciu, že pracujete na nejakom mocnom zadaní, kde jedna z jeho úloh znie: Vytvorte funkciu check_email(char* email), ktorá vráti hodnotu true v prípade, ak emailová adresa použitá ako parameter funkcie predstavuje platnú emailovú adresu alebo false, keď nie. Ako by ste postupovali? Čo by ste kontrolovali?

Tvorba validátorov alebo parserov (rozpoznávačov) je v programovaní veľmi častá. A ako vidíte, rozhodne nie je priamočiara a jednoduchá. Stále je možné nájsť spôsob, ktorým bude možné porušiť niektorú podmienku alebo pravidlo a teda znefunkčniť samotný validátor.

(slide) Práve na tento účel boli vymyslené regulárne výrazy.

Regulárne výrazy

(slide) Regulárny výraz je možné vo všeobecnosti zadefinovať ako špeciálny reťazec, ktorý opisuje vyhľadávací vzor.

(slide) Regulárne výrazy sú však na prvý pohľad značne komplikované, pretože používajú špeciálne znaky so špeciálnym významom.

Regulárne výrazy sú však úplne fantastické na rozpoznávanie a validáciu používateľského vstupu, ako napr. na validáciu formulárov a v nich kontrolu správnosti zadania jednotlivých polí (e-mailová adresa, dátum, IP adresa, URL adresa, občiansky preukaz, ŠPZ, …)

Podporu pre regulárne výrazy viete nájsť aj inde, ako v programovacích jazykoch. Napr. podpora regulárnych výrazov je aj v niektorých textových editoroch.

(slide) Rovnako sa viete stretnúť s rozličnými validátormi regulárnych výrazov - nástrojmi, ktoré vám pomôžu odladiť podobu a správnosť vášho regulárneho výrazu. Napr.:

Regular Expression Validator - pre množstvo jazykov
Regular Expressions 101 - aj s vysvetlivkami
grep, grep -E, egrep - linuxový konzolový nástroj

(slide) Z pohľadu zápisu môžeme regulárne výrazy rozdeliť do dvoch skupín:

POSIX (Portable Operating System Interface) - UNIX kompatibilné, starší typ zápisu a v niektorých implementáciách dokonca pomalší (PHP)
PCRE (Perl Compatible Regular Expressions) - typ z jazyka Perl, novší zápis

Poznámka

Aj napriek tomu, že poznáme dva typy zápisov regulárnych výrazov, ich význam a použitie zostávajú nezmenené. Rozdiel je hlavne syntaktický.

Základy regulárnych výrazov

(slide) Začneme teda základmi používania a písania regulárnych výrazov. A hneď prvou vlastnosťou, ktorú treba povedať je, že pri písaní regulárnych výrazov záleží na veľkosti písmen.

source	pattern	matches
`"Hello, world"`	`"Hello"`	`"Hello"`
`"Hello, world"`	`"HELLO"`	`""`

(slide) Ďalšou základnou vlastnosťou je, že pri používaní regulárnych výrazov záleží na každom jednom znaku. A nezabúdajte na to, že aj medzera je znak! Na to ste už ale hádam prišli počas riešenia zadaní ;-)

source	pattern	matches
`"Hello, world"`	`"Hello, "`	`"Hello, "`
`"Hello, world"`	`"Hello, "`	`""`

Metaznaky

(slide) V regulárnych výrazoch existuje niekoľko špeciálnych znakov, resp. znakov so špeciálnym významom. Týmto znakom hovoríme metaznaky.

Prvým znakom je znak '^'. Tento znak označuje začiatok spracovávaného riadku/vstupu/reťazca.

source	pattern	matches
`"Hello, world"`	`"^Hello"`	`"Hello"`
`" Hello, world"`	`"^Hello"`	`""`
`"Hello, world"`	`"^world"`	`""`

Ďalším metaznakom je znak '$'. Tento znak označuje koniec spracovávaného riadku/vstupu/reťazca.

source	pattern	matches
`"Hello, world"`	`"Hello$"`	`""`
`"Hello, world"`	`"world$"`	`"world"`
`"Hello, world!"`	`"world$"`	`""`

Ďalším metaznakom je znak '.'. Tento znak zastupuje ľubovoľný jeden znak.

source	pattern	matches
`"Hello, world"`	`"."`	`"H" "e" "l" "l" "o" "," " " "w" "o" "r" "l" "d"`
`"Hello, world"`	`"^."`	`"H"`
`"Hello, world!"`	`"..$"`	`"d!"`
`"Hello, world!"`	`".l."`	`"ell" "rld"`

Escaping

Ako by vyzeral regulárny výraz, ak by sme chceli overiť, či reťazec, ktorý máme k dispozícii predstavuje emailovú adresu zo servera gmail.com?
```
"@gmail.com$"
```
Problém tohto regulárneho výrazu je však v tom, že znak '.' je metaznakom a význam tohto metaznaku je, že na danej pozícii sa môže nachádzať akýkoľvek znak. A to je v tomto prípade zle, pretože aj reťazec:
```
"janko.hrasko@gmailXcom"
```
bude vyhovovať napísanému regulárnemu výrazu.
(slide) Ak teda chceme potlačiť význam daného metaznaku, napíšeme pred neho znak '\'. Nasledujúci znak bude považovaný za normálny znak. Tento mechanizmus sa volá escaping.
Správne zapísaný regulárny výraz na zistenie, či uvedená emailová adresa je adresou zo serveru gmail.com bude teda:
```
"@gmail\.com$"
```

Triedy znakov

(slide) Zatiaľ dokážeme rozpoznať na jednej pozícii práve jeden znak. A to buď konkrétny znak alebo ľubovoľný znak. V praxi sa však stretnete častejšie so situáciami, kedy očakávate, že na konkrétnej pozícii sa môže nachádzať jeden znak z istej množiny znakov. Napr. ak by sme chceli rozpoznávať ŠPZ auta tak vieme, že prvé dva znaky môžu byť len písmená, ďalšie tri môžu byť len číslice a posledná dva znaky môžu byť opäť len písmená. Ako teda zabezpečiť to, aby sme vedeli na príslušnej pozícii rozpoznať len vybrané znaky?
(slide) Na toto máme v regulárnych výrazoch tzv. triedy znakov. Trieda znakov je vymedzená hranatými zátvorkami, v ktorých sa nachádza príslušná množina znakov. Trieda znakov však zastupuje vo vstupnom reťazci len jeden znak - ale jeden znak z množiny znakov vymenovaných v hranatých zátvorkách.
(slide) Ukážme si teda náš príklad s ŠPZ - potrebujeme vytvoriť dve triedy znakov:
- jednu, ktorá bude zastupovať písmená (a použijeme ju 4x)
```
[ABCDEFGHIJKLMNOPQRSTUVWXYZ]
```
- druhú, ktorá bude zastupovať číslice (a použijeme ju 3x)
```
[0123456789]
```

(slide) Kompletný regulárny výraz pre rozpoznanie ŠPZ s využitím triedy znakov potom bude vyzerať nasledovne:

[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ]\
[0123456789][0123456789][0123456789]\
[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ]

Ten zápis je strašný. Našťastie je možné použiť v triedach znakov rozsahy. To znamená, že miesto toho, aby bolo potrebné vymenovať všetky znaky jeden po druhom, je možné napísať prvý znak, posledný a medzi ne použiť znak '-'. Tým dokážeme aj regulárny výraz na rozpoznanie ŠPZ napísať podstatne viac sexi (slide):
```
[A-Z][A-Z][0-9][0-9][0-9][A-Z][A-Z]
```
(slide) Samozrejme je možné jednotlivé rozsahy kombinovať a aj vymenovávať znaky osobitne. Napr. ak by sme chceli, aby na niektorej pozícii bolo možné použiť buď malé písmená, veľké písmená, číslice alebo znak '_', trieda znakov by vyzerala takto:
```
[A-Za-z0-9_]
```
(slide) Občas sa ale stane, že je je kratšie vymenovať znaky, ktoré nechcem, aby boli použité ako tie, ktoré použité majú byť. Preto, ak sa v triede znakov bude ako prvý znak nachádzať znak '^', bude tento predstavovať negáciu znakov v skupine. Ak napríklad chceme rozpoznať všetky znaky okrem veľkých písmen, malých písmen, číslic a znaku '_', mohla by skupina vyzerať takto:
```
[^A-Za-z0-9_]
```

Character Repetition

(slide) Zatiaľ sme hovorili o tom, že vieme rozlíšiť práve jeden výskyt nejakého symbolu alebo množiny symbolov. V praxi však budeme potrebovať občas povedať, že niektorý znak alebo množina sa môže opakovať/vyskytovať viackrát. Pamätáte na príklad s ŠPZ? To je presne ono.
(slide) Vieme však povedať, že niektorý znak alebo niektorá množina znakov sa má vyskytovať istý počet krát. A to vieme zabezpečiť použitím zložených zátvoriek niekoľkými spôsobmi:
- {n} - daná postupnosť sa musí opakovať práve n-krát
- {n,} - daná postupnosť sa musí opakovať min. n-krát a viac
- {n,m} - daná postupnosť sa musí opakovať min. n-krát a max. m-krát

Príklady použitia:

source	pattern	matches
`"Regular expressions"`	`".{5}"`	`"Regul" "ar ex" "press"`
`"Regular expressions"`	`"[esr]{1, 3}"`	`"e" "r" "e" "res" "s" "s"`
`"Regular expressions"`	`"[a-z]{3, }"`	`"egular" "expressions"`

(slide) Aplikovaním opakovania na príklade s ŠPZ dostaneme toto:
```
[A-Z]{2}[0-9]{3}[A-Z]{2}
```

Kvantifikátory v regulárnych výrazoch

(slide) Existujú však prípady opakovaní, ktoré sa vyskytujú najčastejšie. Pre tieto prípady boli vymyslené samostatné znaky, ktoré označujeme slovom kvantifikátory.
V regulárnych výrazoch máme tieto tri kvantifikátory:
1. star '*'
2. plus '+'
3. question mark '?'

Star `'*'`

Kvantifikátor star '*' hovorí o tom, že to, čo je pred ním, sa nemusí vyskytovať vôbec alebo ľubovoľný početkrát.

source	pattern	matches
`"aabc abc bc"`	`"a*b"`	`"aab" "ab" "b"`

Plus `'+'`

Kvantifikátor plus '+' hovorí o tom, že to, čo je pred ním, sa musí nachádzať minimálne raz. Počet výskytov nie je zhora ohraničený.

source	pattern	matches
`"aabc abc bc"`	`"a+b"`	`"aab" "ab"`

Question Mark `'?'`

Kvantifikátor question mark '?' hovorí o tom, že to, čo je pred ním, sa môže nachádzať max. raz alebo ani raz.

source	pattern	matches
`"aabc abc bc"`	`"a?b"`	`"ab" "ab" "b"`

Zoskupovanie vzorov

(slide) Reťazce, ktoré spracúvame v programoch od používateľov často nesú informáciu, ktorá je zložená, resp. štruktúrovaná, napr. dátum a čas. Často potom potrebujeme tieto údaje vyextrahovať zo vstupu. Máme síce na to funkcie priamo v knižnici strings.h, ale tie sú pozičné - je potrebné sa spoliehať na presnú pozíciu. Pomocou regulárnych výrazov však túto úlohu vieme vyriešiť tiež pomocou tzv. zoskupovania (grouping) (slide).
(slide) Ak teda chceme nejakú postupnosť znakov uzatvoriť do skupiny, uzavrieme ich do okrúhlych zátvoriek. Pre dátum a čas to teda môže vyzerať nasledovne:
```
(07).(04).(2016) (12):(00):(29)
```
Vo vnútri jednotlivých skupín už iba napíšeme potrebné regulárne výrazy na ich rozpoznanie.
V tomto vám už následne pomôže len knižnica daného jazyka, pomocou ktorej viete pristupovať k jednotlivým skupinám a vytiahnuť z nich údaje, ktoré sa v nich nachádzajú.

Matching Alternatives

Alternatívy sa vymenujú pričom sa od seba oddeľujú pomocou znaku '|'
Príklady použitia:

source pattern matches

source	pattern	matches
`"Monday Tuesday Friday"`	`"(on\|ues\|rida)"`	`"on" "ues" "rida"`
`"Monday Tuesday Friday"`	`"(Mon\|Tues\|Fri)day"`	`"Monday" "Tuesday" "Friday"`
`"Monday Tuesday Friday"`	`"..(nd\|esd\|id)ay"`	`"Monday" "Tuesday" "Friday"`

"Monday Tuesday Friday"

"(on|ues|rida)"

"on"
"ues"
"rida"

"Monday Tuesday Friday"

"(Mon|Tues|Fri)day"

"Monday"
"Tuesday"
"Friday"

"Monday Tuesday Friday"

"..(nd|esd|id)ay"

"Monday"
"Tuesday"
"Friday"

Regulárne výrazy v jazyku C

Knižnice pre regulárne výrazy nie sú súčasťou ANSI verzie jazyka C.
V jazyku C sa v princípe viete stretnúť s dvoma knižnicami pre použitie regulárnych výrazov:
- knižnica regex.h (POSIX)
- knižnica pcre.h (PCRE)
My sa budeme venovať ukážkam použitia knižnice regex.h.

Compilation of Regular Expression

Predtým, ako budete môcť regulárny výraz použiť, musíte ho preložiť. Nejedná sa o ozajstný preklad (compilation), ale o vytvorenie špeciálnej štruktúry údajov s cieľom čo najrýchlejšieho vykonania regulárneho výrazu.
Preložený regulárny výraz bude typu regex_t.
Na preloženie regulárneho výrazu sa používa funkcia regcomp(compiled, pattern, cflags), ktorá má tieto tri parametre:
- compiled - adresa údajového typu regex_t, kde bude uložený preložený regulárny výraz,
- pattern - reťazec reprezentujúci regulárny výraz, a
- cflags - príznaky, pomocou ktorých je možné nastaviť ďalšie možnosti regulárneho výrazu (napr. ignorovať veľkosť písmen)
Funkcia vráti hodnotu typu int, ktorá ak je nenulová, regulárny výraz nemohol byť vytvorený (nebol preložený).

Príklad vytvorenia regulárneho výrazu na rozpoznanie dátumu v tvare

MM.DD.YYYY

zapíšeme v jazyku C nasledovne:

#include <stdio.h>
#include <regex.h>
#include <stdlib.h>

int main(){
    // regular expression compilation
    regex_t regex;
    if(regcomp(&regex, "^([0-9]{2})\\.([0-9]{2})\\.([0-9]{4})$",
       REG_ICASE | REG_EXTENDED) != 0){
        fprintf(stderr,
                "Regular expression could not be compiled.\n");
        exit(EXIT_FAILURE);
    }

    printf("Regular expression was compiled successfully.\n");
}

Matching

Akonáhle máme regulárny výraz preložený, môžeme ho použiť nad nejakým reťazcom a overiť, či daný reťazec danému regulárnemu výrazu vyhovuje.
Spustenie regulárneho výrazu nad reťazcom je možné pomocou volania funkcie regexec(compiled, string, nmatch, matchptr, eflags), ktorej význam parametrov je nasledovný:
- compiled - preložený regulárny výraz,
- string - reťazec, nad ktorým sa regulárny výraz spúšťa,
- eflags - príznaky, pomocou ktorých je možné nastaviť ďalšie možnosti.
Parametre nmatch a matchptr sa používajú v prípade, ak chcete zistiť aj to, čo presne regulárny výraz rozpoznal. Ak vás to však nezaujíma, nastavte nmatch na hodnotu 0 a matchptr na NULL. (na ich použitie sa pozrieme za chvíľku)

Výsledný program na rozpoznanie dátumu pomocou regulárnych výrazov v jazyku C bude vyzerať nasledovne:

#include <stdio.h>
#include <regex.h>
#include <stdlib.h>

int main(){
    // regular expression compilation
    regex_t regex;
    if(regcomp(&regex, "^([0-9]{2}).([0-9]{2}).([0-9]{4})$",
               REG_ICASE | REG_EXTENDED) != 0){
        fprintf(stderr,
                "Regular expression could not be compiled.\n");
        exit(EXIT_FAILURE);
    }

    // read input string
    char buffer[100];
    scanf("%s", buffer);

    // match regular expression
    int result = regexec(&regex, buffer, 0, NULL, 0);

    if(result == REG_NOMATCH){
        printf("Wrong input - Not a date\n");
    }else{
        printf("Correct input\n");
    }
}

Groupping

Výsledný kód v jazyku C, pomocou ktorého budeme vedieť rozpoznať dátum a k jeho zložkám pristupovať pomocou skupín, je nasledovný:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <regex.h>

int main(){
    // read input
    char buffer[100];
    fgets(buffer, 100, stdin);
    buffer[strlen(buffer)-1] = '\0';

    regex_t regex;
    if(regcomp(&regex, "^([0-9]{2}).([0-9]{2}).([0-9]{4})$",
               REG_ICASE | REG_EXTENDED) != 0){
        fprintf(stderr,
                "Regular expression could not be compiled.\n");
        exit(EXIT_FAILURE);
    }

    //int nmatch = 0;
    regmatch_t groups[4];
    int r = regexec(&regex, buffer, 4, groups, 0);
    // printf("input: '%s'\nreturn: %d\nnmatc %d\n",
    //        buffer, r, nmatch);
    if(r == REG_NOMATCH){
        printf("no match\n");
    }else{
        printf("match\n");

        for(int i = 0; i < 4; i++){
            if(groups[i].rm_so == -1){
                break;
            }

            printf("group %d: %d - %d\n",
                   i, groups[i].rm_so, groups[i].rm_eo);
        }
    }
}