编译器构造(影印版)

《编译器构造(影印版)》：大学计算机教育国外有名教材系列

《编译器构造(影印版)》是一本面向计算机系本科生的编译器教材。作者在三所美国大学拥有长达25年的编译器教学经验，在《编译器构造(影印版)》中对编译器构造的基本知识与关键技术进行了全新的讲解。《编译器构造(影印版)》的主要内容包括：编译器历史和概述、词法分析（扫描）、语法分析（包括自顶向下和自底向上的分析）、语法制导翻译、符号表和声明处理、语义分析、中间表示形式、虚拟机上的代码生成、运行时支持、目标代码生成和程序优化等。
《编译器构造(影印版)》提供了详尽清晰的算法，主推在实践中学习编译器构造的相关技术，同时提供了配合教材使用的教学网站、参考资料以及源码下载。不仅可以作为计算机专业本科生或研究生的参考教材，同时也适合相关领域的软件工程师、系统分析师等作为参考资料。

作者：（美国）费希尔（CharlesN.Fischer）（美国）赛特郎（RonaldK.Cytron）（美国）勒布兰（RichardJ.LeBlanc.Jr.）

1Introduction1
1.1HistoryofCompilation2
1.2WhatCompilersDo4
1.2.1MachineCodeGeneratedbyCompilers4
1.2.2TargetCodeFormats7
1.3Interpreters9
1.4SyntaxandSemantics10
1.4.1StaticSemantics11
1.4.2RuntimeSemantics12
1.5OrganizationofaCompiler14
1.5.1TheScanner16
1.5.2TheParser16
1.5.3TheTypeChecker(SemanticAnalysis)17
1.5.4Translator(ProgramSynthesis)17
1.5.5SymbolTables18
1.5.6TheOptimizer18
1.5.7TheCodeGenerator19
1.5.8CompilerWritingTools19
1.6ProgrammingLanguageandCompilerDesign20
1.7ComputerArchitectureandCompilerDesign21
1.8CompilerDesignConsiderations22
1.8.1Debugging(Development)Compilers22
1.8.2OptimizingCompilers23
1.8.3RetargetableCompilers23
1.9IntegratedDevelopmentEnvironments24
Exercises26

2ASimpleCompiler31
2.1AnInformalDe.nitionoftheacLanguage32
2.2FormalDe.nitionofac33
2.2.1SyntaxSpeci.cation33
2.2.2TokenSpeci.cation36
2.3PhasesofaSimpleCompiler37
2.4Scanning38
2.5Parsing39
2.5.1PredictingaParsingProcedure41
2.5.2ImplementingtheProduction43
2.6AbstractSyntaxTrees45
2.7SemanticAnalysis46
2.7.1SymbolTables47
2.7.2TypeChecking48
2.8CodeGeneration51
Exercises54

3Scanning—TheoryandPractice57
3.1OverviewofaScanner58
3.2RegularExpressions60
3.3Examples62
3.4FiniteAutomataandScanners64
3.4.1DeterministicFiniteAutomata65
3.5TheLexScannerGenerator69
3.5.1De.ningTokensinLex70
3.5.2TheCharacterClass71
3.5.3UsingRegularExpressionstoDe.neTokens73
3.5.4CharacterProcessingUsingLex76
3.6OtherScannerGenerators77
3.7PracticalConsiderationsofBuildingScanners79
3.7.1ProcessingIdenti.ersandLiterals79
3.7.2UsingCompilerDirectivesandListingSourceLines83
3.7.3TerminatingtheScanner85
3.7.4MulticharacterLookahead86
3.7.5PerformanceConsiderations87
3.7.6LexicalErrorRecovery89
3.8RegularExpressionsandFiniteAutomata92
3.8.1TransformingaRegularExpressionintoanNFA93
3.8.2CreatingtheDFA94
3.8.3OptimizingFiniteAutomata97
3.8.4TranslatingFiniteAutomataintoRegularExpressions100
3.9Summary103Exercises106

4GrammarsandParsing113
4.1Context-FreeGrammars114
4.1.1LeftmostDerivations116
4.1.2RightmostDerivations116
4.1.3ParseTrees117
4.1.4OtherTypesofGrammars118
4.2PropertiesofCFGs120
4.2.1ReducedGrammars120
4.2.2Ambiguity121
4.2.3FaultyLanguageDe.nition122
4.3TransformingExtendedGrammars122
4.4ParsersandRecognizers123
4.5GrammarAnalysisAlgorithms127
4.5.1GrammarRepresentation127
4.5.2DerivingtheEmptyString128
4.5.3FirstSets130
4.5.4FollowSets134
Exercises138

