A Compiler Generator
Contents

 Introduction: Language and the Computer1
 0.1Language is the Essential Tool of Intellect1 
 0.2The Computer Is Our Intellectual Assistant4 
 0.3To Teach a Computer a Language6 
 
THEORY 
 
 Chapter 1 The Description of Translators11
 1.1Taking Our Own Medicine11 
 1.2Matching the Machine12 
 1.3Matching the Human Reader13 
 1.4Matching the Translation Method14 
 1.5Data14 
 1.6Control15 
 1.7From, To, and By16 
 
 Chapter 2 The Description of Languages19
 2.1The Need for Precise Definition19 
 2.2Phrase Structure and Meaning21 
 2.3Formal Definitions and Notation27 
 
 Chapter 3 Translation: The Association of Form and
Meaning
37
 3.1The Organization of Translators37 
 3.2Trees, Stacks, and Polish Notation41 
 3.3A Simple Compiler46 
 3.4The Canonical Parse and Synthesis53 
 3.5Translating Languages with Nested Scopes63 
 
 Chapter 4 Canonical Parsing Algorithms71
 4.1Computing the Phrase Structure of a Sentence71 
 4.2Using Parsing Functions74 
 4.3Representing Parsing Functions by Tables80 
 4.4Using LR Parsers for LR(k) Grammars89 
 
 Chapter 5 The Construction of Parsing Decision Tables98
 5.1Tabulating Information about Grammars98 
 5.2Collecting the Production Contexts102 
 5.3Computing the Stacking Decision Predicate108 
 5.4Computing the Production Selection Function112 
 5.5Guaranteeing Correctness116 
 5.6Constructing LR Parsers from LR(k) Grammars117 
 
II PRACTICE 
 
 Chapter 6 The Language XPL125
 6.1Evolving XPL125 
 6.2The Syntactic Description of XPL126 
 6.3Numeric Constants130 
 6.4String Constants131 
 6.5Identifiers132 
 6.6Declarations133 
 6.7Macro Definition and Use135 
 6.8Expressions and Assignments136 
 6.9Implicitly Declared Procedures and Variables139 
 6.10The if Statement142 
 6.11The do case Construct143 
 6.12The do while Construct143 
 6.13do with Iteration Count144 
 6.14Procedure Definition and Formal Parameters145 
 6.15Procedure call and return146 
 6.16Labels and the go to Statement147 
 6.17Comments and Compiler Control Toggles147 
 6.18Examples and Exercises in XPL Programming148 
 
 Chapter 7 Programming in BNF161
 7.1Using ANALYZER161 
 7.2Debugging a Grammar164 
 
 Chapter 8 XCOM: A Self-Compiling Compiler191
 8.1Describing XCOM191 
 8.2Reading XCOM192 
 8.3The Procedures193 
 8.4Resource Allocation205 
 8.5String Operations209 
 8.6The Procedure compactify211 
 8.7The Procedre INITIALIZATION214 
 8.8The Analysis Procedures216 
 8.9The Symbol Table217 
 8.10Code Generation219 
 8.11Peephole Optimization223 
 8.12Statistics Collection225 
 8.13The Bootstrap Process226 
 
 Chapter 9 SKELETON: A Proto-Compiler231
 9.1Describing SKELETON231 
 9.2The Procedures232 
 9.3Scanning and Vocabulary233 
 9.4The Analysis Algorithm235 
 9.5Deciphering the Recognition Tables238 
 9.6Building on SKELETON239 
 
 Chapter 10 ANALYZER: A Grammar Analysis and
Table-Building Program
242
 10.1Describing ANALYZER242 
 10.2The Procedures243 
 10.3Program Logic246 
 10.4Tailoring ANALYZER248 
 
APPENDICES AND BIBLIOGRAPHY
 
 Appendix1 Living with an Operating System249
 A1.0The Requirements249 
 A1.1The Execution of an XPL Program249 
 A1.2Specifying an Environment250 
 A1.3XPL Program Loading251 
 A1.4Communicating with the Submonitor254 
 A1.5String Input255 
 A1.6String Output256 
 A1.7Direct-Access Storage256 
 A1.8Debugging Aids257 
 A1.9External Information258 
 A1.10Error Handling and Program Termination258 
 A1.11Submonitor Flow Charts259 
 
 Appendix2 The Trace Routine305
 
 Appendix3 XCOM365
 
 Appendix4 COMPACTIFY459
 
 Appendix5 SKELETON461
 
 Appendix6 ANALYZER479
 
 Exercise Evaluations 514
 
 BIBLIOGRAPHY 521
 
 INDEX 524


XPL home