CS 375: Compilers: 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.

Index

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


CS 375