Syntax highlighter - Regularni izrazi u JavaScript-u

Uvod

Posle izleta u oblast prepoznavanja komentara u programskom kodu, vratićemo se na highlighter i bavićemo se unapređenjem dela programa koji je namenjen interpretaciji jezika JavaScript ....

Sam jezik nudi vizuelno elegantan način za zapisivanje regularnih izraza bez korišćenja navodnika, preko tzv. "regex literals" sintakse, koja podrazumeva da se znak / koristi (kao 'graničnik'), na početku i na kraju regularnog izraza.

Međutim, sama mogućnost pojave takvog zapisa - osim što programski kod čini elegantnijim - takođe ponešto komplikuje parsere i skripte za označavanje sintaksnih elemenata.

		
let reg1 = /\/\/[\s\S]*?\n/;

Slika 1. - Primer regularnog izraza (u JavaScript-u), koji je zapisan preko 'regex literal' sintakse.

Pri prepoznavanju, osnovna ideja podrazumeva pravilno tumačenje znaka /, koji - u zavisnosti od konteksta - može predstavljati:

znak za operaciju deljenja (odnosno deo algebarskog izraza), ili ....
graničnik regularnog izraza

Kada se ustanovi kriterijum za prepoznavanje, ostatak algoritma dolazi 'sam od sebe' ....

Osnovna razmatranja

U sledećem bloku programskog koda ....

		
let e = a / (b + c) / d;
let f = /(b+c)/;

Slika 2. - Primer (relativno) sličnog zapisa algebarskih izraza i regularnih izraza (preko regex literal sintakse) u JavaScript-u.

.... primećujemo dva izraza sa (donekle) sličnim sadržajem znakova, međutim:

prvi niz znakova predstavlja uzastopno deljenje koje obuhvata tri (tj. ukupno četiri) operanda
drugi niz znakova predstavlja regularni izraz

Kada je u pitanju potraga za regularnim izrazima, možda bi čitaocima prvo mogao pasti na pamet algoritam koji bi po programskom kodu (doslovno) pretraživao obrasce po kojima se formiraju regularni izrazi - što svakako jeste veoma zanimljiv pristup, ali, verujemo da naslućujete (da ćemo vam reći), da je takav algoritam prilično kompleksan, to jest, 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 (i posredno - regularne izraze), u tom smislu da bi se smatralo da je regularni izraz "suprotnost algebarskog izraza" ("ako izraz nije algebarski izraz - onda je regex").

Nakon svega, može nam pasti na pamet (prilično 'legitimno'), da je regularni izraz uokviren 'zagradama' koje čine znakovi /, da takav izraz stoji samostalno posle naredbe dodele, i da je upravo po navedenim svojstvima moguće prepoznavati regularne izraze.

U pitanju je pomalo naivno rešenje u bukvalnom smislu (u sledećem odeljku detaljnije ćemo prodiskutovati o 'nivou naivnosti'), ali - budući da je pomenuti "naivni" algoritam idejno blizak pravom rešenju - razmotrićemo i takav pristup nešto detaljnije.

U svakom slučaju, da bi uopšte moglo da se započne sa prepoznavanjem regularnih izraza (bez obzira na algoritam koji se koristi), potrebno je prvo da svi tokeni koji stoje između naredbe dodele i znaka za prelazak u novi red, * budu izdvojeni u pomoćnu listu.

Posle provere, preko koje se utvrđuje da li sadržaj liste predstavlja regularni izraz (ili algebarski izraz; ili naredbu opšteg tipa), u glavnu listu tokena biće vraćen jedan od sledeća dva 'paketa' tokena:

jedan token - koji predstavlja (prepoznati) regularni izraz
više tokena - koji predstavljaju algebarski izraz (ili naredbu dodele opšteg tipa)

U nastavku ćemo sagledati šta nije u redu sa naivnim algoritmom, pa - kada budemo saznali gde 'stvari zapinju' - lako ćemo otkloniti tehničke nedostatke (bar u ovom slučaju; najčešće nije "baš lako" :)), pri čemu smo situaciju sagledali sa više strana, a ne samo sa jedne strane.

Naivno (i neadekvatno) rešenje za proveru izraza

Kao što već znamo, termin naivno rešenje (sa kojim se srećemo u teoriji programiranja), predstavlja postupak koji je (tipično): očigledan, jednostavan za razumevanje - ali i neefikasan, međutim, podrazumeva se da navedeni postupak (ipak) dovodi do očekivanog rezultata.

