Syntax highlighter - 2. deo - Regularni izrazi u JavaScript-u

Uvod

Posle izleta u oblast prepoznavanja komentara u programskom kodu, vraćamo se na highlighter i bavimo 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 (odnosno, 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) 'jurio' 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, da 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; više o 'nivou naivnosti' u sledećem odeljku), ali - budući da je takav "naivni" algoritam idejno blizak pravom rešenju - prodiskutovaćemo o celom pristupu 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 listu 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 (takođe) 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 algoritam 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.

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.

Moglo bi delovati da je algoritam za utvrđivanje razlike između znaka / koji označava operaciju deljenja i znaka / 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, u prikazanom primeru, operatori deljenja 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 operatora (tj. naredbe) dodele.

Međutim, rekli smo "tipično", 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 za 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 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!";

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, 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, takođe - kao što smo najavili - 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 (mada, biće potreban izvestan trud da se sav kod organizuje kako dolikuje).

U sledećem članku bavićemo se algoritmom za prepoznavanje algebarskih izraza (koji nije deo algoritma za označavanje sintaksnih elemenata, ali, svakako je vrlo 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.