Regelmæssige udtryk

Regulære udtryk er et formelt  sprog , der bruges i computerprogrammer, der arbejder med tekst til at søge efter og manipulere understrenge i tekst , baseret på brugen af ​​metategn ( jokertegn ) . For at søge bruges en mønsterstreng ( engelsk mønster , på russisk kaldes det ofte en "skabelon", "maske"), bestående af tegn og metategn og sætter søgereglen. Ved manipulationer med tekst er der desuden angivet en erstatningsstreng, som også kan indeholde specialtegn.   

Funktioner

Regulære udtryk bruges af nogle teksteditorer og hjælpeprogrammer til at søge og erstatte tekst. Ved hjælp af regulære udtryk kan du f.eks. angive mønstre, der giver dig mulighed for at:

Regulære udtryk giver dig også mulighed for at angive meget mere komplekse søgninger eller erstatte mønstre.

Resultatet af at arbejde med et regulært udtryk kan være:

Hvis et regulært udtryk bruges til at erstatte tekst, så bliver resultatet af arbejdet en ny tekststreng, som er kildeteksten, hvorfra de fundne delstrenge (matchet med mønsteret) fjernes, og erstatningsstrenge erstattes (evt. modificeret af grupper af tegn, der huskes under parsing fra kildeteksten). Et særligt tilfælde af tekstændring er fjernelse af alle forekomster af det fundne mønster - for hvilke erstatningsstrengen er angivet tom.

Sættet af hjælpeprogrammer (inklusive sed- editoren og grep- filteret ), der blev leveret med UNIX - distributioner , var blandt de første, der populariserede regulære udtryk til tekstbehandling. Mange moderne programmeringssprog har indbygget understøttelse af regulære udtryk. Blandt dem er ActionScript , Perl , Java [1] , PHP , JavaScript , .NET Framework- sprog [2] , Python , Tcl , Ruby , Lua , Gambas , C++ ( 2011 standard ), Delphi , D , Haxe og andre.

Historie

Oprindelsen til regulære udtryk ligger i automatteorien , teorien om formelle sprog og Chomskys klassifikation af formelle grammatikker [3] .

Disse felter studerer beregningsmodeller (automater) og måder at beskrive og klassificere formelle sprog på . I 1940'erne Warren McCulloch og Walter Pitts beskrev et neuralt system ved hjælp af en simpel automat som model for en neuron .

Matematikeren Stephen Kleene beskrev senere disse mønstre ved hjælp af sin matematiske notation kaldet " regulære mængder ".

Ken Thompson indbyggede dem i QED- editoren og derefter i UNIX ed- editoren. Siden dengang er regulære udtryk blevet meget brugt i UNIX og UNIX-lignende hjælpeprogrammer såsom expr , awk , Emacs , vi , lex og Perl .

Regelmæssige udtryk i Perl og Tcl kommer fra en implementering skrevet af Henry Spencer . Philip Hazel udviklede PCRE ( Perl -kompatible regulære udtryk )  biblioteket  , som bruges i mange moderne værktøjer såsom PHP og Apache .

I teorien om formelle sprog

Regulære udtryk består af konstanter og operatorer , der definerer henholdsvis sæt af strenge og sæt af operationer på dem. Følgende konstanter er defineret:

og følgende operationer:

De regulære udtryk, der findes i moderne programmeringssprog (især PCRE ) har mere magt end det, der kaldes regulære udtryk i formel sprogteori; især har de nummererede tilbagehenvisninger . Dette giver dem mulighed for at parse strenge, der ikke kun er beskrevet af almindelige grammatikker, men også af mere komplekse, især kontekstfrie grammatikker [5] [6] .

Syntaks

Symbolrepræsentation

Almindelige tegn ( bogstaver ) og specialtegn ( metategn )

De fleste tegn i et regulært udtryk repræsenterer sig selv, med undtagelse af specialtegn [ ] \ / ^ $ . | ? * + ( ) { } (dette sæt er forskelligt for forskellige typer regulære udtryk, se Variety of regular expressions ), som kan escapes med et tegn \(omvendt skråstreg) for at repræsentere sig selv som teksttegn. Du kan undslippe en hel sekvens af tegn ved at omslutte den mellem \Qog \E.

Eksempel Overensstemmelse
a\.? a.ellera
a\\\\b a\\b
a\[F\] a[F]
\Q+-*/\E +-*/

