编译器构造：C语言描述 英文版

Chapter1Introduction1

1.1OverviewandHistory1

1.2WhatDoCompilersDo?3

1.3TheStructureofaCompiler8

1.4TheSyntaxandSemanticsofProgrammingLanguages14

1.5CompilerDesignandProgrammingLanguageDesign16

1.6CompilerClassifications18

1.7InfluencesonComputerDesign19

Exercises21

Chapter2ASimpleCompiler23

2.1TheStructureofaMicroCompiler24

2.2AMicroScanner25

2.3TheSyntaxofMicro30

2.4RecursiveDescentParsing33

2.5TranslatingMicro38

2.5.1TargetLanguage38

2.5.2Temporaries39

2.5.3ActionSymbols39

2.5.4SemanticInformation40

2.5.5ActionSymbolsforMicro41

Exercises47

Chapter3ScanningTheoryandPractice50

3.1Overview50

3.2RegularExpressions52

3.3FiniteAutomataandScanners55

3.4UsingaScannerGenerator59

3.4.1ScanGen59

3.4.2Lex64

3.5PracticalConsiderations70

3.5.1ReservedWords70

3.5.2CompilerDirectivesandListingSourceLines72

3.5.3EntryofIdentifiersintotheSymbolTable73

3.5.4ScannerTermination74

3.5.5MulticharacterLookahead74

3.5.6LexicalErrorRecovery76

3.6TranslatingRegularExpressionsintoFiniteAutomata78

3.6.1CreatingDeterministicAutomata80

3.6.2OptimizingFiniteAutomata84

Exercises86

Chapter4GrammarsandParsing91

4.1Context-FreeGrammars:ConceptsandNotation91

4.2ErrorsinContext-FreeGrammars95

4.3TransformingExtendedBNFGrammars98

4.4ParsersandRecognizers98

4.5GrammarAnalysisAlgorithms100

Exercises108

Chapter5LL(1)GrammarsandParsers111

5.1TheLL(1)PredictFunction112

5.2TheLL(1)ParseTable115

5.3BuildingRecursiveDescentParsersfromLL(1)Tables116

5.4AnLL(1)ParserDriver120

5.5LL(1)ActionSymbols121

5.6MakingGrammarsLL(1)123

5.7TheIf-Then-ElseProbleminLL(1)Parsing127

5.8TheLLGenParserGenerator129

5.9PropertiesofLL(1)Parsers133

5.10LL(k)Parsing134

Exercises137

Chapter6LRParsing140

6.1Shift-ReduceParsers141

6.2LRParsers144

6.2.1LR(0)Parsing145

6.2.2HowCanWeBeSureLR(0)ParsersWorkCorrectly?153

6.3LR(1)Parsing155

6.3.1CorrectnessofLR(1)Parsing159

6.4SLR(1)Parsing161

6.4.1CorrectnessofSLR(1)Parsing164

6.4.2LimitationsoftheSLR(1)Technique165

6.5LALR(1)167

6.5.1BuildingLALR(1)Parsers171

6.5.2CorrectnessofLALR(1)Parsing!77

6.6CallingSemanticRoutinesinShift-ReduceParsers178

6.7UsingaParserGenerator180

6.7.1TheLALRGenParserGenerator180

6.7.2Yacc184

6.7.3Uses(andMisuses)ofControlledAmbiguity187

6.8OptimizingParseTables190

6.9PracticalLR(1)Parsers194

6.10PropertiesofLRParsing197

6.11LL(1)orLALR(1),ThatIstheQuestion198

6.12OtherShift-ReduceTechniques202

6.12.1ExtendedLookaheadTechniques202

6.12.2PrecedenceTechniques203

6.12.3GeneralContext-FreeParsers205

Exercises208

Chapter7SemanticProcessing216

7.1Syntax-directedTranslation317

7.1.1UsingaSyntaxTreeRepresentationofaParse217

7.1.2CompilerOrganizationAlternatives219

7.1.3Parsing,Checking,andTranslationinaSinglePass225

7.2SemanticProcessingTechniques227

