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

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/;

Slika 1. - Primer regularnog izraza u Javascript-u zapisanog preko 'regex literal' sintakse.

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)/;

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

.... 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.

Bez obzira na sve navedeno, pre nego što smo usvojili algoritam koji prikazujemo u članku, kao 'zvanično' rešenje koje ćemo koristiti za skriptu na sajtu, proveli smo neko vreme razrađujući skriptu koja se zasniva na algoritmu za prepoznavanje algebarskih izraza (i naredbi dodele opšteg tipa, kakve se recimo sreću pri inicijalizaciji objekata).

Takva algoritam nije baš praktičan za korišćenje (u određenom trenutku, implementacija je postala ipak malo preobimna za skromene potrebe syntax highlightera, pogotovo s obzirom na to da tumačenje i prevođenje koda nije obavezni deo skripte za označavanje sintasknih elemenata), međutim, algoritam za prepoznavanje algebarskih izraza je (sam po sebi) lep, zanimljiv i vredan pažnje (pri tom je zapravo i prilično jednostavan), pa ćemo mu uskoro posvetiti zaseban članak.

Ali, da se ipak vratimo na algoritma koji je glavna tema članka ....

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

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

.... ili kombinacijama navedenih modifikatora ....

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

Slika 4. - Primeri kombinacija za regularne izraze.

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?

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

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;

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 (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)/;

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

.... 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]+?)/
*/

Slika 8. - Primer u kome je regularni izraz 'utopljen' 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 9. - Primer u kome je regularni izraz 'utopljen' u nisku.

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;

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

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

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

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).