5Top-DownParsing143
5.1Overview144
5.2LL(k)Grammars145
5.3Recursive-DescentLL(1)Parsers149
5.4Table-DrivenLL(1)Parsers150
5.5ObtainingLL(1)Grammars154
5.5.1CommonPre.xes156
5.5.2LeftRecursion157
5.6ANon-LL(1)Language159
5.7PropertiesofLL(1)Parsers161
5.8ParseTableRepresentation163
5.8.1Compaction164
5.8.2Compression165
5.9SyntacticErrorRecoveryandRepair168
5.9.1ErrorRecovery169
5.9.2ErrorRepair169
5.9.3ErrorDetectioninLL(1)Parsers171
5.9.4ErrorRecoveryinLL(1)Parsers171
Exercises173

6Bottom-UpParsing179
6.1Overview180
6.2Shift-ReduceParsers181
6.2.1LRParsersandRightmostDerivations182
6.2.2LRParsingasKnitting182
6.2.3LRParsingEngine184
6.2.4TheLRParseTable185
6.2.5LR(k)Parsing187
6.3LR(0)TableConstruction191
6.4Con.ictDiagnosis197
6.4.1AmbiguousGrammars199
6.4.2GrammarsthatarenotLR(k)202
6.5Con.ictResolutionandTableConstruction204
6.5.1SLR(k)TableConstruction204
6.5.2LALR(k)TableConstruction209
6.5.3LALRPropagationGraph211
6.5.4LR(k)TableConstruction219Exercises224

7Syntax-DirectedTranslation235
7.1Overview235
7.1.1SemanticActionsandValues236
7.1.2SynthesizedandInheritedAttributes237
7.2Bottom-UpSyntax-DirectedTranslation239
7.2.1Example239
7.2.2RuleCloning243
7.2.3ForcingSemanticActions244
7.2.4AggressiveGrammarRestructuring246
7.3Top-DownSyntax-DirectedTranslation247
7.4AbstractSyntaxTrees250
7.4.1ConcreteandAbstractTrees250
7.4.2AnEf.cientASTDataStructure251
7.4.3InfrastructureforCreatingASTs252
7.5ASTDesignandConstruction254
7.5.1Design256
7.5.2Construction258
7.6ASTStructuresforLeftandRightValues261
7.7DesignPatternsforASTs264
7.7.1NodeClassHierarchy264
7.7.2VisitorPattern265
7.7.3Re.ectiveVisitorPattern268Exercises272

8SymbolTablesandDeclarationProcessing279
8.1ConstructingaSymbolTable280
8.1.1StaticScoping282
8.1.2ASymbolTableInterface282
8.2Block-StructuredLanguagesandScopes284
8.2.1HandlingScopes284
8.2.2OneSymbolTableorMany?285
8.3BasicImplementationTechniques286
8.3.1EnteringandFindingNames286
8.3.2TheNameSpace289
8.3.3AnEf.cientSymbolTableImplementation290
8.4AdvancedFeatures293
8.4.1RecordsandTypenames294
8.4.2OverloadingandTypeHierarchies294
8.4.3ImplicitDeclarations296
8.4.4ExportandImportDirectives296
8.4.5AlteredSearchRules297
8.5DeclarationProcessingFundamentals298
8.5.1AttributesintheSymbolTable298
8.5.2TypeDescriptorStructures299
8.5.3TypeCheckingUsinganAbstractSyntaxTree300
8.6VariableandTypeDeclarations303
8.6.1SimpleVariableDeclarations303
8.6.2HandlingTypeNames304
8.6.3TypeDeclarations305
8.6.4VariableDeclarationsRevisited308
8.6.5StaticArrayTypes311
8.6.6StructandRecordTypes312
8.6.7EnumerationTypes313
8.7ClassandMethodDeclarations316
8.7.1ProcessingClassDeclarations317
8.7.2ProcessingMethodDeclarations321
8.8AnIntroductiontoTypeChecking323
8.8.1SimpleIdenti.ersandLiterals327
8.8.2AssignmentStatements328
8.8.3CheckingExpressions328
8.8.4CheckingComplexNames329
8.9Summary334Exercises336

