Partea III: Introducere în sisteme formale [Introduction to Formal Systems] · Partea IV: Proiectarea compilatoarelor [Compiler Design] · 1984
This textbook (Parts III–IV) closes the series of course materials “Limbaje și compilatoare” [Programming Languages and Compilers] through two complementary directions: (1) the formalization of languages and of analysis/translation processes, and (2) the effective design of a compiler, viewed as a chain of controlled transformations of representations.
Note: for the moment I do not yet have a complete scanned copy ready for publication. The present page describes the contents on the basis of the course structure.
Cover reconstructed in order to keep the series visually consistent.
In this part of the course, the emphasis shifts from “what a language is” and “how one programs” to “how one specifies rigorously” and “how one builds systematically.” On the one hand, formalization (grammars, language classes, automata) provides the tools for definition and analysis; on the other hand, compiler design treats compilation as a stratified process: lexical analysis, syntax analysis, semantic analysis, and intermediate code generation.
The textbook is conceived as a working guide: each thematic block introduces only the concepts that are strictly necessary, then shows how they take concrete form in models and design procedures (data structures, analysis machines, translation schemes), so that the reader can move from definitions to the architecture of a compiler.
Part III establishes formal languages as the common foundation for describing syntax and for building analyzers. I begin with the Chomsky hierarchy and the relation between grammars and languages, then detail the properties of the classes of practical interest: context-free languages and regular languages. I then introduce the notion of an acceptor automaton as the operational model for recognition, distinguishing between the physical model and the mathematical model, and explicitly discussing the finite automaton and the push-down automaton as a basis for understanding syntactic analysis.
Part IV is the “engineering” part of the course: I follow step by step the design and implementation of the major components of a compiler. I begin with lexical analysis (model, design, implementation), then treat syntax analysis both top-down (recursive descent parser, LL(1), table-driven variants) and bottom-up (shift-reduce, simple/weak precedence, the LR family). After that, semantic analysis is presented as syntax-directed translation, with the corresponding specifications and algorithms for both top-down and bottom-up strategies.
Finally, intermediate code generation is discussed as the stage where representation is stabilized before object code: Polish notation, syntax trees, three-address code (quadruples/triples), and techniques for Boolean expressions and control statements. The aim is to show compilation as a sequence of transformations between representations, each transformation justified and controllable.
II. INTRODUCTION TO COMPILATION THEORY
III. COMPILER DESIGN
