CS 375: Lecture Notes


Copyright © 2014 by 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: Many of these pages use math symbols such as: ∀ ∃ . Microsoft Internet Explorer will not display the math symbols, but Firefox will.

Contents

absolute address 168, 177

absolute code 166

absolute file 168

abstract syntax tree 333

activation 199

activation record 199

address 247

alias 221

alignment 132

alist 334

ambiguity 22, 37

ambiguous grammar 61

annotate 265

antisymmetric 275

aop 326

architecture 302

arithmetic instructions 228

array 136

array performance 144

array reference 142, 237

aspect-oriented programming 326

assignment 200

assoc 334

association list 334

associativity 72

ast 333

atn 66

augmented transition network 66

automaton 40

available 283

available on entry 283

avl tree 116

babbage 295

backpatching 173

banked memory 170

base address 130

base register 167

basic block 273

behavior 303

binding 200, 259, 334

binding list 334

binding time analysis 265

bison 45

bit vector 277

block 273

boolean equations 283

bottom-up parsing 64

bounds check 151

bounds register 167

boxed number 311

branch prediction 300

bss 168

bss storage 169

busy 285

byte code 202

cache 317

cache miss 300, 302

cache prefetch 300

call by name 247

call by reference 247

call by value 247

call overhead 198

callee-saved 233

caller-saved 233

car 332

cartesian product 275

cascading errors 31

cast 186

cdr 332

character class 17

chart parser 65

chomsky 33

chomsky hierarchy 40

church 328

cky parser 65

class 126, 303, 308

closed function 351

code generation 206, 207

code generator 166

code motion 291

code reordering 302

color 287

common 181

compare 229

compile-time 257

compiler 9

compiler generator 266

computed 281

concatenation of languages 60

condition code 229, 300

conditional jump 235

cons 190, 332

constant folding 255

constant propagation 259

context free 34, 56, 57

context sensitive 58

control flow analysis 272

control stack 199

controllability 96

copying collector 193

correctness 251

cross-cutting 326

data area 130

data flow 11

data flow analysis 272, 282

dead code 296

declaration 123

def-use chain 286

defined 281

definition-use chain 286

derivation 57, 59

derivative 296

difference engine 295

disambiguating rules 61

dll 182

dominator 279

dot matching 345

dynamic 149, 259, 265

dynamic data 259

dynamic type checking 329

dynamically linked library 182

efficiency 317, 317

empty string 38

encapsulation 307, 322

environment 200

epilogue 197

equivalence 275

equivalent grammars 60

errors 31

exported symbol 176

expression 208

expression generation 209

external reference 176

finite differencing 294

fix 230

flex 45

float 230

floating point 28, 29, 30, 230

folding 255

forward branch 173

function call 232

futamura projections 266

garbage 189

garbage collection 189, 193, 329

genarith 211

genc 207

generation 35

generic 323

getchar 12

global optimization 253, 288

grammar 34, 39

grammar notation 38

graph 275, 276

graph coloring 286, 287

hardware 299

hash function 118

hash table 117

hash with buckets 119

heap 186

heuristic 287

hiding 306

hierarchy 303

identifier lookup 127

ieee floating point 29

if statement 235

imported symbol 176

in-line 249, 317

induction variable 293

information hiding 306

inheritance 303, 314, 322

initialize 169, 186

inline 249

inline function 351

inlining 351

instance 303, 308

instance variable 308

interaction 329

interface 306

intermediate code 56, 156

interpretation 259

interpreted code 202

interpreter 330

interval 280, 284

intrinsic function 231

invariant code 291

jigsaw-puzzle modularity 325

just in time 317

killed 281

kleene closure 38

lambda calculus 328

language generated 60

language translation 343

layer 323

leader 274

left recursion 82

left-associative 72

leftmost derivation 59

leverage 250

lex 45, 46, 50

lexer output 27

lexical analyzer 13, 16

lexical scoping 120

library 176

lifetime 199

line handler 12

link editor 174, 179

lisp 190, 327, 333

lisp interpreter 330

list 332

literal 227

loader 167

