Software is all about logic. Programarea a câștigat o reputație de a fi un domeniu care este greu de matematică și ecuații nebun. Și informatica pare să fie în centrul acestei concepții greșite.

sigur, există unele matematică și există unele formule — dar nici unul dintre noi de fapt, trebuie să aibă doctorat în calcul pentru ca noi să înțelegem cum funcționează mașinile noastre! De fapt, o mulțime de reguli și paradigme pe care le învățăm în procesul de scriere a codului sunt aceleași reguli și paradigme care se aplică conceptelor complexe de informatică. Și uneori, aceste idei provin de fapt din informatică, și pur și simplu nu am știut-o niciodată.

indiferent de limbajul de programare pe care îl folosim, atunci când majoritatea dintre noi scriem codul nostru, ne propunem să încapsulăm lucruri distincte în clase, obiecte sau metode, separând în mod intenționat diferitele părți ale codului nostru. Cu alte cuvinte, știm că, în general, este bine să ne împărțim codul astfel încât o clasă, un obiect sau o metodă să fie preocupată și responsabilă doar de un singur lucru. Dacă nu am face acest lucru, lucrurile ar putea deveni super dezordonate și împletite într-o mizerie a unei rețele. Uneori, acest lucru se întâmplă încă, chiar și cu separarea preocupărilor.

după cum se dovedește, chiar și funcționarea interioară a computerelor noastre urmează paradigme de design foarte similare. Compilatorul nostru, de exemplu, are părți diferite și fiecare parte este responsabilă pentru gestionarea unei părți specifice a procesului de compilare. Am întâlnit un pic din asta săptămâna trecută, când am aflat despre parser, care este responsabil pentru crearea arborilor de analiză. Dar analizorul nu poate fi însărcinat cu totul.

parserul are nevoie de ajutor de la prietenii săi și este în sfârșit timpul să învățăm cine sunt!

când am aflat recent despre parsare, ne-am scufundat degetele de la picioare în gramatică, sintaxă și modul în care compilatorul reacționează și răspunde la aceste lucruri într-un limbaj de programare. Dar nu am subliniat niciodată ce este exact un compilator! Pe măsură ce intrăm în funcționarea interioară a procesului de compilare, vom învăța multe despre designul compilatorului, deci este vital pentru noi să înțelegem despre ce vorbim exact aici.

compilatoarele pot suna cam înfricoșător, dar slujbele lor nu sunt de fapt prea complexe pentru a fi înțelese — mai ales atunci când împărțim diferitele părți ale unui complier în părți de dimensiuni mușcate.

dar mai întâi, să începem cu cea mai simplă definiție posibilă. Un compilator este un program care citește codul nostru (sau orice cod, în orice limbaj de programare) și îl traduce într-o altă limbă.

compilator: o definiție.

În general vorbind, un compilator este într-adevăr doar vreodată de gând să traducă codul dintr-un limbaj de nivel înalt într-un limbaj de nivel inferior. Limbile de nivel inferior în care un compilator traduce codul sunt adesea denumite cod de asamblare, cod mașină sau cod obiect. Merită menționat faptul că majoritatea programatorilor nu se ocupă sau nu scriu niciun cod de mașină; mai degrabă, depindem de compilator pentru a lua programele noastre și a le traduce în cod de mașină, ceea ce computerul nostru va rula ca program executabil.

ne putem gândi la compilatoare ca la intermediarul dintre noi, programatori și computerele noastre, care pot rula programe executabile numai în limbi de nivel inferior.

compilatorul face munca de traducere a ceea ce vrem să se întâmple într-un mod care este ușor de înțeles și executabil de mașinile noastre.

fără compilator, am fi obligați să comunicăm cu computerele noastre scriind codul mașinii, care este incredibil de ilizibil și greu de descifrat. Codul mașinii poate arăta adesea ca o grămadă de 0 și 1 pentru ochiul uman-totul este binar, îți amintești? – ceea ce face foarte greu pentru a citi, scrie, și depanare. Compilatorul a abstractizat codul mașinii pentru noi ca programatori, deoarece ne-a făcut foarte ușor să nu ne gândim la codul mașinii și să scriem programe folosind Limbi mult mai elegante, clare și ușor de citit.

vom continua să despachetăm din ce în ce mai multe despre compilatorul misterios în următoarele câteva săptămâni, ceea ce, sperăm, îl va face mai puțin o enigmă în acest proces. Dar, deocamdată, să revenim la întrebarea la îndemână: care sunt cele mai simple părți posibile ale unui compilator?