Tako je inače, ali, za postupak koji smo predložili u prethodnom odeljku može se reći da je "naivan" i u svakodnevnom značenju navedene odrednice: algoritam "deluje kao dobra ideja", ali, nedostaci se mogu primetiti sasvim lako - čim algoritam počne da analizira iole kompleksnije programske kodove.

Sam 'naivni' postupak za obradu liste tokena koji se nalaze između operatora dodele = i operatora ; (ili prelaska u novi red), ima sledeće odlike:

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 u slučaju velikog broja regularnih izraza sa kojima se tipično susrećemo, ali, počnimo da se obaziremo na sintaksne elemente koji mogu 'zbuniti' predloženi naivni "algoritam" ....

Pre svega, iznećemo jednu empirijsku pretpostavku: u većini slučajeva, regularni izrazi se (ipak) ne završavaju znakom /, već se na kraju tipično nalazi modifikator g (a često se javljaju i modifikatori i ili m) ....

		
let a = /b+c/g; // pri pretrazi, traže se
                // sva poklapanja, a ne
                // samo prvo poklapanje
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

Slika 3. - Modifikatori "g", "i" i "m", koji menjaju podrazumevano ponašanje regularnih izraza.

Naravno, često se pojavljuju i kombinacije navedenih modifikatora:

		
let a = /b+c/g;
let a = /b+c/gi;
let a = /b+c/gm;

Slika 4. - Primeri kombinacija modifikatora za regularne izraze.

Moguća pojava modifikatora na kraju regularnih izraza, ne predstavlja preveliki problem (pri proveri kraja liste, mogli bi se samo zanemarivati znakovi g, i i m), ali - postoji i mnogo lakši način da predloženi algoritam bude "prevaren" (nismo dugo čekali da vidimo gde stvari zaista zapinju):

		
let a = /* /[a-f0-9]+/ */  /[a-f0-9]*/; // Da li treba da bude greedy?

Slika 5. - Primer regularnog izraza koji je u stanju da 'prevari' prethodno predloženi 'naivni' algoritam.

Preko gornjeg primera moguće je uvideti da predloženi postupak ne daje očekivane rezultate (i još je važnije uvideti da bi dalji pokušaji da se "dotera" algoritam koji "prečišćava" tokene na početku i na kraju liste (sve dok ne naiđe na token /) - samo doveli do nepotrebnih komplikacija).

Da budemo precizni, u prethodnom primeru problem nisu znakovi / unutar komentara (jer, s obzirom na to da glavni algoritam syntax highlighter-a vodi računa o kontekstu čitanja, navedeni znakovi će biti prepoznati kao delovi tokena koji predstavljaju granice komentara).

Problem je u tome što prvi token u naredbi dodele nije znak / - i to je nešto zbog čega bi "naivni algoritam za prepoznavanje regex-a" bio naveden na odustajanje od dalje potrage za regularnim izrazom među izdvojenim tokenima.

O(n) algoritam za prepoznavanje regularnih izraza

Nakon 'stranputica', vreme je da pokušamo da iznađemo efikasniji postupak, koji (shodno naslovu odeljka), u jednom prolasku kroz listu tokena prepoznaje regularne izraze.

Moglo bi delovati da je algoritam za utvrđivanje razlike između tokena / koji označava operaciju deljenja i tokena / koji označava početak regularnog izraza - još komplikovaniji (od prethodnog naivnog rešenja), međutim - to srećom nije slučaj.

Pažljivijim sagledavanjem različitih izraza sa kojima se srećemo, mogu se primetiti sledeće odlike:

operaciji deljenja tipično prethoditi operand
regularnom izrazu tipično prethodi operator

Navedena pravila možemo odmah videti i u primerima.

U sledećem algebarskom izrazu ....

		
let a = b / c / d;

Slika 6. - Primer u kome token "/" predstavlja algebarski operator deljenja.

.... prvi token / - kao operator deljenja - pojavljuje se posle operanda b, a drugi - posle operanda c (možemo reći i da se operatori deljenja, kako u prikazanom primeru tako i inače, pojavljuju između operanada).

Za razliku od prethodnog slučaja, u sledećem regularnom izrazu ....

		
let r = /(b+c)/;

Slika 7. - Primer u kome token "/" predstavlja početak ili kraj regularnog izraza.

.... token / - kao delimiter - pojavljuje se posle tokena koji predstavlja operator (naredbu dodele).

