Compilers, Interpreters and Formal Languages

28h 52m 1s
English
Paid

Welcome to an engaging journey into the world of compilers and interpreters! This course is designed to be a beginner-friendly introduction to compilers, where you will gradually learn to develop an interpreter for a simple scripting language.

Course Overview

Throughout this course, you will explore the following topics:

  • Lexical analysis: Understanding the process of tokenizing source code.
  • Syntax analysis: Delving into the structure of the language.
  • Parsing algorithms: Implementing strategies to parse code effectively.
  • Intermediate Representation (AST): Building Abstract Syntax Trees.
  • Formal languages and grammars: Learning foundational theories.
  • Backus-Naur Form (BNF) and syntax diagrams: Notating grammars concisely.
  • Error detection and handling: Managing and correcting syntax errors.
  • Code generation: Transforming high-level code into machine-executable form.
  • Creating your own virtual machine (VM): Designing an environment for running bytecode.
  • Bytecode generation: Producing efficient intermediate code.
  • Type checking: Ensuring type accuracy in programs.
  • LLVM IR: Understanding the Low-Level Virtual Machine Intermediate Representation.
  • Basic code optimization: Improving code performance.
  • ...and much more!

The Myth of Compilers

Compilers have long been perceived as a complex topic, often symbolized by "dragons," a notion perpetuated by the famous Dragon Book. Contrary to the myth, this course aims to demystify compilers, with a teaching approach tailored for beginners. Think of it as your first step into the world of compilers for those who have yet to write their own interpreters.

What We Will Create

Project Focus: Over the span of this course, you will develop a compiler for a simple programming language called Pinky. Named after its playful inspiration from Lua and ALGOL W, Pinky will serve as a perfect foundation for understanding key compiler concepts.

The course primarily utilizes Python, promoting a focus on compiler-specific principles while enhancing productivity. We also provide valuable insights into implementing these concepts in C for those interested.

Required Tools and Prerequisites

To get started, ensure you have the following:

  • A command line interface
  • A simple text editor
  • A Python interpreter

These tools are cross-platform, so whether you are on Windows, macOS, or Linux, you can seamlessly follow along. While this course does not require any pre-existing knowledge, familiarity with basic programming concepts such as if-else statements, loops, and functions will greatly aid your understanding.

About the Author: Gustavo Pezzi

Gustavo Pezzi thumbnail
Gustavo Pezzi is a university lecturer in London, UK. He has won multiple education awards as a teacher and is also the founder of pikuma.com. Gustavo teaches fundamentals of computer science and mathematics; his academic path includes institutions such as Pittsburg State University, City University of London, and University of Oxford.

Watch Online 171 lessons

This is a demo lesson (10:00 remaining)

You can watch up to 10 minutes for free. Subscribe to unlock all 171 lessons in this course and access 10,000+ hours of premium content across all courses.

