Trustworthy compilers

Vladimir O. Safonov's approach to this complex topic is superb. Developer's who are seasoned as well as those who are building experience will find this text rewarding. I appreciated the gradual and logical approach starting with basic concepts of Trustworthy compilers and development principles. This text should be included in computer science curriculum as it gives a superb backdrop/history and exposes new concepts and approaches within the Trustworthy framework. The questions and exercises after each chapter are detailed and when completed will give the student a firm grasp of the applications and theories presented. I highly recommend this book for new developers, experienced developers, and most importantly, computer science and computer engineering students. Trustworthy Compilers......Page 5 Contents......Page 9 Preface......Page 15 Acknowledgments......Page 21 1. Introduction......Page 23 1.1. The Concept of a Trustworthy Compiler......Page 24 1.2. Kinds of Compilers......Page 26 1.3. Evolution of Java Compilers......Page 27 1.4. Compilation for .NET......Page 28 1.5. Phases of Compilation......Page 29 1.6. Overview of Compiler Development Principles and Technologies......Page 30 1.7. History of Compiler Development in the U.S.S.R. and in Russia......Page 35 Exercises to Chapter 1......Page 37 2.1. The Trustworthy Computing (TWC) Initiative......Page 38 2.2. TWC and Trustworthy Compilers......Page 39 2.3. Verified Compilers......Page 46 2.4. Spec#: Microsoft’s Approach to Verifying Compilers......Page 48 2.5. Perspectives of Verified and Verifying Compilation......Page 50 Exercises to Chapter 2......Page 51 3.1. Token Classes......Page 53 3.2. The Output of the Lexical Analyzer......Page 55 3.3. Processing White Spaces, Comments, and New Lines......Page 56 3.4. Theoretical Models of Lexical Analysis......Page 57 3.6. Processing Identifiers and Keywords......Page 60 3.7. The Architecture of a Lexical Analyzer and the Principles of Its Implementation......Page 64 3.8. The Lexical Analyzer Generator Lex......Page 67 3.9. Lexical Analyzer Generation in ANTLR......Page 70 Exercises to Chapter 3......Page 73 4. Parsing and Trustworthy Methods of Syntax Error Recovery......Page 74 4.1. Basic Concepts and Principles of Parsing......Page 75 4.2. Recursive Descent and Simple Lookahead Mechanism......Page 77 4.3. Overview of Error Recovery in Parsing: Error Recovery for Recursive Descent......Page 84 4.4. LR(1) and LALR(1) Parsing......Page 89 4.5. Error Recovery in LR Parsing......Page 103 4.6. The Yacc Parser Generator......Page 104 4.7. The Bison Parser Generator: Generalized LR Parsing......Page 109 4.8. The Yacc++, JavaCC, SableCC, ANTLR, and CoCo/R Object-Oriented Parser Generators......Page 111 Exercises to Chapter 4......Page 117 5.1. Basic Concepts and Principles of Semantic Analysis......Page 119 5.2. Formal Model of Semantic Analysis: Attributed Grammars......Page 121 5.3. Definition Systems with Forward References and the Algorithm of Their One-Pass Analysis......Page 125 5.4. Commonly Used Semantic Attributes for Program Constructs......Page 129 5.5. Design Flaws of the Semantic Attribute Evaluation and Our Efficient Methods to Speed It Up......Page 133 5.6. Lookup—Traditional and Novel Techniques......Page 136 5.7. Typing and Type-Checking: Basic Concepts......Page 140 5.8. Representing Types at Compile Time......Page 143 5.9. Efficient Method and Algorithm to Represent and Handle Types with Structural Identity......Page 145 5.10. Type Identity and Type Compatibility......Page 148 5.11. Type-Checking, Typing Error Diagnostics, and Recovery......Page 150 5.12. Code Trustworthiness Checks During Semantic Analysis......Page 153 5.13. Checks for Context Restrictions in Semantic Analysis......Page 161 5.14. Intermediate Code Generation—Principles and Architectural Models......Page 163 5.15. Postfix (Reverse Polish) Notation......Page 164 5.16. PCC Trees......Page 168 5.17. Triples......Page 171 5.18. Summary of the Chapter......Page 172 Exercises to Chapter 5......Page 173 6.1. Basic Concepts and Trustworthiness of Optimizations......Page 174 6.2. Optimizations as Mixed Computations......Page 176 6.3. Overview of the Most Common Kinds of Optimizations......Page 177 6.4. Control Flow and Data Flow Dependencies......Page 184 6.5. Static Single Assignment (SSA)......Page 185 6.7. Optimization in Sun Studio Compilers......Page 187 6.8. Optimizations of the Java Bytecode......Page 189 6.10. Optimizations during JIT Compilation......Page 192 Exercises to Chapter 6......Page 195 7.1. Target Platforms for Code Generation......Page 196 7.2. Overview of Code Generation Tasks and Goals......Page 197 7.3. Specifics of Code Generation for .NET......Page 201 7.4. Specifics of Code Generation for SPARC Architecture......Page 202 7.5. Representing Types and Addressing Variables......Page 203 7.6. Representing Procedures, Functions, and Methods......Page 208 7.7. Principles of SPARC Architecture......Page 212 7.8. Example of Code Generation for SPARC Architecture......Page 214 7.9. Generation of Debugging Information......Page 217 7.10. Code Generation for Declarations (Definitions), Expressions, and Statements......Page 219 Exercises to Chapter 7......Page 221 8.1. The Tasks of the Runtime......Page 222 8.2. The Relationship of the Runtime and the Operating System (OS)......Page 224 8.3. JIT Compilation......Page 225 8.4. The Architecture of FJIT––JIT Compiler for SSCLI/Rotor......Page 233 8.5. The Architecture of Optimizing JIT Compiler for SSCLI/Rotor......Page 234 8.6. AOT Compilation......Page 242 Exercises to Chapter 8......Page 243 9. Graph Grammars and Graph Compilers......Page 244 9.1. Basic Concepts of Graph Grammars and Graph Compilers......Page 245 9.2. Categorical Approach to Graph Transformations......Page 248 9.3. Reserved Graph Grammars (RGGs)......Page 252 9.4. Layered Graph Grammars......Page 254 9.5. Meta-Modeling Approach to Graph Grammars and Diameta Editor......Page 255 9.6. Hypergraph Approach to Graph Grammars in Diagen......Page 257 9.7. Graph Compiler Generation Tools......Page 259 Exercises to Chapter 9......Page 260 10. Microsoft Phoenix, Phoenix-Targeted Tools, and Our Phoenix Projects......Page 261 10.1. History of Phoenix and of Our Phoenix Projects......Page 262 10.2. Overview of Phoenix Architecture......Page 264 10.3. Phoenix-Based Tools, Passes, Phases, and Plug-Ins......Page 268 10.4. Phoenix Primitives: Strings and Names......Page 269 10.5. Phoenix Intermediate Representation (IR)......Page 270 10.6. Phoenix Symbol System......Page 275 10.7. Phoenix Type System......Page 279 10.8. Data Flow Analysis, Control Flow Analysis, Graphs, and Static Single Assignment (SSA) in Phoenix......Page 282 10.9. Overview of Other Phoenix Features......Page 286 10.10. Example of a Phoenix-Based Plug-In......Page 287 10.11. Phoenix-Fete—A Compiler Front-End Development Toolkit and Environment Targeted to Phoenix......Page 289 10.11.1. Architectural Specifics of Phoenix-FETE......Page 290 10.11.2. The Input Grammar Meta-Language......Page 291 10.11.3. The Current Status of the Implementation......Page 293 Exercises to Chapter 10......Page 296 Conclusions......Page 299 References......Page 301 Index......Page 307 Trustworthy Compilers 5 Contents 9 Preface 15 Acknowledgments 21 1. Introduction 23 1.1. The Concept of a Trustworthy Compiler 24 1.2. Kinds of Compilers 26 1.3. Evolution of Java Compilers 27 1.4. Compilation for .NET 28 1.5. Phases of Compilation 29 1.6. Overview of Compiler Development Principles and Technologies 30 1.7. History of Compiler Development in the U.S.S.R. and in Russia 35 Exercises to Chapter 1 37 2. Theoretical Foundations and Principles of Trustworthy Compilers 38 2.1. The Trustworthy Computing (TWC) Initiative 38 2.2. TWC and Trustworthy Compilers 39 2.3. Verified Compilers 46 2.4. Spec#: Microsoft’s Approach to Verifying Compilers 48 2.5. Perspectives of Verified and Verifying Compilation 50 Exercises to Chapter 2 51 3. Lexical Analysis and Its Trustworthiness Principles 53 3.1. Token Classes 53 3.2. The Output of the Lexical Analyzer 55 3.3. Processing White Spaces, Comments, and New Lines 56 3.4. Theoretical Models of Lexical Analysis 57 3.5. Lexical Errors, Error Diagnostics, and Recovery 60 3.6. Processing Identifiers and Keywords 60 3.7. The Architecture of a Lexical Analyzer and the Principles of Its Implementation 64 3.8. The Lexical Analyzer Generator Lex 67 3.9. Lexical Analyzer Generation in ANTLR 70 Exercises to Chapter 3 73 4. Parsing and Trustworthy Methods of Syntax Error Recovery 74 4.1. Basic Concepts and Principles of Parsing 75 4.2. Recursive Descent and Simple Lookahead Mechanism 77 4.3. Overview of Error Recovery in Parsing: Error Recovery for Recursive Descent 84 4.4. LR(1) and LALR(1) Parsing 89 4.5. Error Recovery in LR Parsing 103 4.6. The Yacc Parser Generator 104 4.7. The Bison Parser Generator: Generalized LR Parsing 109 4.8. The Yacc++, JavaCC, SableCC, ANTLR, and CoCo/R Object-Oriented Parser Generators 111 Exercises to Chapter 4 117 5. Semantic Analysis and Typing: Efficient and Trustworthy Techniques 119 5.1. Basic Concepts and Principles of Semantic Analysis 119 5.2. Formal Model of Semantic Analysis: Attributed Grammars 121 5.3. Definition Systems with Forward References and the Algorithm of Their One-Pass Analysis 125 5.4. Commonly Used Semantic Attributes for Program Constructs 129 5.5. Design Flaws of the Semantic Attribute Evaluation and Our Efficient Methods to Speed It Up 133 5.6. Lookup—Traditional and Novel Techniques 136 5.7. Typing and Type-Checking: Basic Concepts 140 5.8. Representing Types at Compile Time 143 5.9. Efficient Method and Algorithm to Represent and Handle Types with Structural Identity 145 5.10. Type Identity and Type Compatibility 148 5.11. Type-Checking, Typing Error Diagnostics, and Recovery 150 5.12. Code Trustworthiness Checks During Semantic Analysis 153 5.13. Checks for Context Restrictions in Semantic Analysis 161 5.14. Intermediate Code Generation—Principles and Architectural Models 163 5.15. Postfix (Reverse Polish) Notation 164 5.16. PCC Trees 168 5.17. Triples 171 5.18. Summary of the Chapter 172 Exercises to Chapter 5 173 6. Trustworthy Optimizations 174 6.1. Basic Concepts and Trustworthiness of Optimizations 174 6.2. Optimizations as Mixed Computations 176 6.3. Overview of the Most Common Kinds of Optimizations 177 6.4. Control Flow and Data Flow Dependencies 184 6.5. Static Single Assignment (SSA) 185 6.6. Data Structures Constructed and Used by the Optimizer 187 6.7. Optimization in Sun Studio Compilers 187 6.8. Optimizations of the Java Bytecode 189 6.9. Optimizations of the .NET Common Intermediate Language (CIL) Code 192 6.10. Optimizations during JIT Compilation 192 Exercises to Chapter 6 195 7. Code Generation and Runtime Data Representation 196 7.1. Target Platforms for Code Generation 196 7.2. Overview of Code Generation Tasks and Goals 197 7.3. Specifics of Code Generation for .NET 201 7.4. Specifics of Code Generation for SPARC Architecture 202 7.5. Representing Types and Addressing Variables 203 7.6. Representing Procedures, Functions, and Methods 208 7.7. Principles of SPARC Architecture 212 7.8. Example of Code Generation for SPARC Architecture 214 7.9. Generation of Debugging Information 217 7.10. Code Generation for Declarations (Definitions), Expressions, and Statements 219 Exercises to Chapter 7 221 8. Runtime, JIT, and AOT Compilation 222 8.1. The Tasks of the Runtime 222 8.2. The Relationship of the Runtime and the Operating System (OS) 224 8.3. JIT Compilation 225 8.4. The Architecture of FJIT––JIT Compiler for SSCLI/Rotor 233 8.5. The Architecture of Optimizing JIT Compiler for SSCLI/Rotor 234 8.6. AOT Compilation 242 Exercises to Chapter 8 243 9. Graph Grammars and Graph Compilers 244 9.1. Basic Concepts of Graph Grammars and Graph Compilers 245 9.2. Categorical Approach to Graph Transformations 248 9.3. Reserved Graph Grammars (RGGs) 252 9.4. Layered Graph Grammars 254 9.5. Meta-Modeling Approach to Graph Grammars and Diameta Editor 255 9.6. Hypergraph Approach to Graph Grammars in Diagen 257 9.7. Graph Compiler Generation Tools 259 Exercises to Chapter 9 260 10. Microsoft Phoenix, Phoenix-Targeted Tools, and Our Phoenix Projects 261 10.1. History of Phoenix and of Our Phoenix Projects 262 10.2. Overview of Phoenix Architecture 264 10.3. Phoenix-Based Tools, Passes, Phases, and Plug-Ins 268 10.4. Phoenix Primitives: Strings and Names 269 10.5. Phoenix Intermediate Representation (IR) 270 10.6. Phoenix Symbol System 275 10.7. Phoenix Type System 279 10.8. Data Flow Analysis, Control Flow Analysis, Graphs, and Static Single Assignment (SSA) in Phoenix 282 10.9. Overview of Other Phoenix Features 286 10.10. Example of a Phoenix-Based Plug-In 287 10.11. Phoenix-Fete—A Compiler Front-End Development Toolkit and Environment Targeted to Phoenix 289 10.11.1. Architectural Specifics of Phoenix-FETE 290 10.11.2. The Input Grammar Meta-Language 291 10.11.3. The Current Status of the Implementation 293 Exercises to Chapter 10 296 Conclusions 299 References 301 Index 307 9780470500958

