Kako napraviti syntax highlighter

Uvod

Kada smo prošle godine pokretali sajt, bio nam je potreban 'syntax highlighter' za članke - skripta koja različite funkcionalne elemente programskih kodova označava različitim bojama, pri čemu smo (naravno) imali želju da odmah samostalno implementiramo takvu skriptu, međutim, u praktičnom smislu nije bilo dovoljno vremena za navedeni poduhvat, i stoga smo kao privremeno rešenje izabrali jedan od gotovih open-source highlighter-a.

U međuvremenu, počeli smo da koristimo highlighter iz "domaće radinosti" (živeo DIY! :)) i takođe smo usput poželeli da podelimo sa čitaocima određene ideje koje se tiču implementacije highlighter-a (odnosno, u širem kontekstu - ideje koje se tiču prepoznavanja semantičkih elemenata u programskim kodovima).

U uvodnom članku (iako zbog prilično velikog obima nećemo prikazivati celokupnu implementaciju syntax highlighter-a), bavićemo se idejama koje se tiču prepoznavanja različitih elemenata programskog koda i takođe ćemo prikazati (skoro celokupnu) implementaciju vrlo jednostavnog highlighter-a koji koristi samo regularne izraze (praktično - nešto što možemo smatrati "naivnim rešenjem"), a u narednim člancima, bavićemo se unapređenjima i dodatnim idejama (na pomalo eklektičan način, ali, prilično detaljno).

Iza svega stoji naša (prava) želja i namera - da potaknemo/inspirišemo čitaoce koje tematika zanima, da samostalno implementiraju program za "bojenje sintakse", lekser, parser ili neku drugu skriptu (tj. program) za obradu teksta.

Šta su zadaci skripte za "bojenje sintakse"

Kao što smo više puta primetili u ranijim člancima, programski kod koji se prikazuje 'neposredno onako kako je zapisan' (bez interpretacije), nije "raznobojan i podeljen na funkcionalne celine", onako kako vidimo na sledećoj slici (to jest, onako kako se kodovi tipično prikazuju u editorima, dugi niz godina unazad) ....

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 1. - Primer označavanja različitih kategorija tokena različitim bojama (prikaz kakav je uobičajen u editorima teksta i IDE okruženjima).

Za razliku od prethodno prikazanog bloka, programski kod je - sam po sebi - 'obična niska znakova' ....

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 2. - Programski kod koji je prikazan u osnovnom obliku - bez "bojenja sintakse".

.... i nije teško zaključiti da obična niska znakova ne sadrži i ne može sadržati (u svom osnovnom stanju), informacije o tome da li određeni deo teksta predstavlja deo sintakse programskog jezika kome je pripisano posebno značenje * (komentar, niska, operator, identifikator i sl), ili ne predstavlja takav element.

To dalje znači da, ako različite elemente koda (odnosno različite kategorije tokena) ** treba predstaviti korišćenjem različitih boja, potrebno je prvo kreirati strukturu podataka koja sadrži sve neophodne informacije o strukturi koda. ***

* Editori se 'opredeljuju' za prepoznavanje sintaksnih elemenata određenog računarskog jezika ("a ne nekog drugog"), preko ekstenzije koju nosi datoteka čiji se sadržaj tumači.

Uz korišćenje skripti o kakvima govorimo, na web stranicama je moguće prikazivati proizvoljan broj blokova programskog koda sa različitim jezicima (naravno pod uslovom da highlighter prepoznaje određeni jezik), međutim, za svaki blok se mora (eksplicitno) izabrati jezik, pri čemu se jezici donekle mogu 'mešati', ali, samo u okvirima unapred definisanih pravila.

Na primer, PHP i HTML mogu biti prikazani u okviru PHP bloka, baš kao što, u okviru HTML bloka, CSS i JavaScript mogu biti označeni na odgovarajući način, unutar tagova <style>, odnosno <script>.

Sa druge strane, ne možemo napisati običan tekst i očekivati da će (npr) blokovi C++ i JS koda (koji se nalaze unutar teksta), biti prepoznati sami od sebe i označeni prema pravilima navedenih jezika (to već spada u domen veštačke inteligencije, i nije tema ovog članka).

** Token = niska koja predstavlja pojedinačni element računarskog jezika, sa unapred pripisanim značenjem (kategorije tokena su - da pomenemo samo neke: komentari, niske, operatori, identifikatori, celobrojne, decimalne i heksadecimalne vrednosti i sl).

*** Usput: upravo su strukture podataka koje omogućavaju 'bojenje sintakse', brzinsko pronalaženje delova teksta i sl, razlog zašto - pri otvaranju tekstualnog dokumenta - memorijsko zauzeće ne poraste (samo) u iznosu koji odgovara veličini tekstualne datoteke na disku (već, u iznosu koji je, tipično, primetno veći).

U širem kontekstu, prava svrha "bojenja sintakse" nije - da tekst bude "ulepšan", već, da se osobama koje se bave kodiranjem olakša vizuelno prepoznavanje različitih elemenata koda (ali, da budemo iskreni, ni estetika nije naodmet).

