CS 375: Lecture Notes


Copyright © Gordon S. Novak Jr.

Permission is granted for individuals to make copies of these notes for personal use, or for instructors to make copies for classroom use.

Note: Some of these pages use math symbols such as: ∀ ∃ . Microsoft Internet Explorer will not display the math symbols, but Firefox will.

Contents

absolute address 171, 181

absolute code 169

absolute file 171, 177

abstract syntax tree 339

accessor 310

activation 204

activation record 204

actual parameter 253

address 252

alias 226, 254

alignment 135

alist 340

ambiguity 23, 38

ambiguous grammar 62

annotate 272

antisymmetric 282

aop 332

architecture 308

arithmetic instructions 233

array 139

array performance 147

array reference 145, 242

aspect-oriented programming 332

assignment 205

assoc 340

association list 340

associativity 73

ast 339

atn 67

augmented transition network 67

automaton 41

available 289

available on entry 289

avl tree 119

babbage 301

backpatching 176

banked memory 173

base address 133

base register 170

basic block 280

behavior 309

binding 205, 253, 266, 340

binding list 340

binding time analysis 272

bison 46

bit vector 284

block 280

boolean equations 289

bottom-up parsing 65

bounds check 154

bounds register 170

boxed number 317

branch prediction 306

bss 171

bss storage 172

busy 291

byte code 207

cache 323

cache miss 306, 308

cache prefetch 306

call by name 252

call by reference 252, 253

call by value 252, 253

call overhead 203

callee-saved 238

caller-saved 238

car 338

cartesian product 282

cascading errors 32

cast 191

cdr 338

character class 18

chart parser 66

chomsky 34

chomsky hierarchy 41

church 334

cky parser 66

class 129, 309, 314

closed function 355

code generation 211, 212

code generator 169

code motion 297

code reordering 308

color 293

compare 234

compile-time 264

compiler 9

compiler generator 273

computed 287

concatenation of languages 61

condition code 234, 306

conditional jump 240

cons 195, 338

constant folding 262

constant propagation 266

context free 35, 57, 58

context sensitive 59

control flow analysis 279

control stack 204

controllability 99

copying collector 198

correctness 258

cross-cutting 332

current status variable 84

data area 133

data flow 11

data flow analysis 279, 288

dead code 302

declaration 126

def-use chain 292

defined 287

definition-use chain 292

derivation 58, 60

derivative 302

difference engine 301

disambiguating rules 62

dll 185

dominator 286

dynamic 152, 266, 272

dynamic data 266

dynamic type checking 335

dynamically linked library 185

efficiency 323, 323

empty string 39

encapsulation 313, 328

environment 205

epilogue 202

equivalence 282

equivalent grammars 61

errors 32

executable 171, 177

exported symbol 180

expression 213

expression generation 214

external reference 180

finite differencing 300

fix 235

flex 46

float 235

floating point 29, 30, 31, 235

folding 262

formal parameter 253

forward branch 176

function call 237

futamura projections 273

garbage 194

garbage collection 194, 198, 335

genarith 216

genc 212

generation 36

generic 329

getchar 12

getter 310

global optimization 260, 294

grammar 35, 40

grammar notation 39

graph 282, 283

graph coloring 292, 293

hardware 305

hash function 121

hash table 120

hash with buckets 122

heap 191

heuristic 293

hiding 312

hierarchy 309

hoisting 297

identifier lookup 130

ieee floating point 30

if statement 240

immediate 216

imported symbol 180

in-line 256, 323

induction variable 299

information hiding 310, 312

inheritance 309, 320, 328

initialize 172, 191

inline 256

inline function 355

inlining 355

instance 309, 314

instance variable 314

instruction pointer 186

interaction 335

interface 312

intermediate code 57, 159

interpretation 266

interpreted code 207

interpreter 336

intrinsic function 236

invariant code 297

ip 186

jigsaw-puzzle modularity 331

just in time 323

killed 287

kleene closure 39

lambda calculus 334

language generated 61

language translation 349

layer 329

leader 281

left recursion 85

left-associative 73

leftmost derivation 60

leverage 257

lex 46, 47, 51

lexer output 28

lexical analyzer 13, 16

lexical scoping 123

library 177, 180

lifetime 204

line handler 12

link editor 177

linker 177, 178, 183

lisp 195, 333, 339

