Uvod
Jedna od zanimljivosti jezika JavaScript je način zapisivanja regularnih izraza bez korišćenja navodnika (regex literals), pri čemu se koriste znakovi /, na početku i kraju regularnog izraza, što ponešto komplikuje parsere, odnosno, skripte za označavanje sintaksnih elemenata, koji treba da pravilno protumače takav kod.
let reg1 = /\/\/[\s\S]*?\n/;
Pri prepoznavanju, osnovna ideja je (naravno) da se znak / pravilno protumači kao deo algebarskog izraza, ili kao graničnik regularnog izraza - u zavisnosti od konteksta.
Kada ustanovimo kriterijum po kome će se prepoznavanje obaviti, ostatak implementacije 'dolazi sam od sebe' ....
Osnovna razmatranja
Ako pogledamo sledeći kod ....
let e = a / (b + c) / d;
let e = /(b+c)/;
.... (osim što primećujemo da algoritam funkcioniše, što dalje navodi na zaključak da ne čitate ovaj članak za džabe), primetićemo dva slična izraza: prvi predstavlja uzastopno deljenje koje obuhvata tri operanda, a drugi regularni izraz.
Kada je u pitanju potraga za regularnim izrazima, možda bi našim čitaocima prvo mogao pasti na pamet algoritam koji bi po kodu (doslovno) 'jurimo' obrasce po kojima se formiraju regularni izrazi - što svakako jeste zanimljiv postupak, ali, verujemo da naslućujete da (ćemo vam reći da) takav pristup nije u prevelikom skladu sa brzim izvršavanjem skripte - što je jedan od prioriteta syntax highlightera (da budemo iskreni, nije ni u prevelikom neskladu).
Slično važi i za algoritam koji bi prepoznavao algebarske izraze i naredbe dodele opšteg tipa, pri čemu bismo smatrali da je regularni izraz "suprotnost" algebarskog izraza ili naredbe dodle ("ako izraz ne spada u jednu od dve pomenute kategorije - onda je regex"), kao što smo na početku već pominjali.
Posle toga, može nam pasti na pamet (krajnje legitimno), da je regularni izraz uokviren 'zagradama' koje čine znakovi / i da stoji samostalno posle naredbe dodele - i da ga upravo to ono po čemu možemo prepoznavati regularne izraze.
U svakom slučaju (da bismo išta mogli da radimo), prvi korak je da sve tokene koji stoje između naredbe dodele i znaka za prelazak u novi red (za Javascript, koji vrlo 'liberalno' dozvoljava da se naredbe ne terminišu operatorom ";", ovo je, ne samo praktično, već i krajnje neophodno), izdvojimo u pomoćnu listu, proverimo da li sadržaj liste predstavlja regularni izraz (ili algebarski izraz) i na kraju u glavnu listu tokena vratimo:
- jedan token - koji predstavlja (prepoznati) regularni izraz
- više tokena - koji predstavljaju algebarski izraz (ili naredbu dodle opšteg tipa)
Pošto smo zadovoljili (naj)osnovn(ij)e tehničke preduslove, prvo ćemo se pozabaviti predloženim ('naivnim') algoritmom u kome pretpostavljamo (praktično) da je regularni izraz oivičen tokenima / i da se nalazi između tokena = i ;.
Time ćemo postići dve stvari: pristup u kome prvo razmatramo prirodne ('zdravorazumske') ideje koje imaju određene tehničke nedostatke, bolji je (za pojedince koji uče programiranje) od pristupa u kome se odmah, nekritički prihvata optimalno rešenje.
Kada saznamo gde algoritam 'zapinje', lako ćemo (bar u ovom slučaju; inače zna i da ne bude baš lako) otkloniti tehničke nedostatke.
Naivno (i neadekvatno) rešenje za proveru izraza
U teoriji programiranja, termin "naivno rešenje", predstavlja postupak koji je (tipično) očigledan, jednostavan za razumevanje, ali i neefikasan. Međutim, podrazumeva se da takav postupak (ipak) dovodi do željenog rezultata (ako ne u smislu brzine izvršavanja i efikasnosti, makar u smislu dobijanja očekivanog rezultata).
Za sledeći postupak, možemo reći da je "naivan" u svakodnevnom značenju tog pojma, u smislu da deluje kao dobra ideja, ali da ćemo nedostatke primetiti lako (čim počnemo da uzimamo u obzir sve ono što (namerno) nismo odmah uzeli u obzir).
Sam 'naivni' postupak za listu tokena koja slede posle operatora dodele = i operatora ;, izgleda ovako:
- prvi token u listi (ne računajući white space tokene,
" "i"\t"), mora biti znak"/" - poslednji token u listi (pre operatora ";" i eventualne pojave white space tokena), takođe mora biti
"/" - ako su oba uslova zadovoljena, izraz predstavlja regularni izraz
Navedeni mehanizam provere je (zapravo) adekvatan za veliki broj regularnih izraza sa kojima bismo se tipično susretali, ali, počnimo sa uvođenjem u obzir svih okolnosti koje smo prethodno 'preskočili'.
Pre svega, iznećemo empirijsku pretpostavku da se regularni izrazi, u većini slučajeva, najčešće ne završavaju znakom "/", već modifikatorom "g" (a pored toga i "i" ili "m") ....
let a = /b+c/g; // pri pretrazi, traže se sva poklapanja, a ne samo prvo
let a = /b+c/i; // zanemaruju se razlike između velikih i malih slova
let a = /b+c/m; // traže se poklapanja u više redova
.... ili kombinacijama navedenih modifikatora ....
let a = /b+c/g;
let a = /b+c/gi;
let a = /b+c/gm;
Ni to ne bi bio preveliki problem (pri proveri kraja liste, jednostavno bismo zanemarivali znakove g, i i m), ali, postoji i mnogo lakši način da "prevarimo" predloženi algoritam (nismo dugo čekali da vidimo gde stvari zaista zapinju):
let a = /* /[a-f0-9]+? */ /[a-f0-9]+/; // Da li treba da bude greedy?
Ovde već uviđamo da predloženi postupak ne daje rezultate i da bi dalji pokušaji da "doteramo" algoritam koji "prečišćava" tokene na početku i kraju listu, sve dok ne naiđe na token /, samo doveli do nepotrebnih komplikacija.
Sada je već vreme da se osvrnemo na efikasniji postupak.
O(n) algoritam za prepoznavanje regularnih izraza
Shodno naslovu ovog odeljka, jasno je da tražimo postupak koji u jednom prolasku kroz listu tokena, prepoznaje regularne izraze, a videli smo da se algoritam koji smo pretodno razmotrili (pristup koji na samom početku deluje "skroz jednostavno"), vrlo lako zakomplikovao čim smo počeli da uzimamo u obzir dodatne tokene koji se (i te kako) mogu pojaviti u izrazima.
Može onda delovati da je algoritam za utvrđivanje razlike između znaka "/" koji označava operaciju deljenja, od znaka "/" koji označava početak regularnog izraza -
još komplikovaniji, međutim, to srećom nije slučaj.
Ako malo pažljivije pogledamo izraze, primetićemo sledeće:
- operaciji deljenja prethoditi operand
- regularnom izrazu prethodi operator
Navedena pravila možemo odmah videti i u primerima.
U sledećem algebarskom izrazu ....
let a = b / c / d;
.... prvi token /, kao operator deljenja, pojavljuje se posle operanda b, a drugi, posle operanda c (u ovom slučaju, možeo reći i da se operatori deljenja pojavljuju između operanada), dok se u sledećem regularnom izrazu ....
let r = /(b+c)/;
.... token "/", kao delimiter, pojavljuje posle operatora (naredbe dodele).
Ako svemu dodamo pojavu komentara i niski (već smo videli jedan od načina kako komentari mogu da nas spreče u nameri da za rešenje koristimo naivne postupke), postaje jasno da će rešenje, baš kao i u prethodnom članku (kada smo iz programskog koda uklanjali komentare), biti potebno da vodimo računa o kontekstu čitanja koda.
Za sve ćemo koristiti stek, preko koga ćemo beležiti kontekst u kome se tokeni pojavljuju.
Na primer, regularni izraz koji se pojavjluje između otvarajućeg i zatvarajućeg tokena blok komentara ....
/*
/([\s\w]+?)/
*/
.... mora biti deo komentara (a ne samostalan regularni izraz), baš kao što i regularni izraz koji se pojavi posle znaka navoda, mora biti deo niske ....
let s = "Regularni izrazi, kao što je \"/([\s\w]+?)/\" - su super!";
Sada možemo ustanoviti pravila po kojima ćemo interpretirati izraze.
Pavila za tumačenje izraza
- interpretacija tokena zavisi od režima interepretatora, pri čemu samo određeni tokeni mogu promeniti režim
- pojava tokena
"/*"u osnovnom režimu, uvodi interpretator izraza u režim spajanja tokena, u kome će svi naredni tokeni do pojave tokena"*/"(koji vraća interpretator u osnovni režim), biti spojeni u jedan token i prikazani kao komentar - pojava tokena
"//"u osnovnom režimu, uvodi interpretator u režim spajanja u kome će preostali tokeni u listi*, sve do pojave tokena"\n"(koji vraća interpretator u osnovni režim), biti spojeni u jedan token i prikazani kao komentar - pojava tokena
"\"","\'", ili"\`", uvodi interepretor u režim spajanja tokena, u kome će svi tokeni (do pojave sledećeg odgovarajućeg delimitera za nisku), biti spojeni u jedan token i prikazani kao niska - pojava tokena
"/"značiće uvod u režim za spajanje tokena u regularni izraz (sve do pojave sledećeg tokena"/"), ili - pojavu operatora deljenja - u zavisnosti od prethodnog tokena koji nije bio white space znak (" "ili"\t") - pojava ostalih tokena zavisi od režima
- ako je interpretator u režimu spajanja (komentar, niska, regularni izraz), token opšteg tipa * biće spojen sa ostatkom grupnog tokena (komentara, niske, regularnog izraza)
- ako je interpretator u osnovnom režimu, token će biti prebačen u listu samostalno
Da bismo sve navedeno bolje sagledali, pogledajmo dva primera.
Primer 1: tumačenje algebarskog izraza
U prvom izrazu koristićemo nešto složeniji algebarski izraz koji sadrži i komentare.
let rez = /* novi kod */ f_01(a, b) + 12;
Budući da slika ima puno, formatirali smo prikaz u vidu interaktivnog polja sa objašnjenjima koja su utisnuta u slike.
Lista tokena koju smo izdvojili na početku
U svemu vidimo da nije teško "ubediti" program da pravilno prepozna semantički različite delove koda.
Primer 2: tumačenje regularnog izraza
U drugom primeru, razmotrićemo jednostavan regularni izraz.
let regex = /\d+/; // komentar
I ovoga puta, ostavljamo čitaocima da sami "premotavaju" slike.
Lista tokena koju smo izdvojili na početku
Kao i do sada, detaljnu implementaciju ostavljamo čitaocima.
Ideje za dalja unapređenja highlightera
Posle svih ideja koje smo spominjali (pri čemu smo mnoge detaljno razrađivali), ostaje da se osvrnemo na jednu koja je spomenuta samo okvirno: prepoznavanje jezika unutar jezika.
U svemu mislimo na prepoznavanje CSS i JS blokova u HTML-u (unutar style i script tagova), kao i razvrstavanje HTML i PHP blokova unutar PHP datoteka.
Implementacija nije ni iz daleka trivijalna, ali, ukoliko ste uspostavili mehanizam prepoznavanja specijalnih tokena i komentara na osnovu konteksta, neće biti previše teško da uvedete parser u režim prepoznavanja drugog jezika (ali, biće potreban izvestan trud da se sav kod organizuje kako dolikuje).
U sledećem članku, pozabavimo će se algoritmom za prepoznavanje algebarskih izraza (koji nije deo algoritma za označavanje sintaksnih elemenata, ali svakako zavređuje pažnju sam po sebi).