fiecare compilator, indiferent de modul în care ar putea fi proiectat, are faze distincte. Aceste faze sunt modul în care putem distinge părțile unice ale compilatorului.

analiza sintaxei: prima fază a unui compilator

am întâlnit deja una dintre fazele din aventurile noastre de compilare când am aflat recent despre parser și parse copaci. Știm că parsarea este procesul de a lua o anumită intrare și de a construi un arbore de analiză din ea, care este uneori denumit actul de parsare. După cum se dovedește, lucrarea de analiză este specifică unei faze din procesul de compilare numită analiză de sintaxă.

cu toate acestea, analizorul nu construiește doar un arbore de analiză din aer subțire. Are ceva ajutor! Ne vom aminti că parserul este dat unele jetoane (de asemenea, numite terminale), și construiește un arbore de analiză din aceste jetoane. Dar de unde primesc acele jetoane? Din fericire pentru analizor, nu trebuie să funcționeze în vid; în schimb, are ceva ajutor.

aceasta ne aduce la o altă fază a procesului de compilare, una care vine înainte de faza de analiză a sintaxei: faza de analiză lexicală.

fazele inițiale a unui compilator

termenul „lexical” se referă la semnificația unui cuvânt izolat de propoziția care îl conține și indiferent de contextul său gramatical. Dacă încercăm să ghicim propriul nostru sens bazat exclusiv pe această definiție, am putea afirma că faza de analiză lexicală are legătură cu cuvintele/termenii individuali din program și nu are nimic de-a face cu gramatica sau semnificația propoziției care conține cuvintele.

faza de analiză lexicală este primul pas în procesul de compilare. Nu știe sau nu-i pasă de gramatica unei propoziții sau de semnificația unui text sau program; tot ce știe este semnificația cuvintelor în sine.

analiza lexicală trebuie să aibă loc înainte ca orice cod dintr-un program sursă să poată fi analizat. Înainte de a putea fi citit de parser, un program trebuie mai întâi scanat, împărțit și grupat împreună în anumite moduri.

când am început să analizăm faza de analiză a sintaxei săptămâna trecută, am aflat că arborele de analiză este construit uitându-ne la părți individuale ale propoziției și descompunând expresiile în părți mai simple. Dar în timpul fazei de analiză lexicală, compilatorul nu cunoaște sau nu are acces la aceste „părți individuale”. Mai degrabă, trebuie mai întâi să le identifice și să le găsească, apoi să facă lucrarea de împărțire a textului în bucăți individuale.

de exemplu, când citim o propoziție din Shakespeare caTo sleep, perchance to dream., știm că spațiile și punctuația împart „cuvintele” unei propoziții. Acest lucru este, desigur, pentru că am fost instruiți pentru a citi o propoziție, „lex” ea, și analiza-l pentru gramatica.

dar, pentru un compilator, aceeași propoziție ar putea arăta astfel prima dată când o Citește:Tosleepperhachancetodream. Când citim această propoziție, este puțin mai greu pentru noi să determinăm care sunt „cuvintele” reale! Sunt sigur că compilatorul nostru simte la fel.

Deci, cum se ocupă mașina noastră de această problemă? Ei bine, în timpul fazei de analiză lexicală a procesului de compilare, face întotdeauna două lucruri importante: scanează codul și apoi îl evaluează.

cei doi pași a procesului de analiză lexicală!

activitatea de scanare și evaluare poate fi uneori adunate împreună într-un singur program, sau ar putea fi două programe separate, care depind unul de altul; este într-adevăr doar o chestiune de modul în care orice complier sa întâmplat să fie proiectat. Programul din cadrul compilatorului care este responsabil pentru efectuarea lucrărilor de scanare și evaluare este adesea denumit lexer sau tokenizer, iar întreaga fază de analiză lexicală este uneori numită procesul de lexing sau tokenizare.

pentru a scana, poate pentru a citi

primul dintre cei doi pași de bază în analiza lexicală este scanarea. Ne putem gândi la scanare ca la lucrarea de a „citi” de fapt un text de intrare. Amintiți-vă că acest text de intrare ar putea fi un șir, propoziție, expresie sau chiar un întreg program! Nu contează cu adevărat, pentru că, în această fază a procesului, este doar o pată uriașă de personaje care nu înseamnă nimic încă și este o bucată contiguă.

să ne uităm la un exemplu pentru a vedea cum se întâmplă exact acest lucru. Vom folosi propoziția noastră originală, To sleep, perchance to dream., care este textul nostru sursă sau codul sursă. Pentru compilatorul nostru, acest text sursă va fi citit ca text de intrare care arată ca Tosleep,perchancetodream., care este doar un șir de caractere care nu a fost încă descifrat.

