Leksički analizator

Leksički analizator

Leksičkim analizatorom se realizuje faza leksičke analize u procesu prevođenja jezika. Odnosno, u kodu se identifikuju leksičke celine koje imaju neki sintaksni smisao, transformišu se u simbole (tokene) i prosleđuju se sintaksnom analizatoru.

1Namena leksi

2kog analizatora

Postoji više razloga zbog kojih se leksički analizator izdvaja od sintaksnog analizatora. Možda najvažniji su:

• 
  Jednostavnija realizacija.
  
• 
  Tako se dobija mogućnost da se tehnike za sintaksnu analizu razvijaju nezavisno od jezika. Ulaz u sintaksni analizator je niz simbola definisan određenim formalnim jezikom, nije zavisan od programskog jezika koji se prevodi.
  
• 
  Prenosivost kompilatora – U fazi leksičke analize eliminišu se svi mašinski zavisni elementi i generiše mašinski nezavisna sekvenca simbola koja se prosleđuje sintaksnom analizatoru
  
• 
  Povećanje efikasnosti kompilatora. Posebnim tehnikama baferisanja koje se koriste u realizaciji leksičkog analizatora doprinosi se njegovoj efikasnosti a time i efikasnosti kompilatora.
  

Sprega leksičkog i sintaksnog analizatora prikazana ja na Slici 4.1

Leksički analizator

Sintaksni analizator

Tabela simbola

Izvorni program

Token

Get next token
Slika 4. Veza između leksičkog i sintaksnog analizatora

Pored ove osnovne uloge leksički analizator obavlja još neke zadatke:

• 
  Izbacuje iz ulaznog koda delove koji nisu značajni za sintaksnu analizu: komentare, praznine (blanko znake), tab i newline simbole.
  
• 
  Usklađuje listing gršaka sa ulaznim kodom. Npr. vodi računa o broju newline simbola, što se koristi kod referenciranja na grške.
  

Često se leksički analizator realizuje tako da su njegove funkcije razdvojene u dve faze:

• 
  Ulazna konverzija - Odgovorna za transformaciju ulaznog koda, izbacivanje praznina i sl.
  
• 
  Leksička anliza – Odgovorna za generisanje tokena.
  

U okviru ulazne konverzije vrši se transformisanje i pojednostavljivanje ulaznog koda i njegovo prilagođavanje ulaznom formati leksičkog analizatora. Danas se neke funkcije ulazne konverzije vrše već u fazi pisanja koda, odnosno prenete su editoru za pisanje programa. Mnogi editori transformišu kod u neki standardni format pogodan za kkasnije pregledanje od strane programera ail prilagođen leksičkom analizatoru. Na primer transformisu identifikatore u isti format dodaju ili brišu veliko slovo ak smo in napisali dva puta različito i sl.

Samu leksičku analizu koju vrši leksički analizator objasnićemo na sledećem primeru. Leksički analizator vidi ulazni kod (napisan na nekom programskom jeziku) kao niz slova. Na primer ako u programu imamo:

if (i == j)

Z = 0;

else

Z = 1;
Leksički analizator će ovo videti kao sledeći niz slova:

\tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1;
Njegov zadatak je da iz ovog niza izdvoji podnizove i prestavi ih tokenima. Sintaksnom analizatoru prosleđuje niz tokena. Kao što su u srpskom jeziku leksičke celine imenica, glagol, pridev, u programskim jezicima su to: identifikator, ključna reč, konstanta, i sl.

Tokeni

Jedan token u suštini predstavlja skup nizova (reči). Na primer:

• 
  Identifikator: niz koji počinje slovom a može da sadrži slova i cifre
  
• 
  Integer: neprazan niz cifara, sa ili bez znaka ispred
  
• 
  Ključna reč: else, or, if, begin ....
  
• 
  Belina: Neprazan niz blano znakova, ili znakova za: anewline ili tab
  

