Compilers, Interpreters & Formal Languages

This course is designed to be a beginner-friendly introduction to compilers. As we evolve, we will incrementally put together an interpreter for a very simple scripting language.

We'll cover:

• Lexical analysis
• Syntax analysis
• Parsing algorithms
• Intermediate representation (AST)
• Formal languages & grammars
• BNF notation & syntax diagrams
• Identifying and reporting errors
• Code generation
• Writing our own VM
• Emitting bytecode
• Type checking
• LLVM IR
• Simple code optimization
• ...and much, much more!

Compilers always had a reputation for being a difficult topic, and their historical association with dragons 🐉 (starting with the Dragon Book) never really help the cause.

We'll build together, from the ground up, a compiler for a simple programming language called Pinky. Think of a toy scripting language with a syntax inspired by Lua and ALGOL W.

x := 0
pi := 3.141592
name := 'Pinky'

-------------------------------------
-- Find the max between two numbers
-------------------------------------
func max(a, b)
  if a > b then
    ret a
  end
  ret b
end

-------------------------------------
-- Compute the factorial of a number
-------------------------------------
func factorial(n)
  if n == 1 then
    ret 1
  else
    ret n * factorial(n - 1)
  end
end

-------------------------------------
-- Main function
-------------------------------------
func main()
  i := 0
  while i <= 10 do
    print(i)  
    i := i + 1
  end
  for i := 1, 10 do
    print(factorial(i))
  end
end

main()