7.2.1LLParsersandActionSymbols227

7.2.2LRParsersandActionSymbols228

7.2.3SemanticRecordRepresentations230

7.2.4ImplementingAction-controlledSemanticStacks232

7.2.5Parser-controlledSemanticStacks236

7.3IntermediateRepresentationsandCodeGeneration246

7.3.1IntermediateRepresentationsversusDirectCodeGeneration246

7.3.2FormsofIntermediateRepresentations247

7.3.3ATupleLanguage250

Exercises252

Chapter8SymbolTables254

8.1ASymbolTableInterface255

8.2BasicImplementationTechniques256

8.2.1BinarySearchTrees257

8.2,2HashTables257

8.2.3StringSpaceArrays259

8.3Block-StructuredSymbolTables261

8.4ExtensionstoBlock-StructuredSymbolTables267

8.4.1FieldsandRecords267

8.4.2ExportRules269

8.4.3ImportRules274

8.4.4AlteredSearchRules277

8.5ImplicitDeclarations279

8.6Overloading280

8.7ForwardReferences282

8.8Summary284

Exercises284

Chapter9Run-TimeStorageOrganization287

9.1StaticAllocation288

9.2StackAllocation289

9.2.1Displays292

9.2.2Block-levelandProcedure-levelActivationRecords295

9.3HeapAllocation296

9.3.1NoDeallocation297

9.3.2ExplicitDeallocation298

9.3.3ImplicitDeallocation298

9.3.4ManagingHeapSpace301

9.4ProgramLayoutinMemory302

9.5StaticandDynamicChains305

9.6FormalProcedures307

9.6.1StaticChains309

9.6.2Displays311

9.6.3Perspective312

Exercises313

Chapter10.ProcessingDeclarations319

10.1DeclarationProcessingFundamentals320

10.1.1AttributesintheSymbolTable320

10.1.2TypeDescriptorStructures321

10.1.3ListsintheSemanticStack323

10.2ActionRoutinesforSimpleDeclarations326

10.2.1VariableDeclarations326

10.2.2TypeDefinitions,Declarations,andReferences330

10.2.3RecordTypes335

10.2.4StaticArrays338

10.3ActionRoutinesforAdvancedFeatures340

10.3.1VariableandConstantDeclarations340

10.3.2EnumerationTypes343

10.3.3Subtypes346

10.3.4ArrayTypes349

10.3.5VariantRecords359

10.3.6AccessTypes364

10.3.7Packages366

10.3.8The'attributesandsemanticrecordStructures370

Exercises375

Chapter11ProcessingExpressionsandDataStructureReferences378

11.1Introduction378

11.2ActionRoutinesforSimpleNames,Expressions,andDataStructures380

11.2.1HandlingSimpleIdentifiersandLiteralConstants380

11.2.2ProcessingExpressions382

11.2.3SimpleRecordandArrayReferences387

11.2.4RecordandArrayExample390

11.2.5Strings390

11.3ActionRoutinesforAdvancedFeatures394

11.3.1MultidimensionalArrayOrganizationandReferences394

11.3.2RecordswithDynamicObjects406

11.3.3VariantRecords411

11.3.4Access-TypeReferences411

11.3.5OtherUsesofNamesinAda413

11.3.6RecordandArrayAggregates416

11.3.7OverloadResolution418

Exercises422

Chapter12TranslatingControlStructures426

12.1ifStatements427

12.21OOpS431

12.2.1whileloops432

12.2.2forloops433

12.3Compilingexits440

12.4ThecaseStatement445

12.5CompilinggotoStatements452

12.6ExceptionHandling457

12.7Short-circuitBooleanExpressions463

12.7.1One-addressShort-circuitEvaluation471

Exercises479

Chapter13TranslatingProceduresandFunctions484

13.1SimpleSubprograms485

13.1.1DeclaringSubprogramswithoutParameters485

13.1.2CallingParameterlessProcedures488

13.2PassingParameterstoSubprograms489

13.2.1Value,Result,andValue-ResultParameters490