the Most Complete, Real-world Guide To Compiler

development—and The Principles Of Trustworthy Compilers

drawing On The Author's Over Thirty Years Of Expertise In Compiler Development, Research, And Instruction, Trustworthy Compilers Introduces And Analyzes The Concept Of Trustworthy Compilers And The Principles Of Trustworthy Compiler Development, And Provides Analytical Overview Of Other Promising Research Works In This Area.

vladimir Safonov Shares The Benefit Of His Long Experience As A Teacher And Compiler Development Professional To Explain That—even In Such A Well-studied Area As Compilers—there Is Still An Opportunity For Original Results, Efficient Algorithms, And Promising Research And Development. Beginning With A Definition Of The Trustworthy Compiler And A Review Of The History Of Compiler Development, Trustworthy Compilers Features:

• a Complete Overview Of All Essential Compiler Topics, Including Lexical Analysis, Parsing, Semantic Analysis, Compiler Optimization, Code Generation, And Traditional And Modern Approaches To Runtime
• efficient, Ready-to-apply Algorithms For Various Phases Of Compilation, Especially For Semantic Analysis, Developed By The Author And Used In His Real Compilers
• high-yield Coverage Of Graph Compilers—a Novel Compiler Development Area—plus Related Concepts Such As Graph Grammars And Graph Compilers, And Editor Development Tools Such As Diagen
• real Projects—using Examples Of Real Compilers—that Cover The Key Topics Related To Compiler Development And Compiling Methods
• a Survey Of Novel Kinds Of Compilation, Including Just-in-time (jit) And Ahead-of-time (aot) Compilation, Which Are Characteristic Of Modern Software Development Platforms Java And .net
• sections On Modern Compiler Tools—such As Antlr, Coco/r, And Sablecc

covering Both Classical Techniques And Innovative Ones Not Covered By Other Books, Trustworthy Compilers Helps Both Practicing Professionals And Students Meet The Challenge Of Making Compilers More Trustworthy. The Book's Companion Web Page (www.vladimirsafonov.org/trustworthycompilers) Provides An Overview Of The Book And Related Resources For Compiler Teachers And Students.

This unique guide book explains and teaches the concept of trustworthy compilers based on 50+ years of worldwide experience in the area of compilers, and on the author's own 30+ years of expertise in development and teaching compilers. It covers the key topics related to compiler development as well as compiling methods not thoroughly covered in other books. The book also reveals many state-of-the-art compiler development tools and personal experience of their use in research projects by the author and his team. Software engineers of commercial companies and undergraduate/graduate students will benefit from this guide. The Most Complete, Real-World Guide to Compiler Development-and the Principles of Trustworthy Compilers Drawing on the author's over thirty years of expertise in compiler development, research, and instruction, Trustworthy Compilers introduces and analyzes the concept of trustworthy compilers and the principles of trustworthy compiler development, and provides analytical overview of other promising research works in this area. Vladimir Safonov shares the benefit of his long experience as a teacher and compiler development professional to explain that-even in such a well-studied area