9SemanticAnalysis343
9.1SemanticAnalysisforControlStructures343
9.1.1ReachabilityandTerminationAnalysis345
9.1.2IfStatements348
9.1.3While,Do,andRepeatLoops350
9.1.4ForLoops353
9.1.5Break,Continue,Return,andGotoStatements356
9.1.6SwitchandCaseStatements364
9.1.7ExceptionHandling369
9.2SemanticAnalysisofCalls376
9.3Summary384Exercises385

10IntermediateRepresentations391
10.1Overview392
10.1.1Examples393
10.1.2TheMiddle-End395
10.2JavaVirtualMachine397
10.2.1IntroductionandDesignPrinciples398
10.2.2ContentsofaClassFile399
10.2.3JVMInstructions401
10.3StaticSingleAssignmentForm410
10.3.1Renamingandφ-functions411
Exercises414

11CodeGenerationforaVirtualMachine417
11.1VisitorsforCodeGeneration418
11.2ClassandMethodDeclarations420
11.2.1ClassDeclarations422
11.2.2MethodDeclarations424
11.3TheMethodBodyVisitor425
11.3.1Constants425
11.3.2ReferencestoLocalStorage426
11.3.3StaticReferences427
11.3.4Expressions427
11.3.5Assignment429
11.3.6MethodCalls430
11.3.7FieldReferences432
11.3.8ArrayReferences433
11.3.9ConditionalExecution43511.3.10Loops436
11.4TheLHSVisitor437
11.4.1LocalReferences437
11.4.2StaticReferences438
11.4.3FieldReferences439
11.4.4ArrayReferences439Exercises441

12RuntimeSupport445
12.1StaticAllocation446
12.2StackAllocation447
12.2.1FieldAccessinClassesandStructs449
12.2.2AccessingFramesatRuntime450
12.2.3HandlingClassesandObjects451
12.2.4HandlingMultipleScopes453
12.2.5Block-LevelAllocation455
12.2.6MoreAboutFrames457
12.3Arrays460
12.3.1StaticOne-DimensionalArrays460
12.3.2MultidimensionalArrays465
12.4HeapManagement468
12.4.1AllocationMechanisms468
12.4.2DeallocationMechanisms471
12.4.3AutomaticGarbageCollection472
12.5Region-BasedMemoryManagement479Exercises482

13TargetCodeGeneration489
13.1TranslatingBytecodes490
13.1.1Allocatingmemoryaddresses493
13.1.2AllocatingArraysandObjects493
13.1.3MethodCalls496
13.1.4ExampleofBytecodeTranslation498
13.2TranslatingExpressionTrees501
13.3RegisterAllocation505
13.3.1On-the-FlyRegisterAllocation506
13.3.2RegisterAllocationUsingGraphColoring508
13.3.3Priority-BasedRegisterAllocation516
13.3.4InterproceduralRegisterAllocation517
13.4CodeScheduling519
13.4.1ImprovingCodeScheduling523
13.4.2GlobalandDynamicCodeScheduling524
13.5AutomaticInstructionSelection526
13.5.1InstructionSelectionUsingBURS529
13.5.2InstructionSelectionUsingTwig531
13.5.3OtherApproaches532
13.6PeepholeOptimization532
13.6.1LevelsofPeepholeOptimization533
13.6.2AutomaticGenerationofPeepholeOptimizers536
Exercises538

14ProgramOptimization547
14.1Overview548
14.1.1WhyOptimize?549
14.2ControlFlowAnalysis555
14.2.1ControlFlowGraphs556
14.2.2ProgramandControlFlowStructure559
14.2.3DirectProcedureCallGraphs560
14.2.4Depth-FirstSpanningTree560
14.2.5Dominance565
14.2.6SimpleDominanceAlgorithm567
14.2.7FastDominanceAlgorithm571
14.2.8DominanceFrontiers581
14.2.9Intervals585
14.3IntroductiontoDataFlowAnalysis598
14.3.1AvailableExpressions598
14.3.2LiveVariables601
14.4DataFlowFrameworks604
14.4.1DataFlowEvaluationGraph604
14.4.2MeetLattice606
14.4.3TransferFunctions608
14.5Evaluation611
14.5.1Iteration611
14.5.2Initialization615
14.5.3TerminationandRapidFrameworks616
14.5.4DistributiveFrameworks620
14.6ConstantPropagation623
14.7SSAForm627
14.7.1Placingφ-Functions629
14.7.2Renaming631
Exercises636
Bibliography651
Abbreviations661
PseudocodeGuide663
Index