Enciclopedia universală

Arbore de derivare

Arbore de derivare - Reprezentarea sub forma unui arbore a secventei de derivari (rescrieri), folosind productiile unei gramatici independente de context, ce conduc la obtinerea unei propozitii in limbajul generat de gramatica. Tuturor simbolurilor din partea dreapta a unei productii le corespund in arbore noduri descendenti ai nodului corespunzator simbolului neterminal din stanga productiei. Frunzele arborelui corespund simbolurilor terminale ce compun propozitia generata. Construirea arborelui se poate face intr-o maniera descendenta (top-down) sau ascendenta (bottom-up). In primul caz notiunea corespunzatoare simbolului de start al gramaticii (in cazul limbajelor de programare este vorba de program sau de instructiune) este "explicata" prin rescrieri utilizand notiuni mai simple pana se ajunge la un sir de simboli din alfabetul peste care este construit limbajul (in cazul limbajelor de programare este vorba de atomi lexicali). In al doilea caz se face o abstractizare de notiuni pornind de la un sir de simboli din alfabet pana cand se obtine cea mai generala notiune (de exemplu trecere in contextul procesului de compilare are semnificatia de parcurgere integrala a datelor de intrare (adica a programului sursa sau a unei forme intermediare in care acesta a fost transformat), prelucrarea lor si memorarea rezultatului intr-un fisier sau in memorie. In general se incearca realizarea mai multor etape (faze) ale compilarii in aceeasi trecere.