CS 375: Compilers: Lecture Notes

CS 375: Compilers: Lecture Notes

Copyright © 2006 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 Netscape or 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

89. Using yacc

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. Parameterized Programs

270. Pitfalls of Partial Evaluation

271. Pitfalls ...

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

281. Definition and Reference of Variables

282. Data Flow Analysis for a Block

283. Availability of Expressions

284. Data Flow Analysis for an Interval

285. Busy Variables

286. Variable Uses and Register Assignment

287. Register Allocation by Graph Coloring

288. Overview of Global Optimization

289. gcc Compiler Optimization Options

290. gcc Optimizations

291. Loop Transformations

292. Strip Mining

293. Induction Variable Transformation

294. Finite Differencing

295. Example: Computing Squares

296. General Case

297. Finite Differencing for Set Operations

298. Memoization

299. Hardware Assistance

300. PowerPC Features

301. SPARC Features

302. Hardware Trends

303. Object-oriented Programming

304. Access to Objects

305. Domain Analysis

306. Internal Implementation is Hidden

307. Encapsulation with OOP

308. Object-oriented Programming Terminology

309. Terminology ...

310. Implementation of Objects

311. Are Basic Types Objects?

312. Inheritance and Class Structure

313. Message Sending

314. Dynamic Method Lookup

315. Static Method Lookup

316. Multiple Inheritance

317. Improving OOP Efficiency

319. Smalltalk Code

321. ThingLab Examples

322. Good Features of OOP

323. Unfortunate Features of OOP

324. Why OOP Is Not Enough

325. Top Ten Lies About OOP

326. Aspect-Oriented Programming

328. History of Lisp

329. Advantages of Lisp

330. Lisp Interaction

331. Function Definition

332. List Structure

333. Abstract Syntax Tree

334. Binding Lists

335. Substitution

336. Copying and Substitution Functions

337. Substitution in C

338. Loop Unrolling

339. Instantiating Design Patterns

340. Pattern Matching

341. Pattern Matching

342. Transformation by Patterns

343. Transformation Patterns

344. Program Transformation using Lisp

345. Dot Matching

346. Looping Patterns

347. Code Expansion by Looping Patterns

348. More Complex Rules

349. Multi-Level Patterns

350. Use of Multi-Level Patterns

351. Function Inlining

352. Program Transformation

353. Pattern Optimization Examples

354. Examples ...

355. Examples ...

356. Examples ...

357. Paul Graham:

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