Implementarea Unui Compilator C Pentru Un Microcontroler Didactic

Glosar termeni

Compilator – este un program (sau set de programe) care traduce textul unui program scris într-un limbaj de programare „sursă” într-un alt limbaj de calculator, numit limbaj „țintă”. Sursa originală se numește de obicei cod sursă iar rezultatul cod obiect;[1]

Token sau atom lexical – structura cu doua câmpuri: CodLexical și atribut, utilizată de analizor pentru a transmite apelantului său informațiile legate de un atom al textului sursă;

Recursiv – care se pune în mișcare în mod repetitiv și automatic. O funcție recursivă este o funcție care se apelează pe ea însuși;

Analiză lexicală – este procesul de convertire a unei secvențe de caractere, într-o secvență de token-uri;[2]

Analiză sintactică – verifică dacă un program respectă regulile de sintaxă ale limbajului sursă. Intrarea analizorului sintactic este constituită din șirul codurilor lexicale furnizate de analizorul lexical;

Gramatică – ansamblu de reguli cu privire la modificarea formelor cuvintelor și la îmbinarea lor în propoziții;[3]

Expresie regulată – denumită și RegEx sau RegExp, este un șir de caractere care descrie un model de căutare în alt șir de caractere sau într-un fișier întreg.

Introducere

Prezentarea contextului și tema lucrării

Într-o perioadă în care principalul sistem de operare folosit este Windows iar cea mai bună platforma si mediu de dezvoltare pentru acesta sunt oferite de către limbajul C#, am decis să realizez proiectul de licență folosind acest limbaj.

În cadrul acestui proiect mi-am propus realizarea unui compilator care pe baza instrucțiunilor introduse de către utilizator să afișeze atomii lexicali obținuți în urma parcurgerii analizei lexicale, să afișeze un arbore sintactic și să interpreteze codul sursă astfel încât codul țintă rezultat să poată fi executat cu succes de către un microcontroler didactic.

Compilatorul obținut este capabil să recunoască și să interpreteze instrucțiuni de declarare a variabilelor, de atribuire a unei valori pentru variabile și instrucțiuni decizionale.

Organizarea

În capitolul 2 se prezintă informații despre modul cum funcționează un microcontroler și elementele care îl compun. Tot în acest capitol sunt prezentate specificațiile microcontrolerului pentru care este implementat compilatorul.

În capitolul 3 se prezintă informații despre limbajul de programare C# împreună cu mediul de dezvoltare pentru acesta, Microsoft Visual Studio.

În capitolul 4 se prezintă informații despre modul de funcționare a unui compilator și despre etapele care sunt necesare pentru o compilare.

În capitolul 5 este prezentată proiectarea aplicației.

În capitolul 6 este prezentată implementarea analizatorului lexical.

În capitolul 7 este prezentată implementarea analizatorului sintactic.

În capitolul 8 este prezentată implementarea generatorului pentru codul ținta.

În capitolul 9 este prezentată implementarea interfeței grafice a interpretorul.

În capitolul 10 se oferă exemple de funcționare pentru interpretor împreuna cu dificultățile implementării proiectului întâlnite.

În capitolul 11 este prezentată implementarea concluzia implementării unui astfel de proiect.

În Bibliografie avem prezentată lista de unde au fost preluate informațiile necesare pentru realizarea unui interpretor.

În secțiunea Anexă este prezentat codul sursă care a fost utilizat pentru realizarea lucrării.

Noțiuni despre microcontrolere

Generalități

La modul general un controler este, actualmente, o structură electronică destinată controlului unui proces sau, mai general, unei interacțiuni caracteristice cu mediul exterior, fără să fie necesară intervenția operatorului uman. Primele controlere au fost realizate în tehnologii pur analogice, folosind componente electronice discrete și/sau componente electromecanice.

Evoluția rapida a tehnologiei și astfel a circuitelor integrate a făcut posibila înmagazinarea a sute de mii de tranzistoare intr-un singur cip. Aceasta a fost doar una din condițiile pentru producția de microprocesoare, primele calculatoare fiind produse prin adăugarea perifericelor precum memorie, magistrale de intrare și ieșire, circuit integrat de timp și altele.

O definiție, cu un sens foarte larg de cuprindere, ar fi aceea că un microcontroler este un microcircuit care incorporează o unitate centrală (CPU) și o memorie împreună cu resurse care-i permit interacțiunea cu mediul exterior.

Diferențele dintre un microcontroler și un microprocesor sunt multiple. Prima diferența și cea mai importanta este funcționalitatea acestora. Pentru a fi folosit și a funcționa corespunzător unui microprocesor trebuie sa i se adauge alte componente precum memorie sau componente pentru primirea și trimiterea de date. Chiar daca microprocesorul este considerat un dispozitiv de calcul puternic, punctul lor slab este acela ca nu sunt proiectate sa comunica cu echipamente periferice.

Pentru ca un microprocesor sa comunice cu mediul periferic, microprocesorul trebuie sa folosească circuite adăugate ca cipuri exterioare. In concluzie microprocesorul este inima unui calculator, această concluzie fiind valabila și astăzi.

Pe de altă parte, microcontrolerul este proiectat să fie toate acestea într-unul singur. Nu este nevoie de nicio alta componenta specializata externa deoarece componentele periferice sunt incluse in microcontroler. Astfel, economisim timpul și spațiul necesare pentru construirea de dispozitive.

Utilizarea microcontrolerelor este foarte numeroasa printre multele domenii unde acestea au ajuns un standard industrial se pot menționa: in industria de automobile, în așa zisa electronică de consum, în aparatura electrocasnică, în controlul mediului și climatizare, în industria aerospațială, în mijloacele moderne de măsurare – instrumentație (aparate de măsură, senzori și traductoare inteligente).

Componente Microcontroler

Un microcontroler este un microcircuit care incorporează o unitate centrală de procesare (CPU) și o memorie împreună cu resurse care-i permit interacțiunea cu mediul exterior.

Resursele integrate la nivelul microcircuitului ar trebui să includă, cel puțin, următoarele componente: o unitate centrala de procesare, o memorie locala de tipul ROM / PROM / EPROM/ FLASH și eventual una de tip RAM, un sistem de întreruperi, un circuit Input / Output de tip port paralel, un sistem de timere-temporizatoare, un comparator analogic, un sistem de conversie analog numerică.

Un microcontroler tipic mai are, la nivelul unității centrale, facilități de prelucrare a informației la nivel de bit, de acces direct și ușor la intrări/ieșiri și un mecanism de prelucrare a întreruperilor rapid și eficient.

Unitatea centrala de procesare (CPU) este componenta care monitorizează și controlează toate procesele din interiorul microcontrolerului. Este alcătuit din mai multe subunitati, cele mai importante fiind următoarele:

Decodorul de instrucțiuni face parte din electronica care recunoaște instrucțiunile de program și acționează alte circuite in funcție de acestea. “Setul de instrucțiuni” care este diferit pentru fiecare familie de microcontrolere ne arata capacitatea acestui circuit.

Unitatea aritmetico-logica (ALU) îndeplinește toate operațiunile matematice și logice care sunt efectuate asupra datelor.

Acumulatorul este un registru cu funcții speciale in strânsa legătura cu funcționalitatea unității aritmetico-logica. Acesta poate fi considerat spațiul de lucru pentru stocarea datelor asupra cărora unele operații ar trebui executate ( adunarea / scădere / mutarea biților etc.). De asemenea memorează rezultatul pentru a fi folosit in viitoarea operații. Unul dintre registri cu funcții speciale, numit și Registru de Stare ne arata in orice moment starea unui număr memorat in acumulator. De exemplu Registrul de Stare ne poate indica daca un număr este mai mare sau mai mic decât zero.

Memoria este componenta microcontrolerului folosita pentru stocarea datelor. Cea mai simpla cale pentru a explica funcționalitatea memoriei este de o compara cu un dulap cu sertare. Consideram ca sertarele sunt etichetate și numerotate astfel încât este ușor sa le distingem. Conținutul unui sertar este ușor de aflat in momentul in care avem numărul sertarului al cărui conținut vrem sa-l aflam.

Memorie doar pentru citire (ROM) este folosita pentru salvarea permanenta a programului care urmează sa fie executat. Dimensiunea unui program care poate sa fie scris depinde de dimensiunea acestei memorii. Microcontrolerele din ziua de astăzi folosesc tipic adresarea pe 16 biți, cea ce înseamnă ca sunt capabile sa adreseze o memorie de pana la 64 Kb ( 65535 locații de memorie ).

Memorie cu acces aleatoriu (RAM) este o memorie de tip volatila cea ce înseamnă ca daca alimentarea cu energie se întrerupe datele stocate in aceasta se pierd. Este folosita pentru stocarea temporara a datelor și a rezultatelor create și folosite in timpul rulării microcontrolerului. De exemplu daca programul executa o adunare, in carul memoriei RAM găsim un registru numit „suma” folosit pentru stocarea rezultatului adunării.

Circuitul de intrare / ieșire ( Input/Output) este unul dintre cele mai importante circuite periferice prezente printre printre perifericele unui microcontroler. Acesta permite comunicarea cu exteriorul microcontrolerului, comunicare poate fi bidirecționala (in ambele sensuri poate transmite cat și recepționata) sau unidirecționale (intr-un singur sens poate transmite sau recepționa). Unele circuite de I/O au pini multifuncționali (se oferă funcția de recepționare și transmitere pe același pin),altele pot avea capacitatea de a absorbi curent (pot comanda led-uri).

Circuitul se adresează direct din memorie, astfel operațiile de citire și scriere nu necesita instrucțiuni suplimentare decât cele obișnuite de lucru cu memoria microcontrolerului.

Majoritatea microcontrolelor folosesc întreruperile in funcționarea normala. Întreruperile sunt folosite pentru tratarea evenimentelor din exterior. De exemplu atunci când un buton este acționat rutina normala a microcontrolerului este pusa in așteptare pana când întreruperea este tratata. Daca microcontrolerul nu ar funcționa folosind întreruperi in majoritatea timpului acesta ar verifica existenta evenimentelor din exterior lucru care nu este practic. Folosind întreruperile microcontrolerul verifica o singura componenta pentru existenta evenimentelor din exterior. Un semnal care informează unitatea centrala de procesarea de un astfel de eveniment se numește semnal.

O magistrala reprezintă unul sau mai multe fire fizice, deobicei numărul acestora este de 8 sau 16 fire. Magistralele pot fi sortate după scopul datelor care sunt transmise prin acestea. Astfel avem magistrale de adrese prin cadrul cărora sunt transmise de la CPU la memorie adresele pe care vrem sa le accesam și magistrale de date care sunt folosite pentru conectarea circuitelor din interiorul microcontrolerului.

Specificații microcontroler didactic – Octisimo

Microcontrolerul didactic pentru care s-a realizat compilatorul este un microcontroler pe 8 biți de unde și numele acestuia „Octisimo” (din greaca antica okta- „opt”).

Arhitectura folosita este una R.I.S.C. (Reduced instruction set computing) cea ce înseamnă un număr redus de instrucțiuni care se pot executa eficient și rapid. Printre instrucțiunile care pot fi îndeplinite de către microcontroler se număra operații matematice adunare și scădere, operații cu memoria, operații cu stiva cat și operații la nivel de bit.

16 registre de uz general: R0 – R15 pe 8 biți care pot fi folosiți pentru diverse operații

Registri speciali:

PC (Program counter) registru pe 16 biți cunoscut in mod uzual ca IP(instruction pointer) este folosit pentru memorarea adresei următoarei instrucțiuni ce urmează a fi executate. După fiecare instrucțiuni executata registrul PC este incrementat cu 2(deoarece registrul IR are o dimensiune de 2 octeți). In momentul in care microcontrolerul este resetat, PC revine la 0.

SP (Stack pointer) registru pe 16 biți cunoscut in mod uzual ca stack(stiva). O stiva este o structura de data de tipul LIFO (ultimul venit, primul ieșit).

SR (Status register) registru pe 8 biți folosit pentru furnizarea de informații de la procesor. Acesta conține mai multe indicatoare (flags) precum:

Z – Zero flag, ne indica faptul ca rezultatul unei operații matematice sau logice a fost zero.

C – Carry flag, permite operații cu numere mai mari de 8 biți (octet) prin împrumutul unui singur digit binar de la un octet mai puțin semnificativ la bitul cel mai puțin semnificativ al unui octet mai semnificativ. In momentul unui împrumut de bit se activează indicatorul.

N – Negative flag, ne indica faptul ca rezultatul unei operații matematice este negativ

I – Interrupt flag, ne indica faptul ca o întrerupere este activa iar codul care este executat face parte dintr-o rutina de întreruperi.

IR – (Instrution register) registru pe 16 biți, rolul acestuia fiind de a memora instrucțiunea care se executata. Deoarece registru are o dimensiune de 16 biți (2 octeți) instrucțiunile vor fi pe 16 biți. Tehnica de ordonare a octeților va fi little-endian cea ce înseamnă octetul cel mai puțin semnificativ reținut in memoria cu adresa mai mica.

O – Overflow flag, ne indica faptul ca rezultatul unei operații este prea mare pentru a fi stocat intr-un registru.

IM – (Interrupt mode) registru pe 16 biți folosit pentru specificarea modului de funcționare al întreruperilor.

Memoria este pe 16 linii de adresa cea ce înseamnă ca poate sa adreseze maxim

= 64 Kb

Memoria de program (ROM): 64 Kb

Memoria de date (ROM): 64 Kb

Memoria perifericelor (ROM): 256 b

Setul de instrucțiuni

In următorul tabel vom prezenta setul de instrucțiuni.

Tabelul 2.1. Setul de instrucțiuni

Explicație tabel:

Prima coloana reprezintă numărul curent al instrucțiunii.

A doua coloana reprezintă codul instrucțiunii. Deoarece codul este pe 16 biți aceasta coloana a fost împărțita in alte 4 coloana a cate 4 biți fiecare.

Cea de-a treia coloana reprezintă mnemonica instrucțiunii.

Cea de-a patra coloana reprezintă parametrii instrucțiunii.

Ultima coloana reprezintă explicarea instrucțiunii.

Noțiune despre limbajul C#

Generalități

