Apel grafic

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 mai 2020; verificările necesită 4 modificări .

Un grafic de apel ( ing.  Graficul de apel ) în teoria construirii compilatoarelor  este un grafic direcționat care descrie apeluri între subrutine dintr-un program de calculator . În special, fiecare nod reprezintă o procedură, iar fiecare arc (f, g) arată că procedura f apelează procedura g.

Un grafic de apel este rezultatul unei analize de program care poate fi utilizat pentru înțelegerea umană a programului sau ca bază pentru analize ulterioare. O utilizare simplă a graficului de apel este de a căuta proceduri care nu sunt niciodată apelate.

Graficul de apel poate fi dinamic sau static. Graficul de apel dinamic este o înregistrare a execuției programului. Graficul de apel static este destinat să reprezinte toate variantele posibile de execuție a programului.

Definiție

Graficul de apel al unui program este un set de noduri și muchii , în sensul că [1]

  1. fiecare procedură a programului corespunde unui nod,
  2. fiecare punct de apel, adică locul din program în care este apelată procedura, corespunde unui nod al graficului,
  3. dacă punctul de apel c poate apela procedura p , graficul are o muchie de la nodul c la nodul p .

Multe programe scrise în limbaje de programare precum C și Fortran fac apeluri de procedură direct, astfel încât codul țintă al fiecărui apel poate fi determinat static. În acest caz, fiecare punct de apel din grafic are o margine unică pentru exact o procedură. Apelurile indirecte sunt foarte frecvente în limbajele de programare orientate pe obiecte.

Exemplu

Un program în limbajul de programare C care declară un pointer global pf la o funcție care ia ca parametru și returnează un număr întreg . Există două funcții de acest tip, fun1 și fun2, și o funcție principală al cărei tip nu se potrivește cu indicatorul pf. Cele trei puncte de apel sunt etichetate c1 , c2 și c3  - aceste etichete nu fac parte din programul [2] .

int ( * pf )( int ); int fun1 ( int x ) { dacă ( x < 10 ) c1 : return ( * pf )( x + l ); altfel returnează x ; } int fun2 ( int y ) { pf = & fun1 ; c2 : return ( * pf )( y ); } void main () { pf = & fun2 ; c3 : ( * pf )( 5 ); }

Cea mai simplă analiză a ceea ce ar putea indica pf este examinarea tipurilor de funcții. Funcțiile fun1 și fun2 sunt de același tip ca și indicatorul pf, în timp ce funcția principală este de alt tip. O analiză mai atentă a programului arată că indicatorul pf din funcția principală devine egal cu fun2, iar apoi în funcția fun2 i se atribuie valoarea fun1. Nu există alte atribuiri pentru pointerul pf în program, deci, în special, pointerul pf nu poate indica funcția principală [2] .

Note

  1. ↑ Aho, Lam et al., 2008 , p. 1062.
  2. ↑ 1 2 Aho, Lam et al., 2008 , p. 1063.

Literatură

în rusă

  • Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilatoare: principii, tehnici și instrumente = Compilers: Principles, Techniques, and Tools. - Editura Williams, 2008. - ISBN 0-321-48681-1 .

în engleză

  • Ryder, BG, „Constructing the Call Graph of a Program”, Inginerie software, IEEE Transactions on, vol. SE-5, nr.3pp. 216-226, mai 1979 [1]
  • Grove, D., DeFouw, G., Dean, J. și Chambers, C. 1997. Construcția graficului apel în limbaje orientate pe obiecte, SIGPLAN Not. 32, 10 (oct. 1997), 108-124. [2]
  • Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K., „Constructing the procedure call multigraph”, Inginerie software, IEEE Transactions on, vol.16, nr.4pp.483-487, Apr 1990 [3]