CourseFlix

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 UK-based computer-science lecturer (Pikuma) and one of the most distinctive teachers working at the intersection of low-level programming and game development. His material is unusual in the modern course market for how deep it goes into the foundations: assembly, computer architecture, classical raycasting / rasterisation algorithms, and the math underneath modern graphics.

His CourseFlix listing reflects that range: courses on 3D Computer Graphics Programming, Raycasting Engine Programming, 2D Game Physics Programming, NES Programming with 6502 Assembly, PS1 Programming with MIPS Assembly & C, Atari 2600 Programming, Compilers, Interpreters and Formal Languages, plus C++ engine programming and Lua scripting. Material is paid and aimed at developers who want to understand systems from the ground up rather than ship CRUD apps.

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

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

Course content

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

Related courses

  • Python Django - The Practical Guide thumbnail

    Python Django - The Practical Guide

    By: Academind Pro (Maximilian Schwarzmüller)
    Learn how to build web applications and websites with Python and the Django framework.
    22 hours 54 minutes 38 seconds
  • The Software Designer Mindset (COMPLETE) thumbnail

    The Software Designer Mindset (COMPLETE)

    By: ArjanCodes (Arjan Egges)
    "The Software Designer Mindset" is a course that teaches all aspects of software architecture and offers practical advice on creating scalable software.
    14 hours 32 minutes 58 seconds
  • The Ultimate Django Series: Part 2 thumbnail

    The Ultimate Django Series: Part 2

    By: Mosh Hamedani (Code with Mosh)
    Do you want to take your Django skills to the next level and become that professional back-end developer that companies love to hire?
    5 hours 41 minutes 6 seconds 5 / 5

Frequently asked questions

What is Compilers, Interpreters and Formal Languages about?
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…
Who teaches Compilers, Interpreters and Formal Languages?
Compilers, Interpreters and Formal Languages is taught by Gustavo Pezzi. You can find more courses by this instructor on the corresponding source page.
How long is Compilers, Interpreters and Formal Languages?
Compilers, Interpreters and Formal Languages contains 171 lessons with a total runtime of 28 hours 52 minutes. All lessons are available to watch online at your own pace.
Is Compilers, Interpreters and Formal Languages free to watch?
Compilers, Interpreters and Formal Languages is part of CourseFlix's premium catalog. A CourseFlix subscription unlocks the full video player; the course description, table of contents, and preview information are available to everyone.
Where can I watch Compilers, Interpreters and Formal Languages online?
Compilers, Interpreters and Formal Languages is available to watch online on CourseFlix at https://courseflix.net/course/compilers-interpreters-and-formal-languages. The page hosts every lesson with the integrated video player; no download is required.