Tokenima se identifikuju leksičke celine koje su od interesa za sintaksni analizator. Za sintaksnu analizu nisu bitni razmaci, znaci za nove linije, tabulatori i komentari. U nekim jezicima čak i neke reči naredbe nisu bitne. Na primer u programskom jeziku COBOL naredba može da se sastoji od reči jezika koje su bitne i koje nisu bitne za prepoznavanje naredbe već se koriste samo da bi zapis naredbe bio jasniji.

Za analizu takođe nije bitno da li se na određenom mestu nalazi identifikator koji se zove ALFA ili se zove BETA, već je jedino bitno da je na određenom mestu identifikator. Zbog toga se sintaksnom analizatoru preko tokena prenosi samo ta informacija.

Izbor tokena koji će se koristiti zavisi od programskog jezika na koji se odnosi kompilator, kao i od toga kako je projektovan sintaksni analizator. Na primer u prethodno datom nizu:

\tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1;

biće izdvojeni sledeći tokeni: ključna reč, (, identifikator, relacija, identifikator, ), identifikator , dodela, konstanta, graničnik, ključna rač, identifikator, dodela, konstanta, graničmik.

Napomena: (, ), +, -, * su ovde tokeni ne slova azbuke. Naime specijalni znaci se obično koriste i kao tokeni koji predstavljaju sami sebe kao leksičke celine.

Definisanje tokena može bitno da utiče na kvalitet samog prevođenja a time i na kvalitet jezika. To se može ilustrovati nekim karakterističnim primerima iz istorije programskih jezika.

Na primer prilikom implementacije programskog jezika FORTRAN uzimano je da se blanko znaci ignorišu. To znači da se nizovi VAR1 i VA R1 se tretiraju jednako kao identifikator VAR1. Međutim ovo pravilo je dovelo do čuvene greške koja se potkrala u programu za upravljanje letilicom iz programa Geminy, gde je umesto naredbe

DO 10 I = 1, 100

bilo napisano

DO 10 I = 1. 100

što je od strane leksičkog analizatora prepoznato kao da promenljiva DO10I dobija vrednost 1.100 umesto kao DO petlja.

Leksički analizator se obično implementira tako da se uvek gleda jedan ili više simbola unapred da bi se pravilno identifikovala leksema.

Primera jezika u kojima su neke stvari bile loše postavljene pa su zbog toga otežavale analizu ima mnogo. Pomenućemo još neke:

• 
  U programskom jeziku PL-I ključne reči nisu bile zaštićene pa su mogle da se koriate i kao identifikatori. Nije teško uočiti kakvu zabunu leksičkom analizatoru unosi sledeći deo koda:
  

IF ELSE THEN THEN = ELSE; ELSE ELSE = THEN

Takođe u sledećem primeru:

DECLARE (ARG1,. . ., ARGN)

nije lako sve do zatvorene zagrade zaključiti da li je DECLARE referenca na višedimenzionalno polje ili naredba za opis. Ovo je zahtevalo da se prilikom implementiranja leksičkog analizatora koristi višestruki pogled unapred.

• 
  Na žalost sličnih primera ima i u savremenim jezicima. Na primer u C++ se za definisanje templejta koristi sledeća sintaksa:
  

Foo,

dok je strim sintaksa:

cin >> var;

Međutim javlja se konflikt sa ugnježđenim templejtima:

Foo>

Šabloni

Potreban nam je način da jednoznačno definišemo koji nizovi odgovaraju kom tokenu. Za to se se mogu koristiti regularni izrazi. Odnosno prilikom definisanja ovih regularnih izraza koristi se nešto izmenjena notacija, što ilustruje sledeći primer:

cifra = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ili cifra = [0 – 9]

int = cifra cifra* ili broj = cifra+

slovo = A | B | C | … | Z | a | b | … | z ili slovo = [A - Z a - z]

id = slovo ( slovo | cifra)*

flt = (+ | -)? cifra+ (.cifra+)? (E (+ | -)? cifra+ )?

U ovoj notaciji važi:

( r )? = r | dok je r+ = r*\

