9

In my graduate class on compiler construction we've been introduced to the concept of a lattice. Three lectures have been devoted to lattices and so far it seems like an interesting tangent, but the dilemma is that it doesn't really help explain how a compiler uses a lattice to solve a concrete problem.

We have already covered parsing and typechecking. We're about to start liveness analysis and register allocation.

Note, I'm not looking for resources on building compilers. The following list of links have that covered pretty well. What I'm looking for is an explanation on the relationship between compilers and lattices, bonus points for the most examples.

Learning Resources on Parsers, Interpreters, and Compilers
How much of the compiler should we know?
Learning to write a compiler

Community
  • 1
  • 1
Kelly S. French
  • 12,198
  • 10
  • 63
  • 93
  • 1
    Make sure to attend the upcoming class on liveness analysis, and you will now of at least one important use of lattices in compilers ;) – Jørn Schou-Rode Apr 12 '10 at 20:42
  • That's almost how it went. "Next class is on liveness analysis." A week later, "Let's discuss lattices, meet, join, greatest lower bounds, least upper bounds, ..." The following class, "Now that you understand everything you need to know about liveness analysis..." I'd plead that I slept through class except I have 10+ pages of notes. – Kelly S. French Apr 12 '10 at 20:55
  • Heh, I remember those exact classes from my first compiler course. The teacher presented the topic as "Extraterrestrial Mathematics" :-) – Jørn Schou-Rode Apr 12 '10 at 21:03

1 Answers1

6

Lattices are a very useful structure to represent state while doing static analysis on the program being compiled - eg. for removing dead code detected by liveness analysis, available/very busy expressions, reaching definitions, sign analysis and constant propagation.

Here is a very good read if you want the details: Lecture Notes on Static Analysis

Jørn Schou-Rode
  • 37,718
  • 15
  • 88
  • 122