Andre specialtegn kan repræsenteres på samme måde (de tegnsæt, der kræver escape, kan variere afhængigt af den specifikke implementering). En del af de tegn, der i den ene eller anden implementering ikke kræver escape (f.eks. vinkelparenteser < >), kan escapes af hensyn til læsbarheden.

Ethvert tegn

Metategn .(punktum) betyder ethvert enkelt tegn, men i nogle implementeringer, ekskluderer det nye linjetegn.

I stedet for et tegn .kan du bruge [\s\S](alle mellemrumstegn og ikke-mellemrumstegn, inklusive nylinjetegnet).

Tegnklasser (tegnsæt)

Sæt af tegn i firkantede parenteser [ ]kaldes en karakterklasse og giver dig mulighed for at indikere over for regulære udtryksfortolkeren, at et af de anførte tegn kan optræde et givet sted i en streng. Den indstiller især [абв]muligheden for forekomst i teksten af ​​et af de tre angivne tegn og [1234567890]sætter korrespondancen til et af cifrene. Det er muligt at angive rækker af tegn: [А-Яа-я]matcher for eksempel alle bogstaver i det russiske alfabet, undtagen bogstaverne "Ё" og "ё" [7] . Nogle implementeringer af regulære udtryk kan tillade karakterklasser at inkludere ikke kun tegn, men også hele strenge. [otte]

Hvis du vil angive tegn, der ikke er inkluderet i det angivne sæt, skal du bruge tegnet ^inden for firkantede parenteser, f.eks. [^0-9]betyder et hvilket som helst andet tegn end tal.

Tilføjelse af specialtegn til sættet ved at escape er den enkleste måde. Moderne regulære udtryk arver dog også den traditionelle tilgang – se Traditionelle regulære udtryk .

Nogle karakterklasser kan erstattes med specielle metategn:

Symbol Mulig ækvivalent [9] Overensstemmelse
\d [0-9] Цифровой символ
\D [^0-9] Нецифровой символ
\s [ \f\n\r\t\v] Пробельный символ
\S [^ \f\n\r\t\v] Непробельный символ

Пример: Выражение вида ^\S.* или ^[^ \f\n\r\t\v].* будет находить строки, начинающиеся с непробельного символа

\w[10] [A-Za-z0-9_] Буквенный или цифровой символ или знак подчёркивания; буквы ограничены латиницей

Пример: Выражение вида \w+ будет находить и выделять отдельные слова

\W[11] [^A-Za-z0-9_] Любой символ, кроме буквенного или цифрового символа или знака подчёркивания

Position i en streng

Følgende tegn giver dig mulighed for at placere det regulære udtryk i forhold til tekstelementer: begyndelsen og slutningen af ​​en linje, ordgrænser.

Ydeevne Position Eksempel Overensstemmelse
^ Begyndelsen af ​​tekst (eller linje med ?m modifier) ^a aaa aaa
$ Slut på tekst (eller linje med ?m-modifikator) a$ aaa aaa
\b ordgrænse a\b aaa aaa
\ba aaa aaa
\B Ikke en ordgrænse \Ba\B aaa aaa
\G Tidligere vellykket søgning \Ga aaa aaa(søgningen stoppede på 4. position - hvor den ikke blev fundet a)

Specialtegn

\n - linjeskift

\r - vogn retur

Gruppebetegnelse

Parenteser bruges til at definere omfanget og forrangen af ​​operationer . Et mønster inden for en gruppe behandles som en helhed og kan kvantificeres. For eksempel vil udtrykket (тр[ау]м-?)*finde en sekvens af formen трам-трам-трумтрам-трум-трамтрум.

Optælling

En lodret streg adskiller de gyldige muligheder. For eksempel gray|greytændstikker grayeller grey. Det skal huskes, at opregningen af ​​muligheder udføres fra venstre mod højre, som de er angivet.

Hvis du vil angive en liste over muligheder i et mere komplekst regulært udtryk, skal det være indesluttet i en gruppe. For eksempel, gray|greyeller gr(a|e)ybeskriv en streng grayeller grey. I tilfælde af enkelttegnsalternativer foretrækkes muligheden gr[ae]y, da sammenligning med en karakterklasse er lettere end at behandle en gruppe med en check for alle dens mulige modifikatorer og generere feedback.

Kvantificering (søg efter sekvenser)

