Writing a C Compiler Build a Real Programming Language From Scratch (Nora Sandler)（Z-Library）

® N O R A S A N D L E R W R I T I N G A C C O M P I L E R B U I L D A R E A L P R O G R A M M I N G L A N G U A G E F R O M S C R A T C H THE F INEST IN GEEK ENTERTA INMENT ™ nostarch.com ® ® W R IT IN G A C C O M P IL E R S A N D L E R Compilers are at the heart of everything programmers do, yet even experienced developers fi nd them intimidating. For those eager to truly grasp how compilers work, Writing a C Compiler dispels the mystery. This book guides you through a fun and engaging project where you’ll learn what it takes to compile a real-world programming language to actual assembly code. Writing a C Compiler will take you step by step through the process of building your own compiler for a signifi cant subset of C—no prior experience with compiler construction or assembly code needed. Once you’ve built a working compiler for the simplest C program, you’ll add new features chapter by chapter. The algorithms in the book are all in pseudocode, so you can implement your compiler in whatever language you like. Along the way, you’ll explore key concepts like: • Lexing and parsing: Learn how to write a lexer and recursive descent parser that transform C code into an abstract syntax tree. • Program analysis: Discover how to analyze a program to understand its behavior and detect errors. • Code generation: Learn how to translate C language constructs like arithmetic operations, function calls, and control-fl ow statements into x64 assembly code. • Optimization techniques: Improve performance with methods like constant folding, dead store elimination, and register allocation. Compilers aren’t terrifying beasts—and with help from this hands-on, accessible guide, you might even turn them into your friends for life. A B O U T T H E A U T H O R Nora Sandler is a software engineer based in Seattle. She holds a BS in computer science from the University of Chicago, where she researched the implementation of parallel programming languages. More recently, she’s worked on domain-specifi c languages at an endpoint security company. You can fi nd her blog on pranks, compilers, and other computer science topics at https://norasandler.com. YOU DON’ T NEED A PHD TO WRITE A COMPILER $69.99 ($91.99 CDN) 4-1-1-4 (CV 2–3 pritns 50% tint of PMS 310 U)

WRITING A C COMPILER

® W R I T I N G A C C O M P I L E R B u i l d a R e a l P r o g r a m m i n g L a n g u a g e f r o m S c r a t c h by Nora Sandler San Francisco

WRITING A C COMPILER. Copyright © 2024 by Nora Sandler. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. First printing ISBN-13: 978-1-7185-0042-6 (print) ISBN-13: 978-1-7185-0043-3 (ebook) Published by No Starch Press®, Inc. 245 8th Street, San Francisco, CA 94103 phone: +1.415.863.9900 www .nostarch .com; info@nostarch .com Publisher: William Pollock Managing Editor: Jill Franklin Production Manager: Sabrina Plomitallo-González Production Editor: Sydney Cromwell Developmental Editors: Alex Freed and Eva Morrow Cover Illustrator: James L. Barry Interior Design: Octopod Studios Technical Reviewer: Stephen Kell Copyeditor: Rachel Head Proofreader: Audrey Doyle Indexer: BIM Creatives, LLC Figure 13-1, courtesy of Codekaizen via Wikimedia Commons, has been reproduced under CC BY-SA 4.0, https://creativecommons .org /licenses /by -sa /4 .0. The original image has been converted to grayscale, and fonts have been modified. Library of Congress Control Number: 2023058768 For customer service inquiries, please contact info@nostarch .com. For information on distribution, bulk sales, corporate sales, or translations: sales@nostarch .com. For permission to translate this work: rights@nostarch .com. To report counterfeit copies or piracy: counterfeit@nostarch .com. No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it. ®

To Brian

