Compilers, Interpreters and Formal Languages

28h 52m 1s
English
Paid

Course description

This course is a beginner-friendly introduction to compilers. We will gradually develop an interpreter for a simple scripting language.

Read more about the course

We will cover:

  • Lexical analysis
  • Syntax analysis
  • Parsing algorithms
  • Intermediate Representation (AST)
  • Formal languages and grammars
  • Backus-Naur Form (BNF) and syntax diagrams
  • Error detection and handling
  • Code generation
  • Creating your own virtual machine (VM)
  • Bytecode generation
  • Type checking
  • LLVM IR
  • Basic code optimization
  • ...and much more!

Compilers have always been considered a complex topic, and their historical association with "dragons" (starting with the Dragon Book) only added to this myth's mystique. We will try to explain everything with beginners in mind. This course can be called a "first course" on compilers for developers who have not yet written interpreters.

What We Will Create

We will develop a compiler for a simple programming language called Pinky. It will be a hypothetical scripting language with syntax inspired by Lua and ALGOL W.

The main language for the course will be Python, which will allow us to focus on compiler-specific concepts while remaining productive. In addition, we will provide useful tips for implementing these ideas in the C language.

Required Tools

All you need is a command line, a simple text editor, and a Python interpreter. These tools are cross-platform, so you will be able to work on Windows, macOS, or Linux.

The course does not require prior knowledge, but knowing the basics of programming (if-else, loops, functions) will help you better grasp the material.

Watch Online

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

Watch Online Compilers, Interpreters and Formal Languages

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

Comments

0 comments

Want to join the conversation?

Sign in to comment

Similar courses

Clean Code Zero to One

Clean Code Zero to One

Sources: Shahan Chowdhury
"Clean Code Zero to One" is a guide on writing clean and maintainable code, based on the modern practices of Robert C. Martin (Uncle Bob).
Computer Systems

Computer Systems

Sources: Oz Nova (csprimer.com)
As software engineers, we study computer systems (or computer architecture) to understand how our programs ultimately work and how...
28 hours 15 minutes 48 seconds
Master Gorgeous UI Design

Master Gorgeous UI Design

Sources: together.art (Pablo Stanley)
Transform your visual design skills with Pablo Stanley and his team. This course will help you elevate your project quality and engage clients with a distinctiv
10 hours 56 minutes 16 seconds
Statistics Bootcamp (with Python): Zero to Mastery

Statistics Bootcamp (with Python): Zero to Mastery

Sources: zerotomastery.io
Master statistics with Python through projects and quizzes. Learn with fun from industry experts. Ideal for careers in Data Analytics and Machine Learning.
20 hours 50 minutes 51 seconds
Optimizing web performance and critical rendering path

Optimizing web performance and critical rendering path

Sources: udemy
Performance is a very important aspect of every web application. Web page should be loaded as quickly as possible and the animation should flow smoothly. People
1 hour 16 minutes 17 seconds