包邮编译器构造

1 introduction 1
　1.1 history of compilation 2
　1.2 what compilers do 4
　1.2.1 machine codegenerated bycompilers 4
　1.2.2 targetcode formats 7
　1.3 interpreters 9
　1.4 syntax and semantics 10
　1.4.1 static semantics 11
　1.4.2 runtime semantics 12
　1.5 organization of acompiler 14
　1.5.1 thescanner 16
　1.5.2 theparser 16
　1.5.3 thetypechecker(semantic analysis) 17
　1.5.4 translator(program synthesis) 17
　1.5.5 symbol tables 18
　1.5.6 theoptimizer 18
　1.5.7 thecode generator 19
　1.5.8 compiler writing tools 19
　1.6 programming language and compiler design 20
　1.7 computer architecture and compiler design 21
　1.8 compiler designconsiderations 22
　1.8.1 debugging(development)compilers 22
　1.8.2 optimizing compilers 23
　1.8.3 retargetable compilers 23
　1.9 integrated developmentenvironments 24
　exercises 26
2 a simple compiler 31
　2.1 aninformalde.nition of the aclanguage 32
　2.2 formalde.nition of ac 33
　2.2.1 syntaxspeci.cation 33
　2.2.2 tokenspeci.cation 36
　2.3 phasesof asimplecompiler 37
　2.4 scanning 38
　2.5 parsing 39
　2.5.1 predicting aparsingprocedure 41
　2.5.2 implementing theproduction 43
　2.6 abstractsyntaxtrees 45
　2.7 semantic analysis 46
　2.7.1 symbol tables 47
　2.7.2 typechecking 48
　2.8 code generation 51
　exercises 54
3 scanning—theory and practice 57
　3.1 overviewof ascanner 58
　3.2 regular expressions 60
　3.3 examples 62
　3.4 finite automata and scanners 64
　3.4.1 deterministic finite automata 65
　3.5 the lexscannergenerator 69
　3.5.1 de.ning tokensin lex 70
　3.5.2 thecharacterclass 71
　3.5.3 usingregular expressions to de.netokens 73
　3.5.4 characterprocessingusinglex 76
　3.6 otherscannergenerators 77
　3.7 practicalconsiderations ofbuildingscanners 79
　3.7.1 processingidenti.ers andliterals 79
　3.7.2 usingcompiler directives and listing sourcelines 83
　3.7.3 terminating thescanner 85
　3.7.4 multicharacter lookahead 86
　3.7.5 performanceconsiderations 87
　3.7.6 lexicalerrorrecovery 89
　3.8 regular expressions and finite automata 92
　3.8.1 transforming aregularexpressioninto annfa 93
　3.8.2 creating thedfa 94
　3.8.3 optimizing finite automata 97
　3.8.4 translating finite automata into regular expressions 100
　3.9 summary 103 exercises 106
4 grammars and parsing 113
　4.1 context-freegrammars 114
　4.1.1 leftmost derivations 116
　4.1.2 rightmost derivations 116
　4.1.3 parsetrees 117
　4.1.4 othertypes ofgrammars 118
　4.2 properties of cfgs 120
　4.2.1 reduced grammars 120
　4.2.2 ambiguity 121
　4.2.3 faultylanguage de.nition 122
　4.3 transformingextended grammars 122
　4.4 parsers and recognizers 123
　4.5 grammaranalysisalgorithms 127
　4.5.1 grammarrepresentation 127
　4.5.2 deriving theempty string 128
　4.5.3 firstsets 130
　4.5.4 followsets 134
　exercises 138
5 top-down parsing 143
　5.1 overview 144
　5.2 ll(k)grammars 145
　5.3 recursive-descentll(1)parsers 149
　5.4 table-driven ll(1)parsers 150
　5.5 obtaining ll(1)grammars 154
　5.5.1 common pre.xes 156
　5.5.2 left recursion 157
　5.6 a non-ll(1)language 159
　5.7 properties ofll(1)parsers 161
　5.8 parsetable representation 163
　5.8.1 compaction 164
　5.8.2 compression 165
　5.9 syntacticerrorrecovery andrepair 168
　5.9.1 errorrecovery 169
　5.9.2 errorrepair 169
　5.9.3 errordetectionin ll(1)parsers 171
　5.9.4 errorrecoveryinll(1)parsers 171
　exercises 173
6 bottom-up parsing 179
　6.1 overview 180
　6.2 shift-reduce parsers 181
　6.2.1 lrparsers and rightmostderivations 182
　6.2.2 lrparsing asknitting 182
　6.2.3 lrparsing engine 184
　6.2.4 thelrparsetable 185
　6.2.5 lr(k)parsing 187
　6.3 lr(0)table construction 191
　6.4 con.ictdiagnos