local optimization 253

location counter 171, 180

loop header 279

loop transformation 291

loop unrolling 257

looping statements 111

machine language 6

macro 248

malloc 186

mark-and-sweep 191

matching 340

matrix 292

mccarthy 328

memoization 298

memory management 186

message 304, 309, 313

method 126, 303, 308, 309, 313

method lookup 314

mix 259

mnemonic 7

modulo unrolling 257

move instructions 224, 225

multi-processor 292

multiple inheritance 316

name equivalence 152

nan 169

negate 230

non-volatile 233

nonterminal 34

number conversion 25

obfuscation 352

object 308

object-oriented programming 303

observability 96

offline 265

offset 130, 180

online 265

ontology 305

oop 154, 303

opacity 323

open 249

open function 351

operator precedence 71, 72, 73, 79

optimization 250, 323, 343

out-of-order 300

overhead 323

overloading 154

padding 132

parameter passing 247

parser 56, 62

parsing 36, 110

partial evaluation 258, 259, 317

partial order 275

partition 275

pattern matching 340

pattern-pair 342

peekchar 12, 12

peephole 158

peephole optimization 256

performance 151, 244, 292, 299

pointer 147, 240

pointer arithmetic 186

pointer reference 147

polish 160

polymorphic 154

polymorphism 154, 322

postamble 197

powerpc 300

preamble 197

precedence 72

precompute 259

pretty-printer 78

processor stall 302

productions 34

program analysis 272

prologue 197

prove 251

quadruple 158

quote 332

read-eval-print loop 330

record 134

record reference 141

recursion 329

recursive 57

recursive descent 82

reduce 71

reducing 259

reduction in strength 254

reference counting 194

referenced 281

reflexive 275

register allocation 213, 286, 287

register management 212

register reuse 215

register window 301

regular expressions 46

regular language 43

relation 275

release storage 187

relocatable 175

relocatable code 166

relocate 180

relocation bit 180

representation 329

reserved word 22

restore registers 197

retarget 156

return address 197

return statement 197

reverse polish 160

rewrite rule 348

right-associative 72

rightmost derivation 59

row-major order 143

rpn 160

run-time 257

run-time library 183

save registers 197

scheme 328

scope 120

search 314

selector 309, 313, 314

self 313, 317

semantics 15, 69

send 304, 309, 313

separate compilation 153

set 297

shadow 121

shadowing 122, 314

shift 71, 239

shift-reduce parser 85

side-effect 323

signature 153

simula 303

simulation 303

smalltalk 318, 319

snan 169

sound 151

space 250

sparc 301

specialize 259, 317

speculative execution 300

speedup 292

spill code 287

stack 57, 199

stack frame 199

stack machine 163

stall 302

start address 167

start symbol 39

state 200

static 150, 259, 265

static data 259

storage alignment 132

storage allocation 131, 177

storage leak 187

storage management 187

store-multiple 300

strength reduction 254

strip mining 292

strong typing 151

structural equivalence 152

structure example 145

structure reference 139

subclass 308

subgraph 280

sublis 335

subscripts 81

subst 335, 336

substitution 247, 335, 337

super 308

superclass 308

superscalar 300

switch 241

symbol table 112, 133

symbolic 327

symbols 125

symmetric 275

syntax 22, 33

synthesized translation 88

table lookup 235, 244, 317

terminal 34

thinglab 321

this 313

three-address code 158

time 250

token 13, 23, 24

top-down filtering 63

top-down parser 63

transform 259, 266, 291, 342

transformation 327, 343, 352

transitive 275

tree form 78

triad 159

triple 159

type checking 138, 149, 150

type coercion 138

type constructor 148

type equivalence 152

type inference 138

type lattice 138

type safety 186

type signature 153

types as trees 148

unary 81

undefined symbol 123, 176

unfolding 259

union of languages 60

unrolling 257

use number 216

used 213, 281

var 247

variable declaration 128

variant record 151

volatile 233

white space 19

x86 processor 223

yacc 89

yacc code 129

yacc grammar 93

yacc hints 100


CS 375