I am non computer science undergraduate and work as a web-developer(java, python, AS3 etc.) as a professional. I take 1 course per semester at my local university. I had taken Artificial Intelligence(comprising logic, context free grammar, CYK parsing, introductory NLP, markov chains, HMM etc.) last semester.

I am planning to take an introductory course in compilers in the coming semster which covers the following syllabus:

Lexical Analysis, Syntax Analysis, Semantic Analysis, Run-Time Environment, Intermediate Representations, Code Generation, Register Allocation, Instruction Selection and Scheduling, Introduction to Local and Global Code Optimizations, Data Flow analysis

My question is that, are there any computer science subjects which I should know before taking this course? If yes, it would be great if you could please list those courses.

  • 1
    Depends on your school. Mine was not that tough, so prerequisites were basic data structures and basic algorithms - that is all. Unfortunately they made compilers optional and I wussed out and did not take it.
    – Job
    Jul 13 '11 at 19:00

You should probably have a simple understanding of the following topics:

  • Discrete Math (sets, relations, trees, graphs, matrices, number theory)
  • Data Structures (in a more applied sense, how trees, lists, stacks, queues, and strings work)
  • Basic Algorithms (core concepts, sorting, searching, Big-O notation, etc)
  • Computer Architecture (digital logic, bit operations, micro-components, cache, memory, assembly programming)
  • Miscellaneous (regular expressions, context-free languages, finite state / pushdown automata, Turing machines and computability, lexical and parsing tools)

Optional, and will probably help a lot:

  • Operating System Design (process management, kernel design, synchronization, scheduling, events, locks, threads, and stack vs heap)

Well, I've done a bit of work in writing my own compilers, and I'd say the main prerequisite is a solid understanding of the stuff you'll get in a Data Structures class. Specifically, if you don't understand recursion, trees, and maps/hash tables, you're going to get very lost very quickly trying to learn to build a compiler.


You're going to need some basic background on computer architecture (registers, memory, special purpose registers, etc) and have seen some assembly code before. It would be even better if you've written some assembly code before, so you have a fair understanding of how machine language works.

Depending on the level of the course, it may be expected that you know a little bit about the superscalar processing and the like.

  • 1
    This is only true if we assume that the compiler in question is generating machine code and not some sort of bytecode. Jul 13 '11 at 19:12

If this is anything at all like the compilers class I took back in the late Cretaceous (ca. 1988), the only real prerequisites would be data structures (trees and hash tables especially), some assembly language (for the generated code), possibly some computer architecture, and whatever class would teach things like regular expressions, finite automata, Turing machines, etc. although those may be covered as part of the compiler course itself (FWIW, mine didn't). You'll also want to make sure you understand recursion.


You'll probably need to take a course on formal models and languages as well. Anything that covers the basic Chompsky hierarchy would be fine: Regular Languages + Context Free Languages. This is because it's important to understand the mathematical foundations of parsing so that your parser is clean, performant and correct. I think that a good compilers class will often cover both Regular Expressions and LALR / LL(k) parsers and the theory behind them.


Since they're talking about code optimization, its possible there will be some assembly langauge coding in there. So it might be good to have a passing familiarity with that at least. It'd depend on how that specific course is structured. Otherwise, just having a strong set of programming skills should be sufficient for an intro to compilers class I would think. It'll be a very valuable class.


Depends on your uni but most require these pre requisites:

=> Discrete Mathematics
Should include: propositional logic, predicate logic, set theory etc etc 

=> General Concepts of Programming (In any language of choice would be okay)
=> Algorithms and Data Structures
Should include: data structures, abstract data types, recursive algorithms

Not the answer you're looking for? Browse other questions tagged or ask your own question.