« Fortsatt stavning av "Henning Mankell". Samt lite om agrep | Main | Jazz-nätverk »

april 28, 2004

Skapa strängar från reguljära uttryck - eller: Tystnaden de senaste dagarna

I morse mailade en vän frågan var jag hållit hus de senaste dagarna. Hans misstanke om alien abduction var rörande att läsa. Här är ett något kompletterat utdrag från mitt svarsmail.


Anledningen till tystnaden de senaste dagarna är att jag varit djupt inne i ett skoj projekt, nämligen att generera strängar givet ett reguljärt uttryck (regex). Embryot till systemet var det som skrevs om häromdagen angående stavningen av "Henning Mankell". Detta har även gjorts djupare studier i programspråket Icon/Unicon.

Innan dess läste jag, nästan helt orelaterat, en avhandling om ett nytt sätt att söka i ett dokument, där man kan markera upp de relevanta delarna varpå systemet försöker lista ut vad det är man söker efter. Systemet heter LAPIS, och eventuellt kommer det en lite längre anteckning om detta trevliga system.


Systemet för genererande av strängar från regex har kommit en bra bit framåt. Det är två principiellt fungerande delar som jag försöker att integrera så det blir ett fint webb-program. Dels ett Perlprogram som parsrar det reguljära uttrycket och skapar Icon-kod, dels ett Icon-program som innehåller funktioner för att skapa strängarna. Idealet vore naturligtvis att ha ett enda program, möjligen skrivet i ett helt annat programspråk, t.ex. Java, men det är ett annat projekt.

I kommentaren till Fortsatt stavning av "Henning Mankell". Samt lite om agrep visas en lista som då skapades via en handsnickrad Icon-funktion. Nu kan man alltså göra sådant nästan helt automatiskt.


Här nedan följer en kort förklaring hur systemen fungerar. Det finns dock inte någon webbversion av programmet så ni får helt enkelt lita på mina ord i det följande.

Först bör nämnas en viktig restriktion i strängskapandet: Kvantifikationsoperatorerna * ("ingen eller flera förekomster"), + ("en eller flera förekomster") samt {,}genererar inte oändligt antal strängar utan endast ett begränsat och parameterstyrt antal, för närvarande 3. Regexet (ab)* skapar alltså endast följande strängar:

"","ab", "abab","ababab"

Perl-programmet består nästan bara av en parser och "action-koder" för att bilda Icon-koden. Den parser som används blev, efter ett antal olika försök med andra liknande system, Parse::RecDescent. En trevlig tutorial till detta system finns här .

En stor del av tiden har ägnats åt att debugga grammatiken (dvs reglerna för hur regex-språket ser ut). Tyvärr är detta program långsamt, vilket beror på en kombination av 33% mitt fel, 33% en inte helt trivial grammatik samt cirka 33% att det är en långsam parsergenerator. De största problemen var att få grammatiken att bli "left recursion free", få ordning på det egna lilla språk som finns i character classes (dvs inom []) samt escapeande av tecken här och var. Det finns troligen en och annan bugg kvar att fixa.

Naturligtvis testades först att skriva parserna i Icon eftersom det är där själva genereringen av strängarna görs , men inga av de parsers i kombination med olika varianter av grammatiker fungerade speciellt bra. Spelet är dock inte slut ännu: Nu finns det ju en grammatik som inte är "left-recursive" längre, vilket är ett bra steg framåt.

Exempel: Om input till parserna är det reguljära uttrycket

K(je|ä)ll(er)?(st|b)r?an?d

skapas följande Icon-kod:

suspend ("K" || (((("j" || "e") | "ä")) || ("l" || ("l" ||
(gen_question_mark((("e" || "r"))) || (((("s" || "t") | "b")) ||
(gen_question_mark("r") || ("a" || (gen_question_mark("n") || "d")))))))))

Icon-programmet är i princip klart och klarar av det allra mesta av den önskvärda funktionaliteten. Det enklaste vore att pumpa in strängen som genererades av parsern i en eval()-liknande funktion, men sådana möjligheter saknas tydligen i Icon. Koden behöver naturligtvis snyggas upp och eventuellt OOP-as.


Det är nu skoj att testa de regexar som finns t.ex. på Regular Expression Library eller Rx Cookbook. Ett exempel: På Regex Lib finns ett för validering av email:

(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})

De första strängarna (från en ohyggligt lång lista) som mitt system skapar är:

AA@AA.AA
AA@AA.AAA
AA@AA.BB
AA@AA.BBB
AA@AA.CC
AA@AA.CCC
AA@AA.DD
AA@AA.DDD
....

Icon-progammet har även en slump-mode som genererar sådant som:

Hw@qC.JJ
Hw@q___p.M
H_N@d.LL
Gy@DV.II
Gy@D___S.jj
GFFFL@CU.hh
....


Det finns åtminstone två problem med regexet ovan (och det behöver man egentligen inte ha avancerade program för att komma på):

(Härfinns ett Perl-program som bygger upp ett oerhört mer komplicerat regex för att kontrollera RFC-komplienta mailadresser. Det är möjligen något overkill.)


Om någon känner till något liknande strängskapande system givet ett regex, är denne välkommen att höra av sig, antingen i kommentaren på bloggen eller via mail.


Se även
Regexbibeln Mastering Regular Expressions, Second Edition, av Jeffrey Friedl, som har en companionwebbplats på http://regex.info.

Posted by hakank at april 28, 2004 09:56 EM Posted to Reguljära uttryck etc