Sa pedagoške strane, čvrsto smo uvereni (a o tome smo takođe i pisali), da je za početnike od velike koristi da prvih nekoliko meseci (ili bar više nedelja), pišu kodove bez uključivanja "bojenja sintakse" (a pored toga, krajnje je preporučljivo da početnici samostalno vode računa i o uparenosti zagrada, pravilnom zatvaranju niski i blok komentara i sl).

Sa druge strane, iskusniji programeri rade sa projektima koji su zapisani u više datoteka i zauzimaju više desetina, stotina (pa čak i hiljada) linija koda, greške sa uparivanjem zagrada (i druge greške), dešavaju se usled premora ili nepažnje (dešava se - svakome - bar ponekad) i - u takvoj situaciji je svaka pomoć dobrodošla.

Osnovne ideje za prepoznavanje tokena, lekseri i parseri

Verujemo da čitaoci (koji se interesuju za tematiku ovakvog članka), već neko vreme kodiraju programe i skripte u određenom IDE okruženju (ili editoru sa naprednim podešavanjima), pri čemu se u navedenim programima praktično podrazumeva da se različiti sintaksni elementi obeležavaju različitim bojama.

U pomenutim programima, kodni tekst se (najčešće) detaljno proverava i po pitanju poštovanja semantičkih pravila (u "najgorem slučaju" - makar najosnovnijih pravila).

Lekser je naziv za deo programa preko koga se niz znakova iz ulazne datoteke pretvara u tokene, dok je parser, deo programa koji proverava (manje ili više detaljno), da li je kod u skladu sa semantičkim pravilima izabranog jezika.

Kada je u pitanju 'raznobojno označavanje sintakse na sajtovima', brzina prikaza je prioritet, a uloga parsera se može pojednostaviti (u velikoj meri), uz "prećutnu" pretpostavku da je programski kod unapred proveren i da je samo potrebno da bude prikazan korektno * (onako kako bi bio prikazan u IDE okruženju koje je dati kod 'proglasilo' semantički ispravnim).

Za sam početak implementacije, pozabavićemo se jednostavnijim od dva zadatka - pretvaranjem ulaznog 'teksta' u listu tokena.

Rastavljanje teksta na tokene - osnovne ideje

Pretvaranje kodnog teksta u listu tokena može delovati kao prilično komplikovan zadatak, međutim, uz malo pažljivije 'posmatranje situacije', lako se mogu uočiti određeni obrasci.

Prvo primećujemo (shodno iskustvu), da razmaci i znaci tabulacije predstavljaju granice reči, ali (što je još važnije):

postoje znakovi koji predstavljaju samostalne tokene (međutim, to zapravo zavisi od konteksta, što ćemo u nastavku objasniti)
određeni znakovi takođe predstavljaju granice drugih tokena
određeni znakovi (tj. tokeni), menjaju kontekst čitanja programskog koda

Šta tačno predstavlja odrednica 'kontekst tumačenja', najlakše se može razumeti preko primera.

Uzmimo za primer znak '(' (otvorena zagrada), koji - u zavisnosti od 'konteksta' * - može označavati: **

otvorenu zagradu koja stoji na početku algebarskog izraza koji je uokviren zagradama
početak definisanja parametara funkcije (ako je parser trenutno u kontekstu definisanja funkcije)
početak dela koda u kome se funkciji predaju argumenti (ako je parser trenutno u kontekstu pozivanja funkcije)
običan znak unutar niske ili komentara - ako se parser nalazi u kontekstu spajanja

U sledećoj naredbi ....

		
racunanjeObima(a, b);

Slika 3. - Primer naredbe (poziv funkcije), u kojoj zagrade predstavljaju specijalni znak koji menja kontekst čitanja koda.

.... pojava otvorene zagrade označava kraj učitavanja identifikatora funkcije i početak učitavanja argumenata, * ali zato u sledećem kodu ....

		
let s = "Nikola Tesla (1856-1943)";

Slika 4. - Primer naredbe u kojoj zagrade ne predstavljaju specijalni znak koji menja kontekst čitanja koda, već - obične znakove koji su (samo) deo niske.

.... pojava otvorene zagrade nema nikakvo semantičko značenje, budući da je prva pojava znaka navoda (nekoliko mesta pre zagrade), otvorila kontekst učitavanja niske, što znači da se svaki naredni znak (uključujući i zagrade, i druge znake koji inače imaju specijalno značenje), učitava kao deo niske, sve dok sledeći znak navoda ne zatvori nisku.

Pogledajmo i detaljan primer rastavljanja naredbe na tokene.

Primer rastavljanja naredbe na tokene

Pri čitanju sledećeg koda:

		
c = a1 + b;

Slika 5. - Primer proste naredbe dodele (koja će biti podeljena na tokene).

.... dešava se sledeće:

prvi znak sugeriše da je u pitanju uredno započeti identifikator (takođe, u datom kontekstu, pojava identifikatora je dozvoljena)
pojavom prvog sledećeg razmaka, prekida se učitavanje prvog tokena, koji se prihvata kao identifikator promenljive (sam razmak se zanemaruje) *
sledeći znak (=), predstavlja samostalni token - operator (čija je pojava u datom kontekstu dozvoljena)
drugi razmak se zanemaruje *
znak a predstavlja uredno započeti identifikator (pojava identifikatora u datom kontekstu je takođe dozvoljena)
znak 1 se u trenutnom kontekstu spaja sa započetom niskom (tj, ne prepoznaje se kao samostalan broj ili pojedinačna cifra u višecifrenom zapisu broja)
pojava trećeg razmaka prekida učitavanje identifikatora a1 (identifikator se prihvata; razmak se zanemaruje) *
znak + predstavlja operator
četvrti razmak se zanemaruje *
znak b predstavlja uredno započeti identifikator
znak ; prekida učitavanje identifikatora b (token b se prihvata kao identifikator, a token ; kao operator (kraj naredbe))

Parser vs. lekser (objašnjenje)

Kao što smo već pominjali, pri prevođenju programskih jezika koriste se dva programa:

lekser - program čija je svrha podela teksta na tokene
parser - program čija je svrha provera validnosti tokena u zavisnosti od konteksta

Lekser je program koji deli tekst na tokene - pri čemu se ne obazire na sintaksički i semantički sadržaj tokena, već samo na to da li su tokeni ispravni u najosnovnijem tehničkom smislu. *

Parser je program koji proverava sintaksičku i semantičku ispravnost koda, to jest, proverava da li su tokeni ispravni u smislu samostalnog značenja i međusobne povezanosti.

Razliku između dva navedena programa, verovatno je najlakše razumeti uz poređenje sa prirodnim jezikom:

U prenesenom smislu, lekser je program koji bi rečenicu "Dsnaa ej elp adn!" uredno podelio na tokene: "Dsnaa" "ej" "elp" "adn" "!" (i ne bi "pravio pitanje" oko oblika reči), međutim, parser bi prepoznao sintaksičku neispravnost (navedene grupe znakova ne predstavljaju reči srpskog jezika).

Ako napišemo rečenicu "Supermen šeta dinosauruse po Terazijama.", rečenica bi (ponovo) bila uredno podeljena na tokene (lekser se ni ovoga puta "ne buni"), sintaksička provera bi takođe prošla uredno (sve reči su prepoznate), ali - semantička provera ne prolazi (Supermen je izmišljeni lik, a dinosaurusi su odavno izumrli).

Za razliku od prethodnih primera, rečenica: "Danas je lep dan!" - 'prolazi' sve tri provere.

Moguća rešenja: kontekstni parser vs. regex highlighter

Kada je u pitanju "bojenje sintakse" (na sajtovima), postoje dva "suprotna" pristupa:

korišćenje specijalizovanog leksera i (potom), parsera - koji će zapravo proveravati ispravnost koda
improvizacija funkcionalnost leksera i parsera preko regularnih izraza

Kombinacija specijalizovanog leksera i kontekstnog parsera, svakako je zanimljivija opcija (naravno, i znatno kompleksnija) - i omogućava potpunu funkcionalnost.

Sa druge strane, skripta za bojenje sintakse koja se u potpunosti zasniva na regularnim izrazima, može naizgled biti praktično rešenje, ali, u pitanju je pristup koji takođe ispoljava i određene vrlo očigledne nedostatke.

Na primer, niska kao što je #incloode<studio.ha> biće uredno označena kao pretprocesorska direktiva programskog jezika C (što propisno dizajniranom parseru ne bi promaklo i bilo bi označeno kao greška), ali, u navedenom slučaju (i sličnim okolnostima), možemo ipak biti i praktični.

Na sajtovima se prikazuju kodovi koji su unapred pripremljeni i - provereni (tj. bar bi tako trebalo da bude u većini slučajeva), a može se reći i da je brzina učitavanja stranice jedan od prioriteta.

Dakle, u pitanju je (ipak) kategorija nedostataka koji se 'daju očekivati' s obzirom na to da skripta ne koristi parser (i stoga ne može prepoznavati značaj i smisao tokena), i moglo bi na ovom mestu delovati da drugih nedostataka nema, međutim ....

(Recimo da u ovom trenutku 'dolazimo do prave poente'.)

Nije problem u tome što će jednostavan "regex highlighter" propustiti nisku kao što je#incloode<studio.ha>, već, u tome što će imati problema sa određenim obrascima (pre svega - sa niskama unutar komentara i sa komentarima unutar niski), ali, takvim pojedinostima bavićemo se nešto kasnije u ovom članku (i pogotovo u narednim člancima).

Pored svega navedenog (i nezavisno od toga kakav highlighter koristimo), skripta za "bojenje sintakse" treba da omogući neposredno prepravljanje sadržaja blokova sa programskim kodom (koji treba prikazati), bez intervencija na HTML-u (ali, ipak uz poštovanje određenih standarda tj. preduslova, na šta ćemo obratiti pažnju u sledećem odeljku) i - naravno - skripta treba svoj posao da obavi što brže.

Praktično rešenje (do koga ćemo postepeno doći), može biti: delimična implementacija parsera (uz prepoznavanje konteksta, ali, bez validacije identifikatora), međutim, za početak ćemo razmatrati, upravo - "skroz naivno rešenje" (koje se u potpunosti zasniva na regularnim izrazima), budući da se tehnički aspekti takvog rešenja u većoj meri podudaraju sa 'krajnjim' rešenjem (naravno, ne skroz), i zato ćemo neko vreme 'zaboraviti' na potencijalne nedostatke/'stranputice' i sl. (to jest, "pravićemo se da ih ne vidimo").

