Proiectarea și implementarea unui generator de analizoare sintactice bazate pe relații de precedentă

Analizorul sintactic este o componentă obligatorie pentru orice compilator. Pentru a obţine un product soft (program) trebuie să creăm un program executabil. Pentru aceasta avem nevoie de un limbaj de programare, de exemplu, un limbaj destul de răspândit ca C++. Într-o fereastră obişnuită poate fi scris un cod în pseudolimbaj care va fi tratat şi prelucrat. Pentru a înţelege propoziţiile scrise avem nevoie de un vocabular şi reguli cu ajutorul cărora vor fi tratate cuvintele introduse de programator. Aceasta se realizează cu ajutorul analizoarelor sintactice.

Rolul analizei sintactice constă în transformarea şirului de atomi lexicali într-o descriere structurală a şirului, dacă şirul este corect, sau generarea unui mesaj de eroare, dacă şirul nu este corect. Descrierea structurală este de obicei un echivalent al arborelui de derivare.

O situaţie des întâlnită este cea în care analizorul sintactic în loc să construiască în mod explicit arborele de derivare, pentru fiecare pas în construcţia arborelui, declanşează anumite acţiuni asupra bazei de date prin intermediul procedurilor semantice.

În principiu, există două strategii de construire a arborelui de derivare: strategia descendentă în care arborele este construit de la rădăcină spre frunze şi strategia ascendentă în care arborele este construit de la frunze spre rădăcină. În ambele cazuri construcţia este ghidată de şirul de la intrare. Corespunzător acestor strategii vom avea analizoare sintactice descendente şi, respectiv, analizoare sintactice ascendente.

O altă clasificare a analizoarelor sintactice este bazată pe existenţa revenirilor. Deoarece modelul sintaxei limbajelor de programare este gramatica independentă de context, modelul analizorului sintactic va fi automatul push-down nedeterminist. Este normal deci ca în simularea funcţionării acestuia în cadrul unui program, să prevedem posibilitatea încercării tuturor alternativelor de continuare a analizei. Abandonarea unei alternative necesită revenirea la situaţia anterioară încercării ei. Asigurarea în orice moment a unei singure posibilităţi de continuare a analizei sintactice permite realizarea de analizoare fără reveniri, deci analizoare eficiente.

Pentru analiza sintactică se utilizează gramatica independentă de context – gramatica , toate producţiile gramaticii sunt de forma: , unde , În lucrarea prezentată se utilizează gramatica independentă de context fără -producţii ( -producţii).

Presupunem că există o gramatică cu un număr de reguli respectiv mic. Atunci construirea analizorului sintactic poate fi nu atât de grea. De obicei numărul producţiilor este destul de mare şi construirea manuală a analizorului este practic imposibilă. De exemplu, în limbajul C++ sau Pascal numărul cuvintelor este mai mult de 1000, iar al regulilor este mai mult de 5000.

În acest caz apare necesitatea automatizării construirii analizoarelor sintactice. Cum s-a menţionat mai sus pot fi utilizate 2 metode: analizoare sintactice descendente şi analizoare sintactice ascendente. În lucrarea dată este elaborat un generator de analizoare sintactice ascendente bazate pe relaţii de precedenţă. Această metoda nu este cea mai avansată, dar oferă posibilitatea construirii automate a analizorului şi în acelaşi timp este uşoară şi înţeleasă.

Dezavantajul acestei metode în comparaţie cu alte metode mai avansate constă în faptul că nu în toate cazurile poate fi efectiv tratată eroarea. Adică la apariţia erorii nu întotdeauna poate fi găsit locul şi denumirea ei. Un alt dezavantaj al acestei metode constă în folosirea iraţională a memoriei calculatorului pentru tabela relaţiilor de precedenţă.

Avantajele acestei metode sunt rapiditatea construirii analizorului şi verificarea şirului de simboluri. Al doilea avantaj constă în uşurinţa (în comparaţie cu alte metode) construirii analizorului.

1. Instrumentariu

Construirea generatorului analizoarelor sintactice este realizată utilizând limbajul de programare Visual C++. Acest limbaj dă posibilităţi avansate programatorului, deoarece el este orientat spre obiect şi în acelaşi timp este orientat spre eveniment. Folosind componentele standarde şi nestandarde este elaborată o interfaţă foarte comodă pentru utilizatori.

Programul dat dă posibilitatea de a obţine o informaţie fără greutăţi, deoarece în orice moment de timp utilizatorul poate obţine informaţia necesară despre corectitudinea gramaticii introduse, despre vectorii terminali şi neterminali, poate arăta conţinutul tabelelor “PRIM-ULTIM” sau de precedenţă. Pentru a obţine comoditatea aceasta sunt utilizate clase standarde CDialog (Fereastră de dialog), CEdit (Edit Box), CButton (Buton), CTabCtrl (Tab Control – pagini speciale) şi componenta care nu intră în pachetul standard Visual C++ 6.0 – componenta ActiveX MSFlexGrid destinată afişării tabelelor. Această componentă utilizează clase adăugătoare CRowCursor, COleFont şi CPicture (sursele acestor clase ale componentei ActiveX ale puteţi vedea în anexă).