Regularni izrazi su šabloni za prepoznavanje nizova i njihovo preslikavanje u tokene. To je samo jedan od načina kako se mogu definisati šabloni i u praksi se najviše koristi. U principu šablon tokena može da bude definisan i na bilo koji drugi način. Mi smo na početku ove priče koristili tekstualni opis, pa smo identifikator definisali kao niz koji počinje slovom a može da sadrži slova i cifre.

Primer 4.1 Tokeni, lekseme i šabloni U Tabeli 4.1 predstavljeni su primeri nekih tokena, leksema za koje se generišu i šablona po kojima se generišu. TOKEN LEKSEMA ŠABLON const const const if if if rel <, <=, =, <>, >, >= < | <= | = | <> | > | >= id pi, C, P2 slovo(slovo | cifra)* num 3.1416, 0, 6.02E23 (+ | -)? cifra+ (.cifra+)? (E (+ | -)? cifra+ )? literal “Ovo je podatak” “ (slovo | blanko | cifra) * “

Da zaključimo:

• 
  LEKSEMA – Ulazni niz koji se prepoznaje na osnovu formalnog opisa pomoću šablona i za koji se generiše određeni token.
  
• 
  TOKEN – Izlazni simbol koji se generiše kada je prepoznat određeni ulazni niz znakova.
  
• 
  ŠABLON (pattern) – Regularni izraz, formalni opis ulaznih nizova za koje se generiše odeđeni token.
  

3Tablica simbola

Pored toga što sintaksnom analizatoru predaje niz tokena leksički analizator treba da sačuva neke atribute tih tokena da bi oni bili kasnije iskorišćeni u toku generisanja koda. Na primer u fazi sintaksne analize važna je samo informacija da je na određenom mestu u nizu identifikator, a nije važno koji je to identifikator. Međutim u kasnije u fazi semantičke analize i u fazi generisanja koda, važno je koji je to identifikator, kakvog je tipa, da li je u pitanju skalar ili vektor i sl. Npr. kada se generiše listing grešaka bitno je koji je identifikator i u kojoj liniji se on nalazi.

Kako leksički analizator prvi dolazi u kontakt sa ulaznim kodom i kasnije ga transformiše on mora da sačuva te informacije za kasniju upotrebu. U te svrhe leksički analizator generiše tablicu simbola u koju smešta sve atribute relevantne za generisane tokene. Da bi se kasnije moglo pristupiti odgovarajućem slogu u tablici simbola uz token se, kao njegov atribut, prenosi i pointer na na taj slog. Nekada se neki atributi prenose uz sam token, kao na primer vrednosti konstanti i sl., kako je to pokazano u sledećem primeru:

Primer 4.1 Generisan strim tokena Uzmimo kao primer sledeću naredbu napisanu u programskom jeziku FORTRAN: E = M * C ** 2 Tokeni sa pridruženim atributima: <id, pointer na TS za E> <op_dod> <<id, pointer na TS za M> <op_mul> <id, pointer na TS za C> <op_exp> <num, type integer, val 2>

Tablica simbola se veoma često implementira kao Heš tabela.

4 Implementacija leksičkog analizatora

Kako je osnovni zadatak leksičkog analizatora da prepozna nizove slova koji su definisani preko regularnih izraza za njegovu realizaciju se obično koriste konačni automati.

Na primeru jednog jednostavnog programskog jezika pokazaćemo kako može da bude generisan graf automata koji prepoznaje taj jezik. Pretpostavimo da naš jezik sadrži:

• 
  Komentare oblika: /*Ovo je komentar */
  
• 
  Relacione operatore: <, <=, <>, =, >, >=,
  
• 
  Aritmeti
  
• 
  ke operatore: + , - , / , * , ( , )
  
• 
  Operator dodeljivanja := ,
  
• 
  Terminalni simbol ;
  
• 
  Ključne reči (zapamčene u tabeli ključnih reči)
  
• 
  Identifikatore
  
• 
  Literale (nizove oblika: ‘Ovo je podatak’)
  
• 
  Celobrojne konstante bez znaka
  
• 
  Beline
  

