CS 375: Compilers: Lecture Notes

CS 375: Compilers: Lecture Notes

Copyright © 2009 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: &forall &exist . Microsoft Internet Explorer will not display the math symbols, but Firefox will.

1. CS 375, Compilers: Class Notes

3. Course Topics

4. Pascal Test Program

5. Introduction

6. Machine Language

7. Assembly Language

8. High-Level Language

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 Classes

18. Implementation of Character Classes

19. Hand-written Lexical Analyzer

20. Example Lexical Analyzer

21. Flowchart for Parsing Identifier

22. Lexical Language Design

23. Token Data Structure

24. Example Token Data Structure

25. Number Conversion

26. Simple Number Scanner

27. Lexical Analyzer Output

28. Floating Point Numbers

29. IEEE Floating Point Standard

30. Floating Point Examples

32. Error Messages

33. Formal Syntax

35. Language Generation

39. Phrase Structure Grammar

40. Chomsky Hierarchy

41. Recognizing Automaton

42. Chomsky Language Hierarchy

43. Regular Languages

44. Example Regular Language

46. Regular Expressions

47. Lex Specifications

48. Sample lex Specification

49. C for Lex Sample

51. Comments on Sample lex

52. Translation Section

53. Lex Conventions

54. The Lookahead Operator

55. Auxiliary Procedures

56. Parser Overview

57. Context Free Languages

58. Context Sensitive Languages

59. Derivations

60. Language Generated by a Grammar

61. Ambiguity and Left Recursion

63. Top-down Parser

64. Bottom-up Parsing

65. Chart Parser

66. Augmented Transition Network Grammars

67. Augmented Transition Networks

68. Context Free Parser

69. Semantics Influences Parsing

70. Arithmetic Expressions

71. Example of Operator Precedence

72. Operator Precedence

73. Operator Precedence Parsing

74. Operator Precedence Parser

76. Stack Handling in C

77. Basic Routines

79. Operator Precedence Parser

81. Additional Considerations

82. Recursive Descent Parser

83. Bottom-up Table-driven (LR) Parsing

84. The LR Parsing Algorithm

85. Shift-Reduce Parser

86. Example Parsing Table

87. A Parse of id * id + id

88. Synthesized Translation

91. Yacc Specifications

92. Example: Desk Calculator

93. Yacc: Pascal Subset

94. Auxiliary C Code

95. Auxiliary C Code ...

97. Examples ...

98. Examples ...

99. Hints for yacc

100. File trivb.tree

101. The Semantic Actions

102. Supporting C Routines

104. Comments on the Example

105. Parsing Action Conflicts

106. Resolving Shift/Reduce Conflicts

107. Error Productions

108. Error Handling

109. Parsing Techniques

110. Looping Statements

111. Symbol Table

112. Symbol Table Organization

113. Symbol Table Organizations

114. Binary Tree Symbol Table

116. Hash Table

117. Hash Functions

118. Indexed Buckets

119. Nested Procedures

120. Tree of Symbol Tables

121. Stack Symbol Table

122. Symbol Table Entry

123. Kinds of Symbols

124. Kinds of Symbols ...

125. Looking up ID in Symbol Table

126. Variable Declarations

127. Identifier List etc.

128. Data Addressing

129. Storage Allocation

130. Alignment and Padding

131. Installing Variables in Symbol Table

132. Record Declarations

133. Symbol Table Structures for Record

134. Array Declarations

135. Symbol Table Structures for Array

136. Type Checking, Coercion, and Inference

137. Structure References

138. Structure References....

139. Record References

140. Array References

141. Array References in Pascal

142. Does Array Order Matter?

143. Example of Structure Declaration

144. Example of Structure Reference

145. Pointer Reference

146. Types as Tree Structures

147. Dynamic Type Checking

148. Static Type Checking

149. Strong Typing

150. Type Equivalence

151. Type Signatures

152. Polymorphic Procedures

153. Table for Labels

154. Intermediate Code

155. Quadruples

157. Reverse Polish Notation

158. Trees and Reverse Polish

159. Converting a Tree to RPN

160. Executing Reverse Polish

161. Executing RPN

162. RPN as Intermediate Code

163. Code Generation

164. Loading Process

165. Absolute File

166. Initializing BSS Storage

167. Banked Memory

168. Location Counter

169. Example of Assembly Listing

170. Backpatching

171. Link Editing Process

172. Relocatable Code

173. Finding Relocatable Modules

174. Assigning Absolute Addresses

175. Absolute Addresses

176. Link Editor

177. Form of Relocatable Code

178. Static Allocation

179. Dynamically Linked Library

180. Run-Time Support

181. Operations by Subroutine

182. Special Subroutines

