Formal languages and compilation (Q5891327)

The book provides an in-depth introduction to the foundations of compiler construction with a strong emphasis on the theory of formal languages. It is well suited for a basic course on formal languages (covering the regular and the context-free languages) and an advanced course on compiler construction. The presentation is mathematically exact and thus necessarily formal, but the authors make every effort to illustrate the concepts and algorithms on well-selected examples. Figures are provided whenever graphical illustration would be desirable. Only a mathematical disposition and some programming experience are required as background to appreciate the whole book. Exercises for class-room use are not provided. The long Section 2 sets the stage by recalling the foundations required later in the book. More specifically, it starts with an informal discussion of the matter and then proceeds to formally introduce the main notions starting with formal languages, language operations, the regular languages based on regular expressions, and finally the context-free languages. Much detail is provided for those basic concepts and it additionally considers some interesting material (such as a discussion of ambiguity) that is not typically part of the curriculum. Naturally, particular emphasis is placed on the constructions (e.g., regexp-to-automaton constructions) and notions that will be relevant to compiler construction, but the section also provides a good overview of basic formal language theory (covering the regular and the context-free languages). This exposition is complemented in Section 3 where the theory of regular languages is discussed in great detail. The typical concepts taught in a formal language course are presented including determinization, minimization, and translations between various models computing regular languages. Since the regular expressions are particularly relevant for the compilation, several methods for converting them into executable models (e.g., into a finite automaton) are presented together with a discussion of their strengths and weaknesses. In addition, common variations of regular expressions are discussed including the star-free languages. Section 4 continues with a detailed exposition of the theory of context-free languages with a long discussion of all major parsing strategies relevant to compilation. The requirements of those parsing strategies are made very explicit. Contrary to other textbooks, the focus on expressive power does not disappear here. The classes parseable with the various strategies are investigated and related to each other. This section also discusses parallel parsing strategies that have become much more relevant in the recent future due to the innate parallelism in today's computers. It is concluded with a discussion of error handling, which is required to report errors in the syntactic analysis in an understandable fashion to the user. The final Section 5 goes beyond traditional parsing techniques and deals with the analysis of non-context-free features (such as variable-declaration-and-use checking) and semantic translation (or code generation). Attribute grammars are the formal model used here and this volume is the only recent title with a detailed description of attribute grammars and their use in code generation. This section is a bit shorter than the other sections and gives a nice outlook. Overall, this book is a nice textbook both for a formal language course, a parsing for compilation course, or a compiler course. It should be enjoyable by anybody with some mathematical background. For the first edition see [Zbl 1190.68034].