Pred kraj članka osvrnućemo se na potencijalna rešenja i optimizacije, a u narednim člancima, o svemu ćemo diskutovati detaljnije.

Algoritam za kreiranje liste tokena preko regularnih izraza

Osnovna ideja koja stoji iza regex highlightera je sledeća:

prvo treba učitati tekst iz određenog bloka koji sadrži programski kod (pri čemu je blok označen odgovarajućom klasom)
nakon učitavanja, tekst se deli na tokene i svakom tokenu se dodeljuje odgovarajuća oznaka
korišćenjem informacija iz liste tokena, kreira se novi HTML kod (svaki token zapisan je unutar zasebnog <span> taga, uz dodelu odgovarajuće klase)
na kraju, formatirani HTML kod se vraća na mesto nekadašnjeg (običnog) teksta

Kao što smo prethodno nagovestili, da bi programski kod uopšte mogao da 'dospe' do skripte za analizu sadržaja, potrebno je uredno pripremiti elemente stranice na kojima će kod biti prikazan.

Osnovni tehnički preduslovi za prikaz koda na sajtovima

Priprema programskog koda za prikaz na sajtovima (tako da kod izgleda onako kako smo navikli da programski "tekst" izgleda u tekstualnim editorima), podrazumeva formatiranje koda uz poštovanje sledećih pravila:

tagovi <pre> omogućavaju uredan prikaz višestrukih povezanih razmaka, tabova i prelazaka u novi red (odnosno, prikaz znakova koji se inače koriste za formatiranje koda, ali bivaju zanemareni pri interpretaciji HTML koda u web browserima)
tagovi <code> označavaju da je u pitanju blok programskog koda *
potrebno je koristiti monospace font (da bi se postiglo da širina svakog znaka bude ravnomerna, baš kao u editorima)
potrebno je označiti blokove koda preko klasa sa standardizovanim nazivima
za zapis specijalnih znakova kao što su <, & i sl, potrebno je koristiti klase znakova (<, & i sl)

		
<pre>
    <code class='language-clike'>
#include&lt;stdio.h&gt;
void main()
{

}
    </code>
</pre>

Slika 6. - Primer formatiranja HTML bloka koji se može koristiti za prikaz programskog koda na stranici.

Što se tiče naziva CSS klasa, nepisana pravila nalažu da se blokovi koda označe tako da naziv klase odgovara računarskom jeziku koji se koristi u bloku - pri čemu postoje standardni nazivi.

Na primer:

class="language-c" za C
class="language-cpp" za C++
class="language-csharp" za C#
class="language-html" za HTML
class="language-java" za Java kod

(Slični obrasci koriste se i za druge jezike.)

Striktno govoreći, tagovi <code> "ne moraju" se koristiti (jer kod može biti prikazan i bez njih, budući da su zapravo <pre> tagovi zaduženi za formatiranje u tehničkom smislu) - ali - <code> tagovi su semantički tagovi koji su specifično namenjeni uokviravanju programskog koda koji se prikazuje na sajtovima, i stoga je korišćenje <code> tagova više nego preporučljivo (pogotovo u svrhu SEO optimizacije).

Posle urednog formatiranja ulaznog teksta, spremni smo da započnemo posao ....

Podela teksta na tokene

Uzmimo ponovo (kao primer), kod sa prve slike ....

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 7. - Primer izvorne datoteke (jezik C), koja sadrži programski kod - koji je potrebno potrebno podeliti na tokene (kojima će biti pripisane odgovarajuće klase za prepoznavanje elemenata).

Cilj obrade navedenog koda je da na kraju nastane lista tokena, nalik sledećoj listi:

		
[
	[  `/* ----- Sabiranje brojeva ----- */` , 'komentar'],
	[  '#include<stdio.h>'                   , 'pretprocesorska_direktiva'],
	[  'void'                                , 'rezervisana_rec'],
	[  'main'                                , 'identifikator'],
	[  '('                                   , 'otvorena_zagrada'],
	[  ')'                                   , 'zatvorena_zagrada'],
	....
]

Slika 8. - Lista tokena koja nastaje podelom izvornog koda sa slike #7.

.... ili, u opštem smislu, lista koja je formatirana po sledećem obrascu:

		
[
	[  token_1 , tip  ]
	[  token_2 , tip  ]
	[  token_3 , tip  ]
	....
]

Slika 9. - Uopšteni oblik liste sa slike #8.

Pristup koji ćemo koristiti (u svrhu ilustracije), podrazumeva podelu teksta preko liste pojedinačnih regularnih izraza, tako da se u obzir uzima jedan-po-jedan regularni izraz (preko koga se u neobrađenim delovima teksta prepoznaje određeni obrazac - komentar, niska i sl).

Ukoliko regularni izraz prepozna u tekstu određeni obrazac, prepoznati deo teksta se izdvaja u zaseban token (čime se okolni tekst deli).

Da bi tokeni koji su već obrađeni, u daljoj obradi bili preskočeni, uputno je koristiti i pomoćnu boolean promenljivu koja sugeriše da li je token već obrađen (ili nije):

		
[
	[  token_1 , false, tip  ]
	[  token_2 , false, tip  ]
	[  token_3 , false, tip  ]
	....
]

