Analizare
În informatică , analiza , analiza sintactică sau parsificarea este un proces care analizează un flux continuu de date primite (de intrare , de exemplu citite dintr-un fișier sau o tastatură ) pentru a determina corectitudinea structurii sale datorită unei gramatici formale date. Un analizor este un program care efectuează această sarcină.
Termenul de analiză provine de la latina pars, care indică o parte a unui discurs mai mare.
Analizatorii nu sunt de obicei scrise manual, ci sunt construite prin generatoare de analize .
De obicei, termenul italian este folosit pentru a se referi la recunoașterea unei gramatici și la construcția consecventă a unui arbore parse , care arată regulile utilizate în timpul recunoașterii din intrare; arborele analizat este apoi vizitat (chiar de mai multe ori) în timpul executării unui interpret sau compilator .
Cu toate acestea, în majoritatea limbilor, analiza funcționează pe o succesiune de jetoane în care analizorul lexical tăie intrarea . Prin urmare, termenul englezesc este adesea folosit pentru a indica ansamblul analizei lexicale și analizei sintactice propriu-zise.
Descriere
Exemplu
Următorul exemplu arată un caz obișnuit de analiză a unui limbaj pentru un computer (sau calculator) cu două niveluri de gramatică: lexical și sintactic.
După cum sa menționat, primul pas este generarea de simboluri sau analiza lexicală . De exemplu, intrarea poate fi următoarea „12 * (3 + 4) ^ 2”, în acest caz analizorul împarte intrarea în jetoane după cum urmează: 12, *, (, 3, +, 4,), ^ și 2, fiecare dintre ele fiind un simbol cu semnificație într-o expresie matematică. Analizorul poate conține reguli care îi spun că caracterele *, +, ^, (și) determină pornirea unui nou jeton, astfel încât jetoanele precum "12 *" sau "(3" nu vor fi generate.
Analiza corectă primește secvența de jetoane ca intrare și verifică dacă jetoanele formează expresii valide. Această lucrare se face pe baza unei gramatici fără context, care definește recursiv componentele care determină o expresie și ordinea în care acestea trebuie să apară.
Ultimul pas este analiza semantică , care găsește implicațiile noii expresii validate și efectuează acțiunile rezultate. În cazul calculatorului, acțiunea este de a evalua expresia; un compilator, pe de altă parte, poate genera limbajul mașinii care efectuează funcționalitatea prezentă în cod.
Tipuri de parsere
Sarcina analizatorului este, în esență, de a determina dacă și cum poate fi derivată intrarea din simbolul inițial cu regulile gramaticii formale. Acest lucru se poate face în esență în două moduri:
- Analiză de sus în jos - un analizor poate începe cu simbolul principal și poate încerca să-l transforme în intrare. Intuitiv, analizorul începe cu cel mai mare element și îl împarte în părți din ce în ce mai mici. Analizatorii LL sunt exemple de analizatori de sus în jos.
- Analiză de jos în sus - un analizor poate începe cu intrarea și poate încerca să îl rescrie la simbolul inițial. Intuitiv, analizorul încearcă să găsească simbolul cel mai de bază, apoi procesează elementele care îl conțin și așa mai departe. Analizatorii LR sunt exemple de analizatori de jos în sus.
O altă distincție importantă este aceea dintre analizoarele care generează prin derivarea din stânga sau prin derivarea din dreapta . Analizatorii LL generează o derivare din stânga, iar LR analizează o derivare din cea mai dreaptă.
Limbaje de programare
În general, analizoarele sunt folosite cu limbaje de programare , care au gramatici simple și obișnuite; analizatorii de acest tip tind să se bazeze pe gramatici fără context, deoarece puteți scrie analize rapide și eficiente cu aceste gramatică.
De fapt, gramaticile fără context nu pot descrie singur cele mai frecvent utilizate limbaje de programare. În mod informal, motivul este că memoria oricărui limbaj este limitată; gramatica nu își poate aminti prezența unui construct după o lungime de intrare arbitrară, este necesar, de exemplu, în acele limbi în care numele pot fi referite.
Cu toate acestea, utilizarea gramaticilor mai puternice, cum ar fi gramaticile dependente de context , înseamnă pierderea eficienței. În consecință, este o strategie obișnuită să se utilizeze gramaticile fără context pentru o versiune „relaxată” (cu mai puține constrângeri) a limbajului. Aceste gramatici vor accepta toate constructele valide ale limbajului luat în considerare, precum și alte constructe nevalide care sunt eliminate în timpul analizei semantice a intrării. De exemplu, gramatica ar putea accepta un program care utilizează o variabilă care nu a fost declarată anterior.
Bibliografie
- ( EN ) Parsing , în Free On-line Dictionary of Computing , Denis Howe. Disponibil sub licență GFDL
- Compilatoare: principii, tehnică și instrumente . Aho, Lam, Sethi, Ullman. Addison-Wesley , (ediția a II-a) 2006. ISBN 0-321-48681-1
- Limbaje formale și compilare . Crespi Reghizzi. Pitagora Editrice , 2006. ISBN 978-8837116323
Elemente conexe
Analizator de sus în jos
Analizator de jos în sus
Generatoare de analizori
linkuri externe
- Simulator de analiză Acest simulator este conceput pentru a ajuta elevul să înțeleagă în toată simplitatea diferiții pași pentru construirea tabelelor de analiză. Util pentru cei care doresc să practice pe această temă
- TFunctionParser Un analizor matematic complet (mai mult de 90 de funcții și operații)
- UCalc Fast Math Parser Un analizor de expresie, comercial
- muParser Un analizor de expresie matematică open source
- Tehnici de analiză - Un ghid practic de Dick Grune și Ceriel JH Jacobs.
- Analiza de precedență a operatorului [ link rupt ] Un analizor de expresie matematică open source în limbaj C.
- Torino University Parser Parser of natural language, italian, open source, in Common Lisp language (de Leonardo Lesmo, Universitatea din Torino)
- Stanford Parser Parser din Stanford