About the Author Nora Sandler is a software engineer based in Seattle. She holds a BS in computer science from the University of Chicago, where she researched the implementation of parallel programming languages. After several years as a penetration tester, she found her way back to compilers. Most recently, she worked on domain-specific languages at an endpoint security company. You can read her blog about pranks, compilers, and other computer science top- ics at https://norasandler.com. About the Technical Reviewer Stephen Kell is a researcher, educator, and consultant on the design and implementation of programming languages and systems. He has taught compilers and C programming in various settings over the past 12 years, served on an ISO study group on the evolution of the C language specifica- tion, and published numerous research papers on the specification, design, and implementation of C and its linking and debugging tools. These con- tinue to be a focus of the research that he leads as an academic at King’s College London.

B R I E F C O N T E N T S Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxv PART I: THE BASICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 Chapter 1: A Minimal Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chapter 2: Unary Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Chapter 3: Binary Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Chapter 4: Logical and Relational Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Chapter 5: Local Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Chapter 6: if Statements and Conditional Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Chapter 7: Compound Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Chapter 8: Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Chapter 9: Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Chapter 10: File Scope Variable Declarations and Storage-Class Specifiers . . . . . . . . . . . 207 PART II: TYPES BEYOND INT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .241 Chapter 11: Long Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Chapter 12: Unsigned Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 Chapter 13: Floating-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Chapter 14: Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 Chapter 15: Arrays and Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 Chapter 16: Characters and Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 Chapter 17: Supporting Dynamic Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 Chapter 18: Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

x   Brief Contents PART III: OPTIMIZATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .555 Chapter 19: Optimizing TACKY Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 Chapter 20: Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613 Next Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 Appendix A: Debugging Assembly Code with GDB or LLDB . . . . . . . . . . . . . . . . . . . . . . 675 Appendix B: Assembly Generation and Code Emission Tables . . . . . . . . . . . . . . . . . . . . . 699 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731

C O N T E N T S I N D E T A I L ACKNOWLEDGMENTS xxiii INTRODUCTION xxv Who This Book Is For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi Why Write a C Compiler? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii Compilation from 10,000 Feet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvii What You’ll Build . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxviii How to Use This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxii The Test Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxii Extra Credit Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxii Some Advice on Choosing an Implementation Language . . . . . . . . . . . . . . . . . . . . . xxxiii System Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxiv Installing GCC and GDB on Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxiv Installing the Command Line Developer Tools on macOS . . . . . . . . . . . . . . . xxxv Running on Apple Silicon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxv Validating Your Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxv Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxvi Let’s Go! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxxvii PART I: THE BASICS 1 1 A MINIMAL COMPILER 3 The Four Compiler Passes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Hello, Assembly! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 The Compiler Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 An Example Abstract Syntax Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 The AST Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 The Formal Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Recursive Descent Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 UNARY OPERATORS 25 Negation and Bitwise Complement in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 The Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