C# (pronunțat „C sharp” expresie ce se traduce prin C inteligent) este un limbaj de programare proiectat pentru construirea unei varietăți de aplicații care rulează Framework-ul .NET. C# este un limbaj simplu, puternic, sigur de tip și orientat pe obiecte. Numeroasele inovații prezente in cadrul limbajului C#, ne permit dezvoltarea rapida de aplicații in timp ce beneficiem de expresivitatea și eleganta stilului limbajului C.

Sintaxa limbajului C# este foarte expresiva și apropriate de limbajul natural, cea ce îl face simplu și ușor de învățat. Dezvoltatorii de aplicații software care cunosc un limbaj asemănător precum C, C++ sau Java sunt capabili sa înceapă dezvoltarea eficienta intr-o perioada scurta de timp. Sintaxa este mult mai simplificata decât cea a limbajului C++ unde întâlnim numeroase sintaxe dificile. C# oferă puternice caracteristici precum tipuri de valori goale (null), enumerații, delegați, expresii lamda și acces direct la memorie.

Programarea orientata pe obiecte (P.O.O.) este o paradigma de programare, axata in principal pe organizarea codului in obiecte care interacționează intre ele prin intermediul mesajelor. Principalele concepte pe care se bazează programarea orientata pe obiecte sunt: abstractizarea, încapsularea, modularitatea, polimorfismul și ierarhizarea.

Abstractizarea este procesul prin care datele și metodele sunt grupate in funcție de problema pentru care sunt proiectate sa rezolve. Abstractizarea definește granițele unui obiecte fata de altul astfel acesta se distinge cu ușurința fata de alte obiecte .

Încapsularea reprezintă proprietatea datelor și metodelor de a se grupa intr-o singura structura de date. Totodată definește modalitatea in care diverse obiecte se pot referi la datele specifice obiectului.

Moștenirea este procesul de grupare a unui program in obiecte bine definite ca funcționalitate. Acest lucru permite reducerea complexității și definirea unor granițe bine stabilite.

Ierarhizarea reprezintă procesul prin care datele abstracte sunt ordonate. Se disting doua tipuri de relații. Relații de tip sunt definite prin moștenirile dintre clase, relație in care o clasa derivata moștenește metodele și proprietățile unei alte clase numita și clasa de baza. Cea de-a doua relație este relația de agregare, prin care se înțelege compunerea unui obiect din mai multe obiecte.

Polimorfismul este unul dintre cele mai importanta concepte ale unui limbaj orientat pe obiecte, acest concept permite un răspuns adecvat al unui mesaj transmis intre doua obiecte. Polimorfismul permite obiectelor o moștenire selectiva.

Ca și limbaj de programare orientat pe obiecte limbajul C# suporta conceptele de încapsulare, moștenire și polimorfism. Toate variabilele și metodele inclusiv metoda Main, metoda ce reprezintă punctul de intrare și start al aplicației, sunt încapsulate in definiția clasei. O clasa poate sa moșteneasca direct o clasa părinte, in același timp putând sa aplice numărul dorit de interfețe. Metodele care suprascriu metodele virtuale din cadrul claselor părinte, necesita cuvântul cheie override (cuvânt tradus suprascriere) in felul aceste se evita redefinirile accidentale.

Pe lingă aceste concepte fundamentale de programare orientata pe obiecte, limbajul C# permite dezvoltarea ușoara și rapida a componentelor software prin intermediul diverselor inovații incorporate.

Printre acestea se regăsesc următoarele:

Metoda de încapsulare numita „delegates”, ne permite notificarea in cazul evenimentelor de tipul sigur de tip(type-sefe).

Proprietăți al căror rol este acela de a da acces la variabile de tipul membru privat, metode precum set și get.

Limbajul C# este capabil sa interacționeze cu alte softuri din cadrul Windosului , precum obiecte de tip COM sau win32 DLL. Aceasta interacțiune este posibila cu ajutorul unui proces numit „Interop”. Intetop permite programelor dezvoltate in limbajul C# sa aibă aproape in totalitate funcționalitate unei aplicații dezvoltate in limbajul C++. Astfel suporta chiar și pointere și conceptul de code nesigur („unsafe”) pentru cazurile unde accesul direct la memorie este absolut necesar.

Una dintre cele mai importante specificații a limbajului C# spre deosebire de alte limbaje este mecanismul de curatare automata a memoriei. Acest lucru este efectuat de către o componenta numita garbage collection. In alte limbaje este necesara alocarea de către programator a resurselor necesare unui obiect, înainte ca acesta sa poată fi utilizat in siguranța. Eliberarea acestor resurse revine tot programatorului. In cazul in care resursele nu sunt eliberate, aplicația consuma memorie de care nu are nevoie din ce in ce mai mult. Pe de alta parte daca resursele sunt eliberate prematur sau înainte de terminarea procesării acestora, pot apărea pierderea de date, coruperea altor secțiuni din memorie sau chiar apatia excepțiilor de tip „null pointer”, excepție ce înseamnă conținut gol al unei adrese la care s-a încercat accesarea.

Atât in limbajul C# cat și in Java previne aceste pericole prin managementul independent al duratei de viața pentru toate obiectele folosite in aplicație.

In limbajul Java, eliberarea memoriei este efectuata de către JVM(Java virtual machine) prin stocarea referințelor resurselor alocate. In momentul in care JVM-ul detectează lipsa unei referințe valide a unei resurse alocate aceasta este trimisa către colecția de gunoi.

In limbajul C#, colectarea gunoiului este efectuat de către CLR (common language runtime) similara in funcționalitate cu JVM.

Limbajul C# este un limbaj sigur de tip (type-sefe), caracteristica ce descurajează sau previne erorile de tip. O eroare de tip este comportamentul nedorit al unui program cauzat de o discrepanta dintre diferitele tipuri de date ale variabilelor, constantelor sau metodelor. Spre exemplu tratarea unei date de tipul integer ca și float. Codul cu caracter tip-sigur poate sa acceseze doar memoria la care are autorizație. De exemplu un obiect nu poate sa citească valoare unui alt obiect care este privat.

Pot scrie o concluzie..??

Framework-ul .NET

Un framework in traducere o platforma este un cadru de dezvoltate a softului, in care funcționalitatea acestuia poate fi modificata prin adăugarea unui cod nou de către utilizator.

Aplicațiile dezvoltate in limbajul C# rulează folosind platforma .Net Framework, o componenta integrala a sistemului de operare Windows, care include o execuție virtuala numita „common language runtime” (CLR) și un set de librarii pentru clase. Standardul common language infrastructure (CLI) in traducere infrastructura limbajului comun, este un standard internațional fundamental pentru creare, execuția și dezvoltarea mediului in care limbajele și librăriile funcționează împreuna. CLR este cu desăvârșire cea mai importanta componenta a platformei .NET. In atributele acestei componente intra managementul și execuția codului scris in limbaje .NET.

Codul sursa scrie in limbajul C# este compilat intr-un limbaj intermediar care este in conformitate cu standardele CLI. Resursele limbajului intermediar, precum bitmap-uri sau string-uri sunt stocate sub forma unui fișier executabil numit asamblare, in mod comun cu o extensie exe sau dll. Deși este un fișier executabil nu este un fișier nativ Windows,ci un executabil care va fi rulat de către CLR. Un fișier de tip asamblare conține un manifest care ne furnizează informații despre tipurile de asamblare, versiuni, culturi și necesitați de securitate.

In momentul execuției programului C#, fișierul de tip asamblare este încărcat in CLR, care poate sa acționeze diferit in funcție de informațiile din manifest. Daca cerințele de securitate sunt îndeplinite, CLR-ul executa compilarea codului intermediar in cod mașina. CLR furnizează și alte servicii precum colectarea gunoiului ( eliberarea resurselor și a memoriei), soluționarea excepțiilor și managementul resurselor. Codul executat de către CLR este cunoscut și ca „cod organizat” in contrast cu „cod neorganizat” care este compilat specific pentru un sistem.

Compatibilitatea dintre limbaje este specificația cheie a platformei .NET. Deoarece codul intermediar produs de către compilatorul C# este in conformitate cu standardul CTS, codul produs poate sa interacționeze cu codul generat de către platforma .Net versiunea Visual Basic, Visual C++ sau cu mai mult de 20 de limbaje care sunt in conformitate cu același standard. Un singur fișier de asamblare poate conține mai multe module scrise in limbaje .NET diferite, și sa interacționează ca și cum ar fi scrie intr-un singur limbaj.

Aplicațiile de tip Windows Forms sunt aplicații grafice ușor de dezvoltat și actualizat. Acestea pot funcționa indiferent de prezenta sau lipsa conexiunii la internet a sistemului pe care sunt rulate. Spre deosebire de aplicațiile de consola aplicațiile Windows Foms sunt orientate pe evenimente cea ce înseamnă ca in mare parte a timpului pur și simplu așteaptă un eveniment.

Windows Forms este o tehnologie destinata platformei .NET, o colecție de librarii care simplifica sarcinile uzuale precum citirea și scrierea intr-un fișier din sistem. Împreuna cu un mediu de dezvoltare precum Visual Studio, dezvoltarea de aplicații care afișează informații, solicita utilizatorului sa introducă data și comunica cu alte sisteme folosind rețeaua.

Un form este o suprafața grafica pe care avem posibilitatea de a afișa informații utilizatorului. In mod normal construcția unei aplicații Windows Form presupune adăugarea de controalele și răspunsuri la acțiunile utilizatorului. Acțiuni precum apăsarea unei taste sau click-ul mouse-ului. Un controler este o interfața grafica discreta cu utilizatorul prin care putem sa afișam date sau sa acceptam date citite.

Atunci când utilizatorul interacționează cu form-ul sau cu unul din controalele, acțiunea generează un eveniment. Aplicația reacționează in conformitate cu evenimentul generat folosind instrucțiuni bine definite. Windows Forms conține o varietate de controlere care pot fi adăugate la un form. Controlere care afișează, butoane,liste de selecție, butoane radio și chiar pagini web.

Figură 1

In cadrul figurii de mai suc (fig 1) avem un exemplu de Windows Form care conține controlere pentru afișare și citire. Printre acestea regăsim butoane, butoane radio, cutie pentru bifare, etichete, etichete cu legătura, bara de progres, cutie text,cutie pentru selecție și un meniu.

Microsoft Visual Studio

Microsoft Visual Studio este un mediu de dezvoltare integrat (IDE),folosit in dezvoltarea aplicațiilor Windows, aplicațiilor web și a paginilor web.

In figura de mai sus (Fig 2) avem un exemplu clasic al mediului de programare in care se regăsesc diverse unelte ale acestuia precum editorul de cod, panoul in care putem vizualiza erorile, exploratorul soluției unde se regăsesc clasele proiectului împreuna cu toate uneltele mediului care pot fi accesate din meniul superior.

Visual Studio folosește software produs de către Microsoft precum Windows API, Windows Forms, Windows Store și Microsoft Silverlight. Poate produce atât cod nativ cat și cod gestionat.

Visual Studio include un editor de cod care suporta IntelliSense (completarea automata a codului) precum și refabricarea codului.

Depanatorul inclus funcționează atât ca depanator pentru nivelul sursa cat și pentru nivelul mașina. Printre funcțiile incluse se regăsește proiectare grafica a aplicaților folosita pentru interfața grafica cu utilizatorul, proiectare web proiectarea claselor și a bazelor de date.

Visual Studio suporta diferite limbaje de programare pentru care permite editarea codului și depanarea, printre limbajele incorporate se număra: C, C++, C#, VB.NET și F#. Suportul pentru alte limbaje precum M, Python și Ruby printre altele este valabil prin instalarea separata a serviciilor de suport lingvistic. De asemenea suporta XML/XSLT, HTML/XHTML, JavaScript și CSS, Java și J# au beneficiat de suport printre primele versiuni de Visual Studio.

Precum orice mediu de dezvoltare integrat include un editor de code care oferă repere pentru sintaxa ca și completarea codului folosind IntelliSense pentru variabile, funcții și medote. IntelliSense oferă suport pentru limbajele incluse cat și pentru XML, CSS și JavaScript folosite in dezvoltarea aplicațiilor web și site-uri web. Completarea automata se prezintă intr-o caseta deasupra editorului de cod in proximitatea cursorului.

Visual Studio include compilarea in fundal, funcție numita și compilare incrementala. In timp ce codul este scrie, Visual Studio compilează in fundal pentru a oferi informații despre erorile de sintaxa și compilare, care sunt semnalizate cu prin sublinierea acestora. Avertizările sunt marcate cu o subliniere verde. Compilarea in fundal nu generează cod pentru execuție, deoarece necesita alt compilator pentru aceasta sarcina.

Depanatorul inclus in cadrul mediului de dezvoltare funtioneaza atât ca depanator pentru nivelul sursa cat și pentru nivelul mașina. Funcționează pentru cod nativ cat și pentru cod gestionat și poate fi folosit ca depanator pentru toate limbajele de programare incluse in Visual Studio. In plus se poate atașa proceselor in derulare pentru a le monitoriza și depana. Daca codul sursa al proceselor ce se derulează este valabil, depanatorul afișează codul așa cum este rulat. Depanatorul poate interacționa cu memoria. Depanatorul suporta aplicații care rulează pe mai multe fire de execuție.

Depanatorul permite adăugarea de breakpoint-uri (poziții in care rularea aplicației este oprita temporar) și watches (monitorizarea valorilor variabilelor intr-un anumit moment al execuției). Breakpoint-urile pot fi condiționate, cea ce înseamnă ca acestea pot fi acționate in momentul îndeplinirii condiției. Codul poate fi rulat linie cu linie, poate sa acceseze funții pentru depanarea lor sau poate trece peste depanarea unei funcții. Depanatorul suporta editarea și continuarea spre exemplu permite editarea in timp ce codul este depanat.

Funcția pentru proiectarea aplicațiilor de tip Windows Form este folosita la construirea interfeței cu utilizatorul folosind Windows Forms. Aranjamentul poate fi controlat cu agiotorul mouse-ului. Controlere care afișează date precum textbox, list box etc. pot fi atașate la surse de date precum o baza de date. Interfața cu utilizatorul este in legătura cu codul folosind un program de modelare a evenimentelor