Međutim, rekli smo da se znak deljenja "tipično" pojavljuje nakon operanda (što znači "ne uvek"), pa tako postoji i situacija u kojoj se token / pojavljuje posle operatora, ali, tako da u konkretnom kontekstu - takođe označava operaciju deljenja.

Naravno, mislimo na pojavu tokena / posle zatvorene zagrade, bilo da su u pitanju algebarski izrazi ....

		
let c = (12 + 8) / a;

Slika 8. - Primer algebarskog izraza koji (naizgled) predstavlja odstupanje od pravila koje je vezano za redosled tokena.

.... ili pozivi funkcija ....

		
let c = sabiranje(12, 8) / a

Slika 9. - Primer naredbe, koja sadrži poziv funkcije, i (takođe) naizgled predstavlja odstupanje od pravila koje je vezano za redosled tokena.

Praktično: pojava zagrade koja uokviruje algebarski izraz: (12 + 8), svodi se na token koji u idejnom smislu predstavlja operand (vrednost 20), a isti je slučaj i sa pozivanjem funkcija (na primer: sabiranje(12, 8)), u kom slučaju se identifikator funkcije i sadržaj zagrada svode (pre deljenja), na rezultat 20.

Tumačenjem nizova tokena koji predstavljaju pozive funkcija, bavićemo se detaljnije u narednom članku, a kao primer izraza koji ne predstavlja regularni izraz, koristićemo (u ovom članku, u nastavku), upravo izraz koji sadrži poziv funkcije.

Kada se svemu doda potencijalna pojava komentara i niski - postaje jasno da se mora voditi računa o kontekstu pri čitanju programskog koda (baš kao i u prethodnom članku kada smo iz programskog koda uklanjali komentare).

Na primer, regularni izraz koji se pojavljuje između otvarajućeg i zatvarajućeg tokena blok komentara ....

		
/*
	/([\s\w]+?)/
*/

Slika 10. - Primer regularnog izraza koji je 'utisnut' u komentar.

.... mora biti prepoznat kao deo komentara (a ne kao samostalan regularni izraz), baš kao što i regularni izraz koji se pojavi posle znaka navoda, mora biti prepoznat kao deo niske ....

		
let s = "Regularni izrazi, kao što je \"/([\s\w]+?)/\" - su super!";

Slika 11. - Primer regularnog izraza koji je 'utisnut' u nisku.

Sada možemo ustanoviti pravila po kojima ćemo interpretirati izraze.

Pravila za tumačenje izraza

Budući da interpretacija trenutno posmatranog tokena zavisi od konteksta u kome se token pojavljuje, potrebno je pre svega da kontekst bude pravilno prepoznat i zabeležen.

Kada je u pitanju beleženje konteksta, najpraktičnije je (kao i do sada), koristiti pomoćni stek, a kada je u pitanju prepoznavanje konteksta, potrebno je voditi računa o pojavi sledećih tokena, koji (pod određenim okolnostima), mogu promeniti kontekst tumačenja koda, odnosno, mogu uvesti interpretator u određeni ('novi') 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 interpretator 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 / može označiti:
- 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)
smisao 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 sagledali što bolje, razmotrićemo dva primera.

Primer 1: tumačenje algebarskog izraza

U prvom izrazu koristićemo nešto složeniji algebarski izraz koji sadrži i komentare (i poziv funkcije).

		
let rez = /* novi kod */ f_01(a, b) / 12;

Slika 12. - Primer 1. - Algebarski izraz koji sadrži i dodatne komentare.

Budući da je broj slika 'poveći', 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 prikazanom, 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

Slika 13. - Primer 2. - Regularni izraz koji sadrži i komentare.

I ovoga puta, ostavljamo vam da sami "premotavate" slike.

		Lista tokena koju smo izdvojili na početku

Ideje za dalja unapređenja highlightera

Pored svih ideja koje smo pominjali (i razrađivali), ostaje da se osvrnemo na jednu ideju koja je pomenuta samo okvirno: prepoznavanje jezika unutar jezika.

U svemu mislimo (pre svega) na praktične primere iz svakodnevne prakse: prepoznavanje CSS i JS blokova u HTML-u (unutar tagova <style> i <script>) i, takođe, na 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.

U sledećem članku bavićemo se algoritmom za prepoznavanje algebarskih izraza (koji nije deo osnovnog algoritma za označavanje sintaksnih elemenata, ali, svakako je prilično zanimljiv sam po sebi).

Autor članka Nikola Vukićević Za web portal codeblog.rs

Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.