lisp interpreter 336

list 338

literal 216, 232

loader 170

local optimization 260

location counter 174, 184

loop fusion 297

loop header 286

loop transformation 297

loop unrolling 264

looping statements 114

machine language 6

macro 255

malloc 191

mark-and-sweep 196

matching 346

matrix 298

mccarthy 334

memoization 304

memory management 191

message 310, 315

method 129, 309, 314, 315, 319

method lookup 320

mix 266

mnemonic 7

modulo unrolling 264

move instructions 229, 230

multi-processor 298

multiple inheritance 322

mutator 310

name equivalence 155

nan 172

negate 235

new 191

non-volatile 238

nonterminal 35

number conversion 26

obfuscation 356

object 314

object file 177

object-oriented programming 309

observability 99

offline 272

offset 133, 184

online 272

ontology 309, 311

oop 157, 309

opacity 329

open 256

open function 355

operator precedence 72, 73, 74, 82

optimization 257, 329, 349

out-of-order 306

overhead 329

overloading 157

padding 135

parameter passing 252

parser 57, 63

parsing 37, 113

partial evaluation 265, 266, 323

partial order 282

partition 282

pattern matching 346

pattern-pair 348

pc 186

peekchar 12, 12

peephole 161

peephole optimization 263

performance 154, 249, 298, 305

pic 186

pie 186

pointer 150, 245

pointer arithmetic 191

pointer reference 150

polish 163

polymorphic 157

polymorphism 157, 328

position independent code 186

position independent executable 186

postamble 202

postincrement 299

powerpc 306

preamble 202

precedence 73

precompute 266

pretty-printer 81

printf 190

processor stall 308

productions 35

program analysis 279

program counter 186

prologue 202

prove 258

quadruple 161

quote 338

read-eval-print loop 336

record 137

record reference 144

recursion 335

recursive 58

recursive descent 60, 85

reduce 72

reducing 266

reduction in strength 261

reference counting 199

referenced 287

reflexive 282

register allocation 218, 292, 293

register management 217

register reuse 220

register window 307

regular expressions 47

regular language 44

relation 282

release storage 192

relocatable 177, 179

relocatable code 169

relocate 184

relocation bit 184

representation 335

reserved word 23

restore registers 202

retarget 159

return address 202

return statement 202

reverse polish 163

right-associative 73

rightmost derivation 60

row-major order 146

rpn 163

run-time 264

run-time library 188

save registers 202

scheme 334

scope 123

search 320

selector 314, 315, 319, 320

self 323

semantics 15, 70

send 310, 315

separate compilation 156

set 303

setter 310

shadow 124

shadowing 125, 320

shift 72, 244

shift-reduce parser 88

side-effect 329

signature 156

simula 309

simulation 309

smalltalk 324, 325

snan 172

sound 154

space 257

sparc 307

specialize 266, 323

speculative execution 306

speedup 298

spill code 293

stack 58, 204

stack frame 204

stack machine 166

stall 308

start address 170

start symbol 40

state 205

static 153, 266, 272

static data 266

storage alignment 135

storage allocation 134, 181

storage leak 192

storage management 192

store-multiple 306

strength reduction 261

strip mining 298

strong typing 154

structural equivalence 155

structure example 148

structure reference 142

subclass 314

sublis 341

subscripts 84

subst 341, 342

substitution 252, 341, 343

super 314

superclass 314

superscalar 306

switch 246

symbol table 115, 136

symbolic 333

symbols 128

symmetric 282

syntax 23, 34

synthesized translation 91

table lookup 240, 249, 323

tag 152

terminal 35

thinglab 327

this 319

three-address code 161

time 257

token 13, 24, 25

top-down filtering 64

top-down parser 64

transform 266, 273, 297, 348

transformation 333, 349, 356

transitive 282

tree form 81

triad 162

triple 162

type checking 141, 152, 153

type coercion 141

type constructor 151

type equivalence 155

type inference 141

type lattice 141

type safety 191

type signature 156

types as trees 151

unary 84

undefined symbol 126, 180

unfolding 266

union of languages 61

unrolling 264

use number 221

used 218, 287

var 252

variable declaration 131

variant record 154

volatile 238

white space 20

write 190

writeln 190

x86 processor 228

yacc 92

yacc code 132

yacc grammar 96

yacc hints 103


CS 375