2. uždavinukai Codeforces, Codeeval
3. Gramatikos "konvertavimas" į regex
Liepos pradžioje teko toliau pasiskaitinėti ko nors apie Perl'ą, ir tai buvo keli skyriai iš knygos: "Perl Best Practices" (Damian Conway), koks vienas skyrius iš "Intermediate Perl", ir pradžia knygos "Higher Order Perl" (M.J.Dominus).
"Perl Best Practices" knygos pradžioje rašo apie kodo parašymo stilių jo skaitomumą. Vėliau apžvelgia įvairias užduotis, su kuriomis susiduriama, ir pasiūlo jiems sprendimą ir parekomenduoja modulių, kuriuos geriausia naudoti. Tad knygos pirmoji pusė - patiko.
Patiko "Higher Order Perl" pradžia. Joje siūlomi standartinių uždavinių sprendimas naudojant rekursiją. O taip pat palaipsniui rekomenduojama išabsrahuoti programą, t.y. padaryti jį kuo labiau "generic".
Taip pat atradau asmeninį M.J.Dominus puslapį, ir iš ten tokį pdf'ą su skaidrėmis apie reguliariųjų išraiškų veikimą. Labai geras pdf'as, gerai aiškinantis veikimo mechanizmą ir backtrackingą. Rekomenduoju.
Neseniai viena programa, kurioje naudojau regex, nustojo teisingai veikti, paleidus ją ant naujesnės Perl versijos (5.20, vietoj 5.18). Paklausinėjus Perl'o išminčių forume, jie išsiaiškino, kad tai bug'as. Jį įkėlė į bugų lentyną. Bug'as tame, kad atsirado klaidingas warningo pranešimas ir pradėjo teisingai nebeveikti konstrukcija "{n}+", kitaip tariant - kvantifikatorius su pliusiuku ( pliusiukas reiškia, kad kvanfitikatorius tampa "possessive", t.y. nebebacktrackinantis). Naujesnėje versijoje, matyt, klaidingai buvo nuspręsta, kad toks užrašas neturi prasmės, kada "n" yra konkretus skaičius. Tačiau iš tiesų jis prasmę turi, pvz. tada, kada kvantifikuojamas dalykas pats turi intervalinį kvantifikatorių, pvz. "(a+){n}+".
2. Prisiregistravau į Codeeval puslapį (parekomendavo draugas), tenai radau tris kategorijas uždavinukų: lengvi, vidutiniai, sunkesni. Pasprendžiau lengvesniųjų. Kiekvienam užtrukdamas 6-30 minucių, išsprendžiau 60. Kelių lengvų neišsprendžiau. Daugumą stengiausi spręsti "funkciškais makaronais", t.y. naudojant map, split, join, grep, eval...
Pvz. uždavinuko 'working experience' sprendimas:
Codeforces rengiamuose kontestuose nelabai sekėsi. Kai kuriuos uždavinius netgi buvau neteisingai išsprendęs. Didesnė dalis tokių klaidų įvyko dėl to, kad iki galo neįsiskaitydavau į sąlygas, ir implementuodavau ne viską, ko prašydavo. Dėl to būdavo sunku patikėti, kai pamatydavau, kad sprendimas "krito". Kitų dalyvių programas irgi nesisekė laužti. Arba nesugalvodavau surasti silpnųjų vietų, arba pradėdavau spręsti ne tą uždavinį, kuriame dauguma klysta, ir kiti kambario "hakeriai" sumedžiodavo klaidingus sprendimus. Visus uždavinius sprendžiu Perlu. Na, bet stengiuosi "elegantiškiau", jeigu tik išeina.
3. Visai neseniai teko skaityti failą, kuriame buvo aprašyta gramatika EBNF forma. Galiausiai šia gramatika buvo aprašytas tam tikros struktūros pranešimas. T.y. turint pranešimą, galima patikrinti, ar jis gramatiškai teisingas (atitinka konkrečią gramatiką). Atsirado mintis, kad galima patikrinti, ar pranešimas atitinka gramatiką, sukonstravus reguliariąją išraišką. Ilgesnį laiką pažiūrėjus į gramatiką, kuri sudaryta iš >15 taisyklių (vienos pvz.: zodis = raide, {raide | pabraukimas}), atėjo dar kita mintis: pamėginti parašyti programą (parserį?), kuri skaitytų gramatikos failą, ir iš jo dalių surinktų reguliariąją išraišką. Tuomet pasikeitus gramatikai ir praleidus šią programą, reguliari išraiška atsinaujintų programiškai, o ne rankomis.
Ant šios užduoties pakibau kelias dienas. Ir susidūriau su tokia vieta, kaip kad sakinys (taisyklė): kabute = '"' | "'". Ir supratau, kad negaliu pamodifikavęs šią taisyklę, perduoti jos kintamajame į kažkur, kur ji būtų interpoliuojama, nes jeigu stringo, į kurį interpoliuoju taisyklę, delimiteriai yra viena iš kabučių rūšis, tai įvyks sintaksės klaida. O jeigu naudosiu kitokius Perlo delimiterius su operatoriais q ar qq, tai susidursiu su bėda, apdorodamas kitas taisykles, kuriose aprašyti simboliai, tapatūs šiems delimiteriams.
Dar ilgą laiką negalėjau išspręsti vieno warningo ir loginės klaidos, tai - naudojant \Q...\E metacharacter escape sequence, jie nesiinterpoliavo, kaip tikėjausi. O interpoliavosi tiesiog kaip didžiosios raidės. Kada atsisakiau \Q...\E ir pakeičiau į quotemeta, situacija pagerėjo, ir generuojamas regex'as pasidarė gerokai trumpesnis.
Iš tiesų gavosi "žaidybinis" reguliariosios išraiškos generavimas, kur ji generuojama atsižvelgiant į šios gramatikos taisyklių rinkinį, o ne į bet kokią EBNF gramatiką apskritai. Ir dar "žaidybinė" ji todėl, kad iš gramatikos failo, konstruojant regex'ą, išmetami pradžioje komentarai, po to įterpiamos atominės grupės su kvantifikatoriais vietoje EBNF konstrukcijų ( [], {} ), tik po to escapinami metacharacter'iai, ir tik galiausiai apdorojamos specialios išraiškos ? ... ? . O visa, tai, ką išvardinau, neatitinka operatorių veikimo (ir parsinimo) eiliškumo pagal EBNF taisykles. Taigi, programa, kuri generuoja reguliariąją išraišką galbūt ir atitiks aprašytąją gramatiką, tačiau kažkiek gramatiką pakeitus, jau ir nebeatitiks. T.y. programa yra pritempta.
Priedo uždėjau apsiribojimus:
* kad programa apdoroja tik tokią gramatiką, kurioje tarp kabučių yra įrašyti tik po 1 simbolį.
* kad gramatikoje kiekviena taisyklė gali būti aprašyta tik po jos sekančiomis taisyklėmis.
Struktūra tokia:
ebnf - [Skaito gramatikos failą ir ją "parsina", rezultatas į -> generated];
generated - [Gramatikos taisyklės regex kalba, Perl kodu; +generuoja out-re regex'ą];
out-re - [Sugeneruota (su interpoliacija) regex, atitinkanti dominančią taisyklę (konkrečiai - pranešimo taisyklę)];
test - [Perskaito out-re regex'ą ir skaitydama testinius failus (su pranešimais), atsako, ar jie atitinka gramatiką]
Pvz. ebnf:
1) iškerpa gramatiką
2) iškerpa komentarus (aišku gautųsi bugas, jeigu komentaras tarp kabučių, o visgi kabutės yra auktesnio eiliškumo)
$input =~ s/ \(\* .*? \*\) //gxms;
3) suskaldo į atskirus sakinius-taisykles (skelia per kabliataškį, kuris nėra tarp kabučių)
my @rules = reverse split /; (?!['"])/x, $input;
4) taisyklėse įkeliami '$' prieš kiekvieną žodį (\w+), šalia kurio nėra skliaustelio, nėra jis \p{} išraišks dalis, ar escapintas metachar'as.
s/(?<!['"]) (?<!\\) (?<!\\p{) (\b\w+\b) (?!['"])/'$'.$1/xegms;
5, 6) [] ir {}, kurie gali būti nestinti, O(N**2) lėtumu keičiami į atitinkamus kvantifikatorius su possesyvumu, kadangi EBNF nebacktrakina.
1 while s/ (?<!['"]) \[ (?!\^) ( [^\[\]]* ) \] (?!['"]) /"(?:" . $1 . ")?+"/xegms;
7, 8) escapinami skyrybos ženklai nuo specialaus veikimo
s/'([^'])'/quotemeta "$1"/xegms;
9) ...dar kreivas žaidimas su klaustukais ? ... ?, ir dar kart "quotemeta" ant dešiniosios regex'o pusės, ir taisyklę paverčiant į sakinį pavidalu: "my \$1 = {čia quotemet'intas regex'as tik be escap'intų dolerių ir atominėje grupėje};"
Komentarų nėra:
Rašyti komentarą