Leksički analizator treba da prepoznaje sve gore navedene lekseme, da ignoriše komentare i beline i da generiše tokene za sve preostale slučajeve. Biće realizovan kao konačni automat koji polazi iz početnog stanja uvek kad azapočinje prepoznavanje nove lekseme i prelazi u završno stanje kad aje prepoznao leksemu. U završnim stanjima automata bili bi generisani tokeni.

Deo ovog automata kojim se izbacuju komentari prikazan je na Slici 4.2. Na ovom grafu stanje 2. automata je završno stanje i u njemu se prepoznaje token / kao operator množenja. Kada dođe u stanje 2. analizator će na osnovu toga koji je sledeći znak po redu odlučiti da li je to završno stanje ili će preći u novo stanje. Ako je iza kose crte znak *, analizator prelazi u sledeće stanje . U svim ostalim slučajevima stanje 2 je završno i prepoznaje se token / .

1



4

3

2

not *

*

/

*

*

/

start

Slika 4. Deo automata kojim se izbacuju komentari

Deo automata kojim se prepoznaju relacioni operatori prikazan je na Slici 4.3. Stanje 5 je završno za operator < i u njemu se generiše token lt, u stanju 6 se prepoznaje <= i generiše se token le, dok se u stanju 7 prepoznaje <> i generiše se token ne. Stanje 8 prepoznaje > i daje token gt, a stanje 9 operator >= i token ge, dok je stanje 10 završno stanje za operator = i generiše token eq. Ovaj primer pokazuje kako se tretiraju dvoznaci. U ovom slučaju za niz od dva znaka koja čine jedan operator generiše se jedan token.

8

9

=

7

6

=

<

start

10

>

=

>

1

5
Slika 4. Prepoznavanje relacionih operatora

Na Slici 4.4 predstavljen je deo automata kojim se prepoznaju aritmetički operatori i operator dodele. Svakom od aritmetičkih operatora odgovara po jedno završno stanje. Obično su oni sami za sebe tokeni. U ovom delu treba obratiti pažnju na to kako se prepoznaje operator dodele. Znak dvotačke (:) prevodi automat u stanje 16, ali to stanje nije završno zato što u ovom jeziku dvotačka nema leksički smisao, tek sa pojavom znaka = iza dvotačke prelazi se u stanje 17 koje je završno i u kome se generiše odgovarajući token.

11

(

start

1

12

)

13

+

14

-

15

*

16

:

17

=


Slika 4. Prepoznavanje aritmetičkih operatora

Deo automata kojim se prepoznaju identifikatori, literali i graničnik ; prikazan je na Slici 4.5. Svako slovo prevodi automat u stanje 19. Svako sledeće slovo ili cifra zadržavaju ga u tom stanju sve dok se ne pojavi neki drugi znak kada to stanje postaje završno. Nakon toga najpre se proverava da li je prepoznata reč ključna reč jezika. U te svrhe pretražuje se tablica ključnih reči jezika. Ukoliko se u ovoj tablici ne pronađe ta reč, generiše se token id, što znači da je prepoznat identifikator.


slovo | cifra
18

;

start

1

19

slovo

20

‘

21

not ‘

‘

‘


Slika 4. Prepoznavanje identifikatora i literala

Interesantan je i deo kojim se prepoznaju literali (znakovne konstante). U deo automata koji prepoznaje ove lekseme ulazi se ako se pojavi znak apostrof (‘) koji prevodi automat u stanje 20. Svaki znak koji nije apostrof zadržava automat u tom stanju. Svaki sledeći apostrof prevodi automat u stanje 21. Ovo stanje je završno stanje ako se string završava jednim ili neparnim brojem apostrofa. paran broj apostrofa vraća automat u stanje 20 koje nije završno. U stanju 21 generiše se token str i kao njegov atribut pamti prepoznati string ili se on upisuje u tablicu simbola a uz token se generiše pokazivač na tablicu simbola.

start

1

22

cifra

cifra



ostalo

Slika 4. Prepoznavanje celih brojeva bez znaka

