Introduction to Compilers and Language Design Second Edition Prof. Douglas Thain University of Notre Dame IntroductiontoCompilersandLanguageDesign Copyright©2020DouglasThain. PaperbackISBN:979-8-655-18026-0 Secondedition. AnyoneisfreetodownloadandprintthePDFeditionofthisbookforper- sonaluse. Commercialdistribution,printing,orreproductionwithoutthe author’sconsentisexpresslyprohibited. Allotherrightsarereserved. YoucanfindthelatestversionofthePDFedition,andpurchaseinexpen- sivehardcovercopiesathttp://compilerbook.org RevisionDate: January15,2021 iii ForLisa,William,Zachary,Emily,andAlia. iii iv iv v Contributions Iamgratefultothefollowingpeoplefortheircontributionstothisbook: AndrewLittekendraftedthechapteronARMassembly;KevinLatimer drew the RegEx to NFA and the LR example figures; Benjamin Gunning fixedanerrorinLL(1)parsetableconstruction;TimShaffercompletedthe detailedLR(1)example. Andthefollowingpeoplecorrectedtypos: SakibHaque(27),JohnWesthoff(26),EmilyStrout(26),GonzaloMartinez (25), DanielKerrigan(24), BrianDuSell(23), RyanMackey(20), TJDasso (18), Nedim Mininovic (15), Noah Yoshida (14), Joseph Kimlinger (12), NolanMcShea(11),JongsuhLee(11),KyleWeingartner(10),AndrewLit- teken(9),ThomasCane(9),SamuelBattalio(9),Ste´phaneMassou(8),Luis Prieb (7), William Diederich (7), Jonathan Xu (6), Gavin Inglis (6), Kath- leenCapella(6),EdwardAtkinson(6),TannerJuedeman(5),JohnJohnson (4),LukeSiela(4),FrancisSchickel(4),EamonMarmion(3),MollyZachlin (3), DavidChiang(3), JacobMazur(3), SpencerKing(2), YaoxianQu(2), MariaAranguren(2),PatrickLacher(2),ConnorHiggins(2),TangoGu(2), Andrew Syrmakesis (2), Horst von Brand (2), John Fox (2), Jamie Zhang (2), Benjamin Gunning (1) Charles Osborne (1), William Theisen (1), Jes- sica Cioffi (1), Ben Tovar (1), Ryan Michalec (1), Patrick Flynn (1), Clint Jeffery(1),RalphSiemsen(1),JohnQuinn(1),PaulBrunts(1),LukeWurl (1),BruceMardle(1),DaneWilliams(1),ThomasFisher(1),AlanJohnson (1),JacobHarris(1),JeffClinton(1) Please send any comments or corrections via email to Prof. Douglas Thain([email protected]). v vi vi CONTENTS vii Contents 1 Introduction 1 1.1 Whatisacompiler? . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Whyshouldyoustudycompilers? . . . . . . . . . . . . . . . 2 1.3 What’sthebestwaytolearnaboutcompilers? . . . . . . . . 2 1.4 WhatlanguageshouldIuse? . . . . . . . . . . . . . . . . . . 2 1.5 Howisthisbookdifferentfromothers? . . . . . . . . . . . . 3 1.6 WhatotherbooksshouldIread? . . . . . . . . . . . . . . . . 4 2 AQuickTour 5 2.1 TheCompilerToolchain . . . . . . . . . . . . . . . . . . . . . 5 2.2 StagesWithinaCompiler . . . . . . . . . . . . . . . . . . . . 6 2.3 ExampleCompilation. . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Scanning 11 3.1 KindsofTokens . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 AHand-MadeScanner . . . . . . . . . . . . . . . . . . . . . . 12 3.3 RegularExpressions . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 FiniteAutomata . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4.1 DeterministicFiniteAutomata . . . . . . . . . . . . . 16 3.4.2 NondeterministicFiniteAutomata . . . . . . . . . . . 17 3.5 ConversionAlgorithms. . . . . . . . . . . . . . . . . . . . . . 19 3.5.1 ConvertingREstoNFAs . . . . . . . . . . . . . . . . . 19 3.5.2 ConvertingNFAstoDFAs . . . . . . . . . . . . . . . . 22 3.5.3 MinimizingDFAs . . . . . . . . . . . . . . . . . . . . . 24 3.6 LimitsofFiniteAutomata . . . . . . . . . . . . . . . . . . . . 26 3.7 UsingaScannerGenerator . . . . . . . . . . . . . . . . . . . . 26 3.8 PracticalConsiderations . . . . . . . . . . . . . . . . . . . . . 28 3.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.10 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4 Parsing 35 4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 ContextFreeGrammars . . . . . . . . . . . . . . . . . . . . . 36 vii viii CONTENTS 4.2.1 DerivingSentences . . . . . . . . . . . . . . . . . . . . 37 4.2.2 AmbiguousGrammars. . . . . . . . . . . . . . . . . . 38 4.3 LLGrammars . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3.1 EliminatingLeftRecursion . . . . . . . . . . . . . . . 41 4.3.2 EliminatingCommonLeftPrefixes . . . . . . . . . . . 42 4.3.3 FirstandFollowSets . . . . . . . . . . . . . . . . . . . 43 4.3.4 RecursiveDescentParsing. . . . . . . . . . . . . . . . 45 4.3.5 TableDrivenParsing . . . . . . . . . . . . . . . . . . . 47 4.4 LRGrammars . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.1 Shift-ReduceParsing . . . . . . . . . . . . . . . . . . . 50 4.4.2 TheLR(0)Automaton . . . . . . . . . . . . . . . . . . 51 4.4.3 SLRParsing . . . . . . . . . . . . . . . . . . . . . . . . 55 4.4.4 LR(1)Parsing . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.5 LALRParsing . . . . . . . . . . . . . . . . . . . . . . . 62 4.5 GrammarClassesRevisited . . . . . . . . . . . . . . . . . . . 62 4.6 TheChomskyHierarchy . . . . . . . . . . . . . . . . . . . . . 63 4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.8 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5 ParsinginPractice 69 5.1 TheBisonParserGenerator . . . . . . . . . . . . . . . . . . . 70 5.2 ExpressionValidator . . . . . . . . . . . . . . . . . . . . . . . 73 5.3 ExpressionInterpreter . . . . . . . . . . . . . . . . . . . . . . 74 5.4 ExpressionTrees . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.6 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6 TheAbstractSyntaxTree 85 6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2 Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.3 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.4 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.5 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.6 PuttingitAllTogether . . . . . . . . . . . . . . . . . . . . . . 95 6.7 BuildingtheAST . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7 SemanticAnalysis 99 7.1 OverviewofTypeSystems . . . . . . . . . . . . . . . . . . . . 100 7.2 DesigningaTypeSystem . . . . . . . . . . . . . . . . . . . . . 103 7.3 TheB-MinorTypeSystem . . . . . . . . . . . . . . . . . . . . 106 7.4 TheSymbolTable . . . . . . . . . . . . . . . . . . . . . . . . . 107 7.5 NameResolution . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.6 ImplementingTypeChecking . . . . . . . . . . . . . . . . . . 113 7.7 ErrorMessages . . . . . . . . . . . . . . . . . . . . . . . . . . 117 viii CONTENTS ix 7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 7.9 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 118 8 IntermediateRepresentations 119 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.2 AbstractSyntaxTree . . . . . . . . . . . . . . . . . . . . . . . 119 8.3 DirectedAcyclicGraph . . . . . . . . . . . . . . . . . . . . . . 120 8.4 ControlFlowGraph. . . . . . . . . . . . . . . . . . . . . . . . 125 8.5 StaticSingleAssignmentForm . . . . . . . . . . . . . . . . . 127 8.6 LinearIR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 8.7 StackMachineIR . . . . . . . . . . . . . . . . . . . . . . . . . 129 8.8 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.8.1 GIMPLE-GNUSimpleRepresentation . . . . . . . . 130 8.8.2 LLVM-LowLevelVirtualMachine . . . . . . . . . . 131 8.8.3 JVM-JavaVirtualMachine . . . . . . . . . . . . . . . 132 8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 8.10 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9 MemoryOrganization 135 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 9.2 LogicalSegmentation . . . . . . . . . . . . . . . . . . . . . . . 135 9.3 HeapManagement . . . . . . . . . . . . . . . . . . . . . . . . 138 9.4 StackManagement . . . . . . . . . . . . . . . . . . . . . . . . 140 9.4.1 StackCallingConvention . . . . . . . . . . . . . . . . 141 9.4.2 RegisterCallingConvention . . . . . . . . . . . . . . 142 9.5 LocatingData . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 9.6 ProgramLoading . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.7 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 148 10 AssemblyLanguage 149 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 10.2 OpenSourceAssemblerTools . . . . . . . . . . . . . . . . . . 150 10.3 X86AssemblyLanguage . . . . . . . . . . . . . . . . . . . . . 152 10.3.1 RegistersandDataTypes . . . . . . . . . . . . . . . . 152 10.3.2 AddressingModes . . . . . . . . . . . . . . . . . . . . 154 10.3.3 BasicArithmetic . . . . . . . . . . . . . . . . . . . . . 156 10.3.4 ComparisonsandJumps . . . . . . . . . . . . . . . . . 158 10.3.5 TheStack . . . . . . . . . . . . . . . . . . . . . . . . . 159 10.3.6 CallingaFunction . . . . . . . . . . . . . . . . . . . . 160 10.3.7 DefiningaLeafFunction. . . . . . . . . . . . . . . . . 162 10.3.8 DefiningaComplexFunction . . . . . . . . . . . . . . 163 10.4 ARMAssembly . . . . . . . . . . . . . . . . . . . . . . . . . . 167 10.4.1 RegistersandDataTypes . . . . . . . . . . . . . . . . 167 10.4.2 AddressingModes . . . . . . . . . . . . . . . . . . . . 168 10.4.3 BasicArithmetic . . . . . . . . . . . . . . . . . . . . . 170 ix x CONTENTS 10.4.4 ComparisonsandBranches . . . . . . . . . . . . . . . 171 10.4.5 TheStack . . . . . . . . . . . . . . . . . . . . . . . . . 173 10.4.6 CallingaFunction . . . . . . . . . . . . . . . . . . . . 174 10.4.7 DefiningaLeafFunction. . . . . . . . . . . . . . . . . 175 10.4.8 DefiningaComplexFunction . . . . . . . . . . . . . . 176 10.4.9 64-bitDifferences . . . . . . . . . . . . . . . . . . . . . 179 10.5 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 180 11 CodeGeneration 181 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.2 SupportingFunctions . . . . . . . . . . . . . . . . . . . . . . . 181 11.3 GeneratingExpressions . . . . . . . . . . . . . . . . . . . . . 183 11.4 GeneratingStatements . . . . . . . . . . . . . . . . . . . . . . 188 11.5 ConditionalExpressions . . . . . . . . . . . . . . . . . . . . . 192 11.6 GeneratingDeclarations . . . . . . . . . . . . . . . . . . . . . 193 11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 12 Optimization 195 12.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 12.2 OptimizationinPerspective . . . . . . . . . . . . . . . . . . . 196 12.3 HighLevelOptimizations . . . . . . . . . . . . . . . . . . . . 197 12.3.1 ConstantFolding . . . . . . . . . . . . . . . . . . . . . 197 12.3.2 StrengthReduction . . . . . . . . . . . . . . . . . . . . 199 12.3.3 LoopUnrolling . . . . . . . . . . . . . . . . . . . . . . 199 12.3.4 CodeHoisting . . . . . . . . . . . . . . . . . . . . . . . 200 12.3.5 FunctionInlining . . . . . . . . . . . . . . . . . . . . . 201 12.3.6 DeadCodeDetectionandElimination . . . . . . . . . 202 12.4 Low-LevelOptimizations . . . . . . . . . . . . . . . . . . . . 204 12.4.1 PeepholeOptimizations . . . . . . . . . . . . . . . . . 204 12.4.2 InstructionSelection . . . . . . . . . . . . . . . . . . . 204 12.5 RegisterAllocation . . . . . . . . . . . . . . . . . . . . . . . . 207 12.5.1 SafetyofRegisterAllocation . . . . . . . . . . . . . . 208 12.5.2 PriorityofRegisterAllocation. . . . . . . . . . . . . . 208 12.5.3 ConflictsBetweenVariables . . . . . . . . . . . . . . . 209 12.5.4 GlobalRegisterAllocation . . . . . . . . . . . . . . . . 210 12.6 OptimizationPitfalls . . . . . . . . . . . . . . . . . . . . . . . 211 12.7 OptimizationInteractions . . . . . . . . . . . . . . . . . . . . 212 12.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 12.9 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 215 A SampleCourseProject 217 A.1 ScannerAssignment . . . . . . . . . . . . . . . . . . . . . . . 217 A.2 ParserAssignment . . . . . . . . . . . . . . . . . . . . . . . . 217 A.3 Pretty-PrinterAssignment . . . . . . . . . . . . . . . . . . . . 218 A.4 TypecheckerAssignment . . . . . . . . . . . . . . . . . . . . . 218 x