Visual Studio include și un editor pentru pagini web care permite modificarea și imbunatatirea acestora. Este folosit pentru dezvoltarea aplicațiilor ASP.NET și suporta HTML, CSS și JavaScript. Folosește un model de legătura pentru codul din fundal.

Proiectarea claselor este folosit pentru dezvoltarea și editarea claselor inclusiv membri și accesul acestora folosind un model UML. Proiectarea claselor poate genera cod in limbajul C# și VB.NET. Mai poate genera diagrame pentru clasele dezvoltate de către programator.

In concluzie Microsoft Visual Studio este un mediu de dezvoltare modern care are numeroase facilitați pentru programatorii care folosesc acest mediu.

Noțiuni despre compilatoare

Generalități

Un compilator este un program software proiectat cu scopul de a traduce un set de instrucțiuni scrise intr-un limbaj intr-un set echivalent dar in alt limbaj. Un compilator este un sistem software, complex compus din numeroase componente interne care interacționează cu algoritmi la fel de capabili. Studiul construcției unui compilator ne introduce in tehnici de traducere și imbunatatire a programelor.

Rolul unui calculator in viața de zi cu zi a crescut de la un an la altul. Odată cu expansiunea internetului, a calculatoarelor și a programelor software care rulează pe acestea, a crescut și expansiunea unor categorii in legătura cu tehnologia precum comunicații, știri, divertisment și securitate. Tehnologia a schimbat calea prin care construim automobile, avioane, telefoane, televizoare și radiouri. Era calculatoarelor a creat noi categorii de divertisment de la jocurile video pana la rețelele de socializare. Cu ajutorul super calculatoarelor putem anticipa vremea și astfel cursul unor furtuni violente. Toate acestea aplicații se bazează pe programe software de calculator care construiesc unelte virtuale peste fundația care o furnizează componentele hardware. Un compilator este simplu un program care traduce pe calculator care traduce alte programe.

Pentru ca un compilator sa traducă textul scris intr-un limbaj intr-un alt limbaj, acesta trebuie sa inteleaga forma (sintaxa) cat și conținutul sau semnificația limbajului de la intrare. Este necesar sa inteleaga regulile care guvernează sintaxa și semnificația limbajului de la ieșire. In final are nevoie de o schema pentru organizarea limbajului de la intrare.

Programele pe calculator sunt simple seturi de operații abstracte scrise intr-un limbaj de programare, un limbaj formal proiectat pentru exprimarea calculelor. Limbajele de programare au proprietati și interesuri rigide, spre deosebire de un limbaj natural precum romana sau engleza. Limbajele de programare sunt proiectate sa aibă expresivitate, claritate și concizie. Limbajele naturale permit ambiguități in timp ce limbajele de programare sunt proiectate pentru evitarea ambiguităților.

Limbajele de programare sunt in general proiectate pentru a permite utilizatorului sa își exprime programul dorit printr-o secvența de operații. Procesoarele calculatoarelor împreună cu microprocesoarele sau mașinile de calcul sunt proiectate sa execute secvențe de operații. Operațiile pe care un procesor le implementează sunt in mare parte la un nivel redus de abstractizare decât cele specificate intr-un limbaj de programare. De exemplu in mod tipic un limbaj de programare include o cale clara prin care transmite date către un fișier. Acea singura operațiune de transmitere a datelor trebuie tradusa in sute de operații mașină înainte de a putea fi executate.

Acea unealta care face traducerea se numește compilator. Compilatorul primește ca date de intrare un program scris intr-un anumit limbaj de programare și produce ca date de ieșire un program echivalent. Secvența de program de la ieșire este exprima prin operații valabile limbajului de la ieșire.

In figura de mai sus (fig nr ) avem structura tipica unui compilator. In mod uzual programul “sursa” este un program scris in limbajul de programare C, C++, Java. Limbajul “țintă” este in mod uzual setul de instrucțiuni al unu procesor.

Unele compilatoare produc programul ținta intr-un limbaj de programare in locul unui program de asamblare. Programul pe care aceste compilatoare îl produc are nevoie de o viitoare procesare înainte ca acesta sa poată fi executat direct de către un calculator. Multe compilatoare de cercetare produc programul ținta in limbajul de programare C. Deoarece compilatoarele pentru limbajul C se regăsesc in majoritatea calculatoarelor acest lucru face programul ținta sa poate fi executat de către majoritatea acestor sisteme cu costul de a mai fi o data compilate înainte de obținerea programului final. Compilatoarele care produc programe țintă in limbaje de programare in locul unui program mașină, se numesc copilitoare sursă-către-sursă (source-to-source).

Figură 3

Unele limbaje de programare precum Perl, Scheme și apl sunt implementate cu un translator in locul unui compilator, exemplul de funcționare al acestora îl regăsim in figura fig3.

In afara limbajelor care folosesc un translator avem limbaje care folosesc atât un compilator cat și un translator. Java este compilat din codul sursa intr-o forma numita code byte (byte code), forma cu o reprezentare compacte menita sa scadă timpul de descărcare al mașinii virtuale. Aplicațiile Java funcționează prin rularea codului byte de către interpretor pe mașina virtuala corespunzătoare. Pentru a complica și mai mult lucrurile multe dintre implementările mașinilor virtuale Java includ și un compilator este executat la rulare, numit și compilator chiar la timp (just-in-time) care transforma codul cu frecventa de folosința cea mai mare in cod nativ.

Interpretoarele și compilatoarele au foarte multe lucruri in comun, printre care și sarcinile lor. Amândouă analizează codul introdus și determina daca acesta este sau nu un program valid. Amândouă construiesc un model de structura împreuna cu intelesul programului. Amândouă stabilesc unde sa memoreze valorile din timpul execuției. Cu toate ca interpretarea unui cod pentru a produce un rezultat este cu totul diferit fata de producerea unui program tradus care poate sa fie executat.

Un compilator este program cu o complexitate ridicata, de multe ori acestea includ sute de mii daca nu milioane de linii de cod, organizate in multiple subsisteme și componente. Numeroasele parți ale unui compilator interacționează folosind un sistem de interacțiune. Deciziile de proiectare ale unei componente au ramificații importante in cadrul altor componente. In concluzie proiectarea unui compilator este un exercițiu substanțial de gândire.

Un compilator bun folosește tehnici precum algoritmi greedy, tehnici de căutare euristica, programare dinamica, automate finite și algoritmi cu puncte fixe. In proiectarea unui algoritm se întâlnesc dificultatea precum alocarea dinamica, sincronizarea, organizarea euristica a memoriei precum și planificarea de tip pipeline. Puține sisteme software împreunează atât de multe componente complexe și diverse. Proiectarea unui compilator de la zero înseamnă o experiența in domeniul ingineriei software care nu se poate obține cu ușurința proiectând alte sisteme mai mici și cu o complexitate mult mai redusa.

Compilatoarele demonstrează succesul pe care l-a avut avut aplicarea teoriei asupra problemelor practice. Automatizarea producției de unelte pentru scanare și parcurgere de date a fost posibile datorita aplicării teoriilor din cadrul limbajelor formale. Tot aceste automatizări sunt folosite pentru căutările web, filtrările web, procesare de cuvinte și interpretări pentru limbaje comune.

In timp ce multe dintre problemele proiectării unui compilator isi găsesc soluții exista doua fundamente principale pe care un compilator trebuie sa le respecte întotdeauna.

Primul fundament este nelipsit pentru un compilator: compilatorul trebuie sa păstreze interesul programului pe care îl compilează. Corectitudinea reprezintă o problema fundamentala in programare. Compilatorul trebuie sa păstreze corectitudinea prin implementarea programului respectând sensul cu strictețe. Principiul sta la baza contractului social dintre cel ce proiectează compilatorul și cel ce îl folosește. Un compilator nu trebuie sa isi permită libertatea de a schimba sensul programului pe care îl compilează.

Al doilea fundament pe care un compilator trebuie sa îl practice este acela ca un compilator trebuie sa imbunatateasca codul pe care îl traduce intr-o cale vizibila. Un compilator tradițional imbunateste codul primit prin transformarea acestuia intr-un cod care poate fi executat pe o mașina ținta.

Figură 4

Așa cum sugerează reprezentarea grafica din figura de mai sus (fig 4) un compilator trebuie atât sa inteleaga programul sursa pe care îl primește cat și sa ii organizeze funcționalitate pentru o traducere corecta către mașina ținta. Natura diferita a acestor doua sarcini sugerează impartirea unui compilator in doua mari componente front end (in traducerea încheierea începutului) și un back end (in traducere încheierea sfârșitului).

Front end-ul se concentrează pe înțelegerea limbajului in care este scris programul sursa in timp ce back end-ul se concentrează pe organizarea programului pentru mașina ținta. Separarea sarcinilor implica importante aspecte in proiectarea și implementarea unui compilator.

Front end-ul trebuie sa incorporeze in cod cunoștințele programului sursa intr-o structura care poate fi folosita ulterior de către back end. Reprezentarea intermediara devine structura definitiva pentru traducerea codului in limbajul dorit. Fiecare etapa a compilării are o reprezentare definitiva, este posibil sa folosească mai multe reprezentări intermediare. Putem considera reprezentarea intermediara precum diferitele versiuni ale etapelor compilării.

Intr-un compilator care lucrează in doua etape, front end-ul trebuie sa se asigure ca programul sursa este bine format și trebuie sa-l organizare pentru structura „reprezentare intermediara”. Back end-ul transforma reprezentarea intermediara in seturi de instrucțiuni. Deoarcere back end-ul lureaza numai cu reprezentarea intermediara acesta poate prepune lipsa erorilor sintactice sau semantice.

Compilatorul poate sa parcurgă de mai multe ori reprezentarea intermediara a codului înainte de emiterea programului ținta. Acest lucru rezulta cod mai performant deoarcere compilatorul are timp sa studieze codul intr-o etapa iar in alta poate memora detalii relevante. Detalii folosite pentru o imbunatatire a codului intr-o etape care se desfasoara mai târziu. Aceasta strategie presupune stocarea informațiilor din prima parcurge sa fie stocare in reprezentarea intermediara, de unde viitoare parcurgeri le pot găsi și folosi.

Folosirea „reprezentării intermediare” face posibila adăugarea unui noi etape in cadrul compilării. Aceasta noua etapa se poate adăuga intre cele doua existente (front end și back end) devenind astfel o etapa la jumătate. Etapa din jumătate sau optimizatorul, preia codul intermediar ca și date de intrare și produce un cod intermediar identic din punct de vedere semantic ca și date de ieșire. Folosind reprezentarea intermediara pe post de interfața, compilatorul poate adăuga cea de a treia etapa fara a afecta cele doua componente existente deja. Acest lucru rezulta la un compilator cu trei etape care poate fi reprezentat grafic conform figurii de mai joi (figura 5).

Figură 5

Optimizatorul este un transformator RI-RI (reprezentare intermediara) al cărui rol este acela de a încerca imbunatatirea reprezentării intermediare intr-un anumit fel. Optimizatorul poate sa parcurgă reprezentarea intermediara o data sau de mai multe ori, analizând RI-ul pentru rescrierea acesteia daca este nevoie. Rescrierea apare atunci când optimizatorul poate produce o reprezentare intermediara care va fi procesata mai eficient de către back end.

Structura unui compilator in trei etape reprezintă clasicul compilator cu optimizare. Fiecare etapa este formata din mai multe parcurgeri. Front end-ul este format din doua sau trei etape care au sarcina de a recunoaște limbaje sursa valide și de a produce un codul intermediar inițial. Secțiunea mijlocie reprezintă parcurgerile care realizează optimizarea codului intermediar. Back end-ul este format dintr-o serie de parcurgeri, care cu fiecare parcurgere se aproprie de realizarea codului ținta.

Analiza lexicala

Analiza lexicala reprezintă prima etapa dintr-un proces de trei parți de care compilatorului se folosește pentru înțelegerea programului sursa. Analizatorul lexical citește o secvența de caractere după care produce o secvența de cuvinte. Analizatorul lexical combina caractere pentru a forma cuvinte și aplica un set de reguli pentru a determina daca un cuvânt este apartinte sau nu limbajului sursa. Daca cuvântul este valid adică aparține limbajului, analizatorul îi atribuie o categorie sintactica.

Analizatorul lexical este singura componenta a compilatorului care manipulează toata caracterele programului sursa. Deoarcere analizatorul are o sarcina relativ simpla, gruparea caracterelor pentru formarea cuvintelor limbajului sursa, etapa se finalizeaza rapid. Pentru realizarea acestei etape se folosesc unelte pentru automatizare. Aceste unelte proceseaza o descriere matematica a limbajului.

In majoritatea limbajelor, spatiile și semnele de punctuatie semnalizeaza sfarsitul unui cuvant. Un identificator este un cuvant format dintr-un caracter urmat de mai multe caractere. Identificatorul este separat de alte categorii de cuvinte la aparitia primului caracter non-alfanumeric. Spre exemplu “acasa” și „casa” sunt identificatori valizi dar „89casa” nu este. Putem observa validitatea unui cuvand este rezulta din testarea regulilor și nu cautarea intr-un dictionar.

Limbajele de programare tipice au unele cuvinte, numite și cuvinte rezervate sau cuvinte cheie, acestea indeplinesc regulile unui identificator dar au intelesuri speciale. Spre exemplu „while” și „static” sunt cuvinte cheie atat in C cat și in Java. Chiar daca „static” îndeplinește setul de reguli al unui identificator, analizatorul lexical din cadrul compilatorului îl va atribui unei categorii formata doar din cuvântul cheie „static”. Pentru a recunoaste cuvinte cheie analizatorul lexical poate sa caute cuvantul intr-un dictionar sau poate încorpora cuvantul cheie direct in regulile sintactice.

Simpla structura lexicala a programului sursa ajuta la imbunatatirea analizatorului lexical. Compilatorul porneste de la specificațiile sintactice ale limbajului. Sintaxa este fie inclusa in notatiile acceptate de catre generatorul de analizatoare care apoi construieste un analizator pentru executie fie foloseste specificatiile pentru construirea unui analizator de mana. Ambele analizatoare pot fi implementate pentru parcurgerea unui caracter intr-o perioada de O(1), cea ce rezulta o relatie directa intre numarul de caractere și timpul pana la finalizarea parcurgerii intregului program sursa.

