E-Book Overview
Amazon Digital Services, 2015. — 594 p. — ASIN: B010Y5UEII
This book covers the following topics related to Compiler Design: Lexical Analysis, Syntax Analysis, Interpretation, Type Checking, Intermediate-Code Generation, Machine-Code Generation, Register Allocation, Function calls, Analysis and optimisation, Memory management and Bootstrapping a compiler.
E-Book Content
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 . . . . . . . . .