INDEX

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
eps-free grammar 103                                     Function 259
eps-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                             eps-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


Contents (GIF version) | Contents (Symbol Font version) | Home