Basics of Compiler Design Anniversary edition Virender Singh Disclaimer : Anyone Is Free To Distribute This Book Digitally And For Commercial Purpose. Contents 1 Introduction 1 1.1 Whatisacompiler? . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Thephasesofacompiler . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Whylearnaboutcompilers? . . . . . . . . . . . . . . . . . . . . 4 1.5 Thestructureofthisbook . . . . . . . . . . . . . . . . . . . . . . 5 1.6 Tothelecturer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.8 Permissiontouse . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 LexicalAnalysis 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Regularexpressions . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Shorthands . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Nondeterministicfiniteautomata . . . . . . . . . . . . . . . . . . 15 2.4 ConvertingaregularexpressiontoanNFA . . . . . . . . . . . . . 18 2.4.1 Optimisations . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Deterministicfiniteautomata . . . . . . . . . . . . . . . . . . . . 22 2.6 ConvertinganNFAtoaDFA . . . . . . . . . . . . . . . . . . . . 23 2.6.1 Solvingsetequations . . . . . . . . . . . . . . . . . . . . 23 2.6.2 Thesubsetconstruction. . . . . . . . . . . . . . . . . . . 26 2.7 Sizeversusspeed . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.8 MinimisationofDFAs . . . . . . . . . . . . . . . . . . . . . . . 30 2.8.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.8.2 Deadstates . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.9 Lexersandlexergenerators . . . . . . . . . . . . . . . . . . . . . 35 2.9.1 Lexergenerators . . . . . . . . . . . . . . . . . . . . . . 41 2.10 Propertiesofregularlanguages . . . . . . . . . . . . . . . . . . . 42 2.10.1 Relativeexpressivepower . . . . . . . . . . . . . . . . . 42 2.10.2 Limitstoexpressivepower . . . . . . . . . . . . . . . . . 44 i ii CONTENTS 2.10.3 Closureproperties . . . . . . . . . . . . . . . . . . . . . 45 2.11 Furtherreading . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3 SyntaxAnalysis 53 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2 Context-freegrammars . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Howtowritecontextfreegrammars . . . . . . . . . . . . 56 3.3 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.1 Syntaxtreesandambiguity . . . . . . . . . . . . . . . . . 60 3.4 Operatorprecedence . . . . . . . . . . . . . . . . . . . . . . . . 63 3.4.1 Rewritingambiguousexpressiongrammars . . . . . . . . 64 3.5 Othersourcesofambiguity . . . . . . . . . . . . . . . . . . . . . 66 3.6 Syntaxanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.7 Predictiveparsing . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.8 Nullable and FIRST . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.9 Predictiveparsingrevisited . . . . . . . . . . . . . . . . . . . . . 73 3.10 FOLLOW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.11 Alargerexample . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.12 LL(1)parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.12.1 Recursivedescent . . . . . . . . . . . . . . . . . . . . . . 80 3.12.2 Table-drivenLL(1)parsing . . . . . . . . . . . . . . . . . 81 3.12.3 Conflicts . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.13 RewritingagrammarforLL(1)parsing . . . . . . . . . . . . . . 84 3.13.1 Eliminatingleft-recursion . . . . . . . . . . . . . . . . . 84 3.13.2 Left-factorisation . . . . . . . . . . . . . . . . . . . . . . 86 3.13.3 ConstructionofLL(1)parserssummarized . . . . . . . . 87 3.14 SLRparsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.15 ConstructingSLRparsetables . . . . . . . . . . . . . . . . . . . 90 3.15.1 ConflictsinSLRparse-tables . . . . . . . . . . . . . . . 94 3.16 UsingprecedencerulesinLRparsetables . . . . . . . . . . . . . 95 3.17 UsingLR-parsergenerators . . . . . . . . . . . . . . . . . . . . . 98 3.17.1 Declarationsandactions . . . . . . . . . . . . . . . . . . 99 3.17.2 Abstractsyntax . . . . . . . . . . . . . . . . . . . . . . . 99 3.17.3 Conflicthandlinginparsergenerators . . . . . . . . . . . 102 3.18 Propertiesofcontext-freelanguages . . . . . . . . . . . . . . . . 104 3.19 Furtherreading . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 CONTENTS iii 4 ScopesandSymbolTables 113 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.2 Symboltables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.2.1 Implementationofsymboltables . . . . . . . . . . . . . . 115 4.2.2 Simplepersistentsymboltables . . . . . . . . . . . . . . 115 4.2.3 Asimpleimperativesymboltable . . . . . . . . . . . . . 117 4.2.4 Efficiencyissues . . . . . . . . . . . . . . . . . . . . . . 117 4.2.5 Sharedorseparatenamespaces . . . . . . . . . . . . . . 118 4.3 Furtherreading . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5 Interpretation 121 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.2 Thestructureofaninterpreter . . . . . . . . . . . . . . . . . . . 122 5.3 Asmallexamplelanguage . . . . . . . . . . . . . . . . . . . . . 122 5.4 Aninterpreterfortheexamplelanguage . . . . . . . . . . . . . . 124 5.4.1 Evaluatingexpressions . . . . . . . . . . . . . . . . . . . 124 5.4.2 Interpretingfunctioncalls . . . . . . . . . . . . . . . . . 126 5.4.3 Interpretingaprogram . . . . . . . . . . . . . . . . . . . 128 5.5 Advantagesanddisadvantagesofinterpretation . . . . . . . . . . 128 5.6 Furtherreading . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6 TypeChecking 133 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2 Thedesignspaceoftypes . . . . . . . . . . . . . . . . . . . . . . 133 6.3 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.4 Environmentsfortypechecking . . . . . . . . . . . . . . . . . . 135 6.5 Typecheckingexpressions . . . . . . . . . . . . . . . . . . . . . 136 6.6 Typecheckingoffunctiondeclarations . . . . . . . . . . . . . . . 138 6.7 Typecheckingaprogram . . . . . . . . . . . . . . . . . . . . . . 139 6.8 Advancedtypechecking . . . . . . . . . . . . . . . . . . . . . . 140 6.9 Furtherreading . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7 Intermediate-CodeGeneration 147 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 7.2 Choosinganintermediatelanguage . . . . . . . . . . . . . . . . . 148 7.3 Theintermediatelanguage . . . . . . . . . . . . . . . . . . . . . 150 7.4 Syntax-directedtranslation . . . . . . . . . . . . . . . . . . . . . 151 7.5 Generatingcodefromexpressions . . . . . . . . . . . . . . . . . 152 7.5.1 Examplesoftranslation. . . . . . . . . . . . . . . . . . . 155