A Retargetable C Compiler: Design and Implementation

Paperback (Print)
Used and New from Other Sellers
Used and New from Other Sellers
from $39.50
Usually ships in 1-2 business days
(Save 43%)
Other sellers (Paperback)
  • All (10) from $39.50   
  • New (5) from $61.18   
  • Used (5) from $39.50   

Overview

This new text examines the design and implementation of lcc, a production-quality, retargetable compiler for the ANSI C programming language, designed at AT&T Bell Laboratories and Princeton University. The authors' innovative approach--a "literate program" that intermingles the text with the source code--gives a detailed tour of the code that explains the implementation and design decisions reflected in the software. And while most books describe toy compilers or focus on isolated pieces of code, the authors provide the entire source code for a real compiler, which is available via ftp. Structured as a self-study guide that describes the real-world tradeoffs encountered in building a production-quality compiler, this book is useful to individuals who work in application areas applying or creating language-based tools and techniques.

  • Explores the interaction between compiler theory and practice through the discussion of lcc.
  • Covers compiler theory only as needed to understand the implementation of lcc, focusing instead on practical, applied issues.
  • Encourages a broader understanding of programming in C through an examination of lcc, a production-quality compiler in use since 1988.
  • Provides full code generators for the MIPS R3000, SPARC, and Intel 80x86 architectures and successors.
  • The full source code for the lcc compiler, the three back ends, and the code-generator generator is freely available.
  • Uses icons and brief indices in the margins to cross- reference code fragments and connect code usage.
Audience

Senior undergraduate or graduate level second course. Any researcher or implementer of compilers for parallel or advanced computers.

0805316701B04062001

This new book examines the implementation of Icc, a production-quality, research-oriented retargetable compiler, designed for the ANSI C programming language. The author's innovative approach uses a line-by-line explanation of the code to demonstrate how Icc is built. Accompanying disk contains the full source code for the Icc compiler, the back ends, and the code-generator.

Read More Show Less

Product Details

  • ISBN-13: 9780805316704
  • Publisher: Addison-Wesley
  • Publication date: 1/31/1995
  • Edition description: New Edition
  • Pages: 592
  • Product dimensions: 7.20 (w) x 9.10 (h) x 1.40 (d)

Meet the Author

Since 1975, Christopher W. Fraser has researched compiling, particularly producing code generators automatically from compact specs, and has published many technical articles in this area. He originated retargetable peephole optimization, which GCC, a popular C compiler, uses to help select instructions. From 1977 until 1986, Fraser taught computer science, including compiling, at the University of Arizona. Since 1986, Fraser has conducted computing research at AT&T Bell Laboratories in Murray Hill, New Jersey.

David R. Hanson is a Professor of Computer Science at Princeton University with more than 20 years of research experience in programming languages. He has conducted research in conjunction with Bell Laboratories and is the co-author of lcc, a production quality, research compiler for the C language that is popular with the Unix community. lcc is presented and analyzed in the book A Retargetable C Compiler: Design and Implementation , by Christopher Fraser and David Hanson (c) 1995, Addison-Wesley.

0805316701AB04062001

Read More Show Less

Read an Excerpt

The compiler is the linchpin of the programmer's toolbox. Working programmers use compilers every day and count heavily on their correctness and reliability. A compiler must accept the standard definition of the programming language so that source code will be portable across platforms. A compiler must generate efficient object code. Perhaps more important, a compiler must generate correct object code; an application is only as reliable as the compiler that compiled it.

A compiler is itself a large and complex application that is worthy of study in its own right. This book tours most of the implementation of lcc, a compiler for the ANSI C programming language. It is to compiling what Software Tools by B.W. Kernighan and P.J. Plauger (Addison-Wesley, 1976) is to text processing like text editors and macro processors. Software design and implementation are best learned through experience with real tools. This book explains in detail and shows most of the code for a real compiler. The accompanying diskette holds the source code for the complete compiler.

lcc is a production compiler. It's been used to compile production programs since 1988 and is now used by hundreds of C programmers daily. Detailing most of a production compiler in a book leaves little room for supporting material, so we present only the theory needed for the implementation at hand and leave the broad survey of compiling techniques to existing texts. The book omits a few language features—those with mundane or repetitive implementations and those deliberately treated only in the exercises—but the full compiler is available on the diskette, and the book makes it understandable.

The obvious use for this book is to learn more about compiler construction. But only few programmers need to know how to design and implement compilers. Most work on applications and other aspects of systems programming. There are four reasons why this majority of C programmers may benefit from this book.

First, programmers who understand how a C compiler works are often better programmers in general and better C programmers in particular. The compiler writer must understand even the darkest corners of the C language; touring the implementation of those corners reveals much about the language itself and its efficient realization on modern computers.

Second, most texts on programming must necessarily use small examples, which often demonstrate techniques simply and elegantly. Most programmers, however, work on large programs that have evolved—or degenerated—over time. There are few well documented examples of this kind of "programming in the large" that can serve as reference examples. lcc isn't perfect, but this book documents both its good and bad points in detail and thus provides one such reference point.

Third, a compiler is one of the best demonstrations in computer science of the interaction between theory and practice. lcc displays both the places where this interaction is smooth and the results are elegant, as well as where practical demands strain the theory, which shows in the resulting code. Exploring these interactions in a real program helps programmers understand when, where, and how to apply different techniques. lcc also illustrates numerous C programming techniques.

Fourth, this book is an example of a "literate program." Like TEX: The Program by D.E. Knuth (Addison-Wesley, 1986), this book is lcc's source code and the prose that describes it. The code is presented in the order that best suits understanding, not in the order dictated by the C programming language. The source code that appears on the diskette is extracted automatically from the book's text files.

This book is well suited for self-study by both academics and professionals. The book and its diskette offer complete documented source code for lcc, so they may interest practitioners who wish to experiment with compilation or those working in application areas that use or implement language-based tools and techniques, such as user interfaces.

The book shows a large software system, warts and all. It could thus be the subject of a postmortem in a software engineering course, for example.

For compiler courses, this book complements traditional compiler texts. It shows one way of implementing a C compiler, while traditional texts survey algorithms for solving the broad range of problems encountered in compiling. Limited space prevents such texts from including more than a toy compiler. Code generation is often treated at a particularly high level to avoid tying the book to a specific computer.

As a result many instructors prepare a substantial programming project to give their students some practical experience. These instructors usually must write these compilers from scratch; students duplicate large portions and have to use the rest with only limited documentation. The situation is trying for both students and instructors, and unsatisfying to boot, because the compilers are still toys. By documenting most of a real compiler and providing the source code, this book offers an alternative.

This book presents full code generators for the MIPS R3000, SPARC, and Intel 386 and successor architectures. It exploits recent research that produces code generators from compact specifications. These methods allow us to present complete code generators for several machines, which no other book does. Presenting several code generators avoids tying the book to a single machine, and helps students appreciate engineering retargetable software.

Assignments can add language features, optimizations, and targets. When used with a traditional survey text, assignments could also replace existing modules with those using alternate algorithms. Such assignments come closer to the actual practice of compiler engineering than assignments that implement most of a toy compiler, where too much time goes to low-level infrastructure and accommodating repetitive language features. Many of the exercises pose just these kinds of engineering problems.

lcc has also been adapted for purposes other than conventional compilation. For example, it's been used for building a C browser and for generating remote-procedure-call stubs from declarations. It could also be used to experiment with language extensions, proposed computer architectures and code-generator technologies.

We assume readers are fluent in C and assembly language for some computer, know what a compiler is and have a general understanding of what one does, and have a working understanding of data structures and algorithms at the level covered in typical undergraduate courses; the material covered by Algorithms in C by R. Sedgewick (Addison-Wesley, 1990), for example, is more than sufficient for understanding lcc.

Acknowledgments

This book owes much to the many lcc users at AT&T Bell Laboratories, Princeton University, and elsewhere who suffered through bugs and provided valuable feedback. Those who deserve explicit thanks include Hans Boehm, Mary Fernandez, Michael Golan, Paul Haahr, Brian Kernighan, Doug McIlroy, Rob Pike, Dennis Ritchie, and Ravi Sethi. Ronald Guilmette, David Kristol, David Prosser, and Dennis Rithchie provided valuable information concerning the fine points of the ANSI Standard and its interpretation. David Gay helped us adapt the PFORT library of numerical software to be an invaluable stress test for lcc's code generators.

Careful reviews of both our code and our prose by Jack Davidson, Todd Proebsting, Norman Ramsey, William Waite, and David Wall contributed significantly to the quality of both. Our thanks to Steve Beck, who installed and massaged the fonts used for this book, and to Maylee Noah, who did the artwork with Adobe Illustrator.

Christopher W. Fraser David R. Hanson

Read More Show Less

Table of Contents

Preface.

1. Introduction.

Literate Programs.

How to Read This Book.

Overview.

Design.

Common Declarations.

Syntax Specifications.

Errors.

2. Storage Management.

Memory Management Interface.

Arena Representation.

Allocating Space.

Deallocating Space.

Strings.

3. Types.

Representing Symbols.

Representing Symbol Tables.

Changing Scope.

Finding and Installing Identifiers.

Labels.

Constants.

Generated Variables.

4. Code Generation Interface.

Representing Types.

Type Management.

Type Predicates.

Type Constructors.

Function Types.

Structure and Enumeration Types.

Type-Checking Functions.

Type Mapping.

5. Lexical Analysis.

Type Metrics.

Interface Records.

Symbols.

Types.

Dag Operators.

Interface Flags.

Initialization.

Definitions.

Constants.

Functions.

Interface Binding.

Upcalls.

6. Parsing.

Input.

Recognizing Tokens.

Recognizing Keywords.

Recognizing Identifiers.

Recognizing Numbers.

Recognizing Character Constants and Strings.

7. Expressions.

Languages and Grammars.

Ambiguity and Parse Trees.

Top-Down Parsing.

FIRST and FOLLOW Sets.

Writing Parsing Functions.

Handling Syntax Errors.

8. Expression Semantics.

Representing Expressions.

Parsing Expressions.

Parsing C Expressions.

Assignment Expressions.

Conditional Expressions.

Binary Expressions.

Unary and Postfix Expressions.

Primary Expressions.

9. Expression Semantics.

Conversions.

Unary and Postfix Operators.

Function Calls.

Binary Operators.

Assignments.

Conditionals.

Constant Folding.

10. Statements.

Representing Code.

Execution Points.

Recognizing Statements.

If Statements.

Labels and Gotos.

Loops.

Switch Statements.

Return Statements.

Managing Labels and Jumps.

11. Declarations.

Translation Units.

Declarations.

Declarators.

Function Declarators.

Structure Specifiers.

Function Definitions.

Compound Statements.

Finalization.

The Main Program.

12. Generating Immediate Code.

Eliminating Common Subexpressions.

Building Nodes.

Flow of Control.

Assignments.

Function Calls.

Enforcing Evaluation Order.

Driving Code Generation.

Eliminating Multiply Referenced Nodes.

13. Structuring the Code Generator.

Organization of the Code Generator.

Interface Extensions.

Upcalls.

Node Extensions.

Symbol Extensions.

Frame Layout.

Generating Code to Copy Blocks.

Initialization.

14. Selecting and Emitting instructions.

Specifications.

Labelling the Tree.

Reducing the Tree.

Cost Functions.

Debugging.

The Emitter.

Register Targeting.

Coordinating Instruction Selection.

Shared Rules.

15. Register Allocation.

Organization.

Tracking the Register State.

Allocating Registers.

Spilling.

16. Generating MIPS R3000 Code.

Registers.

Selecting Instructions.

Implementing Functions.

Defining Data.

Segments.

Copying Blocks.

17. Generating SPARC Code.

Registers.

Selecting Instructions.

Implementing Functions.

Defining Data.

Copying Blocks.

18. Generating X86 Code.

Registers.

Selecting Instructions.

Implementing Functions.

Defining Data.

19. Retrospective.

Data Structures.

Interface.

Syntactic and Semantic Analyses.

Code Generation and Optimization.

Testing and Validation.

Bibliography.

Index.

How to Obtain ICC. 0805316701T04062001

Read More Show Less

Preface

The compiler is the linchpin of the programmer's toolbox. Working programmers use compilers every day and count heavily on their correctness and reliability. A compiler must accept the standard definition of the programming language so that source code will be portable across platforms. A compiler must generate efficient object code. Perhaps more important, a compiler must generate correct object code; an application is only as reliable as the compiler that compiled it.

A compiler is itself a large and complex application that is worthy of study in its own right. This book tours most of the implementation of lcc, a compiler for the ANSI C programming language. It is to compiling what Software Tools by B.W. Kernighan and P.J. Plauger (Addison-Wesley, 1976) is to text processing like text editors and macro processors. Software design and implementation are best learned through experience with real tools. This book explains in detail and shows most of the code for a real compiler. The accompanying diskette holds the source code for the complete compiler.

lcc is a production compiler. It's been used to compile production programs since 1988 and is now used by hundreds of C programmers daily. Detailing most of a production compiler in a book leaves little room for supporting material, so we present only the theory needed for the implementation at hand and leave the broad survey of compiling techniques to existing texts. The book omits a few language features--those with mundane or repetitive implementations and those deliberately treated only in the exercises--but the full compiler is available on the diskette, and the book makes it understandable.

The obvious use for this book is to learn more about compiler construction. But only few programmers need to know how to design and implement compilers. Most work on applications and other aspects of systems programming. There are four reasons why this majority of C programmers may benefit from this book.

First, programmers who understand how a C compiler works are often better programmers in general and better C programmers in particular. The compiler writer must understand even the darkest corners of the C language; touring the implementation of those corners reveals much about the language itself and its efficient realization on modern computers.

Second, most texts on programming must necessarily use small examples, which often demonstrate techniques simply and elegantly. Most programmers, however, work on large programs that have evolved--or degenerated--over time. There are few well documented examples of this kind of "programming in the large" that can serve as reference examples. lcc isn't perfect, but this book documents both its good and bad points in detail and thus provides one such reference point.

Third, a compiler is one of the best demonstrations in computer science of the interaction between theory and practice. lcc displays both the places where this interaction is smooth and the results are elegant, as well as where practical demands strain the theory, which shows in the resulting code. Exploring these interactions in a real program helps programmers understand when, where, and how to apply different techniques. lcc also illustrates numerous C programming techniques.

Fourth, this book is an example of a "literate program." Like TEX: The Program by D.E. Knuth (Addison-Wesley, 1986), this book is lcc's source code and the prose that describes it. The code is presented in the order that best suits understanding, not in the order dictated by the C programming language. The source code that appears on the diskette is extracted automatically from the book's text files.

This book is well suited for self-study by both academics and professionals. The book and its diskette offer complete documented source code for lcc, so they may interest practitioners who wish to experiment with compilation or those working in application areas that use or implement language-based tools and techniques, such as user interfaces.

The book shows a large software system, warts and all. It could thus be the subject of a postmortem in a software engineering course, for example.

For compiler courses, this book complements traditional compiler texts. It shows one way of implementing a C compiler, while traditional texts survey algorithms for solving the broad range of problems encountered in compiling. Limited space prevents such texts from including more than a toy compiler. Code generation is often treated at a particularly high level to avoid tying the book to a specific computer.

As a result many instructors prepare a substantial programming project to give their students some practical experience. These instructors usually must write these compilers from scratch; students duplicate large portions and have to use the rest with only limited documentation. The situation is trying for both students and instructors, and unsatisfying to boot, because the compilers are still toys. By documenting most of a real compiler and providing the source code, this book offers an alternative.

This book presents full code generators for the MIPS R3000, SPARC, and Intel 386 and successor architectures. It exploits recent research that produces code generators from compact specifications. These methods allow us to present complete code generators for several machines, which no other book does. Presenting several code generators avoids tying the book to a single machine, and helps students appreciate engineering retargetable software.

Assignments can add language features, optimizations, and targets. When used with a traditional survey text, assignments could also replace existing modules with those using alternate algorithms. Such assignments come closer to the actual practice of compiler engineering than assignments that implement most of a toy compiler, where too much time goes to low-level infrastructure and accommodating repetitive language features. Many of the exercises pose just these kinds of engineering problems.

lcc has also been adapted for purposes other than conventional compilation. For example, it's been used for building a C browser and for generating remote-procedure-call stubs from declarations. It could also be used to experiment with language extensions, proposed computer architectures and code-generator technologies.

We assume readers are fluent in C and assembly language for some computer, know what a compiler is and have a general understanding of what one does, and have a working understanding of data structures and algorithms at the level covered in typical undergraduate courses; the material covered by Algorithms in C by R. Sedgewick (Addison-Wesley, 1990), for example, is more than sufficient for understanding lcc.

Acknowledgments

This book owes much to the many lcc users at AT&T Bell Laboratories, Princeton University, and elsewhere who suffered through bugs and provided valuable feedback. Those who deserve explicit thanks include Hans Boehm, Mary Fernandez, Michael Golan, Paul Haahr, Brian Kernighan, Doug McIlroy, Rob Pike, Dennis Ritchie, and Ravi Sethi. Ronald Guilmette, David Kristol, David Prosser, and Dennis Rithchie provided valuable information concerning the fine points of the ANSI Standard and its interpretation. David Gay helped us adapt the PFORT library of numerical software to be an invaluable stress test for lcc's code generators.

Careful reviews of both our code and our prose by Jack Davidson, Todd Proebsting, Norman Ramsey, William Waite, and David Wall contributed significantly to the quality of both. Our thanks to Steve Beck, who installed and massaged the fonts used for this book, and to Maylee Noah, who did the artwork with Adobe Illustrator.

Christopher W. Fraser David R. Hanson

0805316701P04062001

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)