Free Press

Arborele de sintaxă abstractă este o structură de date utilizată pe scară largă în compilatoare pentru a reprezenta structura codului de program. Un AST este, de obicei, rezultatul fazei de analiză sintactică a unui compilator. Acesta servește adesea ca o reprezentare intermediară a programului prin mai multe etape pe care compilatorul le necesită și are un impact puternic asupra rezultatului final al compilatorului.

MotivațieEditare

Un AST are mai multe proprietăți care ajută la etapele ulterioare ale procesului de compilare:

• Un AST poate fi editat și îmbunătățit cu informații precum proprietăți și adnotări pentru fiecare element pe care îl conține. O astfel de editare și adnotare este imposibilă în cazul codului sursă al unui program, deoarece ar implica modificarea acestuia.
• În comparație cu codul sursă, un AST nu include semne de punctuație și delimitatori neesențiali (paranteze, punct și virgulă, paranteze etc.).
• Un AST conține, de obicei, informații suplimentare despre program, datorită etapelor consecutive de analiză efectuate de compilator. De exemplu, poate stoca poziția fiecărui element în codul sursă, permițând compilatorului să tipărească mesaje de eroare utile.

SAST-urile sunt necesare din cauza naturii inerente a limbajelor de programare și a documentației acestora. Limbajele sunt adesea ambigue prin natura lor. Pentru a evita această ambiguitate, limbajele de programare sunt adesea specificate ca o gramatică fără context (CFG). Cu toate acestea, există adesea aspecte ale limbajelor de programare pe care o CFG nu le poate exprima, dar care fac parte din limbaj și sunt documentate în specificația acestuia. Acestea sunt detalii care necesită un context pentru a le determina validitatea și comportamentul. De exemplu, dacă un limbaj permite declararea de noi tipuri, un CFG nu poate prezice numele unor astfel de tipuri și nici modul în care acestea ar trebui utilizate. Chiar și în cazul în care un limbaj are un set predefinit de tipuri, aplicarea unei utilizări corecte necesită, de obicei, un anumit context. Un alt exemplu este cel al tipizării ratelor, în care tipul unui element se poate schimba în funcție de context. Supraîncărcarea operatorilor este un alt caz în care utilizarea corectă și funcția finală sunt determinate în funcție de context. Java oferă un exemplu excelent, unde operatorul „+” reprezintă atât adunarea numerică, cât și concatenarea șirurilor de caractere.

Deși există și alte structuri de date implicate în funcționarea internă a unui compilator, AST îndeplinește o funcție unică. În timpul primei etape, etapa de analiză sintactică, un compilator produce un arbore de parsare. Acest arbore de parse poate fi utilizat pentru a îndeplini aproape toate funcțiile unui compilator prin intermediul traducerii direcționate sintactic. Deși această metodă poate duce la un compilator mai eficient, ea contravine principiilor de inginerie software de scriere și întreținere a programelor. Un alt avantaj pe care AST îl are față de un arbore de parse este dimensiunea, în special înălțimea mai mică a AST și numărul mai mic de elemente.

DesignEdit

Proiectarea unui AST este adesea strâns legată de proiectarea unui compilator și de caracteristicile sale așteptate.

Cerințele de bază includ următoarele:

• Tipurile de variabile trebuie să fie păstrate, precum și locația fiecărei declarații în codul sursă.
• Ordinea declarațiilor executabile trebuie să fie reprezentată în mod explicit și bine definită.
• Componentele stânga și dreapta ale operațiilor binare trebuie să fie stocate și identificate corect.
• Identificatorii și valorile lor atribuite trebuie să fie stocate pentru declarațiile de atribuire.

Aceste cerințe pot fi folosite pentru a proiecta structura de date pentru AST.

Câteva operații vor necesita întotdeauna două elemente, cum ar fi cei doi termeni pentru adunare. Cu toate acestea, unele construcții de limbaj necesită un număr arbitrar de mare de copii, cum ar fi listele de argumente transmise programelor din shell-ul de comandă. Ca urmare, un AST utilizat pentru a reprezenta codul scris într-un astfel de limbaj trebuie să fie, de asemenea, suficient de flexibil pentru a permite adăugarea rapidă a unei cantități necunoscute de copii.

Pentru a sprijini verificarea compilatorului, ar trebui să fie posibilă descompunerea unui AST în formă de cod sursă. Codul sursă produs ar trebui să fie suficient de asemănător cu originalul în aparență și identic în execuție, la recompilare.

UsageEdit

Ast este utilizat intensiv în timpul analizei semantice, unde compilatorul verifică utilizarea corectă a elementelor programului și a limbajului. Compilatorul generează, de asemenea, tabele de simboluri pe baza AST în timpul analizei semantice. O traversare completă a arborelui permite verificarea corectitudinii programului.

După verificarea corectitudinii, AST servește ca bază pentru generarea de cod. AST este adesea utilizat pentru a genera o reprezentare intermediară (IR), numită uneori limbaj intermediar, pentru generarea de cod.

.