book

Writing a C Compiler

Name: Writing a C Compiler
Author: Nora Sandler
ISBN: 9781718500426

by Nora Sandler

August 2024

Intermediate to advanced

792 pages

23h 9m

English

No Starch Press

Read now

Unlock full access

Title Page
Copyright
Dedication
About the Author and the Technical Reviewer
Acknowledgments
Introduction
Who This Book Is ForWhy Write a C Compiler?Compilation from 10,000 FeetWhat You’ll BuildHow to Use This BookThe Test SuiteExtra Credit FeaturesSome Advice on Choosing an Implementation LanguageSystem RequirementsInstalling GCC and GDB on LinuxInstalling the Command Line Developer Tools on macOSRunning on Apple SiliconValidating Your SetupAdditional ResourcesLet’s Go!
Part I: The Basics
1. A Minimal Compiler
The Four Compiler PassesHello, Assembly!The Compiler DriverThe LexerThe ParserAn Example Abstract Syntax TreeThe AST DefinitionThe Formal GrammarRecursive Descent ParsingAssembly GenerationCode EmissionSummaryAdditional Resources
2. Unary Operators
Negation and Bitwise Complement in AssemblyThe StackThe LexerThe ParserTACKY: A New Intermediate RepresentationDefining TACKYGenerating TACKYGenerating Names for Temporary VariablesUpdating the Compiler DriverAssembly GenerationConverting TACKY to AssemblyReplacing PseudoregistersFixing Up InstructionsCode EmissionSummaryAdditional Resources
3. Binary Operators
The LexerThe ParserThe Trouble with Recursive Descent ParsingThe Adequate Solution: Refactoring the GrammarThe Better Solution: Precedence ClimbingPrecedence Climbing in ActionTACKY GenerationAssembly GenerationDoing Arithmetic in AssemblyConverting Binary Operations to AssemblyReplacing PseudoregistersFixing Up the idiv, add, sub, and imul InstructionsCode EmissionExtra Credit: Bitwise OperatorsSummaryAdditional Resources

