În informatică , analiza lexicală , lexarea , segmentarea sau tokenizarea reprezintă conversia unui șir de caractere (un text) într-o listă de simboluri ( jetoane în engleză). Face parte din prima fază a lanțului de compilare . Aceste simboluri sunt apoi consumate în timpul analizei . Un program care efectuează analize lexicale se numește analizor lexical , tokenizer sau lexer. Un analizator lexical este în general combinat cu un analizor de sintaxă pentru a analiza sintaxa unui text.
Un lexem este o secvență de caractere dintr-un program sursă care se potrivește cu modelul unui simbol lexical și care este analizat de către analizatorul lexical ca instanță a acelui simbol lexical.
Unii autori folosesc termenul „token” pentru a reprezenta atât șirul de caractere procesat de analizorul lexical, cât și structura de date produsă la ieșirea acestei prelucrări.
Termenul „lexemă” în informatică nu are aceeași semnificație ca lexemul în lingvistică . În informatică, definiția sa este similară cu cea a morfemului în lingvistică.
O unitate lexicală sau jeton lexical sau mai simplu jeton este o pereche formată dintr-un nume și o valoare opțională. Denumirea unității lexicale este o categorie de unitate lexicală.
Câteva exemple de nume de unități lexicale care sunt cel mai des întâlnite:
| Numele de familie | Valori |
|---|---|
| identificatori | x, color, UP |
| Cuvinte cheie | if, while, return |
| punctuaţie | }, (, ; |
| operatorii | +, <, = |
| literale | true, 6.02e23, "music" |
Un nume de unitate lexicală poate fi comparat cu conceptul de natură gramaticală .
În limbajele de programare definesc adesea regulile, ca gramatica defineste sintaxa de a adopta. Aceste reguli iau adesea forma unor expresii regulate și definesc secvențele de caractere utilizate pentru a forma lexeme.
Limbile recunoscute printr-o expresie regulată se numesc limbi raționale . Putem asocia un automat finit cu orice expresie regulată . Există, de asemenea, limbaje non-raționale.
Două dintre cele mai importante categorii de unități lexicale sunt caracterele spațiale și comentariile. Ambele sunt definite în gramatica majorității limbilor și acoperite de lexeri, dar sunt considerate cel mai adesea nesemnificative; în cel mai bun caz, separând două jetoane și nu generând niciunul de la sine. Există două excepții majore la acest lucru. În primul rând, așa-numitele limbaje de sintaxă de tip indentare, cum ar fi Python, care delimitează blocuri de cod prin indentare și pentru care caracterele spațiale sunt semnificative și, prin urmare, pot genera jetoane. Apoi, în anumite utilizări ale lexerilor, inclusiv unele instrumente de depanare sau impresie elegantă (pretty-printers engleză), poate fi necesar să se păstreze codul sursă original pentru a fi afișat ulterior utilizatorului.
Numit analizor lexical ( lexer engleză) orice program care efectuează o analiză lexicală.
Analizatorul lexical este obișnuit
Când analizorul lexical detectează un lexem nevalid, raportează o eroare. În contrast, combinațiile de lexeme sunt de obicei lăsate la analiză: de exemplu, un analizor lexical tipic recunoaște parantezele ca lexeme, dar nu verifică dacă o paranteză deschisă "(" este în mod necesar asociată cu o paranteză de închidere ")”.
Analizatorul lexical poate fi scris
Deși lexerele sunt utilizate în principal pentru scrierea compilatoarelor, ele sunt utilizate în proiectarea altor instrumente pentru prelucrarea limbajelor computerului, cum ar fi scame sau sisteme elegante de imprimare ( troff ).
Analiza lexicală este prima fază a proceselor moderne de compilare . Analiza se face de obicei parcurgând textul sursă o singură dată.
Acesta constă în delimitarea și, dacă este posibil, caracterizarea segmentelor șirului de caractere de intrare într-o serie de lexeme care vor fi transmise unei alte forme de analiză.
De exemplu, instrucțiunea sum = 2 + 3;în limbajul C produce după analiza lexicală următoarea listă de simboluri:
| Valoare | Categorie lexicală |
|---|---|
| sumă | nume de utilizator |
| = | operator de misiune |
| 2 | număr întreg literal |
| + | operator de adăugare |
| 3 | număr întreg literal |
| ; | sfârșitul declarației |
Secvența de caractere de intrare, implicit segmentată de spații ca în limbile naturale, a fost transformată într-o listă de șase unități lexicale:
[(identifiant, sum), (opérateur d'affectation, =), (entier littéral, 2), (operator, +), (entier littéral, 3), (fin de déclaration, ;)]
În general, atunci când o unitate lexicală reprezintă mai multe lexeme, analizatorul lexical salvează suficiente informații pentru a putea reproduce lexema originală și a o utiliza în timpul analizei semantice. Analizorul preia aceste informații și le stochează sub forma unui arbore abstract de sintaxă (AST). Acest lucru este necesar pentru a evita pierderea informațiilor în cazul numerelor și identificatorilor.
Lexemele sunt identificate conform regulilor stabilite de analizorul lexical. Printre metodele folosite pentru identificarea lexemelor găsim: expresii regulate , o secvență specifică de caractere numită pavilion , caractere numite separatoare și un dicționar.
Analizorul lexical nu prelucrează, în general, combinații de unități lexicale, această sarcină fiind lăsată pe seama analizatorului. De exemplu, un analizor lexical tipic poate recunoaște și procesa paranteze, dar nu poate să le numere și, prin urmare, să verifice dacă fiecare paranteză de închidere ")" se potrivește cu o paranteză deschisă precedentă "(".
Analiza lexicală a unui șir de caractere are loc în trei etape:
Primul pas, scanarea, este de obicei realizat de o mașină de stat . Acest automat are informațiile necesare procesării tuturor secvențelor de caractere care pot fi conținute într-un lexem (fiecare caracter al acestor secvențe fiind un lexem). De exemplu, un int poate conține toate secvențele posibile de cifre . În multe cazuri, primul caracter semnificativ citit poate fi folosit pentru a deduce natura lexemului curent și fiecare caracter ulterior va fi adăugat la valoarea simbolului până când este citit un caracter inacceptabil. Cu toate acestea, în unele limbi, regula poate fi mai complexă și poate necesita o retrogradare a caracterelor deja citite. De exemplu, în C , un caracter „L” nu este suficient pentru a diferenția un identificator care începe cu „L” de un literal format din acest singur caracter.
Un lexem este doar o serie de caractere caracterizate printr-un tip. Pentru a construi o unitate lexicală analizatorul lexical necesită un al doilea pas, evaluarea, care produce o valoare. Tipul lexemului combinat cu valoarea acestuia este ceea ce constituie un simbol, care poate fi apoi livrat unui analizor. Unele lexeme, precum cele care reprezintă punctuația, nu au valoare reală, astfel încât funcția lor de evaluare poate returna o valoare zero; este nevoie doar de tipul lor. La fel, evaluarea poate elimina complet un lexem, ascunzându-l de analizor, așa cum poate fi cazul pentru caracterele spațiale sau comentarii. Evaluarea identificatorilor este adesea simplă, prin trecerea directă a șirului de caractere care le constituie în valoare, dar pentru valorile numerice analizatorul lexical poate alege să le transforme în unitate lexicală sub formă de șiruri de caractere (amânând analiza semantică de procesare a acestora) sau să le evalueze el însuși.
Chiar dacă este posibil, sau chiar necesar în cazul unui număr mic de lexeme, să scrieți un analizor lexical „manual”, acestea sunt adesea generate de instrumente automate. Aceste instrumente acceptă în general expresii regulate care descriu lexeme autorizate. Fiecare expresie regulată este asociată cu o regulă de producție pentru gramatica formală a limbii evaluate. Aceste instrumente pot genera cod sursă care poate fi compilat și executat sau poate crea o tabelă de tranziție de stare pentru o mașină de stare.
O expresie regulată reprezintă o versiune compactă a modelului pe care lexemele trebuie să îl urmeze pentru a constitui o unitate lexicală validă. De exemplu, pentru o limbă bazată pe limba franceză, un identificator poate fi orice caracter alfabetic sau un subliniere urmat de orice succesiune de cifre alfanumerice sau caractere ASCII și / sau puncte de subliniere. Această secvență poate fi reprezentată de următorul șir de caractere [a-zA-Z_][a-zA-Z_0-9]*.
Expresiile regulate și automatele finite pe care le generează nu sunt suficient de puternice pentru a gestiona tipare recursive precum cele găsite în limbile Dyck . Aceste tratamente sunt lăsate la latitudinea analizatorului de sintaxă.
În limbi mai vechi, cum ar fi ALGOL , prima etapă a compilării s-a numit reconstrucție de linie, care a constat în scanarea textului după cuvinte cheie și eliminarea spațiilor și comentariilor . Analizele lexicale și sintactice au fost efectuate de un singur program parser-lexer.
De obicei, analiza lexicală funcționează la nivel de cuvânt . Cu toate acestea, uneori poate fi dificil să diferențiem ce este un „cuvânt”. Adesea analizatorii lexicali se bazează pe euristici simple, de exemplu:
În limbile care utilizează spații inter-cuvinte (ca majoritatea limbajelor de programare și a limbajelor naturale care utilizează alfabetul latin) această abordare este ușor de implementat. În ciuda acestui fapt, există mai multe cazuri ( contracții , emoticoane , cuvinte compuse, URIuri , etc. ) , care necesită euristice mai complexe pentru a fi procesate de către analizorul lexical. Un exemplu clasic este secvența de caractere „bazată pe New York” care în engleză formează un singur cuvânt, dar care naiv poate fi separată în două sau chiar trei lexeme.
Analiza lexicală poate fi deosebit de dificilă pentru limbile naturale scrise în scriptio continua pentru care nu există niciun simbol pentru punctuație sau separarea lexemelor ca în greaca veche sau în chineză .
Unele limbi, cum ar fi Python, folosesc indentare pentru a delimita blocuri de cod . Analizatorul lexical trebuie, prin urmare, să genereze o unitate lexicală INDENTARĂ când indentarea crește și o unitate lexicală DEDENTĂ atunci când este redusă. Aceste unități lexicale corespund celor generate la citirea parantezelor pătrate deschizând "{" și închizând "}" în limbi precum C. Pentru a putea fi luat în considerare de către analizor, acesta trebuie să poată păstra starea curentă. indentare (deoarece blocurile pot fi cuibărite unul în celălalt) ceea ce face ca gramatica limbajului analizat să fie contextuală . INDENT-DEDENT depinde de context (în acest caz nivelul de indentare anterior).
Analizoarele lexicale sunt adesea generate de instrumente numite generatoare de analize lexicale . Unul dintre cele mai frecvent utilizate este Lex , împreună cu generatorul de parser Yacc și echivalenții lor liberi Flex și Bison . Acești generatori sunt o formă de limbaj dedicat , luând ca intrare o specificație lexicală (de obicei expresii regulate și unele etichete) și scoțând un lexer.
Aceste instrumente permit dezvoltarea rapidă a unui analizor lexical funcțional.
Performanța lexerilor, în special în limbile stabile în care lexerul este foarte des menționat (cum ar fi C sau HTML) este o preocupare majoră. Lexerele generate utilizând Lex / Flex sunt considerate destul de rapide, dar în unele cazuri pot fi de două până la trei ori mai lente decât lexerele scrise „manual” sau instrumentele precum re2c.
În cazul limbajelor de programare, acest algoritm rulează adesea în timp liniar în raport cu dimensiunea cuvântului de intrare. Cu toate acestea, există cazuri patologice în care algoritmul rulează în timp pătratic, precum acesta: cu două lexeme: a și a ... ab, intrarea a n necesită algoritmul să meargă la sfârșitul cuvântului pentru fiecare a pe care îl recunoaște . Complexitatea este apoi pătratică.
Există și alți algoritmi capabili să analizeze un cuvânt în timp liniar.