13.2.2ReferenceandRead-onlyParameters492

13.2.3SemanticRoutinesforParameterDeclarations493

13.3ProcessingSubprogramCallsandParameterLists495

13.4SubprogramInvocation498

13.4.1SavingandRestoringRegisters498

13.4.2SubprogramEntryandExit500

13.5LabelParameters503

13.6NameParameters506

Exercises508

Chapter14AttributeGrammarsandMultipassTranslation510

14.1AttributeGrammars511

14.1.1SimpleAssignmentFormandActionSymbols514

14.1.2Tree-WalkAttributeEvaluators515

14.1:3On-the-FlyAttributeEvaluators524

14.1.4AnAttributeGrammarExample531

14.2Tree-structuredIntermediateRepresentations534

14.2.1InterfacestoAbstractSyntaxTrees536

14.2.2AbstractInterfacestoSyntaxTrees538

14.2.3ImplementingTrees544

Exercises544

Chapter15CodeGenerationandLocalCodeOptimization546

15.1AnOverview547

15.2RegisterandTemporaryManagement548

15.2.1ClassesofTemporaries550

15.2.2AllocatingandFreeingTemporaries551

15.3ASimpleCodeGenerator551

15.4InterpretiveCodeGeneration555

15.4.1OptimizingAddressCalculation556

15.4.2AvoidingRedundantComputations559

15.4.3RegisterTracking562

15.5PeepholeOptimization572

15.6GeneratingCodefromTrees574

15.7GeneratingCodefromDags'578

15.7.1Aliasing586

15.8CodeGeneratorGenerators589

15.8.1Grammar-BasedCodeGenerators593

15.8.2UsingSemanticAttributesinCode

Generators597

15.8.3GenerationofPeepholeOptimizers602

15.8.4CodeGeneratorGeneratorsBasedonTreeRewriting605

Exercises605

Chapter16GlobalOptimization614

16.1AnOverview--GoalsandLimits614

16.1.1AnIdealizedOptimizingCompiler

Structure617

16.1.2PuttingoptimizationinPerspective621

16.2OptimizingSubprogramCalls622

16.2.1lnlineExpansionofSubprogramCalls622

16.2.2OptimizingCallsofClosedSubroutines625

16.2.3InterproceduralDataFlowAnalysis630

16.3LoopOptimization636

16.3.1FactoringLoop-invariantExpressions637

16.3.2StrengthReductioninLoops641

16.4GlobalDataFlowAnalysis645

16.4.1Any-PathFlowAnalysis645

16.4.2All-PathsFlowAnalysis650

16.4.3ATaxonomyofDataFlowProblems652

16.4.4OtherImportantDataFlowProblems652

16.4.5GlobalOptimizationsUsingDataFlowInformation655

16.4.6SolvingDataFlowEquations660

16.5PuttingItAllTogether673

Exercises675

Chapter17ParsingintheRealWorld685

17.1CompactingTables686

17.1.1CompactingLL(1)ParseTables691

17.2SyntacticErrorRecoveryandRepair691

17.2.1ImmediateErrorDetection694

17.2.2ErrorRecoveryinRecursiveDescentParsers695

17.2.3ErrorRecoveryinLL(1)Parsers698

17.2.4TheFMQLL(1)Error-Repair

Algorithm698

17.2.5AddingDeletionstotheFMQRepairAlgorithm703

17.2.6ExtensionstotheFMQAlgorithm706

17.2.7ErrorRepairUsingLLGen712

17.2.8LRErrorRecovery713

17.2.9ErrorRecoveryinYacc714

17.2.10AutomaticallyGeneratedLRRepairTechniques715

17.2.11ErrorRepairUsingLALRGen723

17.2.12OtherLRError-RepairTechniques724

Exercises726

AppendixADefinitionofAda/CS730

AppendixBScanGen759

AppendixCLLGenUserManual768

AppendixDLALRGenUserManual777

AppendixEError-RepairFeaturesofLLGenandLALRGen787

AppendixFCompilerDevelopmentUtilities792

Bibliography799

Index806