Partea III: Introducere în sisteme formale · Partea IV: Proiectarea compilatoarelor · 1984
Acest manual (Partea III–IV) încheie seria materialelor de curs „Limbaje și compilatoare” prin două direcții complementare: (1) formalizarea limbajelor și a proceselor de analiză/traducere și (2) proiectarea efectivă a unui compilator, privită ca un lanț de transformări controlate ale reprezentărilor.
Notă: nu am deocamdată un exemplar scanat complet pentru publicare. Pagina de față descrie conținutul pe baza structurii cursului.
În această parte a cursului, accentul se mută de la „ce este un limbaj” și „cum se programează” către „cum specifici riguros” și „cum construiești sistematic”. Pe de o parte, formalizarea (gramatici, clase de limbaje, automate) oferă instrumentele de definire și analiză; pe de altă parte, proiectarea compilatoarelor tratează compilarea ca un proces stratificat: analiză lexicală, analiză sintactică, analiză semantică și generare de cod intermediar.
Manualul este gândit ca un ghid de lucru: fiecare bloc tematic introduce conceptele strict necesare, apoi arată cum se concretizează ele în modele și proceduri de proiectare (structuri de date, mașini de analiză, scheme de traducere), astfel încât cititorul să poată trece de la definiții la arhitectura unui compilator.
Partea III fixează limbajele formale ca fundament comun pentru descrierea sintaxei și pentru construcția analizatoarelor. Pornesc de la ierarhia Chomsky și de la relația dintre gramatici și limbaje, apoi detaliez proprietățile claselor de interes practic: limbaje independente de context și limbaje regulate. În continuare, introduc noțiunea de automat de acceptare ca model operațional pentru recunoaștere, făcând distincția dintre modelul fizic și cel matematic și discutând explicit automatul finit și automatul cu stivă („push-down”), ca bază pentru înțelegerea analizării sintactice.
Partea IV este partea „inginerească” a cursului: urmăresc pas cu pas proiectarea și implementarea componentelor majore ale unui compilator. Încep cu analiza lexicală (model, proiectare, implementare), apoi tratez analiza sintactică atât descendentă (analizor recursiv descendent, LL(1), variante orientate spre tabele), cât și ascendentă (shift-reduce, precedență simplă/slabă, familia LR). După aceea, analiza semantică este prezentată ca o traducere dirijată prin sintaxă, cu specificații și algoritmi corespunzători atât pentru strategii top-down, cât și bottom-up.
În fine, generarea codului intermediar este discutată ca etapă de stabilizare a reprezentării înainte de codul obiect: notație poloneză, arbori sintactici, cod cu trei adrese (cvadruple/triplete) și tehnici pentru expresii booleene și instrucțiuni de control. Ideea este să se vadă compilarea ca o succesiune de transformări între reprezentări, fiecare transformare fiind justificată și controlabilă.
II. INTRODUCERE ÎN TEORIA COMPILĂRII
III. PROIECTAREA COMPILATOARELOR