Enciclopedia universală

Gramatica in programare

Gramatica in programare - O multime de reguli (numite productii) utilizate pentru generarea propozitiilor corecte dintr-un limbaj formal. Are semnificatie de specificatie finita a limbajului. O regula indica modul in care se poate rescrie un subsir care constituie partea stanga a productiei utilizand subsirul care reprezinta partea dreapta. O regula contine doua categorii de simboluri: simboluri terminale care fac parte din alfabetul utilizat pentru construirea propozitiilor si simboluri neterminale care sunt folosite in procesul generarii. Pornind de la un simbol de start al gramaticii (un simbol neterminal special), prin rescrieri succesive (adica prin aplicari succesive ale productiilor gramaticii) se pot obtine toate propozitiile din limbajul generat de gramatica. Pe baza formei productiilor, gramaticile sunt clasificate conform ierarhiei Chomsky in gramatici regulate (tipul 3), independente de context (tipul 2), dependente de context (tipul 1), general (tipul 0). Pentru limbajele de programare alfabetul este format din litere, cifre, operatori, semne de punctuatie iar simbolurile neterminale reprezinta notiuni ca: program, instructiune, expresie, declaratie, lista, etc. De exemplu, regulile pentru generarea expresiilor aritmetice avand ca operanzi identificatorii a si b si ca operatori adunarea si inmultirea sunt E -> a, E -> b, E -> E + E, E -> E * E. Simbolul de start al gramaticii in acest caz este E.