procesul de scanare, Etapa 1.

primul lucru pe care compilatorul nostru trebuie să-l facă este să împartă acel blob de text în cele mai mici bucăți posibile, ceea ce va face mult mai ușor să identificăm unde sunt cuvintele din blob de text.

cel mai simplu mod de a scufunda o bucată uriașă de text este Citind-o încet și sistematic, câte un caracter pe rând. Și exact asta face compilatorul.

de multe ori, procesul de scanare este gestionat de un program separat numit scaner, a cărui sarcină unică este de a face munca de citire a unui fișier sursă/text, câte un caracter la un moment dat. Pentru scanerul nostru, nu contează cu adevărat cât de mare este textul nostru; tot ce va vedea când „citește” fișierul nostru este un caracter la un moment dat.

Iată cum va fi citită propoziția shakespeariană de către scanerul nostru:

scanarea proces, pasul 2.

vom observa căTo sleep, perchance to dream. a fost împărțit în caractere individuale de scanerul nostru. Mai mult, chiar și spațiile dintre cuvinte sunt tratate ca personaje, la fel ca punctuația din propoziția noastră. Există, de asemenea, un caracter la sfârșitul acestei secvențe, care este deosebit de interesant: eof. Acesta este caracterul „sfârșitul fișierului”și este similar cu tabspace și newline. Deoarece textul nostru sursă este doar o singură propoziție, atunci când scanerul nostru ajunge la sfârșitul fișierului (în acest caz, sfârșitul propoziției), citește sfârșitul fișierului și îl tratează ca pe un personaj.

deci, în realitate, când scanerul nostru a citit textul nostru de intrare, l-a interpretat ca caractere individuale care au dus la acest lucru:.

procesul de scanare, Etapa 3.

acum că scanerul nostru a citit și împărțit textul sursă în cele mai mici părți posibile, va avea un timp mult mai ușor de a afla „cuvintele” din propoziția noastră.

apoi, scanerul trebuie să se uite la caracterele sale divizate în ordine și să determine ce caractere sunt părți ale unui cuvânt și care nu sunt. Pentru fiecare caracter pe care scanerul îl citește, acesta marchează linia și poziția în care acel caracter a fost găsit în textul sursă.

imaginea prezentată aici ilustrează acest proces pentru propoziția noastră shakespeariană. Putem vedea că scanerul nostru marchează linia și coloana pentru fiecare caracter din propoziția noastră. Ne putem gândi la reprezentarea liniei și coloanei ca la o matrice sau matrice de caractere.

reamintim că, deoarece fișierul nostru are o singură linie în el, totul trăiește la linia0. Cu toate acestea, pe măsură ce ne croim drum prin propoziție, coloana fiecărui caracter crește. De asemenea, merită menționat faptul că, deoarece scanerul nostru citește spacesnewlineseof și toate semnele de punctuație ca caractere, acestea apar și în tabelul nostru de caractere!

procesul de scanare, pasul 4.

odată ce textul sursă a fost scanat și marcat, compilatorul nostru este gata să transforme aceste caractere în cuvinte. Deoarece scanerul nu știe doar unde sunt spacesnewlines și eof din fișier, dar și unde trăiesc în raport cu celelalte caractere care le înconjoară, poate scana prin caractere și le poate împărți în șiruri individuale, după cum este necesar.

în exemplul nostru, scanerul va analiza caractereleT, apoio și apoi unspace. Când găsește un spațiu, acesta va împărți To în propriul său cuvânt — cea mai simplă combinație de caractere posibilă înainte ca scanerul să întâlnească un spațiu.

este o poveste similară pentru următorul cuvânt pe care îl găsește, care estesleep. Cu toate acestea, în acest scenariu, citește s-l-e-e-p și apoi citește un ,, un semn de punctuație. Deoarece această virgulă este flancată de un caracter (p) și un space de ambele părți, virgula este, în sine, considerată a fi un „cuvânt”.

atât cuvântulsleep cât și simbolul de punctuație, se numesc lexeme, care sunt subșiruri textul sursă. O lexemă este o grupare a celor mai mici secvențe posibile de caractere din Codul nostru sursă. Lexemele unui fișier sursă sunt considerate „cuvintele” individuale ale fișierului în sine. Odată ce scanerul nostru termină citirea caracterelor unice ale fișierului nostru, acesta va returna un set de lexeme care arată astfel: .

scanarea proces, pasul 5.

