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
鄂公网安备 42010302001612号 