Rolul analizei sintactice

Analizorul sintactic verifica daca un program respecta regulile de sintaxa ale limbajului sursa. Intrarea analizorului sintactic este constituita din sirul codurilor lexicale furnizate de analizorul lexical. In metodele de analiza sintactica descrise in prezentul indrumator se va considera cazul in care analizorul lexical este apelat de cel sintactic ori de cate ori este necesar un nou atom.
Regulile de sintaxa pe care analizorul sintactic trebuie sa le cunoasca sunt descrise fie prin intermediul gramaticilor BNF, fie prin diagrame de sintaxa.
In cazul analizei cu descendenti recursivi diagramele de sintaxa sunt mai sugestive si mai usor de implementat.
 

Principiul analizei cu descendenti recursivi

Este o metoda de analiza descendenta, fara reveniri, aplicabila acelor gramatici care nu prezinta recursivitate la stanga si nici ambiguitati.

Analizorul cu descendenti recursivi este format dintr-o colectie de proceduri care se apeleaza intre ele in mod recursiv. Practic, fiecarui neterminal din gramatica ii corespunde o procedura.

In cazul acestui tip de analizor arborele sintactic nu apare explicit, ca o structura de date, ci poate fi vazut mai degraba ca un arbore al apelurilor de proceduri.

Procesul de analiza consta in derivari succesive ale neterminalelor, incepand cu radacina. Derivarile se materializeaza prin apelarea procedurilor corespunzatoare simbolurilor ce apar pe o anumita ramura de derivare. Selectia ramurii de derivare pentru un neterminal oarecare A, trebuie sa fie unic determinata de simbolul curent din sirul de intrare (altfel metoda cu descendenti recursivi nu se poate aplica) si ea decurge astfel:

Daca a este simbolul curent de intrare, iar pentru A exista mai multe relatii de transformare:

Aalfa₁ | alfa₂ | . . . | alfa_n

se alege alternativa alfa_i care incepe cu a sau conduce prin derivare la un sir care incepe cu a. Cazul in care exista mai multe asemenea alternative se poate rezolva de obicei prin factorizare la stanga.

Daca nu exista nici o alternativa care sa satisfaca conditia:

alfa_ia beta

dar exista relatia AEpsilon (alternativa vida), se alege aceasta cale de derivare (practic, se considera A ca recunoscut, iar analiza se continua cu simbolul ce urmeaza lui A pe calea de derivare curenta ).

Daca nu exista nici alternativa vida pentru A, atunci se considera ca s-a ajuns intr-o situatie de eroare.

Eliminarea recursivitatii stangi

O gramatica este recursiva la stanga, daca contine cel putin un neterminal A pentru care exista relatia:

Recursivitatea la stanga trebuie eliminata in cazul analizei cu descendenti recursivi, deoarece conduce la apeluri recursive infinite.

Algoritmul de eliminare a recursivitatii stangi este:

procedure elimRecursStanga is
    *fie A₁, A₂, ... , A_n - neterminalele gramaticii
    for  i = 2 . . n do
        for  j = 1 . . i - 1 do
            * inlocuieste toate productiile de forma A_i A_j gamma prin
                 A_idelta₁ gamma | delta₂ gamma | . . . | delta_k gamma , unde
                A_jdelta₁ | delta₂ | . . . | delta_k   reprezinta toate productiile corespunzatoare lui A_j;
            *elimina recursivitatea stanga imediata pentru A_i, daca este cazul;
        endfor
    endfor
end elimRecursStanga

Aceasta se rezolva prin introducerea unui neterminal suplimentar A' si a urmatoarelor relatii:

Factorizarea la stanga

Se aplica in cazurile in care avem relatii de forma:

care conduc la situatii de ambiguitate, analizorul sintactic neputand decide ce ramura de derivare sa aleaga. Asemenea cazuri se rezolva prin introducerea unui neterminal suplimentar A' si a urmatoarelor relatii:

Proiectarea analizoarelor cu descendenti recursivi, pe baza diagramelor de sintaxa

Fiecare diagrama se implementeaza printr-o procedura, aplicand urmatoarele reguli:

Daca in diagrama apare o tranzitie spre un neterminal, se va prevedea un apel la rutina corespunzatoare acelui neterminal.

Daca in diagrama apare o tranzitie spre un terminal, se vor prevedea:

• un test care sa verifice daca atomul curent din sirul de intrare este identic cu cel trecut in diagrama;
• daca rezultatul testului este pozitiv se face un apel la analizorul lexical;
• daca rezultatul testului este negativ, se va semnala eroare.

Pentru exemplificare vom considera urmatorul set de diagrame:
 

Procedurile corespunza toare sunt:
 

procedure text is     call instr     while atom = pctVirg do         call ALEX         call instr     endwhile end text	procedure instr is     select  atom of         cheieWHILE:            call ALEX            call instr_while         end cheieWHILE         ident:            call ALEX            call instr_atrib         end ident         else:              *semnaleaza eroare     endselect end instr
procedure instr_while is     call expr     if tom = cheieDO then         call ALEX         call instr     else         *semnaleaza eroare     endif end instr_while	procedure instr_atrib is     if atom = opAtrib then         call ALEX         call expr     else         *semnaleaza eroare     endif end instr_atrib

Lansarea in executie a analizorului se face apeland procedura corespunzatoare radacinii gramaticii (in exemplul de mai sus aceasta ar fi text).

La intocmirea procedurilor de analiza se va tine cont de urmatoarea regula:

La intrarea intr-o procedura analizorul trebuie sa fie deja pozitionat pe un nou atom din textul sursa, ceea ce presupune ca inainte de terminarea unei proceduri trebuie apelat analizorul lexical. Acest apel trebuie prevazut si inaintea lansarii in executie a analizorului sintactic.

Desfasurarea lucrarii

Se va construi un analizor cu descendenti recursivi pentru gramatica propusa in Anexa B, sau o alta gramatica data de conducatorul lucrarii. La semnalarea unei erori se va emite un mesaj corespunzator, si se va stopa analiza.
Programul principal utilizat pentru testare va fi:

MainProgram is
    *sectiune de initializari
    call GetCarUrm
    call ALEX
    call *procedura corespunzatoare radacinii gramaticii
    if nu s-a detectat eroare then
        *afiseaza mesaj 'Program corect d.p.d.v. sintactic'
    endif
end MainProgram

Pe durata punerii la punct a procedurilor se recomanda utilizarea unor jaloane (tipariri de mesaje plasate la intrarea in proceduri) prin care sa se realizeze o trasare a drumului parcurs de analizor.
Pentru analiza lexicala se va utiliza unul dintre analizoarele proiectate la lucrarile anterioare.