Cea mai simpla metoda prin care un algorimt poate recunoaste un cuvant este deobicei o formulare caracter cu caracter. Structura codului poate sa ne furnizeze informatii pentru rezolvarea problemei recunoașterii cuvintelor. Consideram problema recunoasterii cuvantului new. Presupunem prezenta rutinei „NextChar”, rutina care returneaza urmatorul caracter. Codul testeaza prima data daca caracterul pe care il parcurge este „n” urmat de „e” iar apoi de „w”. In fiecare etapa esecul de a gasi caracterul dorit determina codul sa respinga cuvantul și sa incerce altceva.

Analizatorul parcurge cate un cuvant pe rand. Putem reprezenta codul analizatorului folosind o simpla diagrama de tranzitie.

Figură 6

Starea initiala sau starea de start este S0. Starea de start va fi intotdeauna etichetata ca fiind starea S0. S3 reprezinta starea finala sau de acceptare. Starea de acceptare este ajunsa doar atunci cand cuvantul pe care il parcurge analzatorului este „new”. Starile de acceptare sunt desenate cu un cerc dublu, precum starea S3 din figura 6. Sagetile reprezinta tranzitia de la o stare la alta in functie de caracterul primit. Daca automatul porneste in stare S0 și citeste caracterele n,e și w tranzitia ne duce in starea S3. In caz ca secventa de caractere nu este introdusa corect automatul revine in starea S1.

Diagrama de tranzitie are rolul de abstractizare a codului care este necesar este necesar pentru imprementarea unui automat. Diagramelo pot fi vazute și ca un obiect matematic numit și automat cu stari finite. Un automat finit este format din 5 elemente S,∑,δ, S0, SA unde:

S reprezinta numarul starilor din cadrul automatului, impreuna cu o stare de eroare Se.

∑ reprezinta alfabetul finit folosit de catre automat.

δ(s,c) reprezinta functia de tranzitie. Organizeaza fiecare stare s ∈ S și fiecare caracter c ∈ ∑ intr-o următoare stare.

S0 ∈ S este starea de start (sau starea initiala).

SA este setul starilor acceptate, SA ⊆ S. Fiecare stare din SA apare cu un cerc dublu in diagrama de tranzitie.

Daca automatul se afla in stare și si parcurge caracterul C atunci avem tranzitia și →δ(Si,c).

Pentru ca automatele cu stari finite sa fie folositoare este necesara o diagrama capabila sa recunoasca structuri mai complexe. Automatul finit pentru recunoasterea unui numar intreg va parcurge o serie de numere in care primul digit este fie 0 caz in care automatul se opreste, fie este un numar de la 1 la 9 urmat de unul sau mai multi numere care pot fi de la 0 la 9.

Automatul pentru numere intregi poate fi modificat astfel incat acesta poate recunoaste numere reale, cea ce inseamna recunoasterea unui caracter in plus, virgula semn de punctuatie care desparte partea intreaga de partea fractionala.

Figură 7

In figura de mai sus avem un diagrama unui automat capabil sa recunoască numere reale. Automatul pornește in starea de start S0, in funcție de ce caracter citește trecea in starea următoare, conform diagramei de tranzitie.

Daca automatul citește cifra 0 trece in starea S1, stare care poate fi finala, daca din aceasta stare se citeste caracterul virgula automatul trece in S3 de unde poate citi in continuare cifre. Daca automatul se afla in starea de start și citeste o cifra de la 1 la 9 trece in starea S2, starea care poate fi finala sau poate citi in continuare cifre. In caz ca citeste caracterul virgula trece in starea s3 de unde asteapta citirea cifrelor de la 0 la 9 caz in care trece in starea S4, stare finala.

Figură 8

Setul de cuvinte acceptate de catre un automat finit, F, formeaza un limbaj denotat L(F). Diagrama de tranzitie a automatului finit specifica detalii precise ale acelui limbaj. Nu este o specificatie pe care oamenii o considera intuitiva. Pentru orice automat finit putem sa-i descriem limbajul folosind o notatie care se numeste expresie regulata ( RE – regular expression ). Limbajul descris cu ajutorul expresiilor regulate se numește limbaj regulat. Automatele simple sunt formate din specificatii ale expresiilor regulate.

Pentru a putea lucra riguros cu expresii regulate este nevoie de o definire a acestora mult mai riguroasa. O expresie regulata este un sir de caractere dintr-un alfabet, ∑, inzestrat cu ϵ caracter ce reprezinta multimea vida. Un sir de caractere reprezinta un limbaj. Pentru o expresie regulata,r, denotam limbajul specific ca fiind L( r ). O expresie regulata este construita folosind 3 operatii de baza:

Alternanta sau reuniunea a doua siruri de caractere, R și S, denotata R|S, cu proprietatea {x | x ∈ R sau x ∈ S}.

Concatenare – concatenarea a doua siruri R și S denotat RS, contine caracterele din ambele siruri cu proprietatea ca un element din R este alaturat unui element din S sau { xy | x ∈ R și y ∈ S)

Inchidere reprezinta inchiderea unui set R, denotat R*

Din motive de convenienta se foloseste notatia Ri pentru inchiderile finite. O inchidere finite poate sa fie inlocuitata cu enumerarea tuturor posibilitatilor, spre exemplu R3 este (R|RR|RRR). Inchiderea pozitiva este denotata R+ sau RR* și este formata din una sau mai multe apatitii a lui R.

Folosind cele trei operatii de baza alternare, concatenera și inchidere, putem definii expresiile regulate dintr-un alphabet ca fiind urmatoarele:

1. Daca a apartine M, atunci a este denotarea unei expresii regulate care contine doar a.

2. Daca r și s sunt expresii regulate, denotand L( r ) și L( s ) , atunci r | s este o expresie regulate denotand reuniunea sau alternanta lui L( r ) și L( s ), rs este o expresie regulate denotand concatenarea lui L( r ) și L( s ), și r* este o expresie regulate denotand inchiderea lui L( r ).

3. ϵ este o expresie regulate denotand setul care contine sirul de caractere gol.

Pentru a elimina ambiguitatea paranteze au o precedenta mai mare, urmate de catre inchidere, concatenare și alternare in aceasta ordine.

Exemple de expresii regulate:

1. Expresie regulata pentru identificatori, un character alphabetic urmat sau nu de catre mai multe caractere alfanumerice, ([A..Z]|[a..z]) ([A..Z]|[a..z]|[0..9])*. Majoritatea limbajelor permit caractere special precum underscore( _ ), semnul de procent ( % ) sau simbolul ampersand ( & ). In caz ca limbajul limiteaza numarul maxim de caractere dintr-un identificator putem folosi inchiderea patrivita. Spre exemplu o limita de 8 caractere este reprezentate prin urmatoarea expresie regulata: ([A..Z]|[a..z]) ([A..Z]|[a..z]|[0..9])7

2. Expresie regulata pentru numere intregi fara semn, poate sa fie 0 sau o cifra diferita de zero urmata de una sau mai multe cifre de la 0 la 9, 0|[1..9][0..9]*.

3. Expresie regulata pentru numere reale, acesta expresie regulata este mult mai complexe decat cea precendenta, (0|[1..9][0..9]*) (ϵ | . [0..9]*). Prima parte reprezita o expresie regulate pentru un numar intreg. Restul expresiei genereaza fie un sir de caractere gol fie partea zecimala a numarului.

4. Expresie regulata pentru determinarea unui sir de caractere (string). In majoritatea limbajelor orice caracter poate sa apara in interiorul unui sir de caractere. Folosind un complement un caracter din limbajul C sau Java poate fi descris ca ”(^”)* ” . C și Java nu permit sirelor de caractere sa se extinda pe doua linii de cod, cea ce inseamna returnarea unei erori daca analizatorul lexical ajunge la finalul liniei iar sirul de caractere nu a fost inchis. O expresie regulata care poate sa acore și acest caz arata astfel: ”(^(“ | \n))*”.

5. Expresie regulate pentru determinarea unei comentariu dintr-un limbaj de programare. Comentariile apar sub numeroare forme in functie de limbajul de programare la care ne referim. Limbajul de programare C++ și Java ofera programatorilor doua metode prin care pot scrie un comentariu in cadrul codului. Prima metoda este prin delimitare “//”, marcator care anunta comentariu pana la sfarsitul liniei curente. Expresia regulata pentru aceasta metoda este directa: //(^\n)* \n, unde \n reprezinta caracterul pentru o noua linie. Metoda a doua este folosita pentru marcarea unui comentariu pe mai multe linii de cod, acesta incepe cu /* și se termina prin */. Daca permitem aparitia caracterului * in comentariu expresia regulata este simpla: /*(^*)* */. Daca permitem aparia * in comentariu expresia regulata este mai complexa: /*(^*|*+^/)* */.

In concluzie separearea analizei lexicale de catre analiza sintactica a fost pur și simplu justificata prin eficienta.

Analiza sintactica

Analiza sintatica reprezinta cea de-a doua etapa din cadrul unui compilator. Analizatorul lucreaza cu programul transformat de catre analizatorul lexical. Acesta parcurge o succesiune de cuvinte in care fiecare cuvant este notat cu o categorie sintactica. Analizatorul produce o structura sintactica pentru program, fiecare cuvant având locul lui intr-un model gramatical al limbajului de programare sursa. Daca analizatorul determina validitatea succesiunii primite construieste un model concret al programului pentru o folosinta ulterioara a compilatorului. In caz ca succesiunea primita nu este valida analizatorul raporteaza utilizatorului problema impreuna cu o diagnoza potrivita.

Sarcina principana a unui analitor sintatic este de a determina daca programul introdus este valid din punct de vedere sintactic. Pentru a putea construi un analizator sintatic este necesar un mecanism pentru specificarea sintaxei limbajului sursa și o metoda sistematica pentru determinarea apartenentei acestui limbaj formal. Prin restrictionarea formei limbajului sursa la un set de limbaje numite limbaje libere de context, putem asigura bunul raspuns al analizatorului.

Numerosi algorimti sunt disponibili pentru rezolvarea problemei limbajelor libere de context. Printre acesti algorimti se numara parsarea de forma descendenti – recursi și parsarea de forma descendent nerecursiv LL(1).

Pentru a putea descrie sintaxa unui limbaj de programare este nevoie de o notatie mult mai eficienta decat cea a unei expresii regulate. Solutia traditionala pentru aceasta problema este folosirea unui limbaj liber de context. Acest tip de limbaj este format din numeroase clase cu ajutorul cararo se poate construi un analizator eficient.

Un limbaj liber de context ,G, este un set de regule care descriu modul de formare al propozitiilor. O colectie de propozitii care pot fi derivate din G este numita limbaj definit de catre G, denotat G. Colectia de limbaje definite de catre limbaje libere de context se numeste set de limbaje libere de context.

Este o metodă de analiză descendentă, fără reveniri, aplicabilă acelor gramatici care nu prezintă recursivitate la stânga și nici ambiguități.

Analizorul cu descendenți recursivi este format dintr-o colecție de proceduri care se apelează între ele în mod recursiv. Practic, fiecărui neterminal din gramatică îi corespunde o procedură.

În cazul acestui tip de analizor arborele sintactic nu apare explicit, ca o structură de date, ci poate fi văzut mai degrabă ca un arbore al apelurilor de proceduri.

Procesul de analiză constă în derivări succesive ale neterminalelor, începând cu rădăcina. Derivările se materializează prin apelarea procedurilor corespunzătoare simbolurilor ce apar pe o anumită ramură de derivare. Selecția ramurii de derivare pentru un neterminal oarecare A, trebuie sa fie unic determinată de simbolul curent din șirul de intrare (altfel metoda cu descendenți recursivi nu se poate aplica) și ea decurge astfel:

Daca a este simbolul curent de intrare, iar pentru A există mai multe relații de transformare:

A alfa1 | alfa2 | . . . | alfan

se alege alternativa alfai care începe cu a sau conduce prin derivare la un sir care începe cu a. În cazul în care există mai multe asemenea alternative se poate rezolva de obicei prin factorizare la stânga.

Dacă nu există nici o alternativă care să satisfacă condiția:

alfaia beta

dar există relația A Epsilon (alternativă vidă), se alege această cale de derivare (practic, se consideră A ca recunoscut, iar analiza se continuă cu simbolul ce urmează lui A pe calea de derivare curentă ).

Dacă nu există nici alternativă vidă pentru A, atunci se consideră ca s-a ajuns într-o situație de eroare.
Eliminarea recursivității stângi

O gramatică este recursivă la stânga, daca conține cel puțin un neterminal A pentru care exista relația: AA alfa

Recursivitatea la stânga trebuie eliminata în cazul analizei cu descendenți recursivi, deoarece conduce la apeluri recursive infinite.

Proiectarea aplicației

In cadrul acestui capitol este prezentat modul de implementare al aplicației „Implementarea unui compilator C pentru un microcontroler didactic”.

Un compilator este un program care interpretează textul unui program scris intr-un limbaj „sursa” intr-un alt limbaj numit limbaj „tinta”.

Pentru a realiza aceasta sarcina, aplicatia este structurata in diferite componente care efectuează principalele etape ale unui compilator.

Prima componenta este analizatorul lexical, componenta in care textul primit (sau programul sursa) este analizat din punct de vedere lexical cu ajutorul unui automat cu stari finite. Automatul parcurge caracter cu caracter pana cand programul sursa este parcurs in intregime. In momentul in care un sir de caractere formeaza un atom lexicam (sau un token), atomul este stocat intr-o strucutra de tip lista care pe langa atom retine și categoria sintactica din care face parce acesta.

Cea de-a doua componenta a compilatorului este analizatorul sintactic. Analizatorul sintactic parcurge structura de tip lista pe care o primeste de la analizatorul lexical dupa ce acesta termina de parcurs textul. Cu ajutorul unei gramatici bine definite care nu lasa loc pentru ambiguitati și cu o parcurgere de tip descendent nerecursiv LL (1) analizatorul construieste o structura sintactica. Structura sintactica poate fi vazuta ca un arbore ale cărui noduri terminale reprezintă atomi, în timp ce nodurile interioare reprezintă structuri ale gramaticii. In momentul in care analizatorul sintactic intalneste o eroare de sintaxa, eroarea este transmisa utilizatorului specificând locul unde aceasta a fost intalnita, astfel utilizatorul poate corecta greseala cu usurinta.

Pe durata analizei sintactice se realizeaza și o analiza semantica, ceea ce inseamna efectuarea unor verificari in privinta compatibilitatii dintre tipurilor de date și operatile in care acestea sunt implicate.

Ultima componenta a compilatorului o reprezinta generatorul de cod tinta. Acesta parcurge arborele sintactic generat de analizatorul sintatic, in momentul in care intalneste un nod ce reprezinta o structura a gramaticii se genereaza programul in limbajul tinta pentru instructiunea intalnita in arbore.

Deoarcere aplicatia este implementata in limbajul de programare C#, aceasta va fi o aplicatia de tipul Windows Form. Citirea și scrierea datelor este realizata cu ajutorul unui unelte de tipul RichTextBox. Actionarea programului principal se va face prin apasarea unui buton al carui nume este unul intuitiv „Compilare”.

Analizatorul lexical

Descrierea clasei

Analizorul lexical este clasa formata dintr-un automat cu stari finite și din metode care ii permit acestuia sa analizeze textul programului sursa caracter cu caracter pentru construirea unei structuri de tip lista cu atomii lexicali ai programului.

Pentru realizarea analizorului lexical și a listei cu atomolii lexicali rezultati in urma analizei au fost utilizate clasele: class AnalizatorLexical și class ListToken.

În Class AnalizatorLexical se realizează parcurgerea caracter cu caracter de catre automat.

În Class ListToken se introduc elementele rezultate in urma parcurgerii de catre auomat. Printre elementele clasei gasim: tip, token și next.

String tip, utilizat pentru memorarea categoriei sintactice a atomului lexical;

String token, utilizat pentru memorea atomului lexical care a fost format de catre automat;

ListNod next, utilizat pentru memorarea referentei catre urmatorul nod al listei;

Citirea programului sursa se realizează prin intermediul unui controler de tipul RichTextBox.

Un controler de tipul RichTextBox memoreaza texul din caseta intr-un tablou unidimensional de tip string[ ]. O variabila de tipul string[ ] are diverse proprietati și metode care vor fi folosite pentru imprementarea clasei AnalizatorLexical.

Deoarece automatul parcurge textul programului sursa caracter cu caracter, ii este necesar sa cunoasca numarul de randuri al textul pe care il parcurge, sa poate extrage randul dorit și sa cunoasca numarul de caractere de pe randul care il parcurge.

Au fost utilizate urmatoarele metote:

public int nrRanduriText()

{

int nrRanduri = lines.Count();

return (nrRanduri);

}

public int lungimeRand(int Rand)

{

int lungimeRand = lines[Rand].Length;

return (lungimeRand);

}

public string Rand(int Nr)

{

string Rand = lines[Nr];

return Rand;

}

Inainte de a incepe explicatia celor trei metode trebuie mentionat faptul ca variabila „lines” este o variabila globala de tipul string[ ], variabila care este instantiana in cadrul constructorului clasei AnalizatorLexical. Variabila lines primeste textul controlerului RichTextBox1 prin intermediul atribuirii „lines = formPrincipal.richTextBox1.Lines „.

Prima metoda „public int nrRanduriText()”, este o metoda proiectata pentru returnarea numarului de randuri avut de textul programului sursa. In cadrul metodei se declara o variabila „int nrRanduri”. Variabila primeste prin atribuire numarulul de randuri pe care textul le are folosind metoda Count(), metoda specifica tipului sting[ ]. Dupa realizarea acestei atribuiri, se apeleaza functia de returnare pentru variabilei nrRanduri.

A doua metoda „public int lungimeRand(int Rand)”, este o metoda proiectata pentru returnarea numarului de caractere de pe un rand dorit al programului sursa. Aceasta metoda primeste randul dorit prin intermediul parametrului „Rand”. In cadrul metodei avem o declaratie de variabila „int lungimeRand”. Variabila primeste prin atribuire numarul de caractere folosind apelul proprietatii „Lenght”. In final se apeleaza functia de returnare pentru variabila lungimeRand.

A treia metoda „public string Rand(int Nr)”, metoda proiectata pentru returnarea caracterelor de pe un rand dorit al programului sursa. Aceasta metota primeste randul dorit pin intermediul parametrului „Rand”. In cadrul metodei avem o declaratie de variabila „string Rand”. Variabila primeste prin atribuire sirul de caractere de pe randul dorit. In final se apeleaza functia de returnare pentru variabila Rand.

Automatul cu stări finite

Intreaga analiza lexicala se bazeaza pe eficienta automatului cu stări finite. Un automat cu stari finite este un model de comportament compus din stări, tranziții și acțiuni.

Automatul implementat in cadrul clasei AnaliatorLexical este conceput sa recunoasca urmatoarele categorii de atomi lexicali.

Explicare tabel:

„ | ” – reprezintă operația binară sau. Când se întâlnește semnul în program, se alege ramura pe care acesta o să meargă în continuare;

[ ] – reprezintă un interval. Exemplu ['1'-'9'], reprezintă intervalul de la 1 la 9;

' ' sau ” ” – informațiile cuprinse în ghilimele sunt stringuri .

Diagrama de stari și tranzitii este declarata in cadrul clasei ca fiind o variabila bidimensionala de tipul int. Deoarcere este o variabila bidimensionala aceasta se comporta ca un tablou de numere intregi. Daca se doreste returnarea unei componente a tabloului este necesara cunoașterea liniei și a coloanei unde se afla aceasta. Variabila a fost declarata global deoarcere prin declarația globala automatul are acces la diagrama de stări și tranziție fara a a fi nevoie sa o declare pe acesta de fiecare daca când parcurge un caracter, lucru ce a dus la scaderea timpului și resurselor folosite.

In continuare vom prezenta diagrama de stari și tranzitii.

static int ER = 27; // starea de eroare

int[,] diagrama_tranzitie = new int[,]

{

// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21

{ 1, 4, 2, 6,ER, 5, 6, 7, 9, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 25,ER},//1

{ 1, 1, 1,ER, 1,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//2

{ER, 2, 2, 3,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//3

{ER, 3, 3,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//4

{ER,ER,ER, 3,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//5

{ER,ER,ER,ER,ER, 5,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//6

{ER,ER,ER,ER,ER, 6, 6,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//7

{ER,ER,ER,ER,ER,ER,ER, 8,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//8 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//9 {ER,ER,ER,ER,ER,ER,ER,ER, 10,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//10 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//11 {ER,ER,ER,ER,ER,ER,ER,ER,ER, 11,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//12 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//13 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//14 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//15 {ER,ER,ER,ER,ER,ER,ER, 16,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//16 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//17 {ER,ER,ER,ER,ER,ER,ER, 18,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//18 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//19 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//20 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//21 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//22 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//23 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER, 24,ER,ER},//24 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//25 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER, 26,ER},//26 {ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//27

{ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER,ER},//starea de eroare

};

Explicarea diagramei de tranzie stari și tranzitie:

ER – reprezinta starea de eroare

Coloanele – reprezinta conditiile pentru care automatul face tranzitul către o noua stare.

Randurile – reprezinta starile de tranzitie ale automatului. Acesta stări sunt totodată

categorii sintactice ale atomilor lexicali.

In continuare vom prezenta doua tabele prin care se va explica semnificatia atat pentru liniile diagramei cat și pentru coloane acesteia.

In continuare vom prezenta modul de funcționare al automatului cu stări finite.

Automatul parcurge textul programul sursa caracter cu caracter. In momentul in care automatul porneste parcurgerea unui caracter, automatul este initializat cu starea de start adica starea 0. Folosind o metoda bine conceputa automatul stabilește categoria din care face parte caracterul și o memoreaza pe aceasta intr-o variabila de tip int numita „coloana”.

Pentru a afla starea in care automatul trebuie sa tranziteze, se apeleaza la diagrama de stări și tranziții. Următoarea starea a automatului se afla apelând metoda „UrmatoareaStare”.

Atâta timp cat starea curenta este diferita de starea de eroare ( starea 99 ), automatul concatenează (lipește) caracterele parcurse unei variabile auxiliare. In momentul in care starea de eroare este intalnita automatul adauga atomul lexical format unei structuri de tip lista impreuna cu categoria sintactica data de starea anterioara stării de eroare. Dupa adaugarea atomului lexical in cadrul listei, automatul este initializat cu starea de start ( starea 0 ) și se continua parcurgerea caracterelor.

In continuare vom prezenta și explica metoda „UrmatoareaStare”.

public int UrmatoareaStare(int stare, char caracter)

{

int rand = stare;

int coloana = ColoanaCaracter(caracter);

return diagrama_tranzitie[rand, coloana];

}

Acesta metoda este folosita pentru afla starea in care automatul trebuie sa tranziteze. Pentrua aflat acest lucru este nevoie de starea curenta a automatului, valoare care este primita prin intermediul parametrului „stare” și a caracterului pe care automatul il parcurge, caracter care este primit prin intermediul parametrului „caracter”. Caracterul este analizat de catre metoda „ColoanaCaracter”, metoda care determina tipul de caracter din care face parte, tipurile sunt reprezentate prin coloana in diagrama de stări și tranziție.

Starea in care automatul trebuie sa tranziteze este aflata prin extragerea elementului de pe coloana și randul dorit din tabloul bidimensional „diagrama_tranzitie”. Randul este dat de catre starea actuala a automatului iar coloana de catre metoda „ColoanaCaracter”.

In continuare vom prezenta și explica metoda „ColoanaCaracter”.

public int ColoanaCaracter(char caracter)

{

string litere = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

string cifre = "123456789";

if (litere.Contains(caracter)) return 0;

if ( cifre.Contains(caracter)) return 2;

if ( caracter == '0' ) return 1;

switch (caracter)

{

case ',': return 3;

case '_': return 4;

case ' ': return 5;

case ';': return 6;

case '=': return 7;

case '+': return 8;

case '-': return 9;

case '*': return 10;

case '/': return 11;

case '>': return 12;

case '<': return 13;

case '{': return 14;

case '}': return 15;

case '(': return 16;

case ')': return 17;

case '&': return 18;

case '|': return 19;

default: return 20;

} }

Aceasta metoda este folosita de catre automat pentru determinarea tipului de caracter pe care il parcurge. Metoda primeste prin intermediul parametrului „caracter” caracterul pentru care se doreste categoria.

Deoarcere automatul functioneaza pe baza unei diagrame de stari și tranzitii, coloanele acestei diagrame reprezinta conditiile pentru care automatul tranziteaza.

Mai intai sunt declare doua stringuri care contin toate literele și cifrele pentru a putea testa caracterul cu intreg intervalul. Daca nu s-ar aborda o astfel de testare caracterul parcurs ar trebui comparat cu fiecare litera și fiecare cifra. Folosind metoda „Contains” metoda specifica tipului de date string, testam aparatia unui caracter intr-un sir de caractere, in cazul nostru testăm daca caracterul parcurs se găsește printre litere respectiv numere din cele doua siruri de caractere. Deoarece metoda „Contains” este case sensitive (adica face diferenta dintre caracterele scrise cu majuscula și cele care nu sunt scrie cu majuscula) in strigul in care se regasesc literele alfabetului au fost memorate atat literele scrise cu majuscula cat și cele fara majuscula.

( string litere = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" )

Dupa caracterul verificat nu este litera sau număr, acesta este comparat cu diverse simboluri speciale precum <, >, =, + etc. .

In momentul in care s-a identificat din ce categorie face parte caracterul se apeleaza functia return și astfel se returneaza categoria caracterului și metoda ia sfarsit.

Metodele clasei

In continuare vom discuta despre principala metoda a clasei AnalizatorLexical, metoda „public void Automat()”. Aceasta metoda este apelata in constructor dupa instantierea variabilelor. Cea ce inseamna ca in momentul in care se creaza un obiect de tipul clasei AnalizatorLexical aceasta metoda este apelata in mod automat.

Metoda Automat() este folosita pentru parcurgerea caracter cu caracter a textului.

Deoarece metoda Automat() contine doua instructiuni de ciclare de tipul while, o instructiune fiind in corpul ciclului celeilalte, explicarea metodei se va face de la exteriorul metodei catre interior(catre while-ul care se afla in corpul ciclului celuilat while).

public void Automat()

{

int nrRanduri = nrRanduriText(); // nr randuri text box

int randCurent = 0; // plecam cu primul rand

while (randCurent != nrRanduri) //parcurgem de la randul 0 => ultimul

{

// Corpul ciclului while 1

} // Sfarsit while

} // Sfarsit Automat()

Pentru o mai buna referinta și intelegere notam corpul ciclului primului while pe care il intalnim in cadrul metodei Automa(), ”Corpul ciclului while 1”.

Metoda incepe prin declararea variabilei „nrRanduri”,variabila de tipul int care este instantiata cu numarul de randuri al textului folosind metoda nrRanduriText() (metoda explica precedent).

A doua variabila declarata este variabila „randCurent”, variabila de tipul int care este instantiata cu valoarea 0.

Primul while pe care il intalnim in metoda Automat(), este while-ul a carui conditie de ciclare este „randCurent != nrRanduri”. Conditia de ciclare este adevarata atata timp cat indexul (pozitia) randului curent care este parcurs este diferit de cel al numarului total de randuri pe care textul le are. Ultimul rand din text este parcurs și el deoarece in limbajul de programare C#, indexul de start pentru orice variabila este 0.

Daca conditia de ciclare este adevarata, cea ce inseamna ca nu au fost parcurse toate randurile textului atunci se intra in corpul ciclului. Daca conditia de ciclare este falsa, cea ce inseamna ca intregul text a fost parcurs corpul ciclului numai este executat iar metoda automat ia sfarsit.

In continuare vom prezenta și explica ”Corpul ciclului while 1”.

while (randCurent != nrRanduri) //parcurgem de la randul 0 => ultimul

{

int nrCarCurent = 0; //index caracter

string textRand = Rand(randCurent); // randul pe care il analizam

int lungime = lungimeRand(randCurent);

int stare = 0;

int stare_aux = 0;

string token = "";

while (nrCarCurent != lungime)

{

// Corpul ciclului while 2.

}// end while

if (token != "") AdaugaToken(token, stare);

randCurent++; // trecem la urmatorul rand

} // end while

Pentru o mai buna referinta și intelegere notam corpul ciclului celui de-al doilea while pe care il intalnim in cadrul metodei Automat(), ”Corpul ciclului while 2”.

Corpul ciclului incepe prin declararea variabilei „nrCarCurent”, variabila de tipul int care este instantiata cu valoare 0. Aceasta variabila este folosita pentru a retine indexul(pozitia) in relevanta cu randul, a caracterului pe care il parcurgem.

A doua variabila care este declarata este „textRand”, variabila de tipul string care este instantiata cu sirul de caractere al randului la care instructiunea while a ajuns. Sirul de caractere este obtinut folosind metoda Rand(rand) iar indexul randului (randCurent) se regaseste in conditia de ciclare a instructiunii while.

A treia variabila care este declara este „lungime”, variabila de tipul int care este instantiata cu lungimea randului curent. Instantierea se face folosind metoda „lungimeRand(randCurent)” iar indexul randului (randCurent) se regaseste in conditia de ciclare a instructiunii while.

Cea de-a patra variabila care este declarata este „stare”, variabila de tipul int care este instantiata cu valoarea 0. Variabila este folosita pentru a memora starea automatului cu stari finite. Valoare 0 cu care este instantiata viriabila reprezita starea de start a automatului.

Cea de-a cincea variabila care este declata este „stare_aux”, variabila de tipul int care este instantiata cu valoarea 0. Aceasta variabila serveste drep auxiliara pentru variabila „Stare”.

Ultima declaratie de variabila este declaratia variabilei „token”, variabila de tipul sir de caractere care este instantiata cu un sir gol. Variabila este folosita pentru concatenarea caracterol parcurse de automat.

Urmeaza instructiunea de ciclare while a doua ca numar din metoda Automat(),instructiune al carei conditii de ciclare este „nrCarCurent != lungime”. Conditia de ciclare este adevarata atata timp cat pozitia caracterului curent nu este egala cu lungimea sirului. Ultimul caracter din rand este parcurs și el deoarece in limbajul de programare C#, indexul de start pentru orice variabila este 0.

Daca conditia de ciclare este adevarata, cea ce inseamna ca nu au fost parcurse toate caracterele de pe acest rand atunci se intra in corpul ciclului. Daca conditia este falsa, cea ce inseamna ca intregul ramd a fost parcurs corpul ciclului numai este executat și se trece la urmatoarea instructiune.

Urmatoarea o instructiune decizionala if, aceasta instructiune verifica daca sirul de caractere „token” este diferit de sirul gol. In caz ca acesta este diferit se apeleaza metoda „AdaugareToken”, metoda folosita pentru adaugarea atomilor lexicali in structura de tip lista. Deoarece automatul adauga atomeii lexicali in momentul in care intalneste starea de eroare, este posibil ca pentru ultimul atom aflat pe rand sa intalneasca marcatorul de sfarsit de rand, marcator care nu determina o eroare și astfel a fost nevoie de o verificare suplimentara dupa terminarea unui rand. Daca nu se facea și aceasta verificare, ultimul atom al fiecarui rand nu ar fi fost adaugat.

Ultima instructiune din cadrul ciclului este instructiunea de incrementare a variabilei „RandCurent” folosita in conditia de ciclare a primului while drept contor. La terminarea ciclului randul a fost parcurs și astfel RandCurent este increment cu 1.

In continuare vom prezenta și explica ”Corpul ciclului while 2”.

while (nrCarCurent != lungime)

{

char caracterCurent = textRand[nrCarCurent]; // caracter pentru procesare

stare_aux = stare;

stare = UrmatoareaStare(stare, caracterCurent);

if (stare == ER) // ER stare eroare

{

if (token != "")

AdaugaToken(token,stare_aux);

else

nrCarCurent++;

stare = 0; // inseamna ca s a terminat și trebuie tratat car curent din starea 0

token = ""; //golim token pentru o noua procesare

}

else

{

token += caracterCurent;

nrCarCurent++;

}

}// end while

In cadrul codului prezentat mai sus, se realizarea parcurgea caracter cu caracter de către automat.

Corpul ciclului incepe cu o declarație a variabilei „caracterCurent”, variabila de tipul char folosita pentru memorarea caracterului care urmeaza sa fie procesat. Deoarece in while-ul precedent se declara sirul de caractere „textRand” in care regasim caracterele de pe randul curent, extragerea elementului curent se face prin simpla specificare a poziției caracterului dorit. Pozitia caracterului este contorizata in variabila „nrCarCurent”.

A doua instructiune este o atribuire prin care variabila „stare” este stocata in auxiliara „stare_aux”. Acest lucru este realizat pentru a se putea lucru cu variabila „stare” și a nu se pierde valoare acesteia.

Cea de-a treia instrucțiune este o atribuire in care variabila „stare” primeste starea in care automatul trebuie sa tranziteze. Aceasta stare este aflata prin apelul metodei „urmatoareaStare”, medota despre care s-a discutat precedent.

Urmeaza o instructiune decizionala if, care testeaza daca starea actuala a automatului este starea de eroare.

In cazul in care automatul se afla in starea de eroare se continua tot cu o instructiune decizionala if, aceasta din urma testeaza daca variabila in care sunt concatenate caracterele parcurse ( adica variabila token ) este diferita de sirul de caractere gol. Daca variabila token nu este goala aceasta este adaugata in structura de tip lista prin apelul functiei adaugareToken. In cazul in variabila token este goala se incrementeaza contorul nrCarCurent.

Urmează doua instrucțiune pentru reintializarea automatului, stare automatului revine la starea de start adica 0, iar variabila in care se stochează caracterele parcurse este golita.

In cazul in care automatul nu se afla in starea de eroare, caracterul care tocmai a fost parcurs se concateneaza la celalte caractere parcurse prin atribuirea token += caracterCurent și se trece la parcurgerea urmatorului caracter prin incrementarea nrCarCurent++.

In concluzie metoda Automat() este metoda care parcurge textul programului sursa rand cu rand, caracter cu caracter. Daca caracterul este unul recunoscut de catre automat acesta il concateneaza la celelalte caractere pentru a forma un atom lexical. In cazul in care automatul tranzitează in starea de eroare, atomul lexical format este adaugat in lista și se trece mai departe la următorul caracter. Acest lucru se întâmpla pana când tot textul a fost parcurs.

Automatul incepe parcurgerea textului mai intai prin determinarea numarului de randuri pe care acesta le are. Folosind metoda NrRanduri acesta determina un nr de 2 randuri, valoare pe care o memoram in variabila nrRanduri. Se incepe parcurgea de la primul rand, și se va continua pana cand randul curent este ultimul rand.

Se incepe parcurgerea randului caracter cu caracter, de la primul caracter al randului.

Adaugarea in lista se face folosind metoda:

void AdaugaToken (string token, int stare)

{

if (5 != stare)

{

if (6 == stare) token = ";";

currentToken.token = token;

currentToken.tip = TipToken(stare);

currentToken.next = new ListToken();

currentToken = currentToken.next;

}

}

Aceasta metoda primeste prin parametru atomul lexical care urmează sa fie adăugat in lista impreuna cu starea automatului din momentul parcurgerii ultimului caracter al atomului lexical. Starea este folosita in cadrul metodei pentru determinarea categoriei sintactice din care face parte atomul.

Metoda începe cu o instrucțiune decizionala if in care se testează daca starea primita prin parametru este 5. Starea 5 a automatului este pentru spatii, astfel folosind aceasta instructiune s-a evitat adaugarea spatiilor in lista. Daca atomul pe care vrem sa-l adaugam nu este spatiu se continua cu instructiunile metodei.

Urmatoarea instructiune este tot o instructiune decizionala if in care se testeaza daca starea primita prin parametru este 6. Starea 6 este pentru punct și virgula. In limbajele de programare punctul și virgula marchează sfârșitul unei instructiuni. Automatul a fost proiectat ca atunci cand intalneste caractere alaturate de tipul punct și virgula sa le concateneze pe toate intr-un singur atom lexical. Cu ajutorul atribuirii token = ";" se adauga un singur caracter care are același impact precum multiple caractere de tipul punct și virgula.

Următoarele instructiuni sunt pentru adaugarea atomului curent in lista împreuna cu categoria sintactica, astfel:

currentToken.token = token – prin aceasta instructiune se atribuie campului token al nodului curent atomul lexical.

currentToken.tip = TipToken(stare) – prin aceasta instructiune se atribuie campului tip al nodului curent categoria sintactica din care face parte atomul, categoria este stabilita prin apelul metodei TipToken.

currentToken.next = new ListToken() – prin aceasta instructiune se atribuie campului next referinta catre noul nod creat.

currentToken = currentToken.next – print aceasta instructiune se atribuie variabilei currentToken noul nod creat anterior cu o insructiune ( new ListToken() ).

Diagrama nodurile unei liste…

Pentru determinarea categoriei sintactice din care face parte un atom lexical se foloseste metoda:

public string TipToken(int stare)

{

switch (stare)

{

case 1: return ( CuvantCheie(currentToken.token) );

case 2: return ("numar");

case 3: return ("numar");

case 4: return ("numar");

case 5: return ("");

case 6: return ("separator");

case 7: return ("egal");

case 8: return ("op_rel");

case 9: return ("op_bin");

case 10: return ("increment");

case 11: return ("op_bin");

case 12: return ("decrement");

case 13: return ("op_bin");

case 14: return ("op_bin");

case 15: return ("op_rel");

case 16: return ("op_rel");

case 17: return ("op_rel");

case 18: return ("op_rel");

case 19: return ("acolada_deschis");

case 20: return ("acolada_inchis");

case 21: return ("rotund_deschis");

case 22: return ("rotund_inchis");

case 23: return ("and");

case 24: return ("op_rel");

case 25: return ("or");

case 26: return ("op_rel");

default: return ("others");

}

}

Metoda primește prin intermediul parametrului „stare”, starea in care se afla automatul in momentul parcurgerii ultimului caracter al atomului lexical. Aceasta stare ne indica categoria sintactica. Astfel folosind o instructiune decizionala multipla de tipul swich – case se poate returna categoria sintactica.

In cazul in care starea in care a fost finalizata parcurgerea atomului este 1, stare pentru identificatori, se executa o verificare suplimentare și anume CuvantCheie (currentToken.token).

public string CuvantCheie (string token)

{

token = token.ToLower();

switch (token)

{

case "if" : return ("if");

case "main" : return ("main");

case "int" : return ("int");

case "else" : return ("else");

case "true" : return ("true");

case "false": return ("False");

default : return ("id");

}

}

Dupa ce textul programul sursa a fost parcurs in întregime de automatul finit, metoda Automat() ia sfarsit și se trece la urmatoarea instructiune.

Urmatoarea instructiune este new AnalizatorSintactic(formPrincipal, head), instructiune prin care se creaza un obiect nou de tipul clasei AnalizatorSintactic. Analizatorului sintactic ii este transmis prin parametru, referinta catre form-ul principal (form1) și variabila in care este retinut primul nod din lista.

Analizatorul sintactic

Descrierea clasei

Analizatorul sintactic este clasa care verifică dacă un program respectă regulile de sintaxă ale limbajului sursă. Analizatorul sintactic primeste ca date de intrate prin intermediul parametrilor, lista construita de catre analizatorul lexical și referinta catre form-ul principal folosita pentru afisarea datelor.

In urma verificarii pe care analizatorul sintactic o parcurge se genereaza un arbore de parsare (arbore sintatic) folosit mai tarziu pentru a genera codul final.

Pentru realizarea analizorului sintactic și a arborelui de parsare au fost utilizate clasele:

class AnalizatorSintactic, class ListNod și class AnalizatorExpresie.

În Class AnalizatorSintactica se realizează parcurgerea atomilor lexicali preluati de la analizatorul lexical cat și verificarea sintactica folosind numeroase metode.

În Class ListNod se introduc elementele pentru realizarea analizei sintactice și a arborelui sintactic. Printre elementele clasei gasim: tip, token, Nod fiu impreuna cu metodele ConstruireFii și ListNod.

String tip, care este utilizat la introducerea elementelor analizei sintactice (Program, Main, Instrucțiuni, AlteInstructiuni, Declaratie, Atribuire, IF, Expresie, Operator);

String token, utilizat pentru preluarea valorii token-urilor de la analiza lexicală;

Nod fiu[] de array, utilizat pentru implementarea nodurilor de unde pornesc arborii.

Metoda ListNod care este totodata constructorul clasei, este folosita pentru atat pentru verificarea sintactica a elementelor cat și pentru construirea nodurilor fiu.

Metoda ConstruireFii este folosita pentru construirea nodurilor fiu in functie de categoria sintactica a nodului curent.

În Class AnalizatorExpresie se realizarea analiza expresiilor matematice, prin construirea formei poloneze inverse a expresiei.

Gramatica aleasă pentru funcționarea acestui interpretor este prezentată în tabelul urmator.

Explicare tabel:

„ | ” – reprezintă operația binară sau. Când se întâlnește semnul în program, se alege ramura corespunzătoare pe care acesta o să meargă în continuare;

ε – reprezintă mulțimea vidă.

"[ ]” – reprezinta o ramura optionala

Analiza sintactica

Analiza sintactica se realizeaza in cadrul clasei AnalizatorSintactic, cu ajutorul mai multor metode care sunt necesare preluării gramatici.

Constructorul acestei clase este prezentat in continuare:

public AnalizatorSintactic(Form1 formPrincipal,ListToken head)

{

this.formPrincipal = formPrincipal;

this.head = head;

CurrentToken = head;

this.CapatNod = new ListNod("PROGRAM", this);

}

Prima instructiune este folosita pentru a atribui valoarea parametrului formPrincipal, unei variabile declarate global. Aceasta variabila reprezenta referinta catre form-ul principal.

A doua instructiune este folosita pentru a atribui valoarea parametrelui head, unei varibile declarate global. Aceasta variabila reprezinta referinta catre primul element din lista cu atomi lexicali construita de analizatorul lexical. Este nevoie de aceasta variabila pentru prelucrarea completa a listei.

A treia instructiune este similara cu cea precedenta doar ca de data aceast este folosita o alta variabila pentru memorarea referentei catre capatul listei.

In ultima instructiune este creat un obiect nou de tipul clasei ListNod. Prin intermediul parametrului se transmite sirul de caractere „PROGRAM”, și referinta catre obiectul curent adica clasa AnalizatorSintactic.

Se considera ca orice program este format din minim o instructiune. Conform gramaticii prezentate anterior pentru ca un program sa contina cel putin un nod Instructiune este nevoie de constructia nodului Program.

Program → Main EOF

Main → Instructiune

In figura de mai sus este ilustat arborele care este construit la crearea unui obiect noi de tipul ListNod.

Dupa executarea și ultimei instructiuni din cadrul constructorului, se incepe construirea arborelui sintactic folosind clasa ListNod.

In momentul in care obiectul ListNod este creat se executa constructorul acestui obiect.

Constructorul acestei clase este prezentat in continuare:

public ListNod (string tip,Compilator.AnalizatorSintactic AS)

{

this.tip = tip;

this.token = AS.GetToken(tip);

this.AS = AS;

ConstruireFii(tip);

}

Prin intermediul parametrului se transmite categoria sintactica a nodului notata tip și referinta catre clasa analizator sintactic. Referinta se transmite catre toate nodurile din arbore deoarcere verificarea sintactica se face in clasa AnalizatorSintactic și este nevoie de o legatura cu aceasta.

Prima instructiune a constructului este o atribuire prin care valoarea parametrului tip este memorata intr-o variabila globala nodului curent.

A doua instructiune a constructorului atribuie variabilei token, variabila globala a nodului curent, rezultatul apelului metodei GetToken.

A treia instructiune a constructorului este o atribuire prin care valoarea parametrului AS este memorata intr-o variabila globala nodului curent.

Ultima instructiune a constructorului o reprezinta apelul metodei ConstruireFii. Aceasta metoda este folosita pentru construirea nodurilor fii ale nodului curent in functie de tipul acestuia.

In continuare vom prezenta și explica metoda GetToken apelate in cadru celei de-a doua instructiune a constructorului

public string GetToken(string tipul)

{

string tip = CurrentToken.tip;

string token = CurrentToken.token;

if (tip == null) if (tipul.Equals("EOF")) return "EOF";

else return "eroare";

if (tip.Equals(tipul))

{

CurrentToken = CurrentToken.next;

return (token);

}

else

{ if ("MAIN, PROGRAM, INSTRUCTIUNE, AlteINSTRUCTIUNI, DECLARATIE,NULL, IF, EXPRESIE,ATRIBUIRE".Contains(tipul))

return tipul;

else return "eroare";

} }

Pentru o mai usoara intelege a modului cum functioneaza metoda GetToken aceasta nu a fost prezentata in totalita, urmand ca in decursul lucrarii sa fie prezentat și explicat și restul codului.

Principiul de functionare al metodei este unul simplu și anume compara categoria sintactica a atomului lexical care tocmai este parcurs cu categoria sintactica a nodului pentru care a fost apelata aceasta functie.

In primele doua instructiuni din cadrului metodei, se atribuie unor variabile locale metodei categoria sintactica ( tipul ) și continutul ( token ) atomului lexical care este parcurs.

Prima instructiune decizionala, if (tip == null), testeaza daca atomul lexical este null(adica s-a ajuns la sfarsit listei cu atomii lexicali). In cazul in care atomul este null exista doua posibilitati din punct de vedere sintactic.

Prima posibilitate este aceea ca s-au terminat instructiunile cea ce inseamna ca avem un nod de tipul EOF (End of file), in acest caz este corect faptul ca am ajuns la sfarsitul listei atomilor lexicali, lucru care determina metoda GetToken sa transmita arborelui validitatea atomului.

A doua posibilitate este aceea sa nu avem un nod de tipul EOF, cea ce determina metoda GetToken sa transmita o eroare arborelui.

Cea de-a doua instructiunule decizionala if (tip.Equals(tipul)), verifica daca tipul atomului este identic cu tipul nodului. Aceasta verificare se efectueaza folosind metoda equals, metoda specifica tipului de date string. In cazul in care cele doua sunt identice adica atomul lexical este corect din punct de vedere sintactic, se atribuie variabilei curentToken(variabila in care este retinut atomul lexical curent) urmatorul atom lexical și se returneaza arborelui atomul care a fost declarat valid.

In cazul in care tipul nodului nu este identic cu tipul atomului lexical este posibil sa avem un nod care reprezinta una din structurile gramaticii (precum Main, Instructiune, etc.). Caz in care acest lucru trebuie verificat folosind metoda Contains. Metoda specifica tipurilor de date string și care cauta un sir de caractere printre alte siruri de caractere. Daca nodul curent se determina a fi una din structurile gramaticii, atunci transmite validitatea catre arbore.

In cazul in care nodul nu este o structura a gramacii inseamna ca atomul lexical nu este corect din punct de vedere sintactic și se transmite erorea catre arbore.

Figură 9

In figura de mai sus este prezentat modul de verificare al unui nod.

Dupa verificarea sintactica efectuata de catre metoda GetToken, se construiesc nodurile fiu ale nodului curent. Acest lucru se efetuaza prin apelul funcitiei ConstruireFii(tip). Metoda primeste drept parametru tipul nodului pentru care construieste nodurile fiu. Acest lucru ii este necesar pentru a determina numarul și tipurile nodurilor pe care ii construieste

In continuare vom prezenta și explica modul de lucru al metodei ConstruireFii.

void ConstruireFii(string tip)

{

switch (tip)

{

case "PROGRAM"

case "MAIN"

…………….

}

}

Instructiunea principala a metodei ConstruireFii este o instructiune decizionala Swich – Case, care in fuctie de tipul nodului parinte executa instructiunile corespunzatoare.

Inainte de a continua trebuie mentionat faptup ca variabila fiu este o variabila globala in clasa ListToken, declaratia ei fiind aceasta public ListNod[] fiu. Variabila fiu este o variabila de tip vector de obiectul clasa ListNod. Lungimea vectorului nu este specificat in momentul declaratiei urmand sa fie specificat ulterior.

In continuare vom prezenta și explica tipurile de noduri pentru care metoda ConstruireFii, construieste nodurile fiu.

Primul nod pentru care vom studia constructia nodurilor fiu este nodul program deoarece acesta este primul nod care este creat, constructia lui este lansata din constructorul clasei AnalizatorSintactic.

case "PROGRAM":

{

fiu = new ListNod[2];

fiu[0] = new ListNod("MAIN", AS);

fiu[1] = new ListNod("EOF", AS);

return;

}

Pentru construirea nodurilor fiu ale nodului parinte Program este nevoie mai intai sa declaraman lungimea vectorului de obiecte fiu. Al doilea pas il reprezinta crearea unor noi obiecte Nod in cadrul vectorului fiu, noduri care primesc prin parameu tipul pe care acestea le vor avea respectiv Main și EOF.

Cel de-al doilea nod pe care il studiem este nodul Main, acest nod este creat automat odata cu nodul Program.

case "MAIN":

{

fiu = new ListNod[6];

fiu[0] = new ListNod("main", AS);

fiu[1] = new ListNod("rotund_deschis", AS);

fiu[2] = new ListNod("rotund_inchis",AS);

fiu[3] = new ListNod("acolada_deschis", AS);

fiu[4] = new ListNod("INSTRUCTIUNE",AS);

fiu[5] = new ListNod("acolada_inchis", AS);

return;

}

Pentru construirea nodurilor fiu ale nodului parinte Program este nevoie mai intai sa declaraman lungimea vectorului de obiecte fiu. Al doilea pas il reprezinta crearea unor noi obiecte Nod in cadrul vectorului fiu, noduri care primesc prin parameu tipul pe care acestea le vor avea respectiv main, rotund_deschis, rotund_inchis, acolodata_deschis, instructiune și acoloda_inchis.

Urmatoarele doua noduri Instructiune și AlteInstructiuni vor fi prezentate și explicate impreuna deoacere sunt identice ca structura și ca metode folosite pentru implementare

.

Figură 10

case "INSTRUCTIUNE":

{

fiu = new ListNod[2];

fiu[0] = new ListNod(AS.TipInstructiune (), AS);

fiu[1] = new ListNod(AS.AlteInstructiuni(), AS);

return;

}

case "AlteINSTRUCTIUNI":

{

fiu = new ListNod[2];

fiu[0] = new ListNod(AS.TipInstructiune (), AS);

fiu[1] = new ListNod(AS.AlteInstructiuni(), AS);

return;

}

Pentru construirea nodurilor fiu ale nodului parinte Program este nevoie mai intai sa declaraman lungimea vectorului de obiecte fiu. Al doilea pas il reprezinta crearea unor noi obiecte Nod in cadrul vectorului fiu, noduri care primesc prin parameu tipul pe care acestea le vor avea.

Tipul celor doua noduri fiu sunt determinate folosind doua metode respectiv TipInstructiune pentru primul fiu și AlteInstructiuni pentru cel de-al doilea fiu.

In continuare vom prezenta cele doua instructiuni impreuna cu rolul acestora.

public string TipInstructiune ()

{

string tip = CurrentToken.tip;

switch (tip)

{

case "if": return ("IF");

case "int": return ("DECLARATIE");

case "id": if (EsteVariabila(CurrentToken.token)) return ("ATRIBUIRE");

else return ("eroare");

default: return ("eroare");

}

}

Rolul acestei metode este de-a verifica daca tipul atomului lexical curent ne indica urmarea unei instructiuni.

Daca avem tipul if urmeaza o instructiune decizionala if și astfel se returneaza „IF”.

Daca avem tipul int urmeaza o instructiune de declaratie și astfel se returneaza „DECLARATIE”. Daca avem tipul id, identificatorul trebuie testat cu ajutorul metodei EsteVariabila, metoda care verifica daca identificatorul se afla printre variabilele declarate. In caz ca nu se afla printre variabilele declarate acesta este un simplu identificator cea ce conduce la o eroare de sintaxa.

Daca tipul nu se regaseste in niciunul dintre cazuri avem o eroare de sintaxa deoarce programul trebuie sa contina cel putin o instructiune.

public string AlteInstructiuni ()

{

string Instructiune = TipInstructiune();

if (Instructiune.Equals("eroare") )

return ("NULL");

else return ("AlteINSTRUCTIUNI");

}

Metoda AlteInstructiune se bazeaza pe principiu de functionare al metodei TipInstructiune. Aceasta determina daca urmatorii atomi lexicali fac parte dintr-o instructiune. In cazul in care atomii lexicali anunta urmarea unei instructiuni se returneaza tipul instructiunii in caz contratat se returneaza null.

Urmatorul nod pentru care se studiaza construirea fiilor este nodul declaratie. Prin construirea nodurilor fiu pentru acest nod se verifica sintaxa instructiunii prin care se declara o variabila.

case "DECLARATIE":

{

fiu = new ListNod[3];

fiu[0] = new ListNod("int", AS);

fiu[1] = new ListNod("id", AS);

fiu[2] = new ListNod("separator", AS);

if ( (fiu[0].token.Equals("eroare")

|| fiu[1].token.Equals("eroare") ||

fiu[2].token.Equals("eroare")) == false)

AS.DeclaraVariabila (fiu[1].token);

return;

}

Pentru construirea nodurilor fiu ale nodului parinte Declaratoe este nevoie mai intai sa declaraman lungimea vectorului de obiecte fiu. Al doilea pas il reprezinta crearea unor noi obiecte Nod in cadrul vectorului fiu, noduri care primesc prin parameu tipul pe care acestea le vor avea. La finalul metodei cele trei noduri fiu care au fost create sunt verificate din punct de vedere sintactic. In cazul in care aceste noduri sunt corecte se apeleaza metoda DeclaraVariabila. In caz contrat se metoda ia sfarsit.

In continuare vom prezenta metoda DeclaraVariabila folosita pentru declararea variabilelor.

public void DeclaraVariabila (string variabila)

{

ListaVariabile.Add(variabila,default(int));

}

Inainte de a continua explicarea metodei trebuie mentionat faptul ca ListaVariabile este o strunctura de tip Dictionary. O astfel de structura contine o colectie de valori și chei grupate in perechi. Structura ListaVariabile este declarata global astfel accesul la ea se poate face din intreaga clasa.

Declararea variabilelor se face prin stocarea numelui variabilei in structura ListaVariabile iar valoare este data ca valoare implicita pentru tipul int. Numele variabilei este primit prin intermediul parametrului variabila.

Urmatorul nod pentru care se studiaza construirea fiilor este nodul atribuire. Prin construirea nodurilor fiu pentru acest nod se verifica sintaxa instructiunii prin care se atribuie o valoare unei variabile declarate precedent.

case "ATRIBUIRE":

{

fiu = new ListNod[4];

fiu[0] = new ListNod("variabila", AS);

fiu[1] = new ListNod("egal", AS);

fiu[2] = new ListNod("EXPRESIE", AS);

fiu[3] = new ListNod("separator", AS);

if ((fiu[0].token.Equals("eroare") ||

fiu[1].token.Equals("eroare") ||

fiu[2].token.Equals("eroare") ||

fiu[3].token.Equals("eroare")) == false)

AS.AtribuieVaribila(fiu[0].token, AS.Valoare(fiu[2].token));

return;

}

Pentru construirea nodurilor fiu ale nodului parinte Atribuire este nevoie mai intai sa declaraman lungimea vectorului de obiecte fiu. Al doilea pas il reprezinta crearea unor noi obiecte Nod in cadrul vectorului fiu, noduri care primesc prin parameu tipul pe care acestea le vor avea. La finalul metodei cele patru noduri fiu care au fost create sunt verificate din punct de vedere sintactic. In cazul in care aceste noduri sunt corecte se apeleaza metoda AtribuieVaribila. In caz contrat se metoda ia sfarsit.

In continuare vom prezenta metoda DeclaraVariabila folosita pentru declararea variabilelor.

public void AtribuieVaribila (string variabila,int valoare)

{

if (ListaVariabile.ContainsKey(variabila)) ListaVariabile[variabila] = valoare;

else ListaVariabile.Add(variabila, valoare);

}

Metoda primeste prin intermediul parametrului numele variabilei și valoarea acesteia. Intai se testeaza existenta variabilei, in cazul in care aceasta este gasita in structura ListaVariabila se executa instructiunea prin care cheie din structura primeste valoarea parametrului valoare. In cazul in care cheia nu este gasita in structura se executa instruciunea prin care este adaugata cheia impreuna cu valoarea pentru aceasta.

Urmatorul nod pentru care se studiaza construirea fiilor este nodul if. Prin construirea nodurilor fiu pentru acest nod se verifica sintaxa instructiunii decizionale de tipul if.

case "IF":

{

fiu = new ListNod[7];

fiu[0] = new ListNod("if", AS);

fiu[1] = new ListNod("rotund_deschis", AS);

fiu[2] = new ListNod("EXPRESIE", AS);

fiu[3] = new ListNod("rotund_inchis", AS);

fiu[4] = new ListNod("acolada_deschis", AS);

fiu[5] = new ListNod("INSTRUCTIUNE", AS);

fiu[6] = new ListNod("acolada_inchis", AS);

return;

}

Pentru construirea nodurilor fiu ale nodului parinte IF este nevoie mai intai sa declaram lungimea vectorului de obiecte fiu. Al doilea pas il reprezinta crearea unor noi obiecte Nod in cadrul vectorului fiu, noduri care primesc prin parameu tipul pe care acestea le vor avea.

In cadrul construirii nodurilor fiu pentru instructiunea if și atribuire, s-a construit nodul fiu de tipul EXPRESIE. In continuare vom prezenta și explica functionalitatea nodului expresie.

case "EXPRESIE":

{

AS.Expresie();

fiu = new ListNod[1];

fiu[0] = new ListNod(AS.TipFiu(), AS);

token += " @ " + AS.Valoare(fiu[0].token).ToString();

return;

}

Construirea nodului Expresie incepe prin apelul metodei Expresie(). Aceasta metoda creaza un nou obiect de tipul clasei AnalizatorExpresie(). Aceasta clasa este folosita pentru analizarea atomilor din cadrul unei expresii și generarea formei poloneze inverse. Aceasta clasa va fi studiata in subcapitolul urmatorul pentru o explicare mai amanuntita.

Dupa apelul metodei Expresie(), urmatorii atomi lexicali sunt organizati in ordinea corespunzatoare pentru crearea arborelui sintactic al expresiei. Nodurile unui expresii pot fi operator sau operand. Nodul operator este format din operatorii binari și relationari. Nodul operator contine doua noduri fiu care acestea la randul lor pot fi nod de tipul operator sau operand. Nodul operand este un nod terminal al arborelui și contine valoarea operandului.

In concluzie in urma verificarii sintactice a programlui a rezultat un arbore sintactic, ale carui noduri intermediare reprezinta structuri gramaticale iar nodurile terminale reprezinta atomii lexicali preluati de la analizatorul lexical.

Analizator expresie

Aceasta clasa este implementata pentru analizarea expresiilor matematice și returnarea rezultatului. Analizatorul de expresii este capabil sa evalueaza expresii formate din operatori binari, relationari cat și din operatori logici.

Pentru a putea evalua o expresie este nevoie mai intai ca analizatorul sa determine atomii lexicali care formeaza o expresie. Pentru a determina acest lucru analizatorul considera toti atomii dintre prima paranteza deschisa și ultima paranteza ca fiind parte din expresie. In cazul in care expresia nu incepe cu o paranteza deschisa atunci atomii expresiei sunt considerati de la primul atom pentru care s-a apelat analizatorul de expresii pana la atomul lexical care nu reprezinta un operator sau operand al unei expresii.

O expresie matematica este evaluata prin construirea unui arbore binar in care nodurile reprezinta operatorii binari și relationari iar frunzele reprezinta constantele sau variabilele.

Arborele binar este construit prin scrierea formei poloneze prefixata (inverse) a expresiei pe care analizatorul o evalueaza.

Forma poloneza inversa a unei expresii este construita folosind un algorimt care se bazeaza pe lucrul cu patru structuri de date de tip stiva. Toate cele patru stive sunt declarate ca fiind stive de obiecte tip ListToken deoarece in cadrul acestora vor fi stocati atomii lexicali ai expresiei.

Cele patru stive sunt:

Expresie – in aceasta stiva vor fi stocati atomii lexicali ai expresiei

Operatori – in aceasta stiva vor fi stocati operatorii binari ai expresiei

OperatoriRelationali – in aceasta stiva vor fi stocati operatorii relationali ai expresiei

FormaPoloneze – in aceasta stiva vor fi stocati atomii lexicali pe parcursul construirii formei poloneze

Pentru a continua cu algoritmul care construieste forma poloneza inversa trebuie definita precedenta operatorilor.

In continuare vom prezenta pasii algoritmului pentru construirea formei poloneze inverse a unei expresii.

Atomii expresiei sunt adaugati in stiva Expresie. Deoarcere stiva este o structura de date LIFO (last in first out) prin adaugarea atomilor in stiva primul element cu care se incepe parcurgerea va fi ultimul atom al expresiei, cea ce inseamna ca expresia a fost inversata.

Construirea formei poloneze inverve este realizata prin parcurgerea elementelor din stiva Expresie. Cat timp exista elemente in stiva Expresie se va derula parcurgerea.

Parcurgerea presupune diferite actiuni in functie de tipul atomului care este parcurs.

Daca atomul parcurs este numar acesta este adaugat in stiva FormaPoloneza.

Daca atomul parcurs este operator binar atunci precedenta atomului curent este comparata cu precedenta primului element din stiva Operatori. In cazul in care precedenta atomului curent este mai mica decat cea a atomului din stiva Operatori atunci operatorul din stiva Operatori este inlaturat și adaugat in stiva FormaPoloneza. Aceasta comparatie a precedentelor se intampla pana cand precedenta atomului curent este mai mare decat precedenta atomului din stiva Operatori.

Daca atomul parcurs este operator relational atunci precedenta atomului curent este comparata cu precedenta primului element din stiva OperatoriRelationali. In cazul in care precedenta atomului curent este mai mica decat cea a atomului din stiva Operatori atunci operatorul din stiva OperatoriRelationali este inlaturat și adaugat in stiva FormaPoloneza. Acesta comparatie a precedentelor se intampla pana cand precedenta atomului curent este mai mare decat precedenta atomului din stiva Operatori.

Daca atomul parcurs este o paranteza rotunda deschisa atunci atomii din stiva operatori sunt eliminati din stiva operatori și adaugati in stiva FormaPoloneza. Acest lucru se intampla pana cand in stiva Operatori se intalneste Atomul paranteza rotunda inchisa.

Daca atomul parcurs este o paranteza rotunda inchisa acesta este adaugat in stiva operatori.

Dupa parcurgerea atomilor din stiva Expresie, atomii ramasi in stiva Operatori și OperatoriRelationali sunt adaugati in stiva FormaPoloneza.

Dupa executarea acestui algoritm atomii din cadrul stivei FormaPoloneza sunt asezati astfel incat cu acestia se poate construi arborele binar al expresiei.

Pentru o mai buna intelege in continuare vom prezenta diagrama logica a algoritmului:

Notam urmatoarele:

Pre() – functia pentru determinarea precedentei unui element

Ex() – functia pentru determinarea existentei elementelor intr-o stiva

Adauga() – functia care adauga atomut curent intr-o stiva specificata

ACR – atomul curent care este parcurs de catre algorimt

EXPRESIE – stiva expresie

POLONEZA – stiva expresiePoloneza

OPR – stiva operatori

ADAUGA() – functia prin care se adauga atomul curent intr-o stiva specificata

AGAUGA_ELIMINAT() – functia prin are se adauga atomul elimnat precedent intr-o stiva specificata

ELIMINA() – functia prin care se elimina un element dintr-o stiva specifica

PR_DESCHISA – caracterul paranteza rotunda deschisa

PR_INCHISA – caracterul paranteza rotunda inchisa

Figură 11

Folosind algoritmul analizatorului de descris mai sus vom construi forma poloneza inversa.

Se ia expresia: a * b + c * ( d / e )

Prima etapa se inverseaza expresia: ( e / d ) * c + b * a

Se incepe parcurgerea elementerol expresiei.

( – Paranteza rotunda deschisa – adauga la operatori

e – Variabila sau constanta – adauga la forma poloneza ( e )

/ – Operator binar – se adauga la operatori ( / )

d -Variabila sau constanta – adauga la forma poloneza ( ed )

) – Paranteza rotunda inchisa – adaugare opertori la forma poloneza ( ed/ )

*- Operator binar – verifica precedenta, se adauga la operatori

C -Variabila sau constanta – adauga la forma poloneza ( ed/c )

+ – Operator binar – verifica precedenta, se goloseste stiva pentru operaotri (ed/c*)

b – Variabila sau constanta– adauga la forma poloneza (ed/c*b)

* – Operator binar – verifica precedenta, se adauga la operatori

a – Variabila sau constanta– adauga la forma poloneza (ed/c*ba)

Se aduga elementele din stiva operatori stivei forma poloneza ( ed/c*ba*+ )

Forma poloneza inversa rezultata: +*ab*c/de

Arborele sintactic rezultat este prezentat in urmatoarea figura.

Generare cod tinta

Generatorul de cod tinta este componenta care returneaza programul in limbajul tinta. Aceasta clasa primeste ca date de intrate referinta catre analizatorul sintactic de la care poate accesa arborele sintactic.

Pentru realizarea generatorului de cod tinta am utilizat clasa: class GeneratorCodTinta

Figură 12

Pentru parcurgerea intregului arbore se apeleaza recursiv metoda Generare care primeste prin intermediul paramatrelui Nodul care urmeaza a fi parcurs. La finalul parcurgerii nodului se apeleaza din nou metoda dar de aceasta data pentru nodurile fiu ale nodului curent. Aceasta recursivitate este realizata pana cand se intalneste un nod terminal.

Programul testeaza nodul curent pentru a determina daca acesta este un nod care reprezinta o strucutara a gramaticii.

In cele ce urmeaza vom prezenta o secventa de cod care genereaza programul tinta pentru o instructiune de atribuire.

case "ATRIBUIRE":

{

string variabila = CurentNod.fiu[0].token;

int valoarea = AS.ReturneazaVariabila(variabila);

int adresa = AS.ReturneazaAdresa(variabila);

string adresaText = Convert.ToString(adresa, 2).PadLeft(16, '0');

string valoareText = valoarea.ToString("X");

FormPrincipal.richTextBox2.AppendText("MOV R1 , h " + valoareText + Environment.NewLine);

FormPrincipal.richTextBox2.AppendText("MOV R2 , b " + adresaText.Substring(0, 8) );

FormPrincipal.richTextBox2.AppendText("MOV R3 , b " + adresaText.Substring(8, 8) );

FormPrincipal.richTextBox2.AppendText("STR R1 , R2, R3 " + Environment.NewLine);

FormPrincipal.richTextBox2.AppendText(Environment.NewLine);

break;

}

In codul prezentat mai sus, la intalnirea nodului de tipul ATRIBUIRE se afiseaza instructiunile echivalent in limbajul tinta pentru instructiunea atribuire.

Interfata grafica

Interfața grafică a fost realizată utilizând Windows Form furnizat de către limbajul de programare C#.

Pentru afișarea rezultatelor sunt folosite doua ferestre in care se regasesc date diferite.

Figură 13

Prima fereastra este alcatuita din:

2 butoane:

Compilare, la apasarea acestui buton este lansata parcurgea textului introdus in caseta text din stanga deasupra careia se regaseste eticheta program sursa.

Reset, la apasarea acestui buton aplicatia revine la valorile initiale lansarii aplicatiei.

5 casete text:

Caseta program sursa din stanga, pentru introducere programului pe care vrem sa-l compilam;

Caseta program tinta din stanga, pentru afisarea programului rezultat compilarii;

Caseta lista erori din partea de jos, pentru afisarea erorilor intalnite in compilarea programului.

Caseta Lista atomi lexicali din dreapta, pentru afiseara atomilor lexicali obtinuti dupa parcurgerea analizatorului lexical

Caseta lista variabile din dreapta, pentru afisarea variabilelor și valorilor acestora obtinute dupa compilare

4 check boxt:

Arbore sintatic, pentru afisarea ferestrei in care poate fi vizualizat arborele sintactic;

Atome lexicali, pentru afisarea casetei text in care pot fi vizualizati atomii lexicali;

Variabile, pentru afisarea casetei text in care pot fi vizualizate variabilele

Erori, pentru afisarea casetei text in care pot fi vizualizate erorile.

A doua fereastra este alcatuita dintr-o caste text in cadrul careia poate fi vizualizat arborele sintactic generat de analiza sintactica.

Figură 14

Rezultate obținute și dificultati întâmpinate

Rezultate obținute

Pentru a verifica corectitudinea aplcație au fost implementate două programe:

Primul program:

Main ()

{

Int a;

Int b;

Int c;

a = 10;

b = 20;

c = 30;

}

Figură 15

Dupa cum se poate vedea in figura de mai sus pentru programulu introdus in cadrul casetei text program sursa, s-a returnat programul sursa impreuna cu structurile care au fost necesare obtinerii rezultatului final.

Figură 16

In figura de mai sus se gaseste arborele sintactic generat pentru programul de test.

Figură 17

In figura de mai sus se gaseste un exemplu in care programul sursa este gresit din puct de vedere sintactic. Aplicatia transmite utilizatorului mesajele de eroare folosind caseta text lista erori.

Dificultati întâmpinate

In cadrul implementarii aplicatiei au fost întâmpinate urmatoarele probleme:

– In momentul in care automatul cu stari finite tranzita in starea de eroare starea precedenta se pierdea iar pentru atomul lexical nu se putea determina categoria. Solutie pentru aceasta problema a fost folosirea unei variabile auxiliare pentru starea automatului.

– Automatul a trebuit reproiectat deoarece pe parcursul implementarii aplicatiei am constatat necesitatea ca acesta sa recunoasca mai multe tipuri de caractere.

Concluzii

S-a dezvoltat o aplicație capabila sa traduca textul unui program dintr-un limbaj de programare intr-un alt limbaj.

Aplicatia este compusa din trei componente 2

Bibliografie