View Pricing
0:00
/
#1: Motivations & Learning Outcomes
All Course Lessons (171)
#Lesson TitleDurationAccess
1
Motivations & Learning Outcomes Demo
14:35
2
How to Take this Course
02:59
3
Compilers as Translators
06:47
4
CPU Components
11:28
5
Opcodes & Instructions
10:00
6
Stack Push & Pop
05:32
7
Control Flow
15:11
8
What is a Program?
11:10
9
Tokens & Lexemes
05:23
10
Syntax Tree
17:00
11
Setting Up our Project Folder
09:50
12
Configuring Python on Windows
02:58
13
Makefile
01:25
14
Adding Token & Lexer Files
03:22
15
Simple Scanning Algorithm
11:33
16
Single-Character Tokens
11:54
17
Ignoring Whitespace & Comments
09:38
18
Scanning Equals & Not Equals
05:08
19
Scanning Two-Char Tokens
06:24
20
Scanning Numbers
13:22
21
Scanning Strings & Identifiers
09:14
22
Identifying Keywords
04:56
23
Scanning -- as Line Comment
05:13
24
Multiline Comments
01:58
25
Syntax Analysis
05:44
26
Context-Free Grammars & BNF
17:46
27
Grammar for Simple Expressions
13:56
28
A Model for AST Nodes
19:36
29
Recursive Descent Parsing
14:30
30
Parser Helper Functions (Exercise)
05:44
31
AST of a Simple Expression
11:41
32
Pretty AST Printing (Exercise)
03:16
33
AST Printing & Polish Notation
09:20
34
Terminal Colors & ANSI Escape Codes
03:33
35
Standardizing Errors Messages
10:39
36
Storing Line Numbers in Nodes
07:11
37
Renaming Term & Factor
04:59
38
A Tree-Walking Interpreter
07:47
39
Coding a Simple Tree-Walking Interpreter
16:23
40
No Signed Number Tokens?
02:52
41
Pinky Language Data Types
10:24
42
Dynamic Types at Runtime
14:03
43
Runtime Type Checks
08:34
44
Parsing Equality & Comparison (Exercise)
08:57
45
Parsing Equality & Comparison Operators
10:48
46
Exponent Associativity
07:50
47
Exponent & Unary Minus Precedence
03:33
48
Logical And & Logical Or
07:25
49
Short-Circuit Evaluation
12:46
50
Testing Expressions
13:21
51
REPL
03:24
52
Alphabets, Languages, & Grammars
11:56
53
Chomsky Grammar Hierarchy
14:43
54
A Program as a List of Statements
14:03
55
Parsing Print Statements
12:38
56
Interpreting Print Statements
06:51
57
PrintLn Statements (Exercise)
01:02
58
PrintLn Statements & Escape Chars
06:35
59
If Statements
21:04
60
Identifiers & Assignments
16:31
61
Program State & Memory
13:01
62
The Environment Class
13:08
63
Environment Load & Store (Exercise)
11:16
64
Global & Local Variables
10:53
65
While Statement (Exercise)
02:08
66
While Statements
06:43
67
For Statements
17:20
68
Stringifying Booleans & Integers
07:27
69
Mandelbrot Set (Exercise)
07:52
70
Mandelbrot Set Script in Pinky
08:25
71
Compiler-Compilers
08:03
72
Functions in Pinky
10:28
73
Function Model
14:02
74
Parsing Function Declaration
05:49
75
Parsing Function Call
17:20
76
Interpreting Function Declaration
26:35
77
Interpreting Function Call
09:51
78
Expressions as Statements?
03:06
79
Max. Number of Params (Exercise)
01:05
80
Max. Number of Params
00:45
81
Parsing Return Statements
07:20
82
Interpreting Return Statements
15:58
83
Fixing Params as Local Variables
05:17
84
Local Variables & Shadowing
16:55
85
Dragon Curve
18:12
86
Simplified Cosine & Sine Functions
08:07
87
Code Generation & VMs
12:29
88
Example of Stack Instructions
05:58
89
Adding Classes for Compiler & VM
10:46
90
Emitting Push Instructions
17:49
91
Emitting BinOp Instructions
08:40
92
Exercise: Formatting our Code
02:46
93
Formatting our Instructions
03:47
94
Emitting UnOp Instructions
08:28
95
Step by Step Stack Execution
04:41
96
VM Execution
14:36
97
VM Expression Evaluation
16:42
98
VM Comparison Instructions
14:18
99
Generating Code for If Statements
12:06
100
Generating Then & Else Labels
07:36
101
VM Jumps & Branches
10:47
102
String Concat Instruction?
06:26
103
Global Memory Load & Store
14:27
104
Coding Globals Load & Store
17:39
105
Scope Depth
14:58
106
Starting & Ending Blocks
07:37
107
Local Variables & Stack Slots
17:19
108
Local Variables Code Generation
21:12
109
Local Variables at Runtime
08:56
110
Storing Globals by Slot Number
08:23
111
Program Symbols & Debug Info
08:55
112
Exercise: While Code Generation
01:05
113
Generating Code for While Statements
06:02
114
Register vs Stack VMs
05:31
115
Register-based Bytecode
10:26
116
CPython Bytecode Disassembly
10:29
117
Search Locals in Reverse Order
13:15
118
Function Code Generation
11:56
119
Activation Frames
16:33
120
Function Symbol Table
08:04
121
Compiling Function Declarations
12:47
122
Implementing JSR & RTS Instructions
10:48
123
Exercise: Function Parameters
03:51
124
Validating Function Arity & Arguments
08:22
125
Frame Pointer Offsets
13:20
126
Return Statements
07:36
127
Removing Inactive Frame Slots
14:40
128
Type Systems
19:12
129
Type Annotations
20:28
130
Shunting Yard for Simple Expressions
13:11
131
Exercise: Shunting Yard Evaluation
05:19
132
A Simple Shunting Yard Implementation
13:47
133
Shunting Yard & Parentheses
09:53
134
Shunting Yard & Right-Associativity
04:28
135
Pratt Parser
13:43
136
NUD, LED, & Binding Powers
23:11
137
Example Pratt Parsing Expression
11:07
138
Pratt Code (Without Precedence)
11:47
139
Pratt Code (Precedence & Parentheses)
08:24
140
Pratt Code (Right Associativity)
08:53
141
Pratt Code (Prefix Unary Minus)
10:17
142
Parsing Expression Grammar
22:11
143
Using a PEG Library
12:12
144
Optimizations & Transformations
10:27
145
Constant Folding & Propagation
12:17
146
Algebraic Simplifications
05:43
147
Dead Code Elimination
02:58
148
Loop Unrolling & Inlining
06:14
149
Branch Prediction & Vectorization
07:32
150
Tail Call & Peephole Optimization
11:36
151
LLVM IR
14:28
152
Function Definition in LLVM IR
05:31
153
Using Clang to Visualize LLVM IR
12:04
154
Integer & Float LLVM Instructions
12:47
155
SSA Form & Phi Function
08:03
156
LLVM Language Reference Manual
03:11
157
LLVM Load & Store Instructions
14:47
158
Installing Numba's llvmlite
08:07
159
Adding a Module to LLVM
07:27
160
Adding a Function to LLVM
08:36
161
Loading & Storing Variables to LLVM
08:52
162
Calling External C Functions in LLVM
06:23
163
Emit LLVM IR for a Subset of Pinky
20:27
164
Visiting AST Nodes & Emitting LLVM IR
05:07
165
Emitting LLVM IR fadd Instruction
13:46
166
Emitting LLVM IR BinOps & UnOps
10:35
167
Compiling External C Print Functions
11:18
168
LLVM IR Assignments
11:28
169
Emitting LLVM IR for If Statements
09:07
170
Emitting LLVM IR for While Statements
05:58
171
Conclusion & Next Steps
11:32
Unlock unlimited learning

Get instant access to all 170 lessons in this course, plus thousands of other premium courses. One subscription, unlimited knowledge.

Learn more about subscription

Books

Read Book Compilers, Interpreters and Formal Languages

#Title
1Register-based Bytecode
2NUD, LED, & Binding Powers
3Using a PEG Library