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.
1. CS 375, Compilers: Class Notes
2.
3. Course Topics
4. Pascal Test Program
5. Introduction
6. Machine Language
7. Assembly Language
8. High-Level Language
9. Compilers
10. Sequential Phases of a Compiler
11. Data Flow through the Compiler
12. Line Handler
13. Lexical Analyzer
14. Lexical Analysis
15. Character Codes: ASCII
16. Character Classes
17. Implementation of Character Classes
18. Hand-written Lexer
19. Example Lexer
20. Flowchart for Parsing Identifier
21. Lexical Language Design
22. Token Data Structure
23. Example Token Data Structure
24. Number Conversion
25. Simple Number Scanner
26. Lexer Output
27. Floating Point Numbers
28. IEEE Floating Point Standard
29. Floating Point Examples
30. Errors
31. Error Messages
32. Formal Syntax
33. Grammar
34. Language Generation
35. Parsing
36. Ambiguity
37. Notation
38. Phrase Structure Grammar
39. Chomsky Hierarchy
40. Recognizing Automaton
41. Chomsky Language Hierarchy
42. Regular Languages
43. Example Regular Language
44. lex
45. Regular Expressions
46. Lex Specifications
47. Sample lex Specification
48. C for Lex Sample
49. lex.yy.c
50. Comments on Sample lex
51. Translation Section
52. Lex Conventions
53. The Lookahead Operator
54. Auxiliary Procedures
55. Parser Overview
56. Context Free Languages
57. Context Sensitive Languages
58. Derivations
59. Language Generated by a Grammar
60. Ambiguity and Left Recursion
61. Parsing
62. Top-down Parser
63. Bottom-up Parsing
64. Chart Parser
65. Augmented Transition Network Grammars
66. Augmented Transition Networks
67. Context Free Parser
68. Semantics Influences Parsing
69. Arithmetic Expressions
70. Example of Operator Precedence
71. Operator Precedence
72. Operator Precedence Parsing
73. Operator Precedence Parsing
74. Operator Precedence Parsing ...
75. Operator Precedence Parser
76. Examples
77. Stack Handling in C
78. Basic Routines
79.
80. Operator Precedence Parser
81.
82. Additional Considerations
83. Recursive Descent Parser
84. Bottom-up Table-driven (LR) Parsing
85. The LR Parsing Algorithm
86. Shift-Reduce Parser
87. Example Parsing Table
88. A Parse of id * id + id
89. Synthesized Translation
90. Using yacc
91. y.tab.c
92. Yacc Specifications
93. Example: Desk Calculator
94. Yacc: Pascal Subset
95. Auxiliary C Code
96. Auxiliary C Code ...
97. Controllability and Observability
98. Example
99. Examples ...
100. Examples ...
101. Hints for yacc
102. File trivb.tree
103. The Semantic Actions
104. Supporting C Routines
105. Example
106. Comments on the Example
107. Parsing Action Conflicts
108. Resolving Shift/Reduce Conflicts
109. Error Productions
110. Error Handling
111. Parsing Techniques
112. Looping Statements
113. Symbol Table
114. Symbol Table Organization
115. Symbol Table Organizations
116. Binary Search Tree (BST) Symbol Table
117. AVL Trees
118. Hash Table
119. Hash Functions
120. Indexed Buckets
121. Lexical Scoping
122. Tree of Symbol Tables
123. Stack Symbol Table
124. Use of Symbol Table
125. Symbol Table Entry
126. Kinds of Symbols
127. Kinds of Symbols ...
128. Looking up ID in Symbol Table
129. Variable Declarations
130. Identifier List etc.
131. Data Addressing
132. Storage Allocation
133. Alignment and Padding
134. Installing Variables in Symbol Table
135. Record Declarations
136. Symbol Table Structures for Record
137. Array Declarations
138. Symbol Table Structures for Array
139. Type Checking, Coercion, and Inference
140. Structure References
141. Structure References....
142. Record References
143. Array References
144. Array References in Pascal
145. Does Array Order Matter?
146. Example of Structure Declaration
147. Example of Structure Reference
148. Pointer Reference
149. Types as Tree Structures
150. Dynamic Type Checking
151. Static Type Checking
152. Strong Typing
153. Type Equivalence
154. Type Signatures
155. Polymorphic Procedures
156. Table for Labels
157. Intermediate Code
158. Trees
159. Quadruples
160. Triples
161. Reverse Polish Notation
162. Trees and Reverse Polish
163. Converting a Tree to RPN
164. Executing Reverse Polish
165. Executing RPN
166. RPN as Intermediate Code
167. Code Generation
168. Loading Process
169. Absolute File
170. Initializing BSS Storage
171. Banked Memory
172. Location Counter
173. Example of Assembly Listing
174. Backpatching
175. Linker
176. Linking Process
177. Relocatable Code
178. Finding Relocatable Modules
179. Assigning Absolute Addresses
180. Absolute Addresses
181. Linker
182. Form of Relocatable Code
183. Dynamically Linked Library
184. Position Independent Code
185. Advantages of Position Independent Code
186. Run-Time Support
187. Operations by Subroutine
188. Special Subroutines
189. Memory Management
190. Returning Memory
191. Garbage Collection
192. Garbage Collection
193. Mark-And-Sweep Garbage Collection
194. Mark-and-Sweep ...
195. Copying Garbage Collection
196. Reference Counting
197. Reference Counting...
198. Garbage Collection Is Expensive
199. Compiled Procedure
200. Subroutine Call Is Expensive
201. Activations and Control Stack
202. Environment
203. Run-time Memory Organization
204. Code Generation
205. Code Generation
206. Code Generation
207. Running Generated Code
208. Overview of Code Generation
209. Code Generation for Statements
210. Arithmetic Expressions
211. Basic Expression Algorithm
212. Trace of Expression Algorithm
213. Arithmetic Expression Algorithm
214. Register Management
215. Simple Register Allocation
216. Heuristic for Expressions
217. Improving Register Allocation
218. Register Allocation
219. Example of Code Generation
220. Example (2)
221. Example (3)
222. Example (4)
223. Reusing Register Contents
224. Register Targeting
225. x86 Processor
226. Move (Load/Store) Instructions
227. Kinds of Move Addressing
228. Move with Calculated Address
229. Literals
230. Integer Arithmetic Instructions
231. Compare and Jump
232. Floating Point
233. Intrinsic Functions
234. Function Calls
235. Volatile Registers
236. Details of Function Call
237. IF Statement Generation
238. IF Statement Optimization
239. Array References
240. Easy Array References
241. Better Array References
242. Pointer References
243. switch Statement
244. switch Statement Compiled
245. switch Statement Compiled -O
246. Table Lookup
247. Table Lookup Compiled
248. Table Lookup Compiled -O
249. Parameter Passing
250. Reference vs. Value
251. Aliasing
252. Macros
253. In-line Compilation
254. Optimization
255. Correctness of Optimization
256. Optional Optimization
257. Local and Global Optimization
258. Easy Optimization Techniques
259. Constant Folding
260. Peephole Optimization
261. Loop Unrolling
262. Partial Evaluation
263. Partial Evaluation
264. Example
265. Simple Partial Evaluator
266. Simple Partial Evaluator...
267. Examples
268. Futamura Projections
269. Interpreter
270. Specialization
271. Parameterized Programs
272. Program Analysis
273. Basic Block
274. Finding Basic Blocks
275. Relations and Graphs
276. Graph Notations
277. Bit Vector Representations
278. Boolean Matrix Representation of Graph
279. Dominators
280. Data Flow Analysis:
281. Data Flow Analysis for a Block
282. Availability of Expressions
283. Solving Data Flow Equations
284. Busy Variables
285. Variable Uses and Register Assignment
286. Register Allocation by Graph Coloring
287. Overview of Global Optimization
288. Loop Transformations
289. Strip Mining
290. Induction Variable Transformation
291. Finite Differencing
292. Example: Computing Squares
293. General Case
294. Memoization
295. Hardware Assistance
296. IBM Power Architcture Features
297. SPARC Features
298. Hardware Trends
299. Object-oriented Programming
300. Access to Objects
301. Domain Analysis
302. Internal Implementation is Hidden
303. Encapsulation with OOP
304. Object-oriented Programming Terminology
305. Terminology ...
306. Implementation of Objects
307. Are Basic Types Objects?
308. Inheritance and Class Structure
309. Message Sending
310. Dynamic Method Lookup
311. Static Method Lookup
312. Multiple Inheritance
313. Improving OOP Efficiency
314. Good Features of OOP
315. Unfortunate Features of OOP
316. Why OOP Is Not Enough
317. Top Ten Lies About OOP
318. Aspect-Oriented Programming
319. Lisp
320. History of Lisp
321. Advantages of Lisp
322. Lisp Interaction
323. Function Definition
324. List Structure
325. Abstract Syntax Tree
326. Binding Lists
327. Substitution
328. Copying and Substitution Functions
329. Substitution in C
330. Loop Unrolling
331. Instantiating Design Patterns
332. Pattern Matching
333. Pattern Matching
334. Transformation by Patterns
335. Transformation Patterns
336. Program Transformation using Lisp
337. Looping Patterns
338. Code Expansion by Looping Patterns
339. Multi-Level Patterns
340. Use of Multi-Level Patterns
341. Function Inlining
342. Program Transformation
343. Paul Graham:
344. English
345. Expression Trees to English
346. Generating English
347. Parsing English
348. ATN in Lisp
349. Parsing Functions
350. Grammar Compiler
351. Access to Database
352. Restaurant Database Grammar
353. Restaurant Queries
354. Physics Problems
355. Physics Queries