Week 8

Regular Expressions

Intermezzo

Upozornenie: 
  • vypnúť všetko prehrávanie hudby
  • zapnúť nahrávanie
  • zapnúť virtual
  • zapnúť vo virtuale sli.do

Motivácia

  • (slide) Predstavte si situáciu, že pracujete na nejakom mocnom zadaní, kde je jedna z jeho úloh znie: Vytvorte funkciu check_email(char* email), ktorá vráti 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. bežná podpora regulárnych výrazov je v 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.:
  • (slide) Existujú dva typy regulárnych výrazov:
    • 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
  • 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ákladnmi 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ávisí od 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 nezbúdajte na to, že aj medzera je znak.
    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.
  • Prvým znakom je znak '^'. Tento znak reprezentuje neviditeľný znak označujúci začiatok riadku/vstupu/reťazca, ktorý sa spracováva.
    source pattern matches
    "Hello, world"
    "^Hello"
    "Hello"
    "   Hello, world"
    "^Hello"
    "Hello, world"
    "^world"
  • Ďalším metaznakom je znak '$'. Tento znak reprezentuje neviditeľný znak označujúci koniec riadku/vstupu/reťazca, ktorý sa spracuváva.
    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.
  • Ak teda chceme potlačiť význam daného metaznaku, napíšeme pred neho znak '\', čím bude jeho význam potlačený a 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 znakoch 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]
  • 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 (slide):
    [A-Za-z0-9_]
  • 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 (slide):
    [^A-Za-z0-9_]

Character Repetition

  • 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četkrát. A to vieme zabezpečiť použitím zložených zátvoriek niekoľkými spôsobmi (slide).:
    • {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"
  • Aplikovaním opakovania na príklade s ŠPZ dostaneme toto (slide):
    [A-Z]{2}[0-9]{3}[A-Z]{2}

Kvantifikátory v regulárnych výrazoch

  • Existujú však prípady opakovaní, ktoré sa vyskytujú najčastejšie. Pre tieto prípady boli vymyslené samostatné znaky, ktoré označujeme slovom quantifikátory (slide).
  • Máme tri kvantifikátory:
    • 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 '+' - hovorí o tom, že to, čo je pred ním, sa musí nachádzať minimálne raz (zhora však nie je ohraničený počet výskytov)
    source pattern matches
    "aabc abc bc"
    "a+b"
    "aab"
    ,
    "ab"
  • 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).
  • 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 (slide):
    (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
    "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 (regex1.c):
    #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){
            printf("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 (regex2.c):
    #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){
            printf("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");
        }
    }

Grouping

  • 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ý (regex3.c):
    #include <stdio.h>
    #include <regex.h>
    #include <stdlib.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){
            printf("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\nnmatch: %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);
            }
        }
    }

Additional Resources

Diskusia

Upozornenie: Do svojich príspevkov nevkladajte správne riešenia úloh a ani ich od ostatných nežiadajte! Nepoužívajte sprosté slová! Takéto príspevky budú zmazané! Riaďte sa podľa pravidiel etického kódexu.