Automate, limbaje si compilatoare
FISA DISCIPLINEI

Anul universitar 2011- 2012


   Departament Home

Cod: I3501
Titular curs: prof. univ. dr. I. Iancu
Forma de invatamant: cursuri de zi
Ciclul: 1, anul III, Semestrul 1
Curs: 28h, Laborator: 28h/ AA: 28h
Nr. credite: 5
Profil: informatica
Specializare: informatica
Tip disciplina: obligatorie
Categoria formativa: de specialitate
Obiective:
  • Insusirea fundamentelor teoretice si practice care stau la baza proiectarii unui compilator
Continutul cursului:

      I. Limbaje formale si automate
    1. Gramatici si limbaje
      1. Definitii, clasificarea Chomsky
      2. Proprietati
      3. Recursivitate
    2. Automate finite
      1. Definitii, reprezentare
      2. Automate finite complet deterministe
      3. Minimizarea automatelor finite
      4. Automate finite si limbaje regulate
    3. Limbaje independente de context
      1. Proprietati, reprezentare
      2. Simplificari ale gramaticilor independente de context
    4. Automate pushdown
      1. Definire, functionare
      2. Limbaje acceptate de automate pushdown
      3. Echivalarea limbajelor independente de context cu cele acceptate de automate pushdown
    5. Clase speciale de gramatici independente de context
      1. Gramatici in forma normala Chomsky
      2. Gramatici nerecursive
      3. Gramatici LL
      4. Gramatici LR
      5. Gramatici de precedenta
      II. Compilatoare
    1. Traducerea limbajelor
      1. Structura unui compilator
      2. Scheme de traducere orientate de sintaxa
      3. Traducatoare finite
      4. Traducatoare pushdown
    2. Analiza lexicala
      1. Generalitati
      2. Proiectarea unui analizor lexical
    3. Analiza sintactica
      1. Algoritmi generali
      2. Analiza LL(k)
      3. Analiza LR(k)
      4. Analiza de tip precedenta
    4. Analiza semantica
      1. Specificarea semanticii
      2. Model de analiza semantica
    5. Generarea codului intermediar
      1. Arbori sintactici
      2. Cod intermediar cu trei adrese: exemplu de traducerea in cod cu trei adrese a unor instructiuni
    6. Optimizarea codului intermediar
      1. Optimizari simple
      2. Optimizari globale
      3. Optimizari locale
    7. Generarea codului obiect
      1. Tipuri de cod obiect
      2. Algoritmi de generare si eficientizare
    8. Tabela de simboluri
      1. Tipuri de tabele
      2. Tabele arborescente
      3. Tabele dispersate
    9. Tratarea erorilor
      1. Sursele erorilor
      2. Tehnici de corectare

Discipline anterioare cerute:
  • Programare procedurala
    Cod: I1104
  • Programare orientata obiect
    Cod: I1203
  • Tehnici avansate de programare
    Cod: I2402
Discipline anterioare recomandate:
  • Arhitectura calculatoarelor
    Cod: I1105
Forma de evaluare: examen si activitatea din timpul anului la laborator
  1. Examenul consta in proba scrisa (si proba orala pentru cei care care doresc sa-si mareasca nota de la scris)
  2. Nota finala este media ponderata a notei de la examen si a celei de la laborator, cu ponderile 60% si respectiv 40%
Cerinte minime pentru promovare:
  1. Cunoasterea urmatoarelor notiuni
    1. gramatici: definitie, clasificare , limbaj generat
    2. automate finite si pushdown: definitie, configuratie, functionare, limbaj acceptat
    3. structura unui compilator
    4. principiul de functionare al analizei sintactice ascendente/descendente
    5. un algoritm de analiza sintactica
    6. reprezentarea codului intermediar prin arbori sintactici
    7. tipuri de cod obiect
    8. generalitati despre tabela de simboluri: organizare, rolul ei in fazele compilarii
  2. Activitate la laborator
    1. prezenta la cel putin 50% din laboratoare
    2. nota de promovare la temele de laborator
Continutul laboratorului:
  1. Minimizarea automatelor finite
  2. Implementarea a doi algoritmi de simplificare a gramaticilor independente de context
  3. Implementarea unui algoritm de verificare ca o gramatica este LL(k) (sau LR(k) sau de precedenta)
  4. Implementarea unui analizor lexical
  5. Implementarea unui algoritm de analiza sintactica
  6. Implementarea unui algoritm de generare a codului intermediar
  7. Implementarea algoritmului pentru optimizari globale
  8. Implementarea algoritmilor de generare a codului obiect folosind grafuri orientate fara cicluri
  9. Implementarea unui algoritm de creare si accesare a tabelei de simboluri
Bibliografie:
  1. I. Iancu, Automate, limbaje si compilatoare , Editura SITECH, Craiova, 2008
  2. A. Dinca, M. Andrei, Limbaje formale si aplicatii , Editura Universitaria, Craiova, 2002
  3. Gh. Paun, Probleme actuale in teoria limbajelor formale, Editura Stiintifica si Enciclopedica, Bucuresti, 1984
  4. C. Popovici, N. Tandareanu, L. Livovschi, H. Georgescu, Bazele informaticii, Editura Didactica si Pedagogica, Bucuresti, 1981
  5. I. Iancu: Proiectarea compilatoarelor , Editura Universitaria, Craiova, 2002
  6. I. Iancu: Teoria compilatoarelor , Editura Vlad&Vlad, Craiova, 1997
  7. I. Iancu, M. Andrei: Teoria compilatoarelor si semantica limbajelor de programare. Indrumar de laborator, Reprografia Universitatii din Craiova, 1998.
  8. L. D. Serbanati: Limbaje de programare si compilatoare, Ed. Academiei, 1987
  9. Ad. Atanasiu: Limbaje formale si tehnici de compilare. Caiet de lucrari practice. Reprografia Univ. Bucuresti, 1974
  10. J. P. Tremblay, P. G. Sorenson: The theory and practice of compiler writing, Mc Graw-Hill, 1985
  11. D. Gries: Compiler construction for digital computers, Wiley and Sons, New York, 1971
  12. D. Vaida: Limbaje formale si tehnici de compilare, Tipografia Univ. Bucuresti, 1978
  13. A. V. Aho, J. D. Ullman: The theory of parsing, translation and compiling, Prentice-Hall, 1973
  14. A. V. Aho, R. Sethi, J. D. Ullman: Compilers. Principles, techniques and tools, Addison-Wesley,1986
  15. A. Hajjam el Hassani: Les compilateurss et leur principles, Ed. Scientifiques et Techniques, Mulhouse, 1993
Lectii de sinteza

Sinteza 1 Sinteza 2 Sinteza 3
Ultima actualizare: octombrie 2011