observați cum scanerul nostru a luat o pată de text ca intrare, pe care nu a putut să o citească inițial și a continuat să o scaneze o dată caracter la un moment dat, simultan citind și marcând conținutul. Apoi a procedat la împărțirea șirului în cele mai mici lexeme posibile folosind spațiile și punctuația dintre caractere ca delimitatori.

cu toate acestea, în ciuda tuturor acestor lucrări, în acest moment al fazei de analiză lexicală, scanerul nostru nu știe nimic despre aceste cuvinte. Sigur, se împarte textul în cuvinte de diferite forme și mărimi, dar în ceea ce privește ceea ce aceste cuvinte sunt scanerul nu are nici o idee! Cuvintele ar putea fi un șir literal, sau ar putea fi un semn de punctuație, sau ar putea fi cu totul altceva!

scanerul nu știe nimic despre cuvintele în sine sau despre ce „tip” de cuvânt sunt. Știe doar unde se termină și încep cuvintele în textul însuși.

aceasta ne pregătește pentru a doua fază a analizei lexicale: evaluarea. După ce ne — am scanat textul și am împărțit codul sursă în unități lexeme individuale, trebuie să evaluăm cuvintele pe care scanerul ni le-a returnat și să ne dăm seama cu ce tipuri de cuvinte avem de-a face-în special, trebuie să căutăm cuvinte importante care înseamnă ceva special în limba pe care încercăm să o compilăm.

evaluarea părților importante

odată ce am terminat de scanat textul sursă și am identificat lexemele noastre, va trebui să facem ceva cu „cuvintele”noastre lexeme. Aceasta este etapa de evaluare a analizei lexicale, care este adesea menționată în complier design ca procesul de lexing sau tokenizing intrarea noastră.

ce înseamnă pentru a evalua codul scanat?

când evaluăm codul scanat, tot ce facem este să aruncăm o privire mai atentă la fiecare dintre lexemele generate de scanerul nostru. Compilatorul nostru va trebui să se uite la fiecare cuvânt lexeme și să decidă ce fel de cuvânt este. Procesul de a determina ce fel de lexeme fiecare „cuvânt” din textul nostru este modul în care compilatorul nostru transformă fiecare lexeme individuale într-un jeton, tokenizând astfel șirul nostru de intrare.

am întâlnit prima dată jetoane înapoi când am fost de învățare despre copaci analiza. Jetoanele sunt simboluri speciale care se află la baza fiecărui limbaj de programare. Jetoanele, cum ar fi(, ), +, -, if, else, then, Toate ajută un compilator să înțeleagă modul în care diferite părți ale unei expresii și diferite elemente se raportează între ele. Parserul, care este esențial pentru faza de analiză a sintaxei, depinde de primirea jetoanelor de undeva și apoi transformă acele jetoane într-un arbore de analiză.

Jetoane: o definiție.

Ei bine, ghici ce? În sfârșit ne-am dat seama de „undeva”! După cum se dovedește, jetoanele care sunt trimise parserului sunt generate în faza de analiză lexicală de către tokenizer, numit și lexer.

Tokenizing sentința noastră shakespeariană !

deci, cum arată exact un jeton? Un simbol este destul de simplu și este de obicei reprezentat ca o pereche, constând dintr-un nume de simbol și o anumită valoare (care este opțională).

de exemplu, dacă ne tokenizăm șirul shakespearian, am ajunge la jetoane care ar fi în mare parte literali și separatori de coarde. Am putea reprezenta lexema "dream”ca un simbol ca acesta:<string literal, "dream">. Într-un mod similar, am putea reprezenta lexema . ca simbol, <separator, .>.

vom observa că fiecare dintre aceste token — uri nu modifică deloc lexema-ci pur și simplu le adaugă informații suplimentare. Un jeton este lexem sau unitate lexicală cu mai multe detalii; în mod specific, detaliul adăugat ne spune ce categorie de jeton (ce tip de „cuvânt”) avem de-a face.

acum că ne-am tokenizat propoziția shakespeariană, putem vedea că nu există atât de multă varietate în tipurile de Jetoane din fișierul nostru sursă. Propoziția noastră avea doar șiruri și semne de punctuație în ea-dar acesta este doar vârful aisbergului token! Există o mulțime de alte tipuri de „cuvinte” în care o lexemă ar putea fi clasificată.

forme comune de jetoane găsite în codul nostru sursă.

tabelul prezentat aici ilustrează unele dintre cele mai comune jetoane pe care compilatorul nostru le-ar vedea atunci când citește un fișier sursă în aproape orice limbaj de programare. Am văzut exemple de literals, care poate fi orice șir, număr sau logică/valoare booleană, precum și separators, care sunt orice tip de punctuație, inclusiv bretele ({}) și paranteze (()).

