Regulære udtryk: sådan genkender RetKomma et subjekt

Chomsky gjorde allerede i Syntactic Structures opmærksom på, at naturlige sprog som engelsk ikke kan parses gennem en Finite Automaton (også kaldet Finite State Machine eller Markov process). Det vil groft sagt sige, at man ikke kan definere et endeligt antal stadier som en opskrift på, hvordan man mekanisk afgør, om en sætning tilhører det engelske sprog – det vil sige, om en sætning kan genereres gennem en grammatik for engelsk.

Rækken af stadier skal være formaliserede og eksplicitte. Antag fx at man har et sprog L, der består af en vilkårlig række a’er og b’er. Sproget kan beskrives gennem en Finite automaton ved noget i retning af:

  1. antag at vi har inputstrengen {Ø} (dvs. en tom streng)
  2. tilføj nu enten et a eller et b til inputstrengen eller afslut genereringen og returner strengen som den ser ud
  3. gentag (2) indtil du beslutter at returnere strengen

Dette kan visualiseres således:

Finite automaton, ab-sprog

Den dobbelte ring omkring A‘et angiver, at processen kan afsluttes på et hvilket som helst tidspunkt, hvor den er på dette stadie. Nu hvor der kun er ét stadie, giver det naturligvis lidt sig selv.

Men havde Chomsky ikke aflivet den for længst?

Jo, som jeg nævnte indledningsvist var det en af Chomskys kæpheste, at engelsk og andre naturlige sprog ikke kan genereres vha. en FA. Det interessante er, at finitte maskiner som disse faktisk er uhyre effektive til at beskrive dele af sproget. Når man gør det, anvender man typisk de såkaldte regulære udtryk, som kan genkende mønstre i tekst. Man kan med andre ord ikke konstruere ét regulært udtryk, som kan erstatte en engelsk grammatik, men man kan konstruere en række regulære udtryk, som – når de kombineres med egentlige programmeringssprog – rent faktisk kan nå meget langt i en beskrivelse af naturlige sprog.

Regulære udtryk indeholder en række specialtegn, som erstatter grupper af almindelige tegn. Lad os antage, at alle ordklasser har en kode, som består af præcis to tegn. Her kunne artiklen en have koden EN, og artiklet et kunne have koden TN. Som vi skal se senere, er det praktisk, at de begge slutter på N. Derfor koder vi et som TN frem for fx ET.

Okay, lad os videre antage at alle substantiver i ubestemt singularis har koden ON. Det vil sige, at strengen en hest ville have koden ENON, og at strengen et barn ville have koden TNON. Det er en tekststruktur, som vi kan genkende ved hjælp af regulære udtryk.

Det regulre udtryk ‘ENON’ ville finde alle ENON-kombinationer i en streng som fx JDJHASFLKJHDENONFSDALKENON. Tilsvarende ville det regulære udtryk ‘TNON’ finde alle TNON-kombinationer i en streng.

Vi kan også sammenskrive det til ét udtryk: ‘ENON|TNON’. Her angiver | en alternation – dvs. en entel-eller-relation mellem ENON på den ene side og TNON på den anden side. Dvs.: Find alle substrenge i inputstrengen S, som er identiske med enten ENON eller TNON.

Lad os se på, hvordan det rent faktisk fungere.

Lad os først antage, at inputstrengen er ADENLFKONJHAENONAFSDTNON, hvor ENON og TNON er understreget af hensyn til læsningen. Vores FA vil nu gå strengen igennem for at lede efter udtrykket ‘ENON|TNON’. Det vil begynde ved første bogstav: A, og sammenholde det med det regulære udtryks første tegn, som er understreget her: ‘ENON|TNON’. Der er ikke noget match, og derfor vil den forkaste ENON som en mulighed, men maskinen har endnu ikke kontrolleret udsagn 2: TNON. Det vil derfor match A mod TNON, før det fortsætter. Det gøres igen ved at sammenligne A med det første bogstav i udtrykket: ‘ENON|TNON’. Her er der heller ikke noget match, så maskinen fortsætter til næste bogstav i inputstrengen: D, og starter forfra med at matche det op mod det regulære udtryk.

Dette er en relativ langsom proces, men der eksisterer en række teknikker til at speede det op. Fx kunne vi til at begynde med skrive det regulære udtryk smartere. I stedet for ‘TNON|ENON’ kunne vi skrive ‘(TN|EN)ON’. Med regulære udtryk, sådan som de er implementeret i langt de fleste programmeringssprog, kan man desuden se fremad i teksten. Se fx på dette udtryk:

(?=.N)(TN|EN)ON

Den første parentes er en såkaldt lookaround, hvor maskinen ser fremad i teksten. Dette specifikke udtryk kaldes et positive lookahead. Det angives med udtrykket (?=). Det efterfølgende: ‘.N’, er det udtryk, maskinen skal lede efter. Et punktum angiver et hvilket som helst tegn. Altså undersøger maskinen for hvert tegn, om det kan svare sig at begynde at matche selve det regulære udtryk, før det går i gang.

Vi kunne også vedtage, at adjektiver med nøgen form denoteres AN, og at adjektiver med -t-form denoteres BN. Vi kan så fremstille de regulære udtryk:

ENANON|ETBNON|ENANANON|ETBNBNON|ENAN…ANON|ETBN…BNON

Symbolet * anvendes til at symbolisere, at noget kan gentages et vilkårligt antal gange. Man siger normalt, at operatoren er ‘grådig’. Det vil sige, at den altid forsøger at opnå det længst mulige match. Bemærk dog, at den også vil acceptere et nul-match, idet der er tale om et vilkårligt antal matches. Således kan ovenstående udtryk skrives således:

(EN(AN)*|ET(BN)*)ON

Det er en betydelig kortere måde at sige det samme på. Bemærk, at der er nødt til at være parenteser rundt om (AN) og (BN), da AN* betyder ANNNNN…., mens (AN)* betyder ANANANANAN….. Men det er stadig ikke helt præcst. For EN og ET kan principielt udelades. Her kan man anvende operatoen ? til at angive valgfrihed:

((EN)?(AN)*|(ET)?(BN)*)ON

Regulære udtryk er med andre ord utroligt stærke som beskrivelsesredskab for naturligt sprog, og selvom de ikke kan stå alene, er det en stærk måde at formalisere grammatikker på.

2 responses to “Regulære udtryk: sådan genkender RetKomma et subjekt

  1. Pingback: Ordklasser « Sproglige former

  2. hello!,I really like your writing so a lot! percentage we keep in touch more approximately your post on AOL?

    I require a specialist on this house to resolve my problem.
    May be that’s you! Taking a look ahead to peer
    you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s