Na Slici 4.6 prikazan je deo automata kojim se prepoznaju celi brojevi bez znaka. Pojava cifre prevodi automat u stanje 22. Svaka sledeća cifra zadržava ga u tom stanju. Nailaskom znaka koji se razlikuje od cifre stanje 22 postaje završno i generiše se token int.

1

start

3

2

4

5

6

7

8

+

-

cifra

cifra

cifra

cifra

cifra

cifra

cifra

+

-

.

.

.

E

E

E

cifra

E

num=(+ | -)?cifra^* (.cifra⁺)? (E (+ | -)?cifra⁺ )?

Slika 4. Automat koji prepoznaje brojeve prema definiciji u jeziku Pascal

U programskim jezicima se obično definiše više tipova konstanti i one su znatno složenije od celobrojnih konstanti bez znaka koje smo imali u našem primeru. Na slici 4.7 prikazan je graf automata koji prepoznaje celobrojne i realne konstante zapisane u normalnom i eksponencijalnom zapisu, prema njihovoj definiciji u programskom jeziku Pascal.Na slici je dat i regularni izraz kojim se opisuju ove konstante.

Programska realizacija leksičkog analizatora

Programska realizacija leksičkog analizatora se svodi na pisanje programa koji realizuje automat koji je definisa. Tu mogu da se primene zasličite tehnike. Jedan pristup je da se napiše potprogram za svako od stanja automata pa da se pozivi potprograma povežu u skladu sa grafom automata. Drugi pristup je da se napiše program koji realizuje celi automat odjednom.

Ovde će biti prikazano rešenje u kome se čita ulazni niz sve dok se ne generiše vrednost tokena kao izlaznog podatka. U te svrhe se koristi pro

SCAN(PROGRAM, LOOKAHEAD, CHAR, TOKEN, POS)

u kojoj je:

PROGRAM - Ulazni niz koji se analizira

CHAR - promenljiva koja pamti trenutni znak koji se analizira

TOKEN - Izlazna promenljiva koja dobija vrednost tokena koji se generiše

POS - Pozicija u tablici simbola gde se upisuju atributi ( za identifikatore, literale i konstante)

U programu se koriste jos:

GET_CHAR	Procedura koja čita sledeći znak iz niza koji se analizira
LOOKAHEAD	Promenljiva logičkog tipa koja pokazuje da li se znak koji je trenutno u zapamćen kao CHAR koristi sa prethodnim ili ne.
INSERT(STRING, type)	Procedura za upis u Tablicu simbola
KEYWORD(STRING)	Procedura koja ispituje da li je određeni string ključna reč.
STRING.CHAR	Nadovezivanje slova na niz
Pseudo kod programa prikazan ja na Slici 4.8 Slika 4.8 Pseudokod programa leksičkog analizatora Tehnika dvostrukog bafera Prilikom programske realizacije leksičkog nalizatora često se koriste tehnika kod koje se kao pomoćna struktura koristi dvostruki bafer (obično dužine 1024 bajtova), Slika 4.9. Najpre se puni leva polovina bafera. Oba pokazivača (Upoč-pokazivač početka lekseme i Ukaj-pokazivač kraja lekseme) se postavljaju na početak. Kako se skanira znak po znak niza tako se pomera pokazivač kraja lekseme udesno sev dok se ne prepozna leksema. Tada se Upoč pomera na poziciju pUkraj i kreće se sa prepoznavanjem nove lekseme. Kada Ukraj dođe do kraja prvog bafera puni se drugi bafer i nastavlja se sa traženjem kraja lekseme u drugom baferu. Kada se dođe do kraja drugog bafera puni se prvi bafer i nastavlja se sa trženjem lekseme od njegovog početka. Na ovaj način dobija se jedan beskonačni bafer. Jasno je da zbirna dužina oba bafera treba da bude veća od najduže lekseme koja se može pojaviti u programu. Zbog toga je bitno kako su definisani leksički elementi jezika. Već smo pomenuli problem sa dužinom DECLARE naredbe u progrskom jeziku PL-1 koji jse javljao zbog toga što u ovom jeziku ključne reči nisu bile zaštićene već su mogle da se koriste i kao identifikatori promenljivih. E = C**2 eof Slika 4.9 Dvostruki bafer Pseudo kod algoritma koji se koristi pri analizi tehnikom dvostrukog bafera dat je na slici 4.10. Ukraj := Ukraj + 1; if (Ukraj /= eof ) then begin if Ukraj na kraju prve polovine then reload druge polovine; Ukraj := UKraj + 1; end else if Ukraj na kraju druge polovine then begin reload prve polovine; pomeriti UKraj na početak prve polovine end else Kraj lekseme Upoč = Ukraj end Slika 4.10 Algoritam dvostrukog bafera 54.5 Leksičke greške Zbog svog veoma lokalizovanog sagledavanja programa leksički analizator može da otkriva samo ograničen broj grešaka: Tipične greške su: Pojava suvišnog slova u ključnim rčima, Npr: iff, thenn, Izostavljeno slovo els, bein, Upisano pogrešno slovo: than umesto then, Permutacija dva slova: fi umesto if. Savremeni leksički analizatori obično mogu i da ispravljaju ili da sugerišu ispravke tih tipičnih grešaka. Tako mogu da izvrše: brisanje suvišnog znaka, upis znaka koji nedostaje, zamenu progrešnog znaka, permutaciju dva znaka. Međutim čak i otkrivanje ovako jednostavnih grešaka zavisi od toga kako su definisane lekseme i šabloni za njihovo otkrivanje. Uzmimo sledeći primer iz jezika C fi(a == f(x)) Leksički analizator ne može da utvrdi da li je fi permutovano if ili predstavlja ime funkcije tako da može da generiše dva simbola. U Fortranu IF(i,j) može da se tretira i kao element matrice i kao poziv funkcije, ali i da liči i na IF naredbu. Zobog ovakvih i sličnih problema kod novijih analizatora regularni izrazi se zadaju u kontekstu ime se izbegavaju višeznačnosti. Traži se na primer da se regularni izraz r1 uvek javlja u kontekstu regularnog izraza r2: r1/r2. Primer: DO/({slovo} | {cifra})* =({slovo} | {cifra})* U ovom primeru se DO prepoznaje kao kao leksema ako se nalazi u kontekstu nizova opisanih regularnim izrazom koji sledi. 64.6 LEX – Generator leksičkog analizatora Danas se za generisanje leksičkog i sintaksnog analizatora kao glavnih modula kompilatora koriste generatori među kojima su najpoznatiji LEX- generator leksičkih analizatora i YACC- generator sintaksnih analizatora. Ova dva generatora su izvorno razvijena za operativni sitem UNIX i programski jezik C, ali se danas mogu naći verzije ovih i sličnih generatora za mnoge druge programske jezike: Javu, C++ i sl. Leksički analizator pomoću LEX-a se generiše tako što se najpre pomoću posebne notacije piše njegova LEX specifikacija. Ova specifikacija se propušta kroz generator LEX koji kao rezultat daje C-kod programa koji predstavlja specificirani leksički analizator. Kompiliranjem tog C-koda dobija se izvršni fajl leksičkog analizatora (fajl a.out). Na ulaz ovako generisanog analizatora može da se dovodi proizvoljan teksr čija leksička analiza treba da se izvrši. Kao rezultat se dobija niz tokena prema koji odgovaraju specifikaciji analizatora, Slika 4.11. Slika 4.11 Generisanje leksičkog analizatora pomoću generatora LEX Kako radi LEX LEX u suštini generiše C kod kojim se implementira konačni automat koji odgovara opisanom leksičkom analizatoru. Na primer za prepoznavanje identifikatora definisanih regularnim izrazom slovo(slovo | cifra )*, LEX generiše automat prikazan na slici 4.12, a za njegovu realizaciju kos prikazan na slici 4.13. Slika 4.12 Graf automata koji prepoznaje identifikatora Slika 4.11. Deo koda koji generiše LEX Lex specifikacija LEX specifikacija kojom se opisuje leksički analizator koji se generiše sastoji se od tri dela: definicije %% pravila %% korisnički potprogrami Za svako završno stanje grafa leksičkog analizatora kreira se jedno pravilo. Pravilo sadrži uzorak (šablon) koji se prepoznaje i akciju koja će se izvršiti kada se pronađe definisani uzorak. Akcija se najčešće definišu kao pozivi funkcija koje su definisane u delu korisnički programi. Deo sa definicijama sadrži različite elemente: eksterne definicije, globalne promenlive, #include i #define naredbe, lokalne promenljive, kao i zaglavlje koje se direktno umeće u generisani C- kod. Ovaj kod se piše između zagrada: %{ i %}. U delu koji je označen kao korisnički potprogrami pišu se potprogrami preko kojih se definišu akcije. LEX notacija za zadavanje pravila Pravila u okviru LEX specifikacije se zadaju kao regularni izrazi pre čemu se za njihovo zapisivanje koristi posebna notacija. Pri tome sledeća pravila: [ ] Uglasteim zagradama se obuhvataju alternative, ( ) Okrugle zagrade se koriste za grupisanje elemenata, + Element uz koji stoji znak + može da se ponovi više puta, ? Element uz koji stoji znak ? može ali i ne mora da postoji, * znak iteracije, tumači se kao Više puta ali i nijednom, - znak za interval ^ znak za početak reda \ znak koji stoji uz specijalne znake Primer 4.2 Generisan strim tokena Lex specifikacija analizatora koji prepoznaje pozitivne i negativne brojeve tipa integer u programskom jeziku Pascal. D [0-9] H [0-9A-Fa-f] %% \+?{D}+ puts(“ Prepoznata pozitivna dekadna konstanta”); \-{D}+ puts(“ Prepoznata negativna dekadna konstanta”); \+?${H}+ puts(“ Prepoznata pozitivna heksa konstanta”); \-${H}+ puts(“ Prepoznata negativna heksa konstanta”);

