Compiler Constr Uction-Books Pdf

COMPILER CONSTR UCTION
24 Sep 2020 | 1 views | 0 downloads | 372 Pages | 1.87 MB

Share Pdf : Compiler Constr Uction

Download and Preview : Compiler Constr Uction

Report CopyRight/DMCA Form For : Compiler Constr Uction



Transcription

To all who know more than one language, Compilers and operating systems constitute the basic interfaces between a programmer and. the machine for which he is developing software In this book we are concerned with the. construction of the former Our intent is to provide the reader with a rm theoretical basis. for compiler construction and sound engineering principles for selecting alternate methods. implementing them and integrating them into a reliable economically viable product The. emphasis is upon a clean decomposition employing modules that can be re used for many com. pilers separation of concerns to facilitate team programming and exibility to accommodate. hardware and system constraints A reader should be able to understand the questions he. must ask when designing a compiler for language X on machine Y what tradeo s are possible. and what performance might be obtained He should not feel that any part of the design rests. on whim each decision must be based upon speci c identi able characteristics of the source. and target languages or upon design goals of the compiler. The vast majority of computer professionals will never write a compiler Nevertheless. study of compiler technology provides important bene ts for almost everyone in the eld. It focuses attention on the basic relationships between languages and machines Un. derstanding of these relationships eases the inevitable transitions to new hardware and. programming languages and improves a person s ability to make appropriate tradeo s. in design and implementation, It illustrates application of software engineering techniques to the solution of a signi cant. problem The problem is understandable to most users of computers and involves both. combinatorial and data processing aspects, Many of the techniques used to construct a compiler are useful in a wide variety of appli. cations involving symbolic data In particular every man machine interface constitutes. a form of programming language and the handling of input involves these techniques. We believe that software tools will be used increasingly to support many aspects of. compiler construction Much of Chapters 7 and 8 is therefore devoted to parser gen. erators and analyzers for attribute grammars The details of this discussion are only. interesting to those who must construct such tools the general outlines must be known. to all who use them We also realize that construction of compilers by hand will remain. an important alternative and thus we have presented manual methods even for those. situations where tool use is recommended, Virtually every problem in compiler construction has a vast number of possible solutions. We have restricted our discussion to the methods that are most useful today and make no. attempt to give a comprehensive survey Thus for example we treat only the LL and LR. parsing techniques and provide references to the literature for other approaches Because we. do not constantly remind the reader that alternative solutions are available we may sometimes. appear overly dogmatic although that is not our intent. ii Preface, Chapters 5 and 8 and Appendix B state most theoretical results without proof Although.
this makes the book unsuitable for those whose primary interest is the theory underlying a. compiler we felt that emphasis on proofs would be misplaced Many excellent theoretical. texts already exist our concern is reduction to practice. A compiler design is carried out in the context of a particular language machine pair. Although the principles of compiler construction are largely independent of this context the. detailed design decisions are not In order to maintain a consistent context for our major. examples we therefore need to choose a particular source language and target machine The. source language that we shall use is de ned in Appendix A We chose not to use an existing. language for several reasons the most important being that a new language enabled us to. control complexity Features illustrating signi cant questions in compiler design could be. included while avoiding features that led to burdensome but obvious detail It also allows. us to illustrate how a compiler writer derives information about a language and provides an. example of an informal but relatively precise language de nition. We chose the machine language of the IBM 370 and its imitators as our target This. architecture is widely used and in many respects it is a di cult one to deal with The. problems are representative of many computers the important exceptions being those such. as the Intel 8086 without a set of general registers As we discuss code generation and. assembly strategies we shall point out simpli cations for more uniform architectures like. those of the DEC PDP11 and Motorola 68000, We assume that the reader has a minimum of one year of experience with a block. structured language and some familiarity with computer organization Chapters 5 and 8. use notation from logic and set theory but the material itself is straightforward Several. important algorithms are based upon results from graph theory summarized in Appendix B. This book is based upon many compiler projects and upon the lectures given by the. authors at the Universit at Karlsruhe and the University of Colorado For self study we. recommend that a reader with very little background begin with Section 1 1 Chapters 2. and 3 Section 12 1 and Appendix A His objective should be to thoroughly understand the. relationships between typical programming languages and typical machines relationships that. de ne the task of the compiler It is useful to examine the machine code produced by existing. compilers while studying this material The remainder of Chapter 1 and all of Chapter 4 give. an overview of the organization of a compiler and the properties of its major data structures. while Chapter 14 shows how three production compilers have been structured From this. material the reader should gain an appreciation for how the various subtasks relate to one. another and the important characteristics of the interfaces between them. Chapters 5 6 and 7 deal with the task of determining the structure of the source program. This is perhaps the best understood of all compiler tasks and the one for which the most. theoretical background is available The theory is summarized in Chapter 5 and applied in. Chapters 6 and 7 Readers who are not theoretically inclined and who are not concerned. with constructing parser generators should skim Chapter 5 Their objectives should be to. understand the notation for describing grammars to be able to deal with nite automata. and to understand the concept of using a stack to resolve parenthesis nesting These readers. should then concentrate on Chapter 6 Section 7 1 and the recursive descent parse algorithm. of Section 7 2 2, The relationship between Chapter 8 and Chapter 9 is similar to that between Chapter 5. and Chapter 7 but the theory is less extensive and less formal This theory also underlies. parts of Chapters 10 and 11 We suggest that the reader who is actually engaged in com. piler construction devote more e ort to Chapters 8 11 than to Chapters 5 7 The reason is. that parser generators can be obtained o the shelf and used to construct the lexical and. syntactic analysis modules quickly and reliably A compiler designer must typically devote. Preface iii, most of his e ort to specifying and implementing the remainder of the compiler and hence. familiarity with Chapters 8 11 will have a greater e ect on his productivity. The lecturer in a one semester three hour course that includes exercises is compelled to. restrict himself to the fundamental concepts Details of programming languages Chapter 2. machines Chapter 3 and formal languages and automata theory Chapter 5 can only be. covered in a cursory fashion or must be assumed as background The speci c techniques. for parser development and attribute grammar analysis as well as the whole of Chapter 13. must be reserved for a separate course It seems best to present theoretical concepts from. Chapter 5 in close conjunction with the speci c methods of Chapters 6 and 7 rather than as. a single topic A typical outline is, 1 The Nature of the Problem 4 hours. 1 1 Overview of compilation Chapter 1, 1 2 Languages and machines Chapters 2 and 3.
2 Compiler Data Structures Chapter 4 4 hours, 3 Structural Analysis 10 hours. 3 1 Formal Systems Chapter 5, 3 2 Lexical analysis Chapter 6. 3 3 Parsing Chapter 7, Review and Examination 2 hours. 4 Consistency Checking 10 hours, 4 1 Attribute grammars Chapter 8. 4 2 Semantic analysis Chapter 9, 5 Code Generation Chapter 10 8 hours.
6 Assembly Chapter 11 2 hours, 7 Error Recovery Chapter 12 3 hours. Review 2 hours, The students do not write a compiler during this course For several years it has been. run concurrently with a practicum in which the students implement the essential parts of a. LAX compiler They are given the entire compiler with stubs replacing the parts they are to. write In contrast to project courses in which the students must write a complete compiler this. approach has the advantage that they need not be concerned with unimportant organizational. tasks Since only the central problems need be solved one can deal with complex language. properties At the same time students are forced to read the environment programs and to. adhere to interface speci cations Finally if a student cannot solve a particular problem it. does not cause his entire project to fail since he can take the solution given by the instructor. and proceed, Acknowledgements, This book is the result of many years of collaboration The necessary research projects and. travel were generously supported by our respective universities the Deutsche Forschungsge. meinschaft and the National Science Foundation, It is impossible to list all of the colleagues and students who have in uenced our work. We would however like to specially thank four of our doctoral students Lynn Carter Bruce. Haddon Uwe Kastens and Johannes R ohrich for both their technical contributions and their. willingness to read the innumerable manuscripts generated during the book s gestation Mae. Jean Ruehlman and Gabriele Sahr also have our gratitude for learning more than they ever. wanted to know about computers and word processing as they produced and edited those. manuscripts, iv Preface, Contents v, 1 Introduction and Overview 1.
1 1 Translation and Interpretation 1, 1 2 The Tasks of a Compiler 3. 1 3 Data Management in a Compiler 5, 1 4 Compiler Structure 6. 1 5 Notes and References 9, 2 Properties of Programming Languages 11. 2 1 Overview 11, 2 1 1 Syntax Semantics and Pragmatics 11. 2 1 2 Syntactic Properties 12, 2 1 3 Semantic Properties 14.
2 2 Data Objects and Operations 15, 2 2 1 Elementary Types 16. 2 2 2 Composite Types 18, 2 2 3 Strings 19, 2 2 4 Pointers 19. 2 2 5 Type Equivalence 20, 2 3 Expressions 21, 2 4 Control Structures 23. 2 5 Program Environments and Abstract Machine States 25. 2 5 1 Constants Variables and Assignment 25, 2 5 2 The Environment 26. 2 5 3 Binding 31, 2 6 Notes and References 34, 3 Properties of Real and Abstract Machines 37.
3 1 Basic Characteristics 37, 3 1 1 Storage Classes 38. 3 1 2 Access Paths 40, 3 1 3 Operations 42, 3 2 Representation of Language Elements 43. 3 2 1 Elementary Objects 43, 3 2 2 Composite Objects 45. 3 2 3 Expressions 48, 3 2 4 Control Structures 51, vi Contents. 3 3 Storage Management 55, 3 3 1 Static Storage Management 55.
3 3 2 Dynamic Storage Management Using a Stack 56, 3 3 3 Dynamic Storage Management Using a Heap 60. 3 4 Mapping Speci cations 63, 3 5 Notes and References 64. 4 Abstract Program Representation 69, 4 1 Intermediate Languages 69. 4 1 1 Token Sequence 69, 4 1 2 Structure Tree 70, 4 1 3 Computation Graph 73. 4 1 4 Target Tree 74, 4 2 Global Tables 77, 4 2 1 Symbol Table 77.
4 2 2 Constant Table 79, 4 2 3 De nition Table 80, 4 3 Notes and References 81. 5 Elements of Formal Systems 83, 5 1 Descriptive Tools 83. 5 1 1 Strings and Rewriting Systems 83, 5 1 2 Grammars 84. 5 1 3 Derivations and Parse Trees 86, 5 1 4 Extended Backus Naur Form 89. 5 2 Regular Grammars and Finite Automata 91, 5 2 1 Finite Automata 91.
5 2 2 State Diagrams and Regular Expressions 93, 5 3 Context Free Grammars and Pushdown Automata 96. 5 3 1 Pushdown Automata 97, 5 3 2 Top Down Analysis and LL k Grammars 98. 5 3 3 Bottom Up Analysis and LR k Grammars 103, 5 4 Notes and References 108. 6 Lexical Analysis 111, 6 1 Modules and Interfaces 111. 6 1 1 Decomposition of the Grammar 111, 6 1 2 Lexical Analyzer Interface 112.
6 2 Construction 113, 6 2 1 Extraction and Representation 113. 6 2 2 State Minimization 115, 6 2 3 Programming the Lexical Analyzer 116. 6 3 Notes and References 119, 7 Parsing 123, 7 1 Design 123. 7 1 1 The Parser Interface 123, 7 1 2 Selection of the Parsing Algorithm 125. 7 1 3 Parser Construction 126, 7 2 LL 1 Parsers 127.
Contents vii, 7 2 1 Strong LL k Grammars 127, 7 2 2 The Parse Algorithm 129. 7 2 3 Computation of FIRST and FOLLOW Sets 134, 7 3 LR Parsers 136. 7 3 1 The Parse Algorithm 137, 7 3 2 SLR 1 and LALR 1 Grammars 138. 7 3 3 Shift Reduce Transitions 143, 7 3 4 Chain Production Elimination 144. 7 3 5 Implementation 146, 7 4 Notes and References 148.
COMPILER CONSTR UCTION William M W aite Departmen tof Electrical Engineering Univ ersit y of Colorado Boulder Colorado 80309 USA email William Waite colorado e du Gerhard Go os Institut Programmstrukturen und Datenorganisation F akult at f ur Informatik Univ ersit at Karlsruhe D 76128 Karlsruhe German y email ggoos ipd info uni karl sruh e d e Compiler Construction a mo dern text written

Related Books

COMPILER CONSTR UCTION Carnegie Mellon School of

COMPILER CONSTR UCTION Carnegie Mellon School of

COMPILER CONSTR UCTION William M W aite Departmen tof Electrical Engineering Univ ersit y of Colorado Boulder Colorado 80309 USA email William Waite colorado e du Gerhard Go os Institut Programmstrukturen und Datenorganisation F akult at f ur Informatik Univ ersit at Karlsruhe D 76128 Karlsruhe German y email ggoos ipd info uni karl sruh e d e Compiler Construction a mo dern text written

AMD Catalyst Installer Notes for Linux

AMD Catalyst Installer Notes for Linux

z Linux Feedback Program Note To successfully install the AMD Catalyst proprietary driver you should uninstall any third party graphics driver such as NVIDIA proprietary graphics driver for Linux currently on your system Note AMD recommends that you create a central location for your AMD Catalyst proprietary driver downloads

i MX Linux User s Guide NXP Semiconductors

i MX Linux User s Guide NXP Semiconductors

Linux OS BSP where BSP IMXLXRM Contains the information on Linux drivers for i MX i MX Graphics User s Guide IMXGRAPHICUG Describes the graphics features i MX BSP Porting Guide IMXXBSPPG Contains the instructions on porting the BSP to a new board i MX VPU Application Programming Interface Linux Reference Manual IMXVPUAPI Provides the reference

