Contents (GIF version) | Contents (Symbol Font version) | Home © P.D. Terry
The page numbers relate to a version of the text typeset for A4 paper which is available from here as a set of PCL files suitable for direct printing to a LaserJet® compatible printer.
8-bit microprocessor 229 Automata theory 110, 143
Axiomatic semantics 69
Accumulator 25, 30
Absolute addressing 28, 46 Back end 8, 182, 217
Abstract machine 7 Backpatching 74, 219, 224, 262
Abstract syntax tree 10, 101, 181, 232, 270 Backtracking 108, 117
Accumulator machine 27 Backus-Naur form 49, 54
Activation record 246, 263 Bailes 205
Actual parameter 93, 259, 263 Base class 183, 201, 213, 232, 270
Adding machine 162 Base pointer 39, 48, 247
Address 71 BASIC PRINT statement 109
absolute 28 Beacon symbol 137, 211
field expressions 87 Binary search 201, 214
fields 72 Binary tree 82, 214, 244
immediate 28 Block structure 241
indexed 29 BNF 49, 54
indirect 29 notation 54
mode 27 extensions 59
relative 29, 46 Boolean operator 12, 46, 65, 180, 190
return 246 Bootstrap 2, 20, 22, 62
run-time 247, 250, 252, 267 Bottom-up parsing 143
Alex scanner generator 176 Bound checks 46, 228
Alias 259 Bounded buffer 286
Algol 60 report 49, 54, 106 break statement 204
Alphabet 50 Brinch Hansen 205, 216, 251, 263, 275
ALU 30, 39 British Standard for EBNF 61
Ambiguity 49, 133 Bus lines 25
Ambiguous grammar 104, 125, 133 Busy-wait 295
Analytic phase 8
Anonymous type 215 C declarations 177
Antecedent 70 Call-by-reference 259, 274
ANTLR parser generator 148 Call-by-value 259, 274
Applied occurrence 71, 191, 208 Canonical derivation 56, 104
Argument 259 CASE statement 204, 225
Arithmetic expression 100, 151, 190 Character handler 8
Arithmetic logic unit 30, 39 Character set 63, 164
ARM (Annotated Reference Manual) 70 Chomsky hierarchy 107
Array handling 212, 216, 219, 228, 268, 275 Cichelli 202
ASCII 197, 202 Clang
ASSEMBLER Cocol specification 110, 220, Appendix C
grammar 72 code generator interface 212, 217
language 14, 20, 71 constraint analyser 208
Assembly 7 error handling 198, 206
assembler class 75 hand-crafted parser 203, 206
code generation 75, 82 hand-crafted scanner 199
conditional 95 hand-crafted source handler 196
lexical analysis 77 report (on Diskette)
macro processing 92 syntax 111
minimal 37 Clang-Topsy translator 192
one-pass 74, 83 Closure 50
semantic analysis 81 Kleene 50, 59, 65
source handling 76 positive 50
syntax analysis 79 COBEGIN ... COEND 282, 293
two-pass 73, 80 Cocktail 147
AST 10, 101, 181, 232, 270 Coco-2 176
AST code generation 181, 232, 270 Coco/R 61, 123, 146, 161, 189
Asynchronous input 297 Clang error handling 208
Attribute grammar 69, 110, 151, 157 Clang scanner 201
Augmented grammar 123 Clang specification 110, 220, Appendix C
driver program 174 Concrete syntax 10
execution 162 Concrete syntax tree 10
frame file 147, 161, 175 Concurrent processes 281
ftp sites Appendix A Concurrent programming 281
installation 161, Appendix A Condition flag 30, 36, 46
makefile 162 Conditional assembly 95
parser interface 173 Consequence rule 69
scanner interface 166 Consequent 70
support modules 172 Constant declarations 124
Cocol 61, 72, 161 Constant expressions 236
actions 168 Constant folding 184, 235
ANY 164, 168 Constraint analyser 10, 73, 208
CHARACTERS 164 CONTEXT clause 165
COMMENTS 164 Context condition 157
CONTEXT clause 165 Context-free grammar 109, 135
EOF 170 Context-sensitive 73, 106, 262
formal attributes 167 Context switch 291
grammar checks 171 Contextual constraint analyser 10
IGNORE 165 continue statement 204
LexString 173 Control statement 219
NAMES 166 Conway's problem 286
parser specification 167 Critical region 284, 288
Pragmas 162, 166 Cross compiler 2, 7, 17, 22, 75
PRAGMAS 166 Cross reference generator 191
PRODUCTIONS 167 Cycle-free grammar 104
scanner interface 166
scanner specification 163 DAG (directed acyclic graph) 237
semantic errors 172 Dangling ELSE 105, 126, 133, 204, 223
SemError() 173 Data register 25
Successful() 173 Deadlock 285, 295
SynError() 173 Debugger 239
SYNC 168, 170, 208 Declaration level 243
synchronization sets 170, 207 Declaration order 278
syntax error recovery 162, 169 Declarations 81, 138, 208, 241, 245, 260, 262
TOKENS 165 Decompiler 7
user names 166 Decorated tree 10, 152
WEAK 168, 208 Defining occurrence 71, 208
weak separators 171 Delphi 3
weak terminal 168, 170 Denotational semantics 69
Code generation 12 Dereferencing 41
ASSEMBLER 82 Derived from 54
assembler code 238 Descriptor ring 291
from an AST 181, 232, 270 Designator 134, 209, 212, 252, 259, 273
generator interface 212, 217 Deterministic finite automaton (DFA) 142
native 231 Deterministic parsing 116
on-the-fly 179, 184, 226, 250, 255, 266 DFA (deterministic finite automaton) 142
one-address code 179, 181 Dijkstra 284
optimization 12, 181, 235 Direct addressing 28
reentrant code 246 Directed acyclic graph (DAG) 237
stack machine code 226 Directive
Collision 91 assembler 71
Comments 51, 71, 109, 164 compiler 201
pragmatic 201 table 74
Communication 284 Directly produces 54
Compile-time 2, 71 Director set 123
Compiler 2, 7 Disassembler 7
load-and-go 7, 37, 219 Display 252, 257
multi-pass 14 Display copy 253
one-pass 14 Distributed processing 290
structure 8, 195 DLG 148
Compiler generator 4, 146 Driver program 174, 196
Dynamic link 247, 253 Free Software Foundation 19, 202
Dynamic semantics 4, 68 Front end 8, 182, 195
FSA (Finite state automata) 110, 139, 201
e-free grammar 103 Function 259
e-productions 58, 107, 109 assignment 264
EBNF 59 reference 260
British standard 61 return value 265, 277
expressions 60
Edison 70, 216, 225, 284 GNU project 19, 202
Effective address 28, 30, 39 Goal symbol 53, 55
Electronic mail 193 Goods trains 65
Empty set 51 GOTO statement 225, 258
Empty statement 128 Gough 202
Empty string 51, 186 Global variables 163, 242, 292
Emulation 25 gperf 202
Emulator 16 Grammar 53
single-accumulator 35, Appendix D ambiguous 104, 125, 133
stack machine 42, Appendix B attribute 69, 110, 151, 157
Environment 156 augmented 123
Equivalent grammar 100, 125, 133 checks 171
Erasure 59, 107 context-free 109, 135
Error checking code 13, 275 context-sensitive 106
Error cycle free 104
context free 136, 169, 206 e-free 103
context-sensitive 172, 208 equivalent 100, 125, 133
correction 13, 80, 136 expression 57, 100, 149, 151, 179, 190
detection 80, 86, 136 graph representation 185
handling 13 hierarchy 107
recovery 13, 136, 206 L-attributed 157
reporting 13, 87, 198 left-linear 110
semantic 172 null free 103
spurious 136, 138 reduced 103
Escape sequence 200 regular 109
EXIT statement 204, 224 restrictions 102, 118, 125
Exception 13 right-linear 109
Exclusion 284 S-attributed 157
Expression transformation 125
evaluation 151, 190 type 0 107
grammar 57, 100, 149, 151, 179, 190 type 1 107
parameter 259 type 2 109
Extended BNF 59 type 3 109
Extent of identifiers 242 Graph 185
Fetch-execute cycle 26, 35, 43 Half bootstrap 21
Finite state automata (FSA) 110, 139, 162 Hand-crafted parser 203, 206
FIRST function 118, 129, 136 Hand-crafted scanner 139, 199
FOLLOW function 120, 129, 136, 206, 211 Hand-crafted source handler 196
Followers 137, 206 Hash table 90, 214, 245
FOR loop 204, 223, 279 Hashing function 90
Formal Hexadecimal literals 78
attributes 168 High-level translator 7, 14, 19, 192
language 50 Highland Gathering 66
methods 4 Host language 2, 19
parameter 93, 259 Hypothetical stack machine 38, 217, 226
semantics 67
Fortran 2, 9, 50, 60, 117, 241 IF ... THEN ... ELSE 70, 105, 125, 133, 204, 219, 223, 257
Forward Ignorable characters 63, 164
declaration 257 Immediate addressing 28
reference 73, 83, 85, 88, 159, 219, 238, 251 Implementation language 2
Frame file 147, 161, 175 Independent compilation 14
Frame header 246, 263 Index register 30
Indexed addressing 29 Loop
Indivisible operation 284, 295 EXIT 224
Inductive expression 69 FOR 204, 223, 279
Inference rule 69 REPEAT 125, 223
Inherent addressing 28 WHILE 10, 68, 70, 205, 219
Inherited attribute 157 LR(k) parsing 143
Instruction pointer 26
Instruction register 25 Machine
Instruction set 31, 40 abstract 7
Intermediate addressing 247 code 231
Intermediate code 11 dependencies 8
Interpreter 15 instructions 25
Interpretive compiler 15, 22 single-accumulator 30
Interrupts 26 stack 38
IOTRANSFER 297 Macro 92
assembler 7, 74, 92
Java 4 handler class 93
expansion 92, 92
Kernel 290 parameters 93
Keywords 10, 64, 125, 142, 200, 201 recursive 96
Kleene closure 50, 59, 65 Make file 66, 162
Mark stack pointer 39, 248, 263
L-attributed grammar 157 Memory-indexed addressing 29
L-value 212 Memory-indirect addressing 29
Label 71, 81, 99 Metalanguage 49
redefined 82, 85 Metasymbol 50, 59
undefined 82 Minimal perfect hashing function 202
LALR parsing 146 Mnemonic 26, 71
Lambda production 59 Modularity 4
Language 50 Multi-stage translator 14
Language design 5, 276, 280 Music 193
Left canonical derivation 56 Mutual exclusion 284
Left linear grammar 110 Mutually recursive procedures 257
Left recursion 54, 126, 152
Level, declaration 243 Native code 231
lex scanner generator 147 Name equivalence 215
Lexeme 142, 163, 199, 201 NDFA (non-deterministic finite automaton) 142
Lexical analyser 8, 58, 77, 89 Nested blocks 242
Lexical structure 58, 61, 63 Non-deterministic finite automaton (NDFA) 142
Lexicon 58 Non-reachable production 103
LexName 173 Non-terminal 53, 60
LexString 173 Non-terminating production 103
Lifetime of identifiers 242 Null
Link production 58
dynamic 247, 253 string 50
static 248, 257 string problem 120
Linkage area 246 Nullable 59, 119, 130, 134
Linkage editor 7
Linker 7 Oberon 2, 3, 216, 240, 278
Literal pool 39, 48 Object language 2
Literal strings 115, 199, 228 Object orientation 3, 132, 183, 235
LL(1) conflict resolution 210, 223, 241, 245, 266, 269 occam 284
LL(1) restrictions 118, 125 Offset 226, 247, 263, 289
LL(k) parsing 117, 146 On-the-fly code generator 226
LLGen parser generator 147 One-address code 27
Load-and-go translator 7, 219 One and a half address code 27
Loader 37 One-pass assembler 74, 83
Local variables 220, 245 Opcode 27, 71
Location counter 75, 212 Open array 260, 275
Logical operator 180 Operating system 2
LOOP ... EXIT ... END statements 204, 224 Operational semantics 33, 68
Optimization 12, 181, 235, 251 calling 249, 252, 255, 266
Peephole 12, 228, 231, 257 declaration 245
Orthogonality 4 nested 242
Overflow 36, 46, 185 parameters 259
regular 241
P-code assembler 23 return 246, 250, 253
P-machine 17 Process
Parameters concurrent 281
actual 93, 259, 263, 267, 271 descriptor 291
array 268, 275 parallel 282
formal 259, 262 priority 297
passing mechanisms 259, 265, 268 sequential 281
procedural 275 Producer-consumer problem 285
Parameterless procedure 241 Produces 54
Parse stack 144 Produces directly 54
Parse tree 101, 152 Production rule 53
Parser 10, 58 Productions 53, 62
bottom-up 143 Cocol 169
construction 129 null 58, 103
deterministic 116 single 104, 129
generator 146, 185 unreachable 107
interface 173 useless 103, 128
LALR 146 Program counter 26, 30, 39
LL(k) 117 Program proving 69
LR(k) 143 Pseudo-code 16
recursive descent 116, 129, 132, 149, 195 Push-down automata 143
SLR 146
specification 167 Qualified identifier 135
table driven 141, 145
top-down 116, 143 R-value 212
Pascal standard 70 Range checks 229
Pascal-FC 284 Rational Pascal 205
Pascal-P compiler 17, 22, 203, 225 Real-time 282
Pascal-Plus 284 Record types 216
Pascal-S 239, 257, 298 Recursion
Passes 14, 195 in BNF 57, 59
PCCTS compiler generator 148 in grammars 54
Peephole optimization 12, 228, 231, 257 in procedures 254, 257, 276
Perfect hashing function 202 left 54, 126, 152
Pervasive identifier 244, 275 right 54, 126
Phases 8, 195 Recursive descent parsing 116, 129, 132, 149, 195, 276
Phrase 50 Reduce action 144
Phrase structure 56, 58, 61, 63 Reduced grammar 103
Phrase structure tree 56, 101, 151 Reductions 143
Pointer types 216 Redundant code 236
Portability 3, 15, 20 Register 25
Portable interpretive compilers 17, 22 allocation 180
Porting a compiler 20 indexed addressing 29
Post-mortem dump 275 indirect addressing 29
Postfix notation 150 status 30
Pragma 162, 165, 201 Regular
Pragmatic considerations 50, 73 expression 50, 139
Precedence 51, 127, 180 grammar 109
Precedence graph 282 procedure 168, 241
Predeclared identifier 275 Rehashing 91
Preprocessor 7 Relative addressing 29, 46
Pretty printer 192 Relocatable code 7, 97
Priority queue 297 Removal of redundant code 236
Procedural parameter 275 REPEAT loop 125, 204, 223
Procedure Reserved keywords 10, 64, 125, 142, 200
activation 248, 263 Restrictions
grammars 102, 118 Side-effect 70, 84, 279
LL(1) 118, 125 Signal 284, 287, 295
Return address 246, 249, 253 Single-accumulator machine 30
RETURN statement 260, 265, 268, 277 assembler 37
Return value 265 emulator 35
Reverse Polish 65, 150 opcodes 31
Rewrite rule 54 Single pass compilation 14
Right canonical derivation 56 Single production 104, 129
Right linear grammar 109 SKIP statement 205
Right recursion 54, 126 Source handling 76, 196, 198
ROM BIOS 33 Source language 2
Round-robin scheduler 296 Spreadsheet 15, 190
Rule of inference 69 Spurious error 136, 138
Rule of consequence 69 Stack frame 39, 246, 253, 263
Run-time 2, 71 Stack machine 38, 217, 226, 230
assembler 47
S-attributed grammar 157 emulator 42
SLR parsing 146 opcodes 40
SYNC 168, 170, 208 Stack pointer 30, 39, 48, 230
Sale's algorithm 277 Start sets 118
Scanner 8, 52, 58, 77, 89, 129, 139 Start symbol 53, 55
generator 146 State diagram 290
interface 166 State variable 91
specification 163 Static
Scope level 243, 247
insecurities 276 link 248
node 243 semantic analyser 10, 81, 87, 208, 266
rules 242 semantics 4, 68, 209, 266
Self-compiling compiler 20 Status register 30
Self-embedding 53, 54, 143 Storage management 246
Self-resident translator 7 String 50, 199, 228
Semantic table 74, 79
action 149, 151 type 216
attributes 152 Structural equivalence 215
driven parser 169, 210 Subrange 25, 200, 216
error detection 172 Subroutine 93
overtones 61, 133 Subset language 20
Semantics 49 Successful() 173
axiomatic 69 switch statement 204
denotational 69 Symbol 50
dynamic 4, 68 beacon 137, 211
formal 67 goal 53
operational 68 Symbol table 13, 73, 80, 89, 135, 209, 212, 242, 261
short-circuit 12, 180, 228, 239 Synchronization 136, 170, 206, 284
static 4, 68, 81, 209 SynError() 173
Semaphore 284, 287, 291, 295 Syntactic class 53
SemError() 173 Syntax 4
Semicolon 128, 212 analyser 10, 79, 87
Sentence 50, 53 diagram 67
Sentential form 54 equation 54
Sentinel node 243 error recovery 136, 162
Separate compilation 7, 14 Syntax directed translation 149
Sequential algorithms 281 Synthesized attribute 154
Sequential conjunction 12 Synthetic phase 8
Sequential process Systems program 2
Set class 87, 137
Shakespeare 124 T-diagram 6, 19
Shared memory 290 Table-driven algorithm 141, 145
Shift action 144 Target language 2
Shift-reduce conflict 146
Short-circuit semantics 12, 14, 180, 228, 239
Terminal 53, 60
start sets and symbols 118
successors 120
Three-address code 27
Time-slicing 290, 297
Token 8, 50, 165
classes 163
Tonic Solfa 193
Top-down parsing 116, 143
Topsy 114, 195
report (on Diskette)
Transition diagram 141
Transmitted attribute 157
Transputer 290
Tree-building actions 181
Turbo Pascal 3, 7, 16, 35, 183, 198, 257
Two-address code 27
Two-pass assembler 73, 80
Type 0 grammar 107
Type 1 grammar 103
Type 2 grammar 109
Type 3 grammar 109
Type checking 10, 214
Type identifiers 205
UCSD Pascal 17, 23, 99
Umbriel 239, 278
Undeclared identifier 82, 214
Union 146, 183, 213, 216, 232
UNIX 2, 66, 151
Unrestricted grammar 107
Useless production 103, 128
User names 166
VDL 69
VDM 69
Value Designator 212, 232
Variable
declarations 138
designator 212, 259
offset 226, 247, 263, 289
redeclared 242
undeclared 82, 214
Variable Designator 212, 232, 259
Variant record 146, 183, 213, 216, 232
Virtual machine 7, 16, 230
Visibility 242
Vocabulary 53
Void function 129, 168, 241, 244, 257
Wait 284, 287, 295
Weak separator 171, 206
Weak terminal 168, 170
WHILE loop 10, 68, 70, 205, 219
Wirth 3, 59, 189, 206, 240, 257, 277, 298
WITH statement 68
Yacc parser generator 146, 147, 151
Z80 processor 229
Zero-address instruction 40