Yunlin Su Song Y. Yan Principles of Compilers A New Approach to Compilers Including the Algebraic Method With 129 figures Authors Prof. Yunlin Su Prof. Song Y. Yan Head of Research Center of Information Department of Mathematics Technology Universitas Ma Chung Massachusetts Institute of Technology Villa Puncak Tidar No-01 Malang 77 Massachusetts Avenue Java Timur, Indonesia Cambridge MA 02139, U.S.A. E-mail: [email protected] E-mail: [email protected] ISBN 978-7-04-030577-7 Higher Education Press, Beijing ISBN 978-3-642-20834-8 e-ISBN 978-3-642-02835-5 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2011926225 (cid:2) Higher Education Press, Beijing and Springer-Verlag Berlin Heidelberg 2011 Preface The compileris oneofthe mostimportantaspects ofsystemsoftware.When any computer user develops a computer program, one must use some pro- gramming language, rather than using a computer instruction set. This im- plies that there must be the compiler of the programming language that has been installed on the computer one uses, and otherwise the developed program cannot be run. There are some differences between a compiler and programming lan- guage. Once language is designed, it must be kept unchanged (except when it contains a mistake that has to be corrected), while the techniques for im- plementing compilation might be changed over time. Hence people always explore the more efficient and more advanced new techniques to raise the quality of compilers. The course similar to “The principles of Compilers” has become one of the mostimportantcoursesincomputersciencewithinhigherinstitutes.Ac- cordingtoourknowledge,thedevelopmentofcompilationtechniquesevolves in two directions. One is towards the improvement of the compilation tech- niques for existing languages. Another is towards the research and develop- ment of the compilation techniques of new languages. These new languages include object-oriented languages, distributed languages, parallel languages, etc. This book introduces the newest knowledge in the field, and explores the compilation techniques suitable for the languages and computation. It associatesthe compilationof programminglanguageswith the translationof natural languages in human brains so that the reader can easier understand the principlesofcompilers.Meanwhile,itintroducesthe algebraicmethodof compilation that belongs to formal technology. This book consists of 16 chapters. Chapter 1, Introduction, outlines the process of compilation and associates the compilation of programming lan- guageswiththecomprehensionandgenerationofnaturallanguagesinhuman brains. Chapter 2 introduces the grammar and language. The generation of the language is based on the grammar and languages are the fundamentals of the compilation process. Chapter 3 introduces finite automata and regu- lar languages, together with Chapter 4, it is devoted to lexical analysis, the first task of analysis stage. Chapter 3 may be regarded as the theoretical preparation of lexical analysis; while Chapter 4 is the concrete practice of lexical analysis. Chapters 5–7 commonly work together to discuss syntacti- cal analysis. Chapter 5 introduces push-down automata that correspond to context-free grammars. Chapter 6 devotes to the discussion of context-free grammars and the context-free languages which they generate. Chapter 7 explores the second task of analyticalstage—syntacticalanalysis.Following thisisthesemanticanalysis.Aftertheanalyticalstagefinishes,thesynthetic stage starts.The maintask of the synthetic stage is to generate objectcode. Chapter8introducesandanalyzesattributegrammars.Chapter9introduces a new compilation method—the formal method of compilation. Chapter 10 discusses the generationof the intermediate code. Chapter 11 expatiates the debugging and optimization techniques for compilers. Chapter 12 explicates the memory management that is related to compilation of programs. Chap- ter 13 is the destination of the compilation, the generation of object code. The chapter introduces the virtual machine MMIX that is proposedby D.E. Knuthin his bookThe Art of Computer Programming. This virtualmachine is the mixture of features of 14 most popular machines in the current mar- ket, it has rich an instruction set, and makes object codes flexible. Chapters 14 and 15 expound the compilation techniques for object-oriented program- ming languages and parallel programming languages. Chapter 16 discusses issues for gridcomputing. Thoughgridcomputing has attractedone’satten- tion there is no any language especially suitable for grid computing at the present. Hence, we just focus on its features, pointing out the issues which the compilation of the language should be tackled when the language exists. We would like to express our sincere appreciation to Ms. Chen Hongying of Higher Education Press. Without her encouragement, help and patience, we could not finish the writing of this book. We also want to thank the authors whose contributions were referred to the book. A great part of the contents of the book is taken from them. We would like to acknowledgeTim Lammertink and Myrte de Vos for their kind help. Finally, we would like to express our gratitude to our family and students for their long-termsupport and understanding. Nodoubt,theremightbe neglectsormistakesremaininginthebook.We hope that the reader would be generous with your criticism. Yunlin Su Song Y. Yan March 2011 Contents Chapter 1 Introduction · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 1.1 Language and Mankind · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 1.2 Language and Computer · · · · · · · · · · · · · · · · · · · · · · · · · · · 3 1.3 Compilation of Programming Languages· · · · · · · · · · · · · · · · 12 1.4 Number of Passes of Compiler · · · · · · · · · · · · · · · · · · · · · · · 17 1.5 An Example of Compilation of a Statement· · · · · · · · · · · · · · 19 1.6 Organization of the Book· · · · · · · · · · · · · · · · · · · · · · · · · · · 21 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 23 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 23 Chapter 2 Grammars and Languages· · · · · · · · · · · · · · · · · · · · 25 2.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 25 2.2 Preliminary Knowledge· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 25 2.3 Grammar· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 2.4 Language· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 31 2.5 Language Generated by a Grammar · · · · · · · · · · · · · · · · · · · 34 2.6 Turing Machine · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 37 2.7 Issues Concerning Grammars and Languages· · · · · · · · · · · · · 52 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 53 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 54 Chapter 3 Finite State Automata and Regular Languages· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 55 3.1 Motivations of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 55 3.2 Languages, Grammars and Automata · · · · · · · · · · · · · · · · · · 55 3.3 Deterministic Finite Automata· · · · · · · · · · · · · · · · · · · · · · · 59 3.4 Nondeterministic Finite Automata · · · · · · · · · · · · · · · · · · · · 64 3.5 Regular Expressions· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 65 3.6 Regular Grammar · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 66 3.7 Kleene’s and Moore’s Theorems · · · · · · · · · · · · · · · · · · · · · · 68 3.8 Pumping Theorems and Closure Properties for L · · · · · · · 69 REG 3.9 Applications of Finite Automata· · · · · · · · · · · · · · · · · · · · · · 70 3.10 Variants of Finite Automata· · · · · · · · · · · · · · · · · · · · · · · · 72 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 77 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 78 Chapter 4 Lexical Analysis · · · · · · · · · · · · · · · · · · · · · · · · · · · · 79 4.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 79 4.2 Lexical Analyzer · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 80 4.2.1 Role of Lexical Analyzer· · · · · · · · · · · · · · · · · · · · · · · 81 4.2.2 Identifier Analysis · · · · · · · · · · · · · · · · · · · · · · · · · · · 84 4.2.3 Handling of Constants · · · · · · · · · · · · · · · · · · · · · · · · 86 4.2.4 Structure of Lexical Analyzer · · · · · · · · · · · · · · · · · · · 87 4.3 Output of Lexical Analyzer· · · · · · · · · · · · · · · · · · · · · · · · · · 95 4.4 Error Handling · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 97 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 98 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 98 Chapter 5 Push-Down Automata and Context-Free Languages· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 101 5.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 101 5.2 Push-Down Automata · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 102 5.3 Context-Free Languages (L ) · · · · · · · · · · · · · · · · · · · · · · · 103 CF 5.4 Pumping Theorems for Context-Free Languages· · · · · · · · · · · 105 5.5 Push-Down Automata and Context-Free Languages· · · · · · · · 106 5.6 Applications of Context-Free Languages · · · · · · · · · · · · · · · · 106 5.7 Turing Machines · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 107 5.8 Turing Machines as Language Accepters · · · · · · · · · · · · · · · · 108 5.9 Equivalence of Various Turing Machines · · · · · · · · · · · · · · · · 115 5.10 Recursively Enumerable Languages (L ) · · · · · · · · · · · · · · 116 RE 5.11 Context-Sensitive Languages (L ) · · · · · · · · · · · · · · · · · · · 117 CS 5.12 Hierarchy of Machines, Grammars and Languages · · · · · · · · 119 5.12.1 Hierarchy of Machines· · · · · · · · · · · · · · · · · · · · · · · · 119 5.12.2 Hierarchy of Grammars and Languages · · · · · · · · · · · 120 5.13 Relations Among Machines, Languages and Grammars· · · · · 121 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 124 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 124 Chapter 6 Context-Free Grammars · · · · · · · · · · · · · · · · · · · · · 125 6.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 125 6.2 Context-Free Grammars· · · · · · · · · · · · · · · · · · · · · · · · · · · · 126 6.3 Characteristics of Context-Free Grammars· · · · · · · · · · · · · · · 135 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 154 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 155 Chapter 7 Syntax Analysis · · · · · · · · · · · · · · · · · · · · · · · · · · · · 157 7.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 157 7.2 Role of Syntax Analysis in Compilers · · · · · · · · · · · · · · · · · · 158 7.3 Methods of Syntax Analysis · · · · · · · · · · · · · · · · · · · · · · · · · 161 7.4 LL(1) Syntactical Analysis Method· · · · · · · · · · · · · · · · · · · · 173 7.5 Bottom-Up Syntactical Analysis Method· · · · · · · · · · · · · · · · 180 7.6 LR(1) Syntactical Analysis Method· · · · · · · · · · · · · · · · · · · · 185 7.6.1 LR(0) Syntactical Analysis· · · · · · · · · · · · · · · · · · · · · 185 7.6.2 SLR(1) Syntactical Analysis· · · · · · · · · · · · · · · · · · · · 189 7.6.3 LALR(1) Syntactical Analysis· · · · · · · · · · · · · · · · · · · 191 7.6.4 LR(1) Syntactical Analysis· · · · · · · · · · · · · · · · · · · · · 193 7.6.5 Comparison Between LL(1) Syntactical Analysis Method and LR(1) Syntactical Analysis Method · · · · · 202 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 205 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 206 Chapter 8 Attribute Grammars and Analysis· · · · · · · · · · · · · 207 8.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 207 8.2 Attribute Grammar · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 208 8.3 Dependence Graph and Evaluation of Attributes · · · · · · · · · · 212 8.3.1 Dynamic Attribute Evaluation · · · · · · · · · · · · · · · · · · 217 8.3.2 Loop Handling· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 221 8.4 L Attribute Grammas and S Attribute Grammars · · · · · · · · · 222 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 225 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 227 Chapter 9 Algebraic Method of Compiler Design· · · · · · · · · · 229 9.1 Motivation of the Chapter · · · · · · · · · · · · · · · · · · · · · · · · · · 229 9.2 Source Language · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 230 9.3 Algebraic Foundation and Reasoning Language · · · · · · · · · · · 238 9.3.1 Algebra Fundamentals · · · · · · · · · · · · · · · · · · · · · · · · 239 9.3.2 Reasoning Language· · · · · · · · · · · · · · · · · · · · · · · · · · 247 9.4 A Simple Compiler· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 275 9.4.1 The Normal Form · · · · · · · · · · · · · · · · · · · · · · · · · · · 276 9.4.2 Normal Form Reduction· · · · · · · · · · · · · · · · · · · · · · · 277 9.4.3 The Target Machine· · · · · · · · · · · · · · · · · · · · · · · · · · 281 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 282 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 282 Chapter 10 Generation of Intermediate Code· · · · · · · · · · · · · 285 10.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 285 10.2 Intermediate Code Languages· · · · · · · · · · · · · · · · · · · · · · · 286 10.2.1 Graphic Representation · · · · · · · · · · · · · · · · · · · · · · 287 10.2.2 Postfix Representation · · · · · · · · · · · · · · · · · · · · · · · 290 10.2.3 The Quadruple Code · · · · · · · · · · · · · · · · · · · · · · · · 292 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 311 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 312 Chapter 11 Debugging and Optimization · · · · · · · · · · · · · · · · 313 11.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 313 11.2 Errors Detection and Recovery · · · · · · · · · · · · · · · · · · · · · · 313 11.3 Debugging of Syntax Errors · · · · · · · · · · · · · · · · · · · · · · · · 316 11.3.1 Error Handling of LL(1) Parser· · · · · · · · · · · · · · · · · 318 11.3.2 Error Handling in LR(1) Analysis · · · · · · · · · · · · · · · 319 11.4 Semantic Error Check· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 319 11.5 Optimization of Programs· · · · · · · · · · · · · · · · · · · · · · · · · · 320 11.6 Principal Ways of Optimization· · · · · · · · · · · · · · · · · · · · · · 324 11.6.1 Elimination of Subexpressions· · · · · · · · · · · · · · · · · · 324 11.6.2 Copy Propagation· · · · · · · · · · · · · · · · · · · · · · · · · · · 325 11.6.3 Dead-Code Elimination· · · · · · · · · · · · · · · · · · · · · · · 326 11.6.4 Loop Optimization· · · · · · · · · · · · · · · · · · · · · · · · · · 327 11.6.5 Reduction of Strength· · · · · · · · · · · · · · · · · · · · · · · · 328 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 329 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 330 Chapter 12 Storage Management· · · · · · · · · · · · · · · · · · · · · · · 331 12.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 331 12.2 Global Allocation Strategy · · · · · · · · · · · · · · · · · · · · · · · · · 332 12.3 Algorithms for Allocation· · · · · · · · · · · · · · · · · · · · · · · · · · 334 12.3.1 Algorithm for Stack Allocation · · · · · · · · · · · · · · · · · 334 12.3.2 Algorithm for Heap Allocation · · · · · · · · · · · · · · · · · 336 12.4 Reclamation of Used Space· · · · · · · · · · · · · · · · · · · · · · · · · 337 12.4.1 Basic Garbage Collection Algorithm · · · · · · · · · · · · · 338 12.4.2 Supports to Garbage Collector From Compilers · · · · · 340 12.4.3 Reference Counts · · · · · · · · · · · · · · · · · · · · · · · · · · · 342 12.4.4 Tokens and Scans· · · · · · · · · · · · · · · · · · · · · · · · · · · 343 12.4.5 Dual Space Copy · · · · · · · · · · · · · · · · · · · · · · · · · · · 344 12.4.6 Contract · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 345 12.5 Parameter Passing · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 346 12.5.1 Call-by-Value· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 347 12.5.2 Call-by-References · · · · · · · · · · · · · · · · · · · · · · · · · · 347 12.5.3 Copy-Restore· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 348 12.5.4 Call-by-Name· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 348 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 349 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 351 Chapter 13 Generation of Object Code· · · · · · · · · · · · · · · · · · 353 13.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 353 13.2 Issues of Design of Generators of Target Codes· · · · · · · · · · · 354 13.2.1 Input of Code Generators· · · · · · · · · · · · · · · · · · · · · 354 13.2.2 Target Programs · · · · · · · · · · · · · · · · · · · · · · · · · · · 355 13.2.3 Storages Management· · · · · · · · · · · · · · · · · · · · · · · · 355 13.2.4 Selection of Instructions · · · · · · · · · · · · · · · · · · · · · · 356 13.2.5 Register Allocation· · · · · · · · · · · · · · · · · · · · · · · · · · 357 13.2.6 Selection of Order of Computation · · · · · · · · · · · · · · 358 13.2.7 Method of Generation of Codes· · · · · · · · · · · · · · · · · 358 13.3 Target Machine MMIX· · · · · · · · · · · · · · · · · · · · · · · · · · · · 358 13.3.1 Binary Bits and Bytes · · · · · · · · · · · · · · · · · · · · · · · 359 13.3.2 Memory and Registers · · · · · · · · · · · · · · · · · · · · · · · 361 13.3.3 Instructions · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 362 13.3.4 Load and Store· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 363 13.3.5 Arithmetic Operations · · · · · · · · · · · · · · · · · · · · · · · 365 13.3.6 Conditional Instructions· · · · · · · · · · · · · · · · · · · · · · 367 13.3.7 Bit Operations· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 368 13.3.8 Byte Operations· · · · · · · · · · · · · · · · · · · · · · · · · · · · 369 13.3.9 Jumps and Branches· · · · · · · · · · · · · · · · · · · · · · · · · 373 13.3.10 Subprogram Calls· · · · · · · · · · · · · · · · · · · · · · · · · · 375 13.3.11 Interruptions · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 377 13.4 Assembly Language of MMIX· · · · · · · · · · · · · · · · · · · · · · · 382 13.5 Generation of MMIXAL Target Codes· · · · · · · · · · · · · · · · · 389 13.5.1 Translation of Expressions in Reversed Polish Form· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 390 13.5.2 Translation of Triple Expressions· · · · · · · · · · · · · · · · 390 13.5.3 Translation of ExpressionQuadruples · · · · · · · · · · · · 391 13.5.4 Translation of Expressions · · · · · · · · · · · · · · · · · · · · 392 13.5.5 Translation of Syntax Tree Form of Expressions· · · · · 393 13.5.6 Translation of Various Statements· · · · · · · · · · · · · · · 394 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 395 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 397 Chapter 14 Compilation of Object-oriented Languages · · · · · 399 14.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 399 14.2 Objects and Compilation · · · · · · · · · · · · · · · · · · · · · · · · · · 400 14.3 Characteristics of Objects· · · · · · · · · · · · · · · · · · · · · · · · · · 403 14.3.1 Inheritance· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 403 14.3.2 Method Overload· · · · · · · · · · · · · · · · · · · · · · · · · · · 404 14.3.3 Polymorphic· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 405 14.3.4 Dynamic Constraint· · · · · · · · · · · · · · · · · · · · · · · · · 406 14.3.5 Multiple Inheritances · · · · · · · · · · · · · · · · · · · · · · · · 408 14.3.6 Multiple Inheritances of Inter-reliance · · · · · · · · · · · · 410 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 412 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 413 Chapter 15 Compilation of Parallel Languages· · · · · · · · · · · · 415 15.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 415 15.2 Rising of ParallelComputers and Parallel Computation · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 415 15.3 ParallelProgramming· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 419 15.3.1 Shared Variables and Monitors · · · · · · · · · · · · · · · · · 420 15.3.2 Message Passing Model· · · · · · · · · · · · · · · · · · · · · · · 422 15.4 Object-oriented Languages · · · · · · · · · · · · · · · · · · · · · · · · · 424 15.5 Linda Meta Array Space· · · · · · · · · · · · · · · · · · · · · · · · · · · 425 15.6 Data Parallel Languages· · · · · · · · · · · · · · · · · · · · · · · · · · · 427 15.7 Code Generation for Hidden Parallel Programs · · · · · · · · · · 428 15.7.1 Types of Regions · · · · · · · · · · · · · · · · · · · · · · · · · · · 430 15.7.2 Formation of Regions · · · · · · · · · · · · · · · · · · · · · · · · 431 15.7.3 Schedule Algorithms for Regions· · · · · · · · · · · · · · · · 436 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 437 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 437 Chapter 16 Compilation of Grid Computing· · · · · · · · · · · · · · 439 16.1 Motivation of the Chapter· · · · · · · · · · · · · · · · · · · · · · · · · · 439 16.2 Rising of Grid Computing and Intent · · · · · · · · · · · · · · · · · 439 16.3 Grid Computing Model· · · · · · · · · · · · · · · · · · · · · · · · · · · · 442 16.3.1 Group Routing· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 443 16.3.2 Routing in Linear Array· · · · · · · · · · · · · · · · · · · · · · 445 16.4 Compilation of Grid Computing · · · · · · · · · · · · · · · · · · · · · 447 Problems· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 450 References· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 450 Index · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 451