Uvod
Jedna od zanimljivosti jezika Javascript je način zapisivanja regularnih izraza bez korišćenja navodnika, preko tzv. "regex literals" sintakse koja podrazumeva da se znak /
koristi na početku i na kraju regularnog izraza.
Međutim, sama mogućnost pojave takvog zapisa (koji svakako jeste elegantan sam po sebi), ponešto komplikuje parsere i skripte za označavanje sintaksnih elemenata.
let reg1 = /\/\/[\s\S]*?\n/;
Pri prepoznavanju, osnovna ideja je (naravno), da se znak /
pravilno protumači kao:
- deo algebarskog izraza (znak za operaciju deljenja)
- 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 blok koda ....
let e = a / (b + c) / d;
let f = /(b+c)/;
.... primetićemo dva (donekle/naizgled) slična izraza: prvi predstavlja uzastopno deljenje koje obuhvata tri (odnosno, ukupno četiri) operanda, a drugi predstavlja regularni izraz.
Kada je u pitanju potraga za regularnim izrazima, možda bi čitaocima prvo mogao pasti na pamet algoritam koji bi po kodu (doslovno) 'jurio' obrasce po kojima se formiraju regularni izrazi - što svakako jeste veoma 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.
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 dodele ("ako izraz ne spada u jednu od dve pomenute kategorije - onda je regex"), kao što smo na početku već pominjali.
Nakon svega, 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 je upravo to ono po čemu možemo prepoznavati regularne izraze.
Ovo je pomalo naivno rešenje, ali sadrži mnoge elemente pravog rešenja, pa ćemo o ovom pristupu malo više prodiskutovati.
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 dodele opšteg tipa)
Usput ćemo naravno sagledati i šta nije u redu sa predloženom idejom, pa kada budemo saznali gde algoritam 'zapinje', lako ćemo otkloniti tehničke nedostatke (bar u ovom slučaju; inače zna i da ne bude "baš lako"), a pri tom smo situaciju sagledali sa više strana, a ne samo sa jedne.
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" i 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 ;
, ima sledeći tok:
- 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 (zaista nismo dugo čekali da vidimo gde stvari 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.
Da budemo precizni, u prethodnom primeru problem nisu znakovi /
unutar komentara, jer oni će (s obzirom na to da vodimo računa o kontekstu čitanja), biti prepoznati kao deo komentara, već je problem to što prvi token u naredbi dodele nije znak /
, a time bi naš "naivni" algoritam za prepoznavanje regex-a bio naveden na to da odustane od dalje potrage za regularnim izrazom među izdvojenim tokenima.
Sada je vreme da se osvrnemo na efikasniji postupak.
O(n) algoritam za prepoznavanje regularnih izraza
Shodno naslovu odeljka, jasno je da tražimo postupak koji u jednom prolasku kroz listu tokena, prepoznaje regularne izraze
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 sa kojima se srećemo, 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, 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.
Kontekst u kome se tokeni pojavljuju beležićemo preko steka.
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.
Pravila 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 (blok) 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 (linijski) 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 (različita) 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
Detaljnu implementaciju algoritma (kao i do sada) 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 (pre svega) na praktične primere iz svakodnavne prakse: prepoznavanje CSS i JS blokova u HTML-u (unutar style
i script
tagova), kao i razvrstavanje HTML i PHP blokova unutar PHP datoteka (naravno, nisu u pitanju jedine moguće kombinacije).
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).