Pitanja

1. 
   Objasniti namenu leksičkog analizatora.
   
2. 
   Objasniti zašto je bolje da se leksička analiza izdvoji kao posebna faza u procesu prevođenja jezika.
   
3. 
   Šta su to tokeni?
   
4. 
   Objasniti vezu između tokena, leksema i šablona.
   
5. 
   Objasniti vezu izmešu šablona i regularnih izraza.
   
6. 
   Šta je to tablica simbola?
   
7. 
   Koje greške može da otkriva leksički analizator?
   
8. 
   Objasniti tehniku dvostrukog bafera.
   
9. 
   Šta je i čemu služi LEX?
   
10. 
    Objasniti kako radi LEX.
    
11. 
    Objasniti strukturu LEX specifikacije.
    
12. 
    Dati osnovne elemente LEX notacije za pisanje pravila.
    

Zadaci

• 
  Identifikovati lekseme u sledećem delu koda napisanog na programskom jeziku C:
  

float triangle(float width, float height)
{
    float area;

    area = width * height / 2.0;
    return (area);
}

• 
  Celobrojne konstante u programskom jeziku C su definisane sledećim skupom pravila:
  

decimal-constant nonzero-digit|decimal-constant digit

octal-constant0 |octal-constant octal-digit

hexadecimal-constant: 0x hexadecimal-digit | 0X hexadecimal-digit |

hexadecimal-constant hexadecimal-digit

nonzero-digit 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

octal-digit: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

hexadecimal-digit: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | A | B | C | D | E | F

Nacrtati graf automata koji prepoznaje ovako definisane celobrojne konstante.

• 
  Nacrtati graf automata koji prepoznaje sve operatore dodeljivanja i relacione operatore u C++. Uključiti sledeće operatore dodeljivanja:
  

=, *=, /=, %=,+=,–=,<<=, >>=,&=,^=, |=

kao i sledeće relacione operatore: = =, !=, <, >, <=, >=.

• 
  Napisati LEX specifikaciju za analizator iz Zadatka 2.
  
• 
  Kreirati LEX specifikaciju za generisanje leksičkog analizatora jezika mPascal, koji je predstavljen grafom na slici 4.13.