183. Memory Management

184. Returning Memory

185. Heap Memory Management

186. Garbage Collection

187. Garbage Collection

188. Mark-And-Sweep Garbage Collection

189. Mark-and-Sweep ...

190. Copying Garbage Collection

191. Reference Counting

192. Reference Counting...

193. Garbage Collection Is Expensive

194. Compiled Procedure

195. Subroutine Call Is Expensive

196. Activations and Control Stack

197. Environment

198. Run-time Memory Organization

199. PowerPC Stack Frame Layout

200. SPARC Stack Frame Layout

201. SPARC Stack Frame Layout...

202. Global Variable References

203. Global Variables in Algol, Pascal, PL/I

204. Block-structured Symbol Table

205. Run-time Stack for Algol

206. Code Generation

207. Code Generation

208. Code Generation

209. Running Generated Code

210. Code Generation for Statements

211. Arithmetic Expressions

212. Basic Expression Algorithm

213. Trace of Expression Algorithm

214. Arithmetic Expression Algorithm

215. Register Management

216. Simple Register Allocation

217. Heuristic for Expressions

218. Improving Register Allocation

219. Register Allocation

220. Example of Code Generation

221. Example (2)

222. Example (3)

223. Example (4)

224. Reusing Register Contents

225. Register Targeting

226. SPARC Processor

227. Load/Store Instructions

228. Load/Store with Calculated Address

230. Integer Arithmetic Instructions

231. Compare and Branch

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

251. In-line Compilation

252. Optimization

253. Correctness of Optimization

254. Optional Optimization

255. Local and Global Optimization

256. Easy Optimization Techniques

257. Constant Folding

258. Peephole Optimization

259. Loop Unrolling

260. Partial Evaluation

261. Partial Evaluation

263. Simple Partial Evaluator

264. Simple Partial Evaluator...

267. Binding-Time Analysis

268. Futamura Projections

269. Interpreter

270. Specialization

271. Parameterized Programs

272. Pitfalls of Partial Evaluation

273. Pitfalls ...

274. Program Analysis

275. Basic Block

276. Finding Basic Blocks

277. Relations and Graphs

278. Graph Notations

279. Bit Vector Representations

280. Boolean Matrix Representation of Graph

281. Dominators

283. Definition and Reference of Variables

284. Data Flow Analysis for a Block

285. Availability of Expressions

286. Data Flow Analysis for an Interval

287. Busy Variables

288. Variable Uses and Register Assignment

289. Register Allocation by Graph Coloring

290. Overview of Global Optimization

291. gcc Compiler Optimization Options

292. gcc Optimizations

293. Loop Transformations

294. Strip Mining

295. Induction Variable Transformation

296. Finite Differencing

297. Example: Computing Squares

298. General Case

299. Finite Differencing for Set Operations

300. Memoization

301. Hardware Assistance

302. PowerPC Features

303. SPARC Features

304. Hardware Trends

305. Object-oriented Programming

306. Access to Objects

307. Domain Analysis

308. Internal Implementation is Hidden

309. Encapsulation with OOP

310. Object-oriented Programming Terminology

311. Terminology ...

312. Implementation of Objects

313. Are Basic Types Objects?

314. Inheritance and Class Structure

315. Message Sending

316. Dynamic Method Lookup

317. Static Method Lookup

318. Multiple Inheritance

319. Improving OOP Efficiency

321. Smalltalk Code

323. ThingLab Examples

324. Good Features of OOP

325. Unfortunate Features of OOP

326. Why OOP Is Not Enough

327. Top Ten Lies About OOP

328. Aspect-Oriented Programming

330. History of Lisp

331. Advantages of Lisp

332. Lisp Interaction

333. Function Definition

334. List Structure

335. Abstract Syntax Tree

336. Binding Lists

337. Substitution

338. Copying and Substitution Functions

339. Substitution in C

340. Loop Unrolling

341. Instantiating Design Patterns

342. Pattern Matching

343. Pattern Matching

344. Transformation by Patterns

345. Transformation Patterns

346. Program Transformation using Lisp

347. Dot Matching

348. Looping Patterns

349. Code Expansion by Looping Patterns

350. More Complex Rules

351. Multi-Level Patterns

352. Use of Multi-Level Patterns

353. Function Inlining

354. Program Transformation

355. Pattern Optimization Examples

356. Examples ...

357. Examples ...

358. Examples ...

359. Paul Graham:

361. Expression Trees to English

362. Generating English

363. Parsing English

364. ATN in Lisp

365. Parsing Functions

366. Grammar Compiler

367. Access to Database

368. Restaurant Database Grammar

369. Restaurant Queries

370. Physics Problems

371. Physics Queries