Kvantifikatoren efter et tegn, tegnklasse eller gruppe bestemmer, hvor mange gange det foregående udtryk kan forekomme. Bemærk, at en kvantifier kun kan henvise til mere end ét tegn i et regulært udtryk, hvis det er en karakterklasse eller -gruppe.

Ydeevne Antal gentagelser Tilsvarende Eksempel Overensstemmelse
? Nul eller en {0,1} colou?r color,colour
* Nul eller mere {0,} colou*r color, colourosv colouur .
+ En eller flere {1,} colou+r colourosv colouur . (men ikke color)
Ydeevne Antal gentagelser Eksempel Overensstemmelse
{n} Præcis n gange colou{3}r colouuur
{m,n} Fra m til n inklusive colou{2,4}r colouur... colouuur_colouuuur
{m,} Ikke mindre end m colou{2,}r colouur, colouuurosv colouuuur .
{,n} ikke mere end n colou{,3}r color... colour_ colouur_colouuur

En sekvens bruges ofte til .*at angive et vilkårligt antal tegn mellem to dele af et regulært udtryk.

Karakterklasser i kombination med kvantifikatorer giver dig mulighed for at matche med rigtige tekster. For eksempel kolonner med tal, telefonnumre, postadresser, HTML -markup-elementer osv.

Hvis tegn { } ikke danner en kvantifier, ignoreres deres særlige betydning.

Grådig og doven kvantificering Et eksempel på brug af grådige og dovne udtryk

Udtrykket (<.*>)matcher en streng, der indeholder flere HTML -markup-tags i sin helhed.

<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью.</p>

For at fremhæve individuelle tags kan du anvende en doven version af dette udtryk: (<.*?>) Det svarer ikke til hele linjen vist ovenfor, men til individuelle tags (fremhævet i farve):

<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью.</p>

I nogle implementeringer svarer kvantifikatorer i regulære udtryk til den længst mulige streng (kvantifikatorer er grådig , engelsk  grådig ). Dette kan være et væsentligt problem. For eksempel forventes et udtryk ofte at finde HTML- tags(<.*>) i tekst . Men hvis der er mere end ét HTML-tag i teksten, matcher hele linjen, der indeholder flere tags, udtrykket.

<p><b>Википедия</b> — свободная энциклопедия, в которой <i>каждый</i> может изменить или дополнить любую статью.</p>

Dette problem kan løses på to måder.

  1. Overvej tegn, der ikke matcher det ønskede mønster ( <[^>]*>for ovenstående tilfælde).
  2. Definer en kvantifier som ikke-grådig ( doven , engelsk  doven ) - de fleste implementeringer giver dig mulighed for at gøre dette ved at tilføje et spørgsmålstegn efter det.

Brugen af ​​dovne kvantifikatorer kan føre til det omvendte problem, når et udtryk matcher for kort, især den tomme streng.

Grådig Doven
* *?
+ +?
{n,} {n,}?

Også et almindeligt problem med både grådige og dovne udtryk er returpunkterne for at gentage varianter af et udtryk. Perioder placeres efter hver iteration af kvantifieren. Hvis tolken ikke finder et match efter kvantifieren, begynder den at vende tilbage for alle sætpunkterne og genberegne udtrykket derfra på en anden måde.

Jaloux kvantificering (supergrådig)

Når tolken leder efter et udtryk i en streng, vil tolken gå omtrent ad følgende vej: (a+a+)+a aaaaa

  1. aaaaa
  2. aaaa
  3. aaaaa
  4. aaa
  5. aaaaa
  6. aaaa
  7. aaaaa- og først derefter, efter at have tjekket alle returpunkter, stopper det.

Når du bruger en jaloux kvantifier, vil kun det første trin af algoritmen blive udført.

I modsætning til almindelig (grådig) ​​kvantificering forsøger jaloux (besiddende) kvantificering ikke kun at finde den længste mulighed, men tillader heller ikke algoritmen at vende tilbage til tidligere søgetrin for at finde mulige matches for resten af ​​det regulære udtryk.

Brugen af ​​jaloux kvantifiers øger søgehastigheden, især i tilfælde hvor strengen ikke matcher det regulære udtryk. Derudover kan jaloux kvantifiers bruges til at eliminere uønskede kampe.

