Introduction: | Language and the Computer | 1 | |||
0.1 | Language is the Essential Tool of Intellect | 1 | |||
0.2 | The Computer Is Our Intellectual Assistant | 4 | |||
0.3 | To Teach a Computer a Language | 6 | |||
I | THEORY | ||||
Chapter 1 | The Description of Translators | 11 | |||
1.1 | Taking Our Own Medicine | 11 | |||
1.2 | Matching the Machine | 12 | |||
1.3 | Matching the Human Reader | 13 | |||
1.4 | Matching the Translation Method | 14 | |||
1.5 | Data | 14 | |||
1.6 | Control | 15 | |||
1.7 | From, To, and By | 16 | |||
Chapter 2 | The Description of Languages | 19 | |||
2.1 | The Need for Precise Definition | 19 | |||
2.2 | Phrase Structure and Meaning | 21 | |||
2.3 | Formal Definitions and Notation | 27 | |||
Chapter 3 | Translation: The Association of Form and Meaning | 37 | |||
3.1 | The Organization of Translators | 37 | |||
3.2 | Trees, Stacks, and Polish Notation | 41 | |||
3.3 | A Simple Compiler | 46 | |||
3.4 | The Canonical Parse and Synthesis | 53 | |||
3.5 | Translating Languages with Nested Scopes | 63 | |||
Chapter 4 | Canonical Parsing Algorithms | 71 | |||
4.1 | Computing the Phrase Structure of a Sentence | 71 | |||
4.2 | Using Parsing Functions | 74 | |||
4.3 | Representing Parsing Functions by Tables | 80 | |||
4.4 | Using LR Parsers for LR(k) Grammars | 89 | |||
Chapter 5 | The Construction of Parsing Decision Tables | 98 | |||
5.1 | Tabulating Information about Grammars | 98 | |||
5.2 | Collecting the Production Contexts | 102 | |||
5.3 | Computing the Stacking Decision Predicate | 108 | |||
5.4 | Computing the Production Selection Function | 112 | |||
5.5 | Guaranteeing Correctness | 116 | |||
5.6 | Constructing LR Parsers from LR(k) Grammars | 117 | |||
II | PRACTICE | ||||
Chapter 6 | The Language XPL | 125 | |||
6.1 | Evolving XPL | 125 | |||
6.2 | The Syntactic Description of XPL | 126 | |||
6.3 | Numeric Constants | 130 | |||
6.4 | String Constants | 131 | |||
6.5 | Identifiers | 132 | |||
6.6 | Declarations | 133 | |||
6.7 | Macro Definition and Use | 135 | |||
6.8 | Expressions and Assignments | 136 | |||
6.9 | Implicitly Declared Procedures and Variables | 139 | |||
6.10 | The if Statement | 142 | |||
6.11 | The do case Construct | 143 | |||
6.12 | The do while Construct | 143 | |||
6.13 | do with Iteration Count | 144 | |||
6.14 | Procedure Definition and Formal Parameters | 145 | |||
6.15 | Procedure call and return | 146 | |||
6.16 | Labels and the go to Statement | 147 | |||
6.17 | Comments and Compiler Control Toggles | 147 | |||
6.18 | Examples and Exercises in XPL Programming | 148 | |||
Chapter 7 | Programming in BNF | 161 | |||
7.1 | Using ANALYZER | 161 | |||
7.2 | Debugging a Grammar | 164 | |||
Chapter 8 | XCOM: A Self-Compiling Compiler | 191 | |||
8.1 | Describing XCOM | 191 | |||
8.2 | Reading XCOM | 192 | |||
8.3 | The Procedures | 193 | |||
8.4 | Resource Allocation | 205 | |||
8.5 | String Operations | 209 | |||
8.6 | The Procedure compactify | 211 | |||
8.7 | The Procedre INITIALIZATION | 214 | |||
8.8 | The Analysis Procedures | 216 | |||
8.9 | The Symbol Table | 217 | |||
8.10 | Code Generation | 219 | |||
8.11 | Peephole Optimization | 223 | |||
8.12 | Statistics Collection | 225 | |||
8.13 | The Bootstrap Process | 226 | |||
Chapter 9 | SKELETON: A Proto-Compiler | 231 | |||
9.1 | Describing SKELETON | 231 | |||
9.2 | The Procedures | 232 | |||
9.3 | Scanning and Vocabulary | 233 | |||
9.4 | The Analysis Algorithm | 235 | |||
9.5 | Deciphering the Recognition Tables | 238 | |||
9.6 | Building on SKELETON | 239 | |||
Chapter 10 | ANALYZER: A Grammar Analysis and Table-Building Program | 242 | |||
10.1 | Describing ANALYZER | 242 | |||
10.2 | The Procedures | 243 | |||
10.3 | Program Logic | 246 | |||
10.4 | Tailoring ANALYZER | 248 | |||
APPENDICES AND BIBLIOGRAPHY | |||||
Appendix | 1 | Living with an Operating System | 249 | ||
A1.0 | The Requirements | 249 | |||
A1.1 | The Execution of an XPL Program | 249 | |||
A1.2 | Specifying an Environment | 250 | |||
A1.3 | XPL Program Loading | 251 | |||
A1.4 | Communicating with the Submonitor | 254 | |||
A1.5 | String Input | 255 | |||
A1.6 | String Output | 256 | |||
A1.7 | Direct-Access Storage | 256 | |||
A1.8 | Debugging Aids | 257 | |||
A1.9 | External Information | 258 | |||
A1.10 | Error Handling and Program Termination | 258 | |||
A1.11 | Submonitor Flow Charts | 259 | |||
Appendix | 2 | The Trace Routine | 305 | ||
Appendix | 3 | XCOM | 365 | ||
Appendix | 4 | COMPACTIFY | 459 | ||
Appendix | 5 | SKELETON | 461 | ||
Appendix | 6 | ANALYZER | 479 | ||
Exercise Evaluations | 514 | ||||
BIBLIOGRAPHY | 521 | ||||
INDEX | 524 |