The Android graphics path eLinux

The Android graphics path eLinux

Inception of a pixel Everything begins when an activity draws to a surface 2D applications can use drawing functions in Canvas to write to a Bitmap android graphics Canvas drawRect drawText etc descendants of the View class to draw objects such as buttons and lists a custom View class to implement your own appearance and behaviour In all cases the drawing is

From Click to Pixel A Tour of the Linux Graphics Stack

From Click to Pixel A Tour of the Linux Graphics Stack

From Click to Pixel A Tour of the Linux Graphics Stack Carl Worth carl d worth intel com Overview What the stacks looks like 2D and 3D Tutorial Inspecting rendering layer by layer What s changing now 1 From Click to Pixel A Tour of the Linux Graphics Stack Alphabet Soup 2 From Click to Pixel A Tour of the Linux Graphics Stack Alphabet Soup Qt Arthur GTK Pango Cairo OpenGL Mesa GLX

The Linux graphics stack Optimus and the Nouveau driver

The Linux graphics stack Optimus and the Nouveau driver

The Linux graphics stack Optimus and the Nouveau driver Cooperative rendering across GPUs on Linux Martin Peres Nouveau developer PhD student at LaBRI X Org Foundation board member September 26 2014 Introduction to the Linux graphics stack Optimus Prime Nouveau Q amp A Summary 1 Introduction to the Linux graphics stack General overview Kernel space User space 2 Optimus 3 Prime 4 Nouveau 5 Q amp

The Modern Linux Graphics Stack on Embedded Systems

The Modern Linux Graphics Stack on Embedded Systems

The Modern Linux Graphics Stack on Embedded Systems Michael Tretter m tretter pengutronix de 2 44 User Interface for Linux Desktop 3 44 Desktop Environment Window Manager Choose desktop environment GNOME KDE Install desktop environment Graphical user interface just works But what about embedded systems 4 44 Agenda Modern Linux Graphics Stack Graphics in Embedded Systems

Engineering Communications to Improve the Customer

Engineering Communications to Improve the Customer

A communication engineering team can help reduce these unintended consequences Experts trained in the structure of human behavior use a scientific approach to re engineer an invoice that will save companies time and money while improving the overall customer experience Transaction based documents such as invoices and contracts

Introduction to Communication Systems

Introduction to Communication Systems

Introduction to Communication Systems James Flynn Sharlene Katz Communications System Diagram 2 Flynn Katz SDR July 1 2010 Information Source and Input Transducer Transmitter Channel Receiver Output Transducer Communications System Diagram 3 Flynn Katz SDR July 1 2010 Information Source and Input Transducer Transmitter Channel Receiver Output Transducer Information Source Audio

DEPARTAMENTO DE MEDICINA VETERIN RIA

DEPARTAMENTO DE MEDICINA VETERIN RIA

de tema Abordagem diagn stica e terap utica a Epilepsia Idiop tica Canina e a terceira e ltima parte referente a um caso cl nico de um c o com Epilepsia Idiop tica As convuls es s o o dist rbio neurol gico mais comum em c es sendo a maioria devido a Epilepsia Idiop tica Esta caracterizada por crises epil ticas espont neas imprevis veis e recorrentes sem