Grådig Jaloux
* *+
? ?+
+ ++
{n,} {n,}+
Eksempel Overensstemmelse
ab(xa)*+a abxaabxaa; men ikke , da brevet allerede er taget abxaabxaaa

Dette er analogt med atomgruppering .

Gruppering

Feedback

En anvendelse af gruppering er at genbruge tidligere fundne grupper af tegn ( understrenge , blokke , markerede underudtryk , indfangninger ). Når udtrykket behandles, gemmes de understrenge, der findes af mønsteret i gruppen, i et separat hukommelsesområde og modtager et tal, der starter fra en. Hver understreng matcher et par parenteser i det regulære udtryk. Gruppekvantificering påvirker ikke det gemte resultat, dvs. kun den første forekomst gemmes. Normalt understøttes op til 9 nummererede understrenge, nummereret 1 til 9, men nogle tolke giver dig mulighed for at arbejde med flere. Efterfølgende, inden for dette regulære udtryk, kan notationen fra \1til bruges \9til at kontrollere for en overensstemmelse med en tidligere fundet understreng.

For eksempel vil det regulære udtryk (та|ту)-\1matche strengen та-таeller ту-ту, men springe strengen over та-ту.

Tidligere fundne understrenge kan også bruges, når de erstattes med regulære udtryk. I dette tilfælde indsættes de samme symboler i erstatningsteksten som i selve udtrykket.

Gruppering uden feedback

Hvis gruppen kun bruges til gruppering, og dens resultat ikke er nødvendig senere, kan du bruge grupperingen af ​​typen . Et separat hukommelsesområde er ikke allokeret til resultatet af en sådan gruppering, og følgelig er der ikke tildelt et nummer til det. Dette har en positiv effekt på hastigheden af ​​udtrykkets udførelse, men reducerer læsbarheden. (?:шаблон)

Atomgruppering

En atomisk gruppering af et synspunkt , ligesom en gruppering uden feedback, skaber ikke feedback. I modsætning hertil forbyder en sådan gruppering at gå tilbage gennem strengen, hvis en del af mønsteret allerede er fundet. (?>шаблон)

Eksempel Overensstemmelse Oprettede grupper
a(bc|b|x)cc abccaxcc

abccaxcc

abccaxcc

abccaxcc

a(?:bc|b|x)cc abccaxcc,abccaxcc Ingen
a(?>bc|b|x)cc abccaxcc

men ikke abccaxcc: variant xfundet, andre ignoreret

Ingen
a(?>x*)xa ikke fundet axxxa: alle har xtravlt, og der er ingen tilbagevenden inde i gruppen

Atomisk gruppering er endnu hurtigere end open-loop-gruppering og sparer CPU-tid, mens resten af ​​udtrykket udføres, da det forhindrer, at andre muligheder inden for gruppen kontrolleres, når en mulighed allerede er fundet. Dette er meget nyttigt, når du optimerer grupper med mange forskellige muligheder.

Dette er analogt med jaloux kvantificering .

Modifikatorer

Modifikatorer er gyldige fra tidspunktet for forekomsten indtil slutningen af ​​det regulære udtryk eller den modsatte modifikator. Nogle fortolkere kan anvende modifikationen på hele udtrykket i stedet for fra det øjeblik, det opstår.

Syntaks Beskrivelse
(?i) Inkluderer ufølsomhed _  _ _
(?-i) Slukker
(?s) Inkluderer punktmatch-tilstand for linjeskift og vognretur-tegn
(?-s) Slukker
(?m) Symboler ^og $kun forårsage et match efter og før nylinjetegn
(?-m) med begyndelse og slutning af tekst
(?x) Inkluderer tilstand uden at tage hensyn til mellemrum mellem dele af det regulære udtryk og giver dig mulighed for at bruge #til kommentarer
(?-x) Slukker

Modifikatorgrupper kan kombineres til én gruppe: (?i-sm). En sådan gruppe slår tilstanden til og fra for itilstandene sog m. Hvis brugen af ​​modifikatorer kun er påkrævet inden for en gruppe, så er det ønskede mønster angivet inde i gruppen efter modifikatorerne og efter kolon. For eksempel (?-i)(?i:tv)setvil den finde , TVsetmen ikke TVSET.

Kommentarer

