Oversikt

Regulære uttrykk (regex) er et formelt språk for å beskrive mønstre i tekst. De brukes i nesten alle språkteknologiske systemer -- fra tokenisering og informasjonsekstraksjon til datavalidering. I IN1140 er regex en av de mest praktiske ferdighetene du testes i, og oppgavene krever at du kan skrive presise uttrykk som matcher akkurat det som spesifiseres.

Grunnleggende byggeklosser

De viktigste operatorene i regex er: tegnklasser [abc] matcher ett av tegnene a, b eller c; [0-9] matcher et siffer; [a-zA-Z] matcher en bokstav. Disjunksjon a|b matcher enten a eller b -- merk at disjunksjon har lav presedens, sa ab|cd|efg matcher hele strengen "ab", "cd" eller "efg" (ikke bare enkeltbokstaver). Kvantitatorer: ? (0 eller 1), * (0 eller flere), + (1 eller flere), {n} (nøyaktig n), {n,m} (mellom n og m). Grupperinger med parenteser () styrer presedens og fanger grupper.

Spesialtegn og escaping

Punktum . matcher et vilkårlig tegn. Backslash \ brukes for å escape spesialtegn, f.eks. \. for å matche et faktisk punktum. Forkortelser: \d = [0-9], \s = mellomrom/tab/newline, \w = ordtegn [a-zA-Z0-9_]. Ankere: ^ = starten av linjen, $ = slutten av linjen.

Parenteser og grupperinger

Parenteser har to funksjoner: de grupperer uttrykk for å styre presedens (f.eks. (ab)+ matcher "ab", "abab", osv.), og de fanger delstrenger for bruk videre. På H2022-eksamen ble du spurt om parenteser i uttrykket (0?[1-9]|1[012])-(31|[123]0|[012]?[1-9]) kunne fjernes -- svaret avhenger av om parentesene er nødvendige for å skille alternativene innenfor disjunksjonen fra resten av uttrykket.

Praktiske eksamensoppgaver

Regex er testet på alle eksamener, og oppgaven kommer alltid først. To hovedtyper går igjen: (1) Skriv et regex selv som matcher en spesifikasjon -- f.eks. datoformat, pris, klokkeslett og billettype i ett søkeresultat, eller en flerlinje-postadresse med flere gyldige varianter. (2) Analyser et gitt regex -- avgjør hvilken streng som ikke matches, om en parentes kan fjernes, eller om en påstand om uttrykket er sann/usann. En klassisk "skriv selv"-variant er å lage ett uttrykk som gjenkjenner flere bøyningsformer av en ordliste (infinitiv, presens, preteritum, imperativ) ved hjelp av en felles stamme og en disjunksjon av endelser, eller å gjenkjenne en klasse forkortelser bygd opp på samme mate (bokstav(er) etterfulgt av punktum, evt. gjentatt). Nøkkelen er alltid å bryte ned kravene i delproblemer og bygge uttrykket steg for steg.

Regulære uttrykk og endelige tilstandsmaskiner

Regulære uttrykk svarer formelt til endelige tilstandsmaskiner (finite-state automata): et sett tilstander med transisjoner på input-symboler, en starttilstand og en eller flere aksepttilstander. En maskin er deterministisk (DFA) hvis hver kombinasjon av tilstand og symbol har nøyaktig en transisjon -- ellers er den ikke-deterministisk (NFA), f.eks. hvis samme symbol fra en tilstand kan føre til flere tilstander, eller hvis det finnes tomme (epsilon-)transisjoner. Du kan bli bedt om å sette opp en transisjonstabell (rader = tilstander, kolonner = symboler, celler = neste tilstand) og begrunne om maskinen er deterministisk.

Eksempel 1: Matche norske datoer (H2022-stil)

Krav: Match datoer som 5.6.2014, 05.06.2014, 5.6.14, 05.06.14 (dag.måned.ar).

/([012]?[1-9]|[123]0|31)\.(0?[1-9]|1[012])\.\d\d(\d\d)?/

Forklaring: Dagen matcher 1-31 (med valgfri ledende null), etterfulgt av punktum, måned 1-12, punktum, og to eller fire sifre for året.

Eksempel 2: Matche telefonnumre (H2021-stil)

Gitt: ((\ +47|0047)\s)?([0-9][0-9]\s){3}([0-9][0-9]){1}

Spørsmålet var om uttrykket kun gjenkjenner numre som begynner med +47/0047, eller om det også matcher numre uten landskode. Svaret: Gruppen med landskode er valgfri (markert med ?), sa uttrykket matcher både med og uten landskode. Påstand 1 ("kun med landskode") er altså usann.

Eksempel 3: Ett regex for flere bøyningsformer (skriv-selv-stil)

Oppgave: Skriv ett regulært uttrykk som gjenkjenner infinitiv, presens, preteritum og imperativ av verbene danse, hoppe og rope.

Strategi: Samle stammene i en disjunksjon, og legg endelsene utenpå. Imperativ = stammen alene, infinitiv = stamme + e, presens = stamme + er, preteritum = stamme + et/te. Et mulig uttrykk:

/(dans|hopp|rop)(e|er|et)?/

Her er stammen (dans|hopp|rop) felles, og (e|er|et)? dekker de boyde formene mens den valgfrie ? tillater imperativen (bar stamme). Legg gjerne til ankere ^...$ hvis uttrykket skal matche hele ordet og ikke bare en delstreng. Poenget sensor ser etter er at du faktorerer ut det felles og bruker disjunksjon + valgfrie grupper -- ikke at du lister hver form for seg.

Studieguide: Regulære uttrykk

Studieguide: Regulære uttrykk