However, there are also keywords, which are terms that are reserved in the language (such as ifvarwhilereturn), as well as operators, which operate on arguments and return some value ( +-x/). De asemenea, am putea întâlni lexeme care ar putea fi tokenizate ca identifiers, care sunt de obicei nume variabile sau lucruri scrise de utilizator/programator pentru a face referire la altceva, precum și , care ar putea fi comentarii de linie sau bloc scrise de utilizator.

propoziția noastră originală ne-a arătat doar două exemple de Jetoane. Să rescriem propoziția noastră pentru a citi în schimb: var toSleep = "to dream";. Cum ar putea compilatorul nostru Lex această versiune a lui Shakespeare?

lexer tokenize această propoziție?

aici, vom vedea că avem o varietate mai mare de Jetoane. Avem unkeyword învar, unde declarăm o variabilă și unidentifiertoSleep, care este modul în care denumim variabila noastră sau facem referire la valoarea viitoare. Următorul este =, care este un operator jeton, urmat de șirul literal "to dream". Declarația noastră se termină cu un; separator, indicând sfârșitul unei linii și delimitând spațiul alb.

Un lucru important de reținut despre procesul de tokenizare este că nu tokenizăm niciun spațiu alb (spații, linii noi, file, sfârșitul liniei etc.), nici nu-l transmite parserului. Amintiți-vă că numai jetoanele sunt date parserului și vor ajunge în arborele de analiză.

de asemenea, merită menționat faptul că diferite limbi vor avea caractere diferite care constituie spațiu alb. De exemplu, în unele situații, limbajul de programare Python folosește indentarea — inclusiv filele și spațiile — pentru a indica modul în care se schimbă domeniul de aplicare al unei funcții. Deci, tokenizatorul compilatorului Python trebuie să fie conștient de faptul că, în anumite situații, un tab sau space de fapt trebuie să fie tokenizat ca un cuvânt, deoarece de fapt trebuie să fie transmis parserului!

constrângerile lexer vs scanerul.

acest aspect al tokenizerului este o modalitate bună de a contrasta modul în care un lexer/tokenizer este diferit de un scaner. În timp ce un scaner este ignorant și știe doar cum să descompună un text în părțile sale posibile mai mici („cuvintele” sale), un lexer/tokenizer este mult mai conștient și mai precis în comparație.

tokenizer trebuie să cunoască complexitatea și specificațiile limbii care este compilat. Dacătabs sunt importante, trebuie să știe că; dacănewlines poate avea anumite semnificații în limba compilată, tokenizatorul trebuie să fie conștient de aceste detalii. Pe de altă parte, scanerul nici măcar nu știe care sunt cuvintele pe care le împarte, cu atât mai puțin ceea ce înseamnă.

scanerul unui complier este mult mai agnostic lingvistic, în timp ce un tokenizer trebuie să fie specific limbajului prin definiție.

aceste două părți ale procesului de analiză lexicală merg mână în mână și sunt esențiale pentru prima fază a procesului de compilare. Desigur, diferiți complieri sunt proiectați în propriile lor moduri unice. Unele compilatoare fac pasul de scanare și tokenizare într-un singur proces și ca un singur program, în timp ce altele le vor împărți în clase diferite, caz în care tokenizatorul va apela la clasa scanerului atunci când este rulat.

Lexical analiză: un rezumat vizual rapid!

în ambele cazuri, etapa analizei lexicale este foarte importantă pentru compilare, deoarece faza de analiză a sintaxei depinde direct de ea. Și chiar dacă fiecare parte a compilatorului are propriile sale roluri specifice, ele se sprijină una pe cealaltă și depind una de cealaltă — la fel cum fac întotdeauna prietenii buni.

resurse

deoarece există multe moduri diferite de a scrie și proiecta un compilator, există și multe moduri diferite de a-i învăța. Dacă faceți suficiente cercetări cu privire la elementele de bază ale compilării, devine destul de clar că unele explicații intră în detalii mult mai detaliate decât altele, ceea ce poate fi sau nu util. Dacă doriți să aflați mai multe, mai jos sunt o varietate de resurse pe compilatoare — cu accent pe faza de analiză lexicală.

1. Capitolul 4-Crafting interpreți, Robert Nystrom
2. construcție compilator, profesorul Allan Gottlieb
3. bazele compilator, profesorul James Alan Farrell
4. scrierea unui limbaj de programare — Lexer, Andy Balaam
5. note cu privire la modul în care Parsere și compilatoare de lucru, Stephen Raymond Ferg
6. care este diferența dintre un simbol și un lexeme?, StackOverflow