4. Logical and Relational Operators
Short-Circuiting OperatorsThe LexerThe ParserTACKY GenerationAdding Jumps, Copies, and Comparisons to the TACKY IRConverting Short-Circuiting Operators to TACKYGenerating LabelsComparisons and Jumps in AssemblyComparisons and Status FlagsConditional Set InstructionsJump InstructionsAssembly GenerationReplacing PseudoregistersFixing Up the cmp InstructionCode EmissionSummaryAdditional Resources
5. Local Variables
Variables, Declarations, and AssignmentThe LexerThe ParserThe Updated AST and GrammarAn Improved Precedence Climbing AlgorithmSemantic AnalysisVariable ResolutionThe --validate OptionTACKY GenerationVariable and Assignment ExpressionsDeclarations, Statements, and Function BodiesFunctions with No return StatementExtra Credit: Compound Assignment, Increment, and DecrementSummary
6. If Statements and Conditional Expressions
The LexerThe ParserParsing if StatementsParsing Conditional ExpressionsVariable ResolutionTACKY GenerationConverting if Statements to TACKYConverting Conditional Expressions to TACKYExtra Credit: Labeled Statements and gotoSummary
7. Compound Statements
The Scoop on ScopesThe ParserVariable ResolutionResolving Variables in Multiple ScopesUpdating the Variable Resolution PseudocodeTACKY GenerationSummary
8. Loops
Loops and How to Escape ThemThe LexerThe ParserSemantic AnalysisExtending Variable ResolutionLoop LabelingImplementing Loop LabelingTACKY Generationbreak and continue Statementsdo Loopswhile Loopsfor LoopsExtra Credit: switch StatementsSummary
9. Functions
Declaring, Defining, and Calling FunctionsDeclarations and DefinitionsFunction CallsIdentifier LinkageCompiling LibrariesThe LexerThe ParserSemantic AnalysisExtending Identifier ResolutionWriting the Type CheckerTACKY GenerationAssembly GenerationUnderstanding Calling ConventionsCalling Functions with the System V ABIConverting Function Calls and Definitions to AssemblyReplacing PseudoregistersAllocating Stack Space During Instruction Fix-UpCode EmissionCalling Library FunctionsSummary
10. File Scope Variable Declarations and Storage-Class Specifiers
All About DeclarationsScopeLinkageStorage DurationDefinitions vs. DeclarationsError CasesLinkage and Storage Duration in AssemblyThe LexerThe ParserParsing Type and Storage-Class SpecifiersDistinguishing Between Function and Variable DeclarationsSemantic AnalysisIdentifier Resolution: Resolving External VariablesType Checking: Tracking Static Functions and VariablesTACKY GenerationAssembly GenerationGenerating Assembly for Variable DefinitionsReplacing Pseudoregisters According to Their Storage DurationFixing Up InstructionsCode EmissionSummary
Part II: Types Beyond Int
11. Long Integers
Long Integers in AssemblyType ConversionsStatic Long VariablesThe LexerThe ParserSemantic AnalysisAdding Type Information to the ASTType Checking ExpressionsType Checking return StatementsType Checking Declarations and Updating the Symbol TableTACKY GenerationTracking the Types of Temporary VariablesGenerating Extra Return InstructionsAssembly GenerationTracking Assembly Types in the Backend Symbol TableReplacing Longword and Quadword PseudoregistersFixing Up InstructionsCode EmissionSummary
12. Unsigned Integers
Type Conversions, AgainConverting Between Signed and Unsigned Types of the Same SizeConverting unsigned int to a Larger TypeConverting signed int to a Larger TypeConverting from Larger to Smaller TypesThe LexerThe ParserThe Type CheckerTACKY GenerationUnsigned Integer Operations in AssemblyUnsigned ComparisonsUnsigned DivisionZero ExtensionAssembly GenerationReplacing PseudoregistersFixing Up the Div and MovZeroExtend InstructionsCode EmissionSummary
13. Floating-Point Numbers
IEEE 754, What Is It Good For?The IEEE 754 Double-Precision FormatRounding BehaviorRounding ModesRounding ConstantsRounding Type ConversionsRounding Arithmetic OperationsLinking Shared LibrariesThe LexerRecognizing Floating-Point Constant TokensMatching the End of a ConstantThe ParserThe Type CheckerTACKY GenerationFloating-Point Operations in AssemblyWorking with SSE InstructionsUsing Floating-Point Values in the System V Calling ConventionDoing Arithmetic with SSE InstructionsComparing Floating-Point NumbersConverting Between Floating-Point and Integer TypesAssembly GenerationFloating-Point ConstantsUnary Instructions, Binary Instructions, and Conditional JumpsType ConversionsFunction CallsReturn InstructionsThe Complete Conversion from TACKY to AssemblyPseudoregister ReplacementInstruction Fix-UpCode EmissionFormatting Floating-Point NumbersLabeling Floating-Point ConstantsStoring Constants in the Read-Only Data SectionInitializing Static Variables to 0.0 or –0.0Putting It All TogetherExtra Credit: NaNSummaryAdditional Resources
14. Pointers
Objects and ValuesOperations on PointersAddress and Dereference OperationsNull Pointers and Type ConversionsPointer Comparisons& Operations on Dereferenced PointersThe LexerThe ParserParsing DeclarationsParsing Type NamesPutting It All TogetherSemantic AnalysisType Checking Pointer ExpressionsTracking Static Pointer Initializers in the Symbol TableTACKY GenerationPointer Operations in TACKYA Strategy for TACKY ConversionAssembly GenerationReplacing Pseudoregisters with Memory OperandsFixing Up the lea and push InstructionsCode EmissionSummary
15. Arrays and Pointer Arithmetic
Arrays and Pointer ArithmeticArray Declarations and InitializersMemory Layout of ArraysArray-to-Pointer DecayPointer Arithmetic to Access Array ElementsEven More Pointer ArithmeticArray Types in Function DeclarationsThings We Aren’t ImplementingThe LexerThe ParserParsing Array DeclaratorsParsing Abstract Array DeclaratorsParsing Compound InitializersParsing Subscript ExpressionsThe Type CheckerConverting Arrays to PointersValidating LvaluesType Checking Pointer ArithmeticType Checking Subscript ExpressionsType Checking Cast ExpressionsType Checking Function DeclarationsType Checking Compound InitializersInitializing Static ArraysInitializing Scalar Variables with ZeroInitTACKY GenerationPointer ArithmeticSubscriptingCompound InitializersTentative Array DefinitionsAssembly GenerationConverting TACKY to AssemblyReplacing PseudoMem OperandsFixing Up InstructionsCode EmissionSummary
16. Characters and Strings
Character TraitsString LiteralsWorking with Strings in AssemblyThe LexerThe ParserParsing Type SpecifiersParsing Character ConstantsParsing String LiteralsPutting It All TogetherThe Type CheckerCharactersString Literals in ExpressionsString Literals Initializing Non-static VariablesString Literals Initializing Static VariablesTACKY GenerationString Literals as Array InitializersString Literals in ExpressionsTop-Level Constants in TACKYAssembly GenerationOperations on CharactersTop-Level ConstantsThe Complete Conversion from TACKY to AssemblyPseudo-Operand ReplacementInstruction Fix-UpCode EmissionHello Again, World!Summary
17. Supporting Dynamic Memory Allocation
The void TypeMemory Management with void *Complete and Incomplete TypesThe sizeof OperatorThe LexerThe ParserThe Type CheckerConversions to and from void *Functions with void Return TypesScalar and Non-scalar TypesRestrictions on Incomplete TypesExtra Restrictions on voidConditional Expressions with void OperandsExisting Validation for Arithmetic Expressions and Comparisonssizeof ExpressionsTACKY GenerationFunctions with void Return TypesCasts to voidConditional Expressions with void Operandssizeof ExpressionsThe Latest and Greatest TACKY IRAssembly GenerationSummary
18. Structures
Declaring Structure TypesStructure Member DeclarationsTag and Member NamespacesStructure Type Declarations We Aren’t ImplementingOperating on StructuresStructure Layout in MemoryThe LexerThe ParserSemantic AnalysisResolving Structure TagsType Checking StructuresTACKY GenerationImplementing the Member Access OperatorsConverting Compound Initializers to TACKYStructures in the System V Calling ConventionClassifying StructuresPassing Parameters of Structure TypeReturning StructuresAssembly GenerationExtending the Assembly ASTCopying StructuresUsing Structures in Function CallsPutting It All TogetherReplacing Pseudo-operandsCode EmissionExtra Credit: UnionsSummaryAdditional Resources
Part III: Optimizations
19. Optimizing Tacky Programs
Safety and Observable BehaviorFour TACKY OptimizationsConstant FoldingUnreachable Code EliminationCopy PropagationDead Store EliminationWith Our Powers Combined … Testing the Optimization PassesWiring Up the Optimization StageConstant FoldingConstant Folding for Part I TACKY ProgramsSupporting Part II TACKY ProgramsControl-Flow GraphsDefining the Control-Flow GraphCreating Basic BlocksAdding Edges to the Control-Flow GraphConverting a Control-Flow Graph to a List of InstructionsMaking Your Control-Flow Graph Code ReusableUnreachable Code EliminationEliminating Unreachable BlocksRemoving Useless JumpsRemoving Useless LabelsRemoving Empty BlocksA Little Bit About Data-Flow AnalysisCopy PropagationReaching Copies AnalysisRewriting TACKY InstructionsSupporting Part II TACKY ProgramsDead Store EliminationLiveness AnalysisRemoving Dead StoresSupporting Part II TACKY ProgramsSummaryAdditional Resources
20. Register Allocation
Register Allocation in ActionTake One: Put Everything on the StackTake Two: Register AllocationTake Three: Register Allocation with CoalescingUpdating the Compiler PipelineExtending the Assembly ASTConverting TACKY to AssemblyRegister Allocation by Graph ColoringDetecting InterferenceSpilling RegistersThe Basic Register AllocatorHandling Multiple Types During Register AllocationDefining the Interference GraphBuilding the Interference GraphCalculating Spill CostsColoring the Interference GraphBuilding the Register Map and Rewriting the Function BodyInstruction Fix-Up with Callee-Saved RegistersCode EmissionRegister CoalescingUpdating the Interference GraphConservative CoalescingImplementing Register CoalescingSummaryAdditional Resources
Next Steps
Add Some Missing FeaturesHandle Undefined Behavior SafelyWrite More TACKY OptimizationsSupport Another Target ArchitectureContribute to an Open Source Programming Language ProjectThat’s a Wrap!
Appendix A. Debugging Assembly Code With GDB or LLDB
The ProgramDebugging with GDBConfiguring the GDB UIStarting and Stopping the ProgramPrinting ExpressionsExamining MemorySetting Conditional BreakpointsGetting HelpDebugging with LLDBStarting and Stopping the ProgramDisplaying Assembly CodePrinting ExpressionsExamining MemorySetting Conditional BreakpointsGetting Help
Appendix B. Assembly Generation and Code Emission Tables
Part IConverting TACKY to AssemblyCode EmissionPart IIConverting TACKY to AssemblyCode EmissionPart III
References
Index

Overview

Compilers are at the heart of everything programmers do, yet even experienced developers find 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 significant 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-flow 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.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

C++20 for Programmers: An Objects-Natural Approach, 3rd Edition

Publisher Resources

ISBN: 9781098182229Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills