Limbaje formale şi translatoare (Compilatoare)

1

Scopul analizei lexicale este transformarea şirului de caractere care formează codul sursă, într-o secvenţă de grupuri sintactice nume atomi lexicali.

Dacă lipseşte etapa de reconstrucţie a liniilor, analizorul lexical trebuie să elimine şi separatorii din codul sursă.

Poate elimina comentariile din codul sursă, caz în care operaţia respectivă nu va mai trebui realizată în etapa de preprocesare; în cazul în care limbajul în care a fost scris codul sursă nu necesită celelalte operaţii din preprocesare, această etapă poate fi eliminată complet.

2

1. Cuvintele rezervate ale limbajului de programare în care este scris codul sursă Ex: în C int, long, float, double, unsigned, void, if, else, for, while, do, switch,

default, case, struct ◦ În C++ class, inline, virtual

2. Identificatorii ◦ A. Nume de variabile ◦ B. Nume de funcţii ◦ C. Nume de constante

3. Constante Ex: întregi (12, +3, 0), reale (12.0, +3.2, 0.0), caracter (‘a’, ‘\n’), şir de caractere

(“”, “la facultate”), bool (true, false), hexazecimale (0x45, 0xFA), ş.a. 4. Operatori

◦ A. Aritmetici ◦ Ex: în C +,-,*,/,%, ◦ B. Logici ◦ Ex: în C &,|,!

5. Semne de punctuaţie (simboli sau grupuri de simboli cu rol delimitativ) Ex: în C spaţiu, punct şi virgulă 6. Comentariile Ex: în C liniile care încep cu //, sau şirurile de caractere dintre “/*” şi “*/”

3

Fiecare atom lexical poate fi reprezentat prin două elemente: tipul şi valoarea.

Tipul atomului lexical este dat de clasa de atomi lexicali din care face parte.

Valoarea unui atom lexical este reprezentată de succesiunea de caractere care formează atomul lexical respectiv.

Ex: identificator, NumeVariabilă Împărţirea se bazează pe faptul că în analiza sintactică

care urmează nu este important care atom lexical urmează, ci mai ales ce tip de atom lexical urmează.

Ex: pentru instrucţiunea “int a1;” este important că după cuvântul cheie “int” urmează un identificator; nu are importanţă că acest identificator este “a1”.

4

În etapa de analiză lexicală se generează şi se completează tabela de simboli; aceasta se bazează pe următoarele structuri:

1. Tabela de identificatori: cuprinde numele identificatorului, tipul acestuia, şi în funcţie de tip, o serie de informaţii semantice.

2. Tabela de constante: cuprinde tipul constantei şi valoarea acesteia.

3. Tabela de cuvinte rezervate.

5

După relaţia dintre analizorul lexical şi cel sintactic:

1. Analizor lexical independent de analizorul sintactic ◦ Analizorul lexical este lansat pentru analiza întregul

program: generează întreaga secvenţă de atomi lexicali şi completează în mod corespunzător tabela de simboli şi structurile asociate.

◦ Acţiunea analizorului sintactic este succesivă acţiunii analizorului lexical.

6

2. Analizor lexical comandat de către analizorul sintactic ◦ Analizorul lexical este implementat sub forma unei

proceduri (funcţii) care la fiecare apel întoarce un atom lexical

◦ Poate fi implementat pentru a fi utilizat în două modalităţi:

Prin apel direct: Analizorul sintactic cere următorul atom lexical care poate fi extras din codul sursă

Prin apel indirect: Analizorul sintactic cere un anumit atom lexical

7

După structura analizorului lexical: ◦ Analizor lexical monobloc (unipas): primeşte ca şi

intrare secvenţa de caractere care formează codul sursă şi returnează secvenţa de atomi, fără a trece prin etape intermediare.

◦ Analizor lexical structurat (multipas): împarte codul sursă în atomi lexicali prin parcurgerea mai multor etape:

1. Transliterarea

2. Exploatarea

3. Selectarea

8

Analiza lexicală este partea cea mai critică pentru un compilator, din punct de vedere al performanţelor.

De exemplu, dacă analizorul lexical este implementat în forma comandată de către analizorul sintactic, atunci el va fi apelat pentru fiecare atom lexical din codul sursă.

Rezultă deci că această componentă trebuie să fie foarte eficientă.

Căutarea liniară sau utilizarea unei succesiuni foarte lungi de instrucţiuni “if” la procesarea unui atom lexical trebuie evitate.

În acest sens toate tabele care vor fi construite vor fi implementate prin tabele de dispersie (tabele hash) sau prin tabele indexate.

9

O tabelă hash este o structură de date care utilizează o funcţie de hash pentru a mapa valorile de identificare (numite chei), de exemplu numele unui identificator la valorile asociate, de exemplu tipul acestuia, valoarea şi domeniul de valabilitate.

Funcţia hash permite transformarea cheii într-un index al unui element dintr-un vector în care se află valorile corespunzătoare.

Este de preferat ca funcţia de hash să permită maparea fiecărei chei la un index unic în vectorul de valori. În practică însă nu se poate găsi întotdeauna o astfel de funcţie. De aceea se utilizează listele de coliziuni: listele de valori pentru cheile care au aceeaşi valoare hash, implementate prin liste simplu/dublu înlănţuite.

Căutarea în listele de coliziuni va fi o căutare secvenţială.

10

11

Analizorul lexical ar trebui să ofere şi o bună diagnosticare a erorilor care survin la analiză, precum şi un mecanism eficient de tratare a acestora.

Ex: ◦ Dacă a fost folosită o constantă numerică cu valoarea

mai mare decât valoarea maximă acceptată de către limbaj, atunci analizorul lexical ar trebui să emită un mesaj în acest sens şi să înlocuiască valoarea constantei cu valoarea maximă.

◦ Dacă a fost folosit un şir de caractere cu o lungime mai mare decât lungimea maximă acceptată, atunci analizorul lexical trebuie să emită un mesaj în acest sens şi să trunchieze şirul la lungimea acceptată.

12

În vederea generării de mesaje de eroare sau de atenţionare cât mai utile, analizorul lexical trebuie să păstreze şi informaţii privind locaţia în codul sursă a fiecărui atom lexical.

Informaţiile de poziţie sunt completate în câmpuri special create din tabela corespunzătoare.

13

A scrie un analizor lexical înseamnă a scrie un program care este capabil să recunoască şi să extragă toate cuvintele (secvenţele de caractere) care aparţin limbajului supus analizei.

Cum putem defini un limbaj? ◦ Expresii regulate ◦ Automate finite: maşini abstracte capabile să recunoască

limbaje ◦ Automate finite deterministe: pot fi foarte uşor

convertite în programe

În plus: ◦ Putem translata orice expresie regulată într-un AF ◦ Pentru orice AF putem construi un AFD echivalent ◦ Orice AFD poate fi tradus într-un program

14

Fie sirul : while a-b>0 do b:=b+7

1. Sirul transliterat

c.l c.l c.l c.l c.l c.b c.l c.o c.l c.o c.c c.b c.l c.l c.l c.o c.o c.l c.o c.c

w h i l e _ a - b > 0 _ d o b : = b + 7

2. Sirul explorat

Clasa identif id op id op identif id atrib id op cif

Valoare while a - b > do b := b + 7

3. Sirul selectat

Clasa while id operat id operat cifra do id operat id operat Cifra Valoare - 108 - 112 > 2 - 112 := 112 + 4

TS TS TC TS TS TC

15

Fie gramatica de atomi lexicali :

G1: 8. <atom> -> <id> | <const> | <op> | <delimitator> | <comentariu>

G2: 7. <id> -> <lit> | <id><lit> | <id><cifra>

6. <const> -> <cifra> | <const><cifra>

5. <op> -> + | * | < | <= | >= | > | = | <>

4. <delimitator> -> ; | blk | <delimitator> blk

3. <comentariu> -> */ …blk…/*

G3 : 2. <litera> -> A| …| Z

1. <cifra> -> 0 | … | 9

Gramatica se poate transforma in 3 gramatici regulate la care intrarea uneia este iesirea alteia G1 , G2 ,G3

16

x din {A,..,Z} (lit, x)

blk (bl, blk)

; (pv, ;)

y din {0, …,9} (cif, y)

+ (pl, +)

* (mul, *)

/ (sl, /)

< (ls, <)

> (gt, >)

= (eq, =)

17

lit lit,cif iesire (id, -)

cif cif iesire (const, -)

pl iesire (op, pl)

sl altceva iesire (op,mul)

mul sl iesire (com, -)

eq orice orice iesire (op,eq)

pv iesire (op,pv)

blk blk iesire (bel, blk)

ls iesire (op, ls)

eq iesire (op, le)

gt iesire (op, ne)

gt iesire (op,gt)

eq iesire (op,ge)

18

del zona de selectie pv (dl, pv)

blk

com

op (op,{mul,pl...})

const (const, pointer TC)

id id (id, pointer TS)

if (if, -)

begin (begin, -)

SEL

CAUTC

CAUT CVR

ATOMI LEXICALI

19

Automatul finit nedeterminist echivalent expresiei regulate:

este:

20

21

Automatul finit determinist echivalent celui anterior (nedeterminist) este:

# înseamnă: în cazul oricărei alte intrări, mergi la starea 25.

22

23

http://inst.eecs.berkeley.edu/~cs164/sp10/notes/notes.pdf

http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx

24