Slika 10. - Tokeni (sa slike #9), kojima je dodata boolean promenljiva preko koje je zapisano da li je token obrađen, ili nije.

Pre nego što se algoritam "pusti u pogon", potrebno je preuzeti tekst iz odgovarajućeg polja i navesti da je u pitanju neobrađen tekst (preuzetom tekstu se doslovno dodeljuje tip "tekst"):

		
let poljeCode1  = document.getElementsByClassName("language-clike")[0];
let tekstUPolju = poljeCode1.innerText;
let listaTokena = [];
listaTokena.push( [ tekstUPolju, false, "tekst" ] );

Slika 11. - Primer skripte za preuzimanje programskog koda koji je zapisan u HTML dokumentu.

Zarad izdvajanja komentara (počnimo, na primer, baš od komentara), potrebno je podeliti listu na sledeće grupe tokena:

tokene koji predstavljaju komentare (i)
"sve ostalo"

Potom je potrebno dalje deliti neobrađeni deo teksta ("sve ostalo"), na tokene koje predstavljaju (npr) pretprocesorske direktive i obične tekstualne tokene, zatim bi se izdvajale (npr) niske .... nakon čega bi usledilo izdvajanje i drugih kategorija tokena, redom, sve dok se ne označe svi elementi (tj. tokeni) koje skripta prepoznaje.

Niske se tipično dele preko funkcije split (kao što je poznato od ranije), tako što se funkciji kao argument predaje regularni izraz.

Na primer, za izdvajanje komentara, koristićemo sledeći kod:

		
let regex     = /(\/\*[\s\S]*?\*\/)/g
let novaLista = listaTokena[i][0].split(regex);

Slika 12. - Podela tekstualnog tokena preko funkcije split i regularnih izraza (u praktičnom smislu - izdvajanje komentara).

Index i upućuje na element liste koji još nije obrađen, a indeks 0, na element u koloni koja sadrži sam tekst.

Pokretanjem koda, promenljivoj novaLista biće dodeljen sledeći sadržaj:

		
[
	[  '/* ----- Sabiranje brojeva ----- */' , true,  'komentar'  ],
	[  tekstUPolju /* ostatak koda */        , false, 'tekst'     ]
]

Slika 13. - Struktura liste novaLista koja je nastala podelom ulaznog teksta na sledeće delove: tokene koji su pronađeni preko regularnog izraza, i obične tekstualne tokene - koji će biti dalje obrađivani.

Na ovom mestu potrebno je, umesto prvog tokena u listi listaTokena, smestiti sadržaj liste novaLista (kod nećemo prikazivati, jer, posle prvog koraka, lista listaTokena će imati isti sadržaj kao pomoćna lista sa gornje slike) ....

Potom, preko sledećeg regularnog izraza ....

		
let regex     = /(\#.*\n)/g;
let novaLista = listaTokena[i][0].split(regex);

Slika 14. - Podela tekstualnog tokena preko funkcije split i regularnih izraza (u praktičnom smislu - izdvajanje pretprocesorskih direktiva).

.... algoritam pronalazi pretprocesorske direktive, nakon čega lista novaLista ima sledeći sadržaj ....

		
[
	[  '#include<stdio.h>'        , true,  'komentar'  ],
	[  tekstUPolju /* ostatak */  , false, 'tekst'     ]
]

Slika 15. - Pomoćna lista pronađenih tokena koje treba vratiti u glavnu listu.

Kada se sadržaj liste novaLista vrati u listu listaTokena, dobija se sledeći rezultat:

		
[
	[  '/* ----- Sabiranje brojeva ----- */' , true,  'komentar'  ],
	[  '#include<stdio.h>'                   , true,  'komentar'  ],
	[  tekstUPolju /* ostatak */             , false, 'tekst'     ]
]

Slika 16. - Sadržaj glavne liste tokena, posle prva dva koraka u obradi.

Postupak se (naravno) ponavlja i za ostale kategorije tokena, a u svemu se mora obratiti pažnja i na implementaciju funkcije koja iz liste uklanja jedan token i zamenjuje ga tokenima iz druge liste.

Šematski prikaz postupka

Da bismo što bolje razumeli sve do sada navedene tehnikalije, osvrnućemo se još jednom na osnovne ideje, nakon čega ćemo prikazati 'šemu' postupka:

lista tokena na početku sadrži jedan token (token predstavlja ceo tekst, i označen je za dalju obradu)
u cilju obrade, potrebno je proći kroz drugu listu, u kojoj svaki element sadrži regularni izraz i naziv klase tokena (koji se preko datog regularnog izraza izdvajaju)
u obzir se uzimaju samo tokeni koji nisu već obrađeni
potrebno je obratiti pažnju na umetanje tokena u glavnu listu

Lista sa regularnim izrazima, mogla bi se definisati na sledeći način ....

		
let C_definicijaJezika = [
	[  /(\/\*[\s\S]*?\*\/)/g  ,  'komentar_blok'              ],
	[  /(\/\/.*\n)/g          ,  'linijski_komentar'          ],
	[  /(\#.*\n)/g            ,  'pretprocesorska_direktiva'  ],
	[  /(\'[\s\S]*?\')/g      ,  'niska_apostrofi'            ],
	[  /(\"[\s\S]*?\")/g      ,  'niska_navodnici'            ],
	[  /(\`[\s\S]*?\`)/g      ,  'niska_backtick'             ],
]

Slika 17. - Lista regularnih izraza, koja praktično predstavlja definiciju jezika.

.... ali, bolje rešenje bi bilo - da spremimo šablone koji predstavljaju određene regularne izraze ....

		
let SABLON_KOMENTAR_BLOK      = /(\/\*[\s\S]*?\*\/)/g;
let SABLON_KOMENTAR_LINIJSKI  = /(\/\/.*\n)/g;
let SABLON_PRETPROCESOR       = /(\#.*\n)/g;
let SABLON_NISKA_APOSTROFI    = /(\'[\s\S]*?\')/g;
let SABLON_NISKA_NAVODNICI    = /(\"[\s\S]*?\")/g;
let SABLON_NISKA_BACKTICK     = /(\`[\s\S]*?\`)/g;

let C_definicijaJezika = [
	[  SABLON_KOMENTAR_BLOK      ,  'komentar_blok'              ],
	[  SABLON_KOMENTAR_LINIJSKI  ,  'linijski_komentar'          ],
	[  SABLON_PRETPROCESOR       ,  'pretprocesorska_direktiva'  ],
	[  SABLON_NISKA_APOSTROFI    ,  'niska_apostrofi'            ],
	[  SABLON_NISKA_NAVODNICI    ,  'niska_navodnici'            ],
	[  SABLON_NISKA_BACKTICK     ,  'niska_backtick'             ],
]

Slika 18. - Lista sa slike #17, zapisana na opštiji način (koji olakšava definisanje ostalih jezika).

.... što može pomoći pri definisanju lista regularnih izraza za druge jezike (na primer, komentari i niske prepoznaju se po istom obrascu: i u C-u, i u Javi, i u JavaScript-u i sl).

U svemu, redosled regularnih izraza je veoma (!) bitan.

Na primer, ako bi navodnici odmah bili izdvojeni kao zasebni tokeni (što znači da navodnici nisu više delovi preostalih tekstualnih tokena), regularni izraz za pronalaženje niski koje su definisane preko navodnika (koji bi bio korišćen u sledećem koraku), ne bi više bio u stanju da prepozna niske!

Kada se sve pripremi (uz obraćanje pažnje na redosled), potrebno je 'izlistati' regularne izraze ....

Izdvajanje komentara

Za prepoznavanje (tj. izdvajanje) komentara, biće korišćeni sledeći regularni izrazi:

		
/(\/\*[\s\S]*?\*\/)/g - blok komentar
/(\/\/.*\n)/g         - linijski komentar

Slika 19. - Regularni izrazi za prepoznavanje komentara.

(Naravno, mislimo na blok komentare u C-olikim jezicima, koji počinju sa /* i završavaju se sa */, ili, linijske komentare, koji počinju sa //.)

Na donjoj slici možemo videti listu koja na početku sadrži jedan token.

Kreiranje liste tokena - korak 01 — Slika 20. - Kreiranje liste tokena - korak 1(a) - na samom početku, lista sadrži jedan token (u kome je zapisan ceo kod).

U prvom koraku, tokeni koji nisu rešeni biće podeljeni preko regularnih izraza, na dve celine:

tokene koji su prepoznati kao komentari
tokene koji i dalje ostaju označeni kao obični (nerešeni) tekstualni sadržaj (koji će proći kroz dalju obradu, preko drugih regularnih izraza)

Kreiranje liste tokena - korak 02 — Slika 21. - Kreiranje liste tokena - korak 1(b) - Posle prvog koraka, izdvojeni su tokeni koji predstavljaju komentare.

Posle prvog koraka, prikaz koda ima sledeći oblik:

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 22. - Prikaz koda u kome su označeni komentari.

Izdvajanje pretprocesorskih direktiva

Za izdvajanje pretprocesorskih direktiva, koristićemo sledeći regularni izraz:

		
/(\#.*\n)/g

Slika 23. - Regularni izraz za pronalaženje pretprocesorskih direktiva.

U nerešenim tekstualnim tokenima ....

Kreiranje liste tokena - korak 03 — Slika 24. - Kreiranje liste tokena - korak 2(a) - Pronalaženje pretprocesorskih direktiva.

.... traže se tokeni koji označavaju pretprocesorske direktive (u ovom slučaju, pronađen je samo jedan takav token):

Kreiranje liste tokena - korak 04 — Slika 25. - Kreiranje liste tokena - korak 2(b) - Posle drugog koraka, u tekstualnim tokenima pronađene su pretprocesorske direktive.

Posle drugog koraka, prikaz koda ima sledeći oblik:

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 26. - Prikaz koda u kome su označeni komentari i pretprocesorske direktive.

Izdvajanje niski

Za izdvajanje (različitih tipova) niski, koristićemo sledeće regularne izraze:

		
/(\'[\s\S]*?\')/g - niska uokvirena apostrofima
/(\"[\s\S]*?\")/g - niska uokvirena navodnicima
/(\`[\s\S]*?\`)/g - niska uokvirena backtick-ovima

Slika 27. - Regularni izrazi za pronalaženje niski.

U nerešenim tekstualnim tokenima:

Kreiranje liste tokena - korak 05 — Slika 28. - Kreiranje liste tokena - korak 3(a) - Pronalaženje niski.

.... algoritam pronalazi dve niske:

Kreiranje liste tokena - korak 06 — Slika 29. - Kreiranje liste tokena - korak 3(b) - Posle trećeg koraka, u tekstualnim tokenima pronađene su niske.

Posle trećeg koraka, prikaz koda ima sledeći oblik:

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 30. - Prikaz koda u kome su označeni komentari, pretprocesorske direktive i niske.

Izdvajanje zagrada

Zagrade možemo izdvojiti preko sledećih regularnih izraza:

		
/(\()/g - otvorena zagrada
/(\))/g - zatvorena zagrada
/(\{)/g - otvorena zagrada za blokove
/(\})/g - zatvorena zagrada za blokove
/(\[)/g - otvorena zagrada za nizove
/(\])/g - zatvorena zagrada za nizove

Slika 31. - Regularni izrazi za izdvajanje zagrada.

Posle pronalaženja zagrada, prikaz koda ima sledeći oblik:

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 32. - Prikaz koda u kome su označeni komentari, pretprocesorske direktive, niske i zagrade.

Izdvajanje operatora

Za operatore ćemo koristiti nešto kompleksniji regularni izraz:

		
/(\+\+|\-\-|>\=|>|<\=|<|\=\=|<<|>>|\->|\&\&|\;|\|\||\=|\+|\-|\*|\/)/g

Slika 33. - Regularni izraz za pronalaženje operatora.

Posle pronalaženja (tj. izdvajanja) operatora, prikaz koda ima sledeći oblik:

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 34. - Prikaz koda u kome su označeni komentari, pretprocesorske direktive, niske, zagrade i operatori.

Na ovom mestu prestaju mogućnosti predloženog algoritma koji koristi regularne izraze (bez dodatnih tehnika), i stoga ćemo iskoristiti prostor da prikažemo šemu liste tokena koja je nastala obradom svih regularnih izraza (pažnja: biće potrebno puno skrolovanja).

Kreiranje liste tokena - korak 07 — Slika 35. - Kreiranje liste tokena - korak 7.

Kreiranje liste tokena - korak 08 — Slika 36. - Kreiranje liste tokena - korak 8.

Prepoznavanje rezervisanih reči i identifikatora iz sistemskih biblioteka

Budući da se rezervisane reči ne mogu efikasno prepoznavati preko regularnih izraza (a pri tom je očekivano da rezervisane reči takođe budu označene na poseban način), praktično rešenje za navedeni zadatak može biti - korišćenje stabala pretrage, ili (još bolje i tipičnije), hash mapa koje sadrže "spisak" rezervisanih reči.

Posle prepoznavanja rezervisanih reči (i drugih tokena od posebne važnosti), prikaz koda ima sledeći oblik:

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 37. - Prikaz koda u kome su označeni komentari, pretprocesorske direktive, niske, zagrade, operatori i rezervisane reči.

Prepoznavanje identifikatora

U pravom smislu reči, prepoznavanje identifikatora je posao za parser (koji će proveriti da li se u kodu pojavljuju samo identifikatori koji su definisani, kao i to da li se definisani identifikatori pojavljuju samo na dozvoljenim mestima i sl).

U implementaciji syntax highlighter-a za web sajtove, možemo sebi dati slobodu (koju inače nikako ne bi trebalo uzimati - kada bi (recimo) trebalo osmisliti highlighter koji će biti korišćen u editoru teksta, za kodiranje), to jest - možemo jednostavno smatrati da (svi) preostali tokeni predstavljaju identifikatore.

Na kraju, posle svih koraka u obradi, prikaz koda ima sledeći oblik ....

		
/* ----- Sabiranje brojeva ----- */
#include<stdio.h>
void main()
{
	int a, b, r;
	printf("Unesite dve celobrojne vrednosti:\n");
	scanf("%d %d", &a &b);
	r = a + b;
	printf("Rezultat sabiranja je: %d", r);
}

Slika 38. - Prikaz koda u kome su označeni svi tokeni.

.... i naravno tek sada možemo početi da diskutujemo o tome kako skriptu treba optimizovati tako da zapravo bude u stanju da tumači programski kod.

Osnovne optimizacije

.... za sam početak

Za početak, može se primetiti da bi skripta mogla biti ubrzana preko optimizacija koje smo već pominjali: * npr. lista regularnih izraza (preko kojih se tekst deli i preko kojih se prepoznaju kategorije tokena) ....

		
[ /\/\*[\s\S]+?\*\// , "blok_komentar"             ] ,
[ /\/\/.*?\n/        , "linijski_komentar"         ] ,
[ /#.*?\n/           , "pretprocesorska_direktiva" ] ,
// ....

Slika 39. - Lista samostalnih regularnih izraza za podelu teksta.

.... mogla bi se svesti na jedan regularni izraz:

		
let regex = /\/\*[\s\S]+?\*\/|\/\/.*?\n|#.*?\n/;

Slika 40. - Jedinstven regularni izraz za podelu teksta (koji nastaje spajanjem regularnih izraza sa prethodne slike).

.... preko koga bi podela bila obavljena efikasnije.

* Podsećamo na to da smo odmah napomenuli (na samom početku), da postupak koji prikazujemo u prvom članku nije optimalan - ni približno - već je samo u pitanju postupak koji je najrazumljiviji pri početnom upoznavanju.

Kada je u pitanju efikasnost, razlike između različitih algoritama (o kojima diskutujemo) najbolje se mogu primetiti ukoliko se skripta izvršava na ('podosta') starijem i sporijem računaru, ali, čak i u navedenim okolnostima nije "tek tako" moguće osetiti razliku.

U suprotnom (u slučaju obrade blokova koda umerene veličine, na iole novijim i bržim računarima - što je zapravo uobičajeni 'scenario' u kome će se skripta koristiti), moći ćete samo da pročitate u konzoli browsera da razlika postoji (naravno, pod uslovom da osposobite deo koda koji: očitava trenutke u kojima počinje i završava se obrada, i računa i prikazuje vremensku razliku).

Međutim, postoji i bitniji problem (koji smo takođe pomenuli još ranije), to jest, dolazimo konačno do analize koja se tiče veoma očiglednog 'saplitanja' regex highlightera po pitanju niski unutar komentara (odnosno komentara unutar niski i sl).

Za primer možemo uzeti sledeći kod ....

		
/* "Niska" */

let s = "Niska";

Slika 41. - Primer programskog koda koji će biti pravilno protumačen bez obzira na to da li regularni izraz prvo traži niske, ili komentare.

.... koji će biti protumačen korektno, ali zato sledeći kod ....

		
/* "Niska" */

let s = " /* Niska */ ";

Slika 42. - Primer programskog koda koji neće biti pravilno protumačen - bez obzira na to da li regularni izraz prvo traži niske, ili komentare.

.... neće biti korektno protumačen!

Rešenje naravno (!) nije, da "zamenimo redosled", to jest, da pustimo da skripta prvo traži niske (pa onda komentare), jer u tom slučaju nastaje problem sa niskama koje su zapisane unutar komentara (nasuprot problemu sa komentarima koji su zapisani unutar niski (koji je prikazan na gornjoj slici)).

Jedna od ideja za rešavanje prikazanog problema (koja je zastupljena u pojedinim highlighterima sa kojima biste se mogli sresti), podrazumeva korišćenje komplikovani(ji)h regularnih izraza.

Navedeni pristup jeste moguć, ali, budući da takve algoritme ne smatramo optimalnim rešenjem (pogotovo pri početnom upoznavanju sa tematikom upotrebe highlightera), predlažemo implementaciju jednostavnog parsera.

Lekser će i dalje koristiti regularne izraze, ali - umesto regularnih izraza koji prepoznaju celokupan sadržaj komentara i niski - biće korišćeni samo sledeći regularni izrazi:

		
[ /\/\*/ , "blok_komentar"     ] ,
[ /\*\// , "blok_komentar"     ] ,
[ /\/\// , "linijski_komentar" ] ,
[ /\"/   , "niska_navodnici"   ] ,
[ /\'/   , "niska_apostrofi"   ] ,
[ /\`/   , "niska_backtick"    ] ,
// ....

Slika 43. - Lista samostalnih regularnih izraza za podelu teksta, preko kojih se mogu izdvojiti tokeni koji predstavljaju početak i kraj niski i komentara.

Kao što vidimo, u pitanju su regularni izrazi preko kojih se prepoznaju granice niski i komentara (naravno, za ostale elemente, treba koristiti druge regularne izraze).

Preostaje da uspostavimo mehanizam za prepoznavanje konteksta, ali - to će biti tema za jedan od narednih članaka (ili nešto što ćete pokušati samostalno da implementirate).

Šta dalje ....

Čitaocima koji žele da samostalno isprobaju implementaciju kontekstnog parsera, preostaje (upravo) - samostalna implementacija ideja o kojima smo diskutovali (prepoznavanje konteksta i sl).

Sa naše strane, iako nećemo (doslovno) prikazati implementaciju kontekstnog parsera u narednim člancima, razradićemo ideje koje smo nagovestili, kao i još nekoliko zanimljivih ideja za unapređenje.

Naravno, ako se neko oseća posebno "hrabro" i "inspirisano", može se upustiti i u samostalnu implementaciju pravog parsera koji "vidi sve" (a ako ima takvih pojedinaca - želimo im puno sreće). :)

Za kraj, jedan savet opšteg tipa.

Ako se upustite u implementaciji, pa (u najgorem slučaju), "na pola puta" ipak shvatite da niste još uvek bili u potpunosti spremni - nemojte smatrati da ste protraćili vreme.

Prošli ste kroz iskustvo koje će vas (iskreno se nadamo), isključivo ohrabriti da ponovo pokušate, i (naravno), imaćete bolju predstavu o svojim realnim mogućnostima.

Na kraju, kada uspete (kao i obično - želimo da uspete :)), veoma dobro ćete razumeti značaj onoga što ste postigli.

Srećno!

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.