2012_Book_ModernCompilerDesign"Modern Compile

文件名称: 2012_Book_ModernCompilerDesign

所属分类: 其它

开发工具:

文件大小: 4mb

下载次数: 0

上传时间: 2019-01-12

提供者: l2563******

下载 (4mb)

不能下载？报告错误

详细说明："Modern Compiler Design" makes the topic of compiler design more accessible by focusing on principles and techniques of wide application. By carefully distinguishing between the essential (material that has a high chance of being useful) and the incidental (material that will be of benefit only in e Dick grune· Kees van Reeuwijk● Henri e.Bal Ceriel J H. Jacobs. Koen Langendoen Modern Compiler design Second edition ②spr ringer Dick grune Ceriel j h. jacobs Vrije Universiteit Vrije Universite Amsterdam The Netherlands Amsterdam. The Netherlands Kees van Reeuwijk Koen Langendoen Vrije Universiteit Delft University of Technology Amsterdam The Netherlands Delft. The Netherlands Henrie. bal Vrije Universiteit Amsterdam. The netherlands Additionalmaterialtothisbookcanbedownloadedfromhttp://extras.springercom ISBN978-1-4614-4698-9 ISBN978-1-4614-4699-6( eBook) DOI10.1007978-1-4614-4699-6 Springer New York Heidelberg Dordrecht London Library of congress Control Number: 2012941168 C Springer Science+ Business Media New York 2012 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher's location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through Rights Link at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law The use of general descriptive names, registered names, trademarks, service marks, etc in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein Printed on acid-free paper SpringerispartofSpringerScience-+businessMedia(www.springer.com) Preface Twelve years have passed since the first edition of Modern Compiler Design For many computer science subjects this would be more than a life time but since com piler design is probably the most mature computer science subject, it is different An adult person develops more slowly and differently than a toddler or a teenager, and so does compiler design. The present book reflects that Improvements to the book fall into two groups: presentation and content. The look and feel'of the book has been modernized but more importantly we have rearranged significant parts of the book to present them in a more structured manner large chapters have been split and the optimizing code generation techniques have been collected in a separate chapter Based on reader feedback and experiences in teaching from this book both by ourselves and others material has been expanded clarified, modified, or deleted in a large number of places. We hope that as a result of this the reader feels that the book does a better job of making compiler design and construction accessible The book adds new material to cover the developments in compiler design and construction over the last twelve years. Overall the standard compiling techniques and paradigms have stood the test of time, but still new and often surprising opti mization techniques have been invented; existing ones have been improved; and old ones have gained prominence. Examples of the first are: procedural abstraction, in which routines are recognized in the code and replaced by routine calls to reduce size; binary rewriting, in which optimizations are applied to the binary code; and just-in-time compilation, in which parts of the compilation are delayed to improve the perceived speed of the program. An example of the second is a technique which extends optimal code generation through exhaustive search, previously available for tiny blocks only, to moderate-Size basic blocks. And an example of the third is tai recursion removal, indispensable for the compilation of functional languages. These developments are mainly described in Chapter 9 Although syntax analysis is the one but oldest branch of compiler construction Lexical analysis being the oldest), even in that area innovation has taken place Generalized(non-deterministic)LR parsing, developed between 1984 and 1994, is now used in compilers. It is covered in Section 3.5.8 New hardware requirements have necessitated new compiler developments.The main examples are the need for size reduction of the object code, both to fit the code into small embedded systems and to reduce transmission times; and for lower power Prefab consumption to extend battery life and to reduce electricity bills. Dynamic memory allocation in embedded systems requires a balance between speed and thrift, and the question is how compiler design can help These subjects are covered in Sections 9.2, 9.3, and 10.2.8, respectively With age comes legacy. There is much legacy code around, code which is so old that it can no longer be modified and recompiled with reasonable effort. If the source code is still available but there is no compiler any more recompilation must start with a grammar of the source code For fifty years programmers and compiler designers have used grammars to produce and analyze programs; now large legacy programs are used to produce grammars for them. The recovery of the grammar from legacy source code is discussed in Section 3.6. If just the binary executable program is left, it must be disassembled or even decompiled. For fifty years com piler designers have been called upon to design compilers and assemblers to convert source programs to binary code; now they are called upon to design disassemblers and decompilers, to roll back the assembly and compilation process. The required techniques are treated in sections 8.4 and 8.5 The bibliography The literature list has been updated, but its usefulness is more limited than before for two reasons. The first is that by the time it appears in print, the Internet can pro- vide more up-to-date and more to-the-point information, in larger quantities than a printed text can hope to achieve. It is our contention that anybody who has under- stood a larger part of the ideas explained in this book is able to evaluate Internet information on compiler design The second is that many of the papers we refer to are available only to those fortunate enough to have login facilities at an institute with sufficient budget to obtain subscriptions to the larger publishers; they are no longer available to just anyone who walks into a university library. Both phenomena point to paradigm shifts with which readers, authors, publishers and librarians will have to cope The structure of the book This book is conceptually divided into two parts. The first, comprising Chapters 1 through 10, is concerned with techniques for program processing in general; it in cludes a chapter on memory management, both in the compiler and in the generated code. The second part, Chapters ll through 14, covers the specific techniques re quired by the various programming paradigms. The interactions between the parts of the book are outlined in the adjacent table. The leftmost column shows the four phases of compiler construction: analysis, context handling, synthesis, and run-time systems. Chapters in this column cover both the manual and the automatic creation Preface of the pertinent software but tend to emphasize automatic generation. The other columns show the four paradigms covered in this book; for each paradigm an ex ample of a subject treated by each of the phases is shown. These chapters tend to contain manual techniques only, all automatic techniques having been delegated to Chapters 2 through 9 ve In imperativ in functional in logic In parallel/ and object programs rograms distributed oriented ( Chapter 12) Chapter 13) programs programs ( Chapter 14) ( Chapter 11) How to do analysIs Chapters 2&3) context identifier polymorphic static rule Linda static nandin identification type checking matching analysis Chapters 4 5 synthesis code for code for list structure marshaling (Chapters 6-9) while comprehension unification statement run -time stack Warren replication systems machii Abstract (no chapter Machine The scientific mind would like the table to be nice and square, with all boxes filled-in short"orthogonal but we see that the top right entries are missing and that there is no chapter for run-time systems"in the leftmost column. The top right entries would cover such things as the special subjects in the program text analysis of logic languages, but present text analysis techniques are powerful and flexible enough and languages similar enough to handle all language paradigms there is nothing to be said there, for lack of problems. The chapter missing from the leftmost column would discuss manual and automatic techniques for creating run-time systems. Unfortunately there is little or no theory on this subject: run-time systems are still crafted by hand by programmers on an intuitive basis; there is nothing to be said there for lack of solutions Chapter l introduces the reader to compiler design by examining a simple tradi tional modular compiler/interpreter in detail. Several high-level aspects of compiler construction are discussed, followed by a short history of compiler construction and introductions to formal grammars and closure algorithms Chapters 2 and 3 treat the program text analysis phase of a compiler: the conver sion of the program text to an abstract syntax tree. Techniques for lexical analysis lexical identification of tokens, and syntax analysis are discussed Chapters 4 and 5 cover the second phase of a compiler: context handling. Sev eral methods of context handling are discussed: automated ones using attribute grammars, manual ones using L-attributed and S-attributed grammars, and semi automated ones using symbolic interpretation and data-flow analysis Presa Chapters 6 through 9 cover the synthesis phase of a compiler, covering both in- terpretation and code generation. The chapters on code generation are mainly con cerned with machine code generation; the intermediate code required for paradigm specific constructs is treated in Chapters ll through 14 Chapter 10 concerns memory management techniques, both for use in the com piler and in the generated program Chapters ll through 14 address the special problems in compiling for the various paradigms-imperative, object-oriented, functional, logic, and parallel/distributed Compilers for imperative and object-oriented programs are similar enough to be treated together in one chapter, Chapter 11 Appendix b contains hints and answers to a selection of the exercises in the book. Such exercises are marked by a b followed the page number on which the answer appears. A larger set of answers can be found on Springer's Internet page the corresponding exercises are marked by Dwww Several subjects in this book are treated in a non-traditional way and some words of justification may be in order Lexical analysis is based on the same dotted items that are traditionally reserved for bottom-up syntax analysis, rather than on Thompsons NFA construction. We see the dotted item as the essential tool in bottom-up pattern matching, unifying lexical analysis, LR syntax analysis, bottom-up code generation and peep-hole op timization. The traditional lexical algorithms are just low-level implementations of item manipulation. We consider the different treatment of lexical and syntax analy sis to be a historical artifact also the difference between the lexical and the syntax levels tends to disappear in modern software Considerable attention is being paid to attribute grammars, in spite of the fact that their impact on compiler design has been limited Yet they are the only known way of automating context handling, and we hope that the present treatment will help to lower the threshold of their application Functions as first-class data are covered in much greater depth in this book than is usual in compiler design books. After a good start in Algol 60, functions lost much status as manipulatable data in languages like C, Pascal, and Ada, although Ad 95 rehabilitated them somewhat. The implementation of some modern concepts for example functional and logic languages, iterators, and continuations, however requires functions to be manipulated as normal data. The fundamental aspects of the implementation are covered in the chapter on imperative and object-oriented languages; specifics are given in the chapters on the various other paradigms Additional material, including more answers to exercises, and all diagrams and all code from the book, are available through Springer's Internet page. Use as a course book The book contains far too much material for a compiler design course of 13 lectures of two hours each, as given at our university, so a selection has to be made. An Preface introductory, more traditional course can be obtained by including, for example Chapter 1 Chapter 2 up to 2.7; 2.10; 2.11; Chapter 3 up to 3.4.5;3.5 up to 3.5.7; Chapter 4 up to 4.1.3; 4.2.1 up to 43; Chapter 5 up to 5.2.2; 5.3 Chapter 6; Chapter 7 up to 9.1.1; 9.1.4 up to 9.1.4.4; 7.3; Chapter 10 up to 10.1.2; 10.2 up to 10.2.4; Chapter 1l up to 11. 2.3.2; 11.2.4 up to 11. 2.10; 11. 4 up to 11. 4.2.3 A more advanced course would include all of Chapters I to ll, possibly exclud- ing Chapter 4. This could be augmented by one of Chapters 12 to 14 An advanced course would skip much of the introductory material and concen trate on the parts omitted in the introductory course, Chapter 4 and all of Chapters 10to14. Acknowledgments We owe many thanks to the following people, who supplied us with help, remarks wishes, and food for thought for this Second Edition: Ingmar Alting, Jose Fortes, Bert Huijben, Jonathan Joubert, Sara Kalvala, Frank Lippes, Paul s Moulson, Pras ant K Patra, Carlo Perassi, Marco Rossi, Mooly Sagiv, Gert Jan Schoneveld, Ajay Singh, Evert Wattel, and Freek Zindel. Their input ranged from simple corrections to detailed suggestions to massive criticism. Special thanks go to Stefanie Scherzinger, whose thorough and thoughtful criticism of our outline code format induced us to improve it considerably; any remaining imperfections should be attributed to stub bornness on the part of the authors. The presentation of the program code snippets in the book profited greatly from Carsten Heinz's listings package, we thank him for making the package available to the public We are grateful to Ann Kostant, Melissa Fearon, and Courtney Clark of Springer US, who, through fast and competent work, have cleared many obstacles that stood in the way of publishing this book. We thank them for their effort and pleasant cooperation We mourn the death of Irina Athanasiu, who did not live long enough to lend her expertise in embedded systems to this book We thank the Faculteit der Exacte Wetenschappen of the Vrije Universiteit for their support and the use of their equipment Amsterdam Dick grune March 2012 Kees van reeuwijk Henrie. bal Ceriel.h. jacobs Delft Koen g Langendoen

(系统自动生成,下载前可以参看下载内容)