For at tilføje kommentarer til et regulært udtryk kan du bruge kommentargrupper i formularen . En sådan gruppe ignoreres fuldstændig af tolken og kontrolleres ikke for forekomst i teksten. For eksempel matcher udtrykket strengen . (?#комментарий)А(?#тут комментарий)БАБ

Se frem og tilbage

De fleste implementeringer af regulære udtryk har en måde at søge efter et stykke tekst ved at "kigge igennem" (men ikke inkludere) den omgivende tekst, der kommer før eller efter det stykke tekst, der søges efter. Negativt opslag bruges sjældnere og "sørger for", at de angivne matches tværtimod ikke forekommer før eller efter det søgte tekstfragment.

Ydeevne Vis type Eksempel Overensstemmelse
(?=шаблон) positivt se fremad Людовик(?=XVI) ЛюдовикXV, ЛюдовикXVI, ЛюдовикXVIII, ЛюдовикLXVII, ЛюдовикXXL
(?!шаблон) Negativt kig fremad (med negation) Людовик(?!XVI) ЛюдовикXV, ЛюдовикXVI, ЛюдовикXVIII, ЛюдовикLXVII, ЛюдовикXXL
(?<=шаблон) Positivt tilbageblik (?<=Сергей )Иванов Сергей Иванов, Игорь Иванов
(?<!шаблон) Negativt tilbageblik (med negation) (?<!Сергей )Иванов Сергей Иванов, Игорь Иванов

Søg efter betingelse

I mange implementeringer af regulære udtryk er det muligt at vælge, hvilken vej checken skal tage et eller andet sted i det regulære udtryk, baseret på de værdier, der allerede er fundet.

Ydeevne Forklaring Eksempel Overensstemmelse
(?(?=если)то|иначе) Hvis scanningen lykkes, udføres den næste del то, ellers udføres delen иначе. Enhver af de fire opslagsoperationer kan bruges i et udtryk. Bemærk, at opslagsoperationen er nul-bredde, så delene тоi tilfælde af et positivt opslag eller иначеi tilfælde af et negativt opslag skal indeholde beskrivelsen af ​​skabelonen fra opslagsoperationen. (?(?<=а)м|п) мам,пап
(?(n)то|иначе) Hvis den n -te gruppe returnerede en værdi, udføres søgningen efter betingelse af mønsteret то, ellers af mønsteret иначе. (а)?(?(1)м|п) мам,пап

Flag

På nogle sprog (for eksempel i JavaScript ) den såkaldte. "flag", der udvider funktionaliteten af ​​RegExp. Flagene er specificeret efter det regulære udtryk (rækkefølgen af ​​flagene har ingen betydning). Typiske flag:

  • g  - global søgning (alle matches med søgemønsteret behandles);
  • i  - bogstaver betyder ikke noget;
  • m  - multiline søgning;
  • s  - teksten behandles som én linje, i dette tilfælde .matcher metakarakteren (prikken) ethvert enkelt tegn, inklusive nylinjetegnet;
  • u  - unicode fortolkning. Udtrykket kan indeholde specielle mønstre, der er specifikke for Unicode, såsom /\p{Lu}/ store bogstaver.

Flaget er angivet efter mønsteret, for eksempel sådan: . /[0-9]$/m

Varianter af regulære udtryk

Grundlæggende POSIX regulære udtryk

( Engelske  grundlæggende regulære udtryk (BRE)). Traditionelle UNIX regulære udtryk . Den grundlæggende regulære udtrykssyntaks er nu forældet af POSIX , men den bruges stadig i vid udstrækning af årsager til bagudkompatibilitet. Mange UNIX-værktøjer bruger som standard sådanne regulære udtryk.

Denne version indeholder metategn:

  • .;
  • [ ];
  • [^ ];
  • ^(kun gyldig i begyndelsen af ​​et udtryk);
  • $(kun gyldig i slutningen af ​​udtrykket);
  • *;
  • \{ \} - indledende version for { };
  • \( \) - indledende version for ( );
  • \n, hvor n  er et tal fra 1 til 9.

Ejendommeligheder:

  • Stjernen skal komme efter det udtryk, der matcher det enkelte tegn. Eksempel: [xyz]*.
  • Udtrykket bør betragtes som ugyldigt. I nogle tilfælde matcher den nul eller flere gentagelser af strengen . I andre matcher den strengen .\(блок\)*блокблок*
  • Inden for en karakterklasse ignoreres specielle tegnværdier generelt. Særlige tilfælde:
    • For at tilføje et tegn ^til et sæt, må det ikke placeres der først.
    • For at tilføje et tegn -til et sæt, skal det placeres der enten først eller sidst. For eksempel:
      • DNS-navneskabelon, som kan indeholde bogstaver, tal, minus og skilletegn: [-0-9a-zA-Z.];
      • ethvert tegn undtagen minus og tal: [^-0-9].
    • For at tilføje et symbol [eller ]til et sæt, skal det placeres der først. For eksempel:
      • [][ab]matcher ], [, aeller b.

Udvidede POSIX regulære udtryk

( Engelske  udvidede regulære udtryk (ERE)). Syntaksen er grundlæggende den samme som den traditionelle.

  • Fjernede brugen af ​​omvendte skråstreger for metategn { }og ( ).
  • En omvendt skråstreg før et metategn annullerer dets særlige betydning (se Repræsentation af specialtegn ).
  • Teoretisk uregelmæssigt design afvises .\n
  • Tilføjet metategn +, ?, |.

Perl -kompatible regulære udtryk

Perl -kompatible regulære udtryk (PCRE) har en rigere syntaks end selv POSIX ERE .  Af denne grund bruger mange programmer den Perl-kompatible regulære udtrykssyntaks.

Regulære udtryk, der er kompatible med Unicode

Unicode  er et tegnsæt, hvis formål er at definere alle tegn og symboler fra alle menneskelige sprog, levende og døde. Regulære udtryk designet til mange sprog er således ikke bundet til specifikke tegnsæt, men beskriver dem efter accepterede regler. Så for eksempel ville et udtryk for at finde store bogstaver i ethvert alfabet se sådan ud: /\p{Lu}/.

Nogle regexp-udtryk er unicode:
ydeevne funktionalitet
mulig kortform mulig lang form
Breve
\p{L} \p{Letter} ethvert bogstav på ethvert sprog
\p{Ll} \p{Lowercase_Letter} små bogstaver (små bogstaver) af dem, der har en stor stavemåde
\p{Lu} \p{Uppercase_Letter} store bogstaver (store bogstaver) for dem med små bogstaver
\p{Lt} \p{Titlecase_Letter} et stort bogstav, der vises i begyndelsen af ​​et lille ord
\p{L&} \p{Cased_Letter} et bogstav, der både har store og små bogstaver
\p{Lm} \p{Modifier_Letter} specialtegn, der bruges som bogstaver
\p{Lo} \p{Other_Letter} et tegn eller et ideogram, der ikke har store eller små bogstaver
Særlige symboler
\p{M} \p{Mark} tegn indsat for at kombinere med andre tegn (f.eks. accenter, omlyd, ombrydningsparenteser)
\p{Mn} \p{Non_Spacing_Mark} et tegn indsat for at blive kombineret med andre tegn uden at optage ekstra bredde
\p{Mc} \p{Spacing_Combining_Mark} tegn, der er indsat for at blive kombineret med andre tegn, optager ekstra bredde (som i mange orientalske sprog)
\p{Me} \p{Enclosing_Mark} tegn, der omslutter en karakter. For eksempel cirkel, firkant osv.
Mellemrum og separatorer
\p{Z} \p{Separator} enhver form for mellemrum eller usynlige adskillere
\p{Zs} \p{Space_Separator} mellemrumstegn, der er usynlige, men som har en bredde
\p{Zl} \p{Line_Separator} linjeadskillelsessymbol U+2028
\p{Zp} \p{Paragraph_Separator} paragrafmærke U+2029
Matematiske symboler
\p{S} \p{Symbol} matematiske symboler, valutasymboler, pseudografiske symboler (rammer) osv.
\p{Sm} \p{Math_Symbol} eventuelle matematiske symboler
\p{Sc} \p{Currency_Symbol} eventuelle valutasymboler
\p{Sk} \p{Modifier_Symbol} kombineret tegn (mærke) som en kombination af selve tegnet og mærketegnet
\p{So} \p{Other_Symbol} forskellige symboler, ikke-matematiske, ikke-valutasymboler eller kombinationer deraf
Numeriske tegn
\p{N} \p{Number} enhver form for digitale tegn på alle sprog
\p{Nd} \p{Decimal_Digit_Number} tal fra nul til ni på alle sprog
\p{Nl} \p{Letter_Number} et tal, der kan ligne bogstaver, såsom romertal
\p{No} \p{Other_Number} et tal repræsenteret som hævet eller sænket skrift, eller et tal, der ikke består af cifre (undtagen tal fra ideografiske skrifter)
Punktum
\p{P} \p{Punctuation} enhver form for tegnsætningstegn
\p{Pd} \p{Dash_Punctuation} enhver form for bindestreg eller bindestreg
\p{Ps} \p{Open_Punctuation} enhver form for åbningsbeslag
\p{Pe} \p{Close_Punctuation} enhver form for lukkebeslag
\p{Pi} \p{Initial_Punctuation} enhver form for åbningscitater
\p{Pf} \p{Final_Punctuation} enhver form for afsluttende citater
\p{Pc} \p{Connector_Punctuation} tegnsætningstegn, såsom understregninger eller ordsammensætninger
\p{Po} \p{Other_Punctuation} enhver form for tegnsætning, der ikke er prikker, parenteser, anførselstegn eller stik
Kontrolkarakterer
\p{C} \p{Other} usynlige kontrolkarakterer og ubrugte positioner
\p{Cc} \p{Control} ASCII eller Latin-1 kontroltegn: 0x00-0x1F og 0x7F-0x9F
\p{Cf} \p{Format} usynlige formateringsindikatorer
\p{Co} \p{Private_Use} alle stillinger, der er reserveret til personlig brug
\p{Cs} \p{Surrogate} halvdelen af ​​surrogatpar kodet i UTF-16
\p{Cn} \p{Unassigned} alle positioner, der ikke har tildelt symboler

Fuzzy regulære udtryk

I nogle tilfælde er det praktisk at bruge regulære udtryk til at analysere tekstfragmenter i naturligt sprog , det vil sige skrevet af mennesker, og som muligvis indeholder slåfejl eller ikke-standard ordbrug. For eksempel, hvis du foretager en undersøgelse (f.eks. på et websted) "hvilken metrostation bruger du", kan det vise sig, at besøgende kan angive "Nevsky Prospekt" som:

  • Nevskij
  • Nevsk. Ave.
  • Ny allé
  • emb. Griboyedov-kanalen ("Griboedov-kanalen" er navnet på den anden udgang fra Nevsky Prospekt-metrostationen)

Her er de sædvanlige regulære udtryk ikke anvendelige, primært på grund af det faktum, at ordene inkluderet i mønstrene måske ikke matcher særlig nøjagtigt (fuzzy), men ikke desto mindre ville det være praktisk at beskrive de strukturelle afhængigheder mellem elementerne i mønsteret med regulære udtryk, for eksempel, i vores tilfælde angiver, at matchningen kan være med prøven "Nevsky Prospekt" ELLER "Griboedov Canal", desuden kan "Prospect" forkortes til "pr" eller fraværende, og forkortelsen "Eb. " kan placeres før "Kanal".

Denne opgave ligner fuldtekstsøgning , idet den adskiller sig ved, at her skal et kort fragment sammenlignes med et sæt mønstre, og i fuldtekstsøgning er mønsteret tværtimod normalt ét, mens tekstfragmentet er meget stort. , eller det leksikalske disambigueringsproblem , som dog ikke tillader specificering af strukturerende forhold mellem mønsterelementer.

Der er et lille antal biblioteker , der implementerer den regulære udtryksmekanisme med mulighed for uklar sammenligning:

  • TRE er et gratis C-bibliotek, der bruger POSIX-lignende regulære udtrykssyntaks (stabilt projekt);
  • FREJ er et open source Java-bibliotek, der bruger en Lisp-formet syntaks og mangler mange af funktionerne i konventionelle regulære udtryk, men fokuserer på forskellige former for automatiske udskiftninger af tekstfragmenter (betaversion).

Implementeringer

  • NFA ( non- deterministic  finite-state automata  - non- deterministic finite automata ) bruger en grådig tilbagesporingsalgoritme , kontrollerer alle mulige udvidelser af et regulært udtryk i en bestemt rækkefølge og vælger den første passende værdi. NFA kan håndtere underudtryk og tilbagereferencer. Men på grund af rollback-algoritmen kan traditionel NFA tjekke det samme sted flere gange, hvilket påvirker arbejdshastigheden negativt. Da traditionel NFA tager det første match, det finder, finder det muligvis ikke det længste match (dette er påkrævet af POSIX -standarden , og der er modifikationer af NFA, der opfylder dette krav - GNU sed ). Det er denne regulære udtryksmekanisme, der f.eks. bruges i Perl , Tcl og .NET .
  • DFA ( eng.  deterministic finite-state automata  - deterministic finite automata ) arbejder lineært i tid, fordi de ikke bruger rollbacks og aldrig dobbelttjekker nogen del af teksten. De kan med garanti finde den længst mulige snor. En DFA indeholder kun en endelig tilstand, så den håndterer ikke tilbagereferencer, og den understøtter heller ikke eksplicitte udvidelseskonstruktioner, hvilket betyder, at den heller ikke kan håndtere underudtryk. DFA bruges f.eks. i lex og egrep .

Se også

Noter

  1. ↑ docs.oracle.com . Hentet 20. august 2013. Arkiveret fra originalen 9. september 2013.
  2. ↑ MSDN . Hentet 11. juli 2011. Arkiveret fra originalen 15. september 2012.
  3. ↑ Aho A., Ulman J. Teori om parsing, oversættelse og kompilering. Syntaktisk analyse. - Verden. - M. , 1978. - T. 2.
  4. ↑ Mange bøger bruger ∪, + eller ∨ i stedet for |.
  5. ↑ Nikita Popov. Den sande kraft af regulære udtryk (15. juni 2012). Hentet 30. maj 2019. Arkiveret fra originalen 16. maj 2019. Oversættelse: The True Power of Regular Expressions Arkiveret 30. maj 2019 på Wayback Machine .
  6. ↑ Vladimir Komendantsky. Matching problem for regulære udtryk med variabler // Tendenser i funktionel programmering: 13th International Symposium, TFP 2012, St. Andrews, UK, 12-14 juni 2012, Revised Selected Papers. — Springer, 2013. — S. 149–150. — ISBN 9783642404474 .
  7. ↑ For at bruge bogstavsekvenser skal du indstille den korrekte tegntabel, hvori disse sekvenser vil gå i rækkefølge fra og til de angivne tegn. For det russiske sprog er disse Windows-1251 , ISO 8859-5 og Unicode , da russiske bogstaver i DOS-855 , DOS-866 og KOI8-R ikke går i én hel gruppe eller ikke er ordnet alfabetisk. Der bør lægges særlig vægt på bogstaver med diakritiske tegn , som det russiske Ё / ё, som normalt er spredt uden for hovedkarakterernes rækkevidde.
  8. ↑ UTS #18: Unicode regulære  udtryk . Hentet 8. august 2021. Arkiveret fra originalen 8. august 2021.
  9. ↑ Varierer afhængigt af implementeringen af ​​den regulære udtryksmotor
  10. ↑ Der er en tilsvarende notation [[:word:]]
  11. ↑ Der er en tilsvarende notation [^[:ord:]]

Litteratur

  • Friedl, J. Regulære udtryk = Beherskelse af Regulære udtryk. - Sankt Petersborg. : "Peter" , 2001. - 352 s. — (Programmer's Bibliotek). — ISBN 5-318-00056-8 .
  • Smith, Bill. Metoder og algoritmer til beregning på strenge (regexp) = Computing Patterns in Strings. - M . : "Williams" , 2006. - 496 s. — ISBN 0-201-39839-7 .
  • Forta, Ben. Lær dine egne regulære udtryk. 10 minutter pr. lektion = Sams Lær dig selv regulære udtryk på 10 minutter. - M . : "Williams" , 2005. - 184 s. — ISBN 5-8459-0713-6 .
  • Jan Goyverts, Steven Levitan. Regelmæssige udtryk. Kogebog = Regelmæssige udtryk: Kogebog. - Sankt Petersborg. : "Symbol-Plus" , 2010. - 608 s. - ISBN 978-5-93286-181-3 .
  • Melnikov SV Perl for professionelle programmører. Regelmæssige udtryk. - M . : "Binom" , 2007. - 190 s. — (Fundamentals of Information Technology). — ISBN 978-5-94774-797-3 .
  • Michael Fitzgerald. Regelmæssige udtryk. Grundlæggende. - M. : "Williams" , 2015. - 144 s. — ISBN 978-5-8459-1953-3 .

Links

 Formelle sprog og formelle grammatikker
Generelle begreber
Type 0
Type 1
Type 2
Type 3
parsing