De regulære udtryk

De regulære udtryk dukker op i Stephen Kleenes arbejde fra 1956 og er siden blevet arvegods inden for datalogi. Især i Unix-verdenen dukker varianter af regulære udtryk op igen og igen – i sed, awk, grep og selvfølgelig i Emacs (og i vi – undskyld til fans af denne editor), men også i regulære (!) programmeringssprog/scriptsprog som Perl, Python og Tcl. Også i søgninger i tekst (men ikke på Google) kan man have regulære udtryk til sin rådighed.

I The Guardian skriver Cory Doctorrow om regulære udtryk og plæderer for at man skal undervise i dem.

Det kunne faktisk være en rigtig interessant idé. Det interessante er at indførelsen af regulære udtryk inddrager en hel masse matematisk apparatur, som dukker op i datalogi. Måske har vi her endnu en måde at inddrage matematikanvendelser på og endnu et godt eksempel på at datalogi ikke er “et kursus i Word”:

De regulære udtryk definerer sprog over et givet alfabet A. De er givet ved at

  • \emptyset er et regulært udtryk
  • a er et regulært udtryk for ethvert tegn a i alfabetet A
  • \varepsilon er et regulært udtryk
  • Hvis r_1 og r_2 er r_1 \circ r_2 og r_1 \cup r_2 det også
  • Hvis r er et regulært udtryk er r^{\ast} det også

Allerede kan man se, at simpel mængdelære dukker op. Operationen \circ er så ikke en almen mængdeoperation, men konkatenation af sprog. Den store forhindring for mange studerende er at kende forskel på \emptyset, der betegner den tomme mængde \emptyset og \varepsilon, der betegner sproget bestående af den tomme streng, \{ \varepsilon \}. Om det mon hjælper at blive undervist i dette tidligt, ved jeg dog ikke.

I al fald giver de regulære udtryk os en lille opvisning i hvilke begreber, der dukker op i programmeringssprogsteori. De regulære udtryk er nemlig en lille kalkyle i sig selv (Robin Milner og Tony Hoare var inspireret af regulære udtryk i deres arbejde med de simple proceskalkyler CCS og CSP). Ovenstående definition af de regulære udtryk er det vi kalder for en induktiv definition og kan også ses som en abstrakt syntaks givet ved opbygningsreglen

r ::= \emptyset \mid a \mid \varepsilon \mid r_1 \circ r_2 \mid r_1 \cup r_2 \mid r_1^{\ast}

Vi kan også definere sproget L(r) for et vilkårligt regulært udtryk. Det er i virkeligheden en denotationel semantik (denotationen/”betydningen” af et udtryk er et sprog). Og vi kan for ethvert regulært udtryk induktivt opstille den ækvivalente nondeterministiske endelige automat; det er reelt en operationel semantik (et udtryks “adfærd” er den automat, der fortæller os om en streng er beskrevet af udtrykket eller ej).

Det gode ved regulære udtryk er at de er vel understøttet af mange slags software, så her er tale om et stykke matematik, der kan opleves hands-on. Det mindre gode er at der er så utroligt mange afarter af hvordan de bliver understøttet – og nogle af disse afarter gør livet kompliceret i jagten på det enkle. Man skal tænke sig meget nøje om inden man vælger hvilken afart man vil satse på.

Men faktisk er den lille definition, jeg lige har givet, nok; ethvert sprog der kan beskrives med “rigere” regulære udtryk end de her givne kan beskrives med de simple udtryk ovenfor. Måske skulle man starte med dem og kun dem og siden introducere de “smarte” udvidelser.

(Visited 130 times, 1 visits today)
Loading Facebook Comments ...

Skriv et svar