nav_dugme codeBlog codeBlog
  • početna Početna stranica
  • Sačuvani članci Sačuvani članci
  • Učionica
  • Saveti
  • Zanimljivosti
  • Kontakt

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

Viber
zoom_plus zoom_minus bookmark

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.

Primećujemo i da algoritam koji ćemo kasnije opisati funkcioniše, što dalje navodi na zaključak da ne čitate ovaj članak uzalud. :)

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.

Mada, da budemo iskreni, nije ni u prevelikom neskladu, pa ako imate vremena :) ....

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.

Zato i jesmo rekli da je ovakav algoritam "naivan" u bukvalnom smislu - stvarno ga nije teško zbuniti. :)

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

Ponašanje JS endžina u situacijama kada umetnemo operator (recimo "+") između dva regularna izraza, predstavlja svojevrsnu "sivu zonu".

Takve naredbe svakako treba izbegavati, ali, pošto syntax highlighter treba i na takve pojave da odreaguje "nekako", kalibrisaćemo ga tako da se ponaša onako kako se tipično ponašaju parseri u drugim editorima, a to je - upravo shodno pravilima koja smo već naveli: ako se pre tokena "/" nađe operator, token će biti protumačen kao "regex zagrada", dok će u suprotnom biti protumačen kao operator deljenja.

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.

U postupku koji opisujemo, pretpostavka je da operišemo nad listom tokena koja je podeljena po pravilima koje smo naveli u prvom članku o dizajnu syntax highlightera, tako da se, kao zasebni tokeni, izdvajaju operatori, white space znakovi, kao i (što je za nas u ovom trenutku bitnije): /*, */, //, \", \', \`.

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

* Navedeno se zapravo odnosi i na tokene koji u osnovnom kontekstu imaju specijalno značenje, ali u drugom kontekstu nemaju (ili, još opštije, na sve tokene osim tokena koji čitač vraća u osnovno stanje).

Primera radi, ako token \" uvede čitač u režim spajanja tokena u nisku, pojava tokena /*, koji inače označava početak komentara, neće imati posebno značenje, a jedini specijalni token u datom kontekstu je token \", koji označava kraj niske.

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.

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

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

Autor članka Nikola Vukićević Za web portal www.codeblog.rs
Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu www.codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.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.
© 2020-2023. Sva prava zadržana.
Viber
početna Početna > Članci > Syntax highlighter - 2. deo - Regularni izrazi u Javascript-u

Info & povezani članci Info o članku - dugme

Info

trejler_sat Datum objave: 21.09.2021.

trejler_sat Poslednja izmena: ----

trejler_dokument Jezici: Javascript

trejler_teg_narandzasti Težina: 7/10

Povezani članci

Šablonske niske u programskim jezicima ASCII, UNICODE i UTF-8 - Predstavljanje znakova na računarima Operacije sa nizovima u programskom jeziku JavaScript JSON - tekstualni format za predstavljanje objekata Uvod u Node.js Callback funkcije i lambda izrazi Uvod u web dizajn - 7. deo - Podešavanja editora i efikasna obrada teksta Uvod u Javascript i DOM (Document Object Model) JSON Web Token (JWT) - Struktura i primena u oblasti autorizacije web aplikacija Ostali članci
In programming,the hard part isn't solving problems, but deciding what problems to solve.
Paul Graham
codeBlog codeBlog
Projekat posvećen popularizaciji kulture i veštine programiranja.
Napomena: Tekstovi i slike na sajtu www.codeblog.rs (osim u slučajevima, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.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 odobrenja autora.
© 2020-2023. Sva prava zadržana.
Facebook - logo
Instagram - logo
LinkedIn - logo
Twitter - logo
E-mail
Naslovna
   •
Uslovi korišćenja
   •
Obaveštenja
   •
FAQ
   •
Kontakt