xii   Contents in Detail The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 TACKY: A New Intermediate Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Defining TACKY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Generating TACKY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Generating Names for Temporary Variables . . . . . . . . . . . . . . . . . . . . . . . . . 38 Updating the Compiler Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Converting TACKY to Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Replacing Pseudoregisters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Fixing Up Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 BINARY OPERATORS 47 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 The Trouble with Recursive Descent Parsing . . . . . . . . . . . . . . . . . . . . . . . . . 50 The Adequate Solution: Refactoring the Grammar . . . . . . . . . . . . . . . . . . . . . 51 The Better Solution: Precedence Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Precedence Climbing in Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Doing Arithmetic in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Converting Binary Operations to Assembly . . . . . . . . . . . . . . . . . . . . . . . . . 61 Replacing Pseudoregisters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Fixing Up the idiv, add, sub, and imul Instructions . . . . . . . . . . . . . . . . . . . . . 64 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Extra Credit: Bitwise Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4 LOGICAL AND RELATIONAL OPERATORS 71 Short-Circuiting Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Adding Jumps, Copies, and Comparisons to the TACKY IR . . . . . . . . . . . . . . . 75 Converting Short-Circuiting Operators to TACKY . . . . . . . . . . . . . . . . . . . . . . 76 Generating Labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Comparisons and Jumps in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Comparisons and Status Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Conditional Set Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Jump Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Replacing Pseudoregisters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Fixing Up the cmp Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Contents in Detail   xiii Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5 LOCAL VARIABLES 93 Variables, Declarations, and Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 The Updated AST and Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 An Improved Precedence Climbing Algorithm . . . . . . . . . . . . . . . . . . . . . . . 101 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Variable Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 The - -validate Option . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Variable and Assignment Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Declarations, Statements, and Function Bodies . . . . . . . . . . . . . . . . . . . . . . 110 Functions with No return Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Extra Credit: Compound Assignment, Increment, and Decrement . . . . . . . . . . . . . . . . 113 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6 IF STATEMENTS AND CONDITIONAL EXPRESSIONS 117 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Parsing if Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Parsing Conditional Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Variable Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Converting if Statements to TACKY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Converting Conditional Expressions to TACKY . . . . . . . . . . . . . . . . . . . . . . 127 Extra Credit: Labeled Statements and goto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7 COMPOUND STATEMENTS 131 The Scoop on Scopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Variable Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Resolving Variables in Multiple Scopes . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Updating the Variable Resolution Pseudocode . . . . . . . . . . . . . . . . . . . . . . . 138 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 8 LOOPS 143 Loops and How to Escape Them . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

xiv   Contents in Detail Extending Variable Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 Loop Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Implementing Loop Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 break and continue Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 do Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 while Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 for Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Extra Credit: switch Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 9 FUNCTIONS 161 Declaring, Defining, and Calling Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Declarations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Identifier Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Compiling Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Extending Identifier Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Writing the Type Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Understanding Calling Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Calling Functions with the System V ABI . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Converting Function Calls and Definitions to Assembly . . . . . . . . . . . . . . . . . 194 Replacing Pseudoregisters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 Allocating Stack Space During Instruction Fix-Up . . . . . . . . . . . . . . . . . . . . . 200 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 Calling Library Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 10 FILE SCOPE VARIABLE DECLARATIONS AND STORAGE-CLASS SPECIFIERS 207 All About Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Storage Duration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 Definitions vs . Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 Error Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Linkage and Storage Duration in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Parsing Type and Storage-Class Specifiers . . . . . . . . . . . . . . . . . . . . . . . . . 225 Distinguishing Between Function and Variable Declarations . . . . . . . . . . . . . 226 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 Identifier Resolution: Resolving External Variables . . . . . . . . . . . . . . . . . . . . 227 Type Checking: Tracking Static Functions and Variables . . . . . . . . . . . . . . . . 229

Contents in Detail   xv TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 Generating Assembly for Variable Definitions . . . . . . . . . . . . . . . . . . . . . . . 236 Replacing Pseudoregisters According to Their Storage Duration . . . . . . . . . . 237 Fixing Up Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 PART II: TYPES BEYOND INT 241 11 LONG INTEGERS 243 Long Integers in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 Static Long Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 Adding Type Information to the AST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Type Checking Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Type Checking return Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 Type Checking Declarations and Updating the Symbol Table . . . . . . . . . . . . 257 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 Tracking the Types of Temporary Variables . . . . . . . . . . . . . . . . . . . . . . . . . 260 Generating Extra Return Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 Tracking Assembly Types in the Backend Symbol Table . . . . . . . . . . . . . . . . 266 Replacing Longword and Quadword Pseudoregisters . . . . . . . . . . . . . . . . . 267 Fixing Up Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 12 UNSIGNED INTEGERS 273 Type Conversions, Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Converting Between Signed and Unsigned Types of the Same Size . . . . . . . . 274 Converting unsigned int to a Larger Type . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Converting signed int to a Larger Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 Converting from Larger to Smaller Types . . . . . . . . . . . . . . . . . . . . . . . . . . 275 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 The Type Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Unsigned Integer Operations in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Unsigned Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Unsigned Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 Zero Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

xvi   Contents in Detail Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Replacing Pseudoregisters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 Fixing Up the Div and MovZeroExtend Instructions . . . . . . . . . . . . . . . . . . . 290 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 13 FLOATING-POINT NUMBERS 295 IEEE 754, What Is It Good For? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 The IEEE 754 Double-Precision Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Rounding Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 Rounding Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 Rounding Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 Rounding Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 Rounding Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 Linking Shared Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 Recognizing Floating-Point Constant Tokens . . . . . . . . . . . . . . . . . . . . . . . . 302 Matching the End of a Constant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 The Type Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 Floating-Point Operations in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 Working with SSE Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 Using Floating-Point Values in the System V Calling Convention . . . . . . . . . . 312 Doing Arithmetic with SSE Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Comparing Floating-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 Converting Between Floating-Point and Integer Types . . . . . . . . . . . . . . . . . . 317 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 Floating-Point Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Unary Instructions, Binary Instructions, and Conditional Jumps . . . . . . . . . . . 327 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Return Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 The Complete Conversion from TACKY to Assembly . . . . . . . . . . . . . . . . . . 333 Pseudoregister Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 Instruction Fix-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 Formatting Floating-Point Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 Labeling Floating-Point Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 Storing Constants in the Read-Only Data Section . . . . . . . . . . . . . . . . . . . . . 339 Initializing Static Variables to 0 .0 or –0 .0 . . . . . . . . . . . . . . . . . . . . . . . . . 340 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Extra Credit: NaN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

Contents in Detail   xvii 14 POINTERS 347 Objects and Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Operations on Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 Address and Dereference Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 Null Pointers and Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 Pointer Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 & Operations on Dereferenced Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Parsing Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 Parsing Type Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Type Checking Pointer Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 Tracking Static Pointer Initializers in the Symbol Table . . . . . . . . . . . . . . . . . 369 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 Pointer Operations in TACKY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 A Strategy for TACKY Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 Replacing Pseudoregisters with Memory Operands . . . . . . . . . . . . . . . . . . . 378 Fixing Up the lea and push Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 15 ARRAYS AND POINTER ARITHMETIC 383 Arrays and Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Array Declarations and Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Memory Layout of Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 Array-to-Pointer Decay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 Pointer Arithmetic to Access Array Elements . . . . . . . . . . . . . . . . . . . . . . . . 387 Even More Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 Array Types in Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 Things We Aren’t Implementing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 Parsing Array Declarators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 Parsing Abstract Array Declarators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 Parsing Compound Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 Parsing Subscript Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 The Type Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 Converting Arrays to Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 Validating Lvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 Type Checking Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400 Type Checking Subscript Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 Type Checking Cast Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 Type Checking Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 Type Checking Compound Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 Initializing Static Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 Initializing Scalar Variables with ZeroInit . . . . . . . . . . . . . . . . . . . . . . . . . . 405

xviii   Contents in Detail TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 Subscripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Compound Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 Tentative Array Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 Converting TACKY to Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 Replacing PseudoMem Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 Fixing Up Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 16 CHARACTERS AND STRINGS 423 Character Traits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 String Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 Working with Strings in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 Parsing Type Specifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 Parsing Character Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 Parsing String Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 Putting It All Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 The Type Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 String Literals in Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 String Literals Initializing Non-static Variables . . . . . . . . . . . . . . . . . . . . . . . 437 String Literals Initializing Static Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 437 TACKY Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 String Literals as Array Initializers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 String Literals in Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 Top-Level Constants in TACKY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 Assembly Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443 Operations on Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443 Top-Level Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 The Complete Conversion from TACKY to Assembly . . . . . . . . . . . . . . . . . . 446 Pseudo-Operand Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448 Instruction Fix-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 Hello Again, World! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 17 SUPPORTING DYNAMIC MEMORY ALLOCATION 457 The void Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 Memory Management with void * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 Complete and Incomplete Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 The sizeof Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 The Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463