English | MP4 | AVC 1920×1080 | AAC 44KHz 2ch | 171 Lessons (28h 52m) | 5.32 GB
Create your own programming language by writing an interpreter and a compiler from scratch.
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 try to approach every explanations with beginners in mind. You can think of it as a “first course” on compilers for developers that never wrote an interpreter before.
What we’ll build
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.
Our main host language will be Python. Python allows us to focus our attention on compiler-specific concepts while being extremely productive. Still, I’ll try to include some helpful tips on how to implement the ideas we just learned using the C programming language.
The tools you’ll need
All you need is a command-line, a simple code editor, and a Python interpreter. All these tools are cross-platform, so you’ll be able to code along on either Windows, macOS, or Linux!
Is this course for you?
If you never wrote an interpreter before, or even if you did but still feel you have some blind spots in your understanding of how it all works, then this course is definitely for you!
Table of Contents
1 Motivations & Learning Outcomes
2 How to Take this Course
3 Compilers as Translators
4 CPU Components
5 Opcodes & Instructions
6 Stack Push & Pop
7 Control Flow
8 What is a Program?
9 Tokens & Lexemes
10 Syntax Tree
11 Setting Up our Project Folder
12 Configuring Python on Windows
13 Makefile
14 Adding Token & Lexer Files
15 Simple Scanning Algorithm
16 Single-Character Tokens
17 Ignoring Whitespace & Comments
18 Scanning Equals & Not Equals
19 Scanning Two-Char Tokens
20 Scanning Numbers
21 Scanning Strings & Identifiers
22 Identifying Keywords
23 Scanning — as Line Comment
24 Multiline Comments
25 Syntax Analysis
26 Context-Free Grammars & BNF
27 Grammar for Simple Expressions
28 A Model for AST Nodes
29 Recursive Descent Parsing
30 Parser Helper Functions (Exercise)
31 AST of a Simple Expression
32 Pretty AST Printing (Exercise)
33 AST Printing & Polish Notation
34 Terminal Colors & ANSI Escape Codes
35 Standardizing Errors Messages
36 Storing Line Numbers in Nodes
37 Renaming Term & Factor
38 A Tree-Walking Interpreter
39 Coding a Simple Tree-Walking Interpreter
40 No Signed Number Tokens?
41 Pinky Language Data Types
42 Dynamic Types at Runtime
43 Runtime Type Checks
44 Parsing Equality & Comparison (Exercise)
45 Parsing Equality & Comparison Operators
46 Exponent Associativity
47 Exponent & Unary Minus Precedence
48 Logical And & Logical Or
49 Short-Circuit Evaluation
50 Testing Expressions
51 REPL
52 Alphabets, Languages, & Grammars
53 Chomsky Grammar Hierarchy
54 A Program as a List of Statements
55 Parsing Print Statements
56 Interpreting Print Statements
57 PrintLn Statements (Exercise)
58 PrintLn Statements & Escape Chars
59 If Statements
60 Identifiers & Assignments
61 Program State & Memory
62 The Environment Class
63 Environment Load & Store (Exercise)
64 Global & Local Variables
65 While Statement (Exercise)
66 While Statements
67 For Statements
68 Stringifying Booleans & Integers
69 Mandelbrot Set (Exercise)
70 Mandelbrot Set Script in Pinky
71 Compiler-Compilers
72 Functions in Pinky
73 Function Model
74 Parsing Function Declaration
75 Parsing Function Call
76 Interpreting Function Declaration
77 Interpreting Function Call
78 Expressions as Statements?
79 Max. Number of Params (Exercise)
80 Max. Number of Params
81 Parsing Return Statements
82 Interpreting Return Statements
83 Fixing Params as Local Variables
84 Local Variables & Shadowing
85 Dragon Curve
86 Simplified Cosine & Sine Functions
87 Code Generation & VMs
88 Example of Stack Instructions
89 Adding Classes for Compiler & VM
90 Emitting Push Instructions
91 Emitting BinOp Instructions
92 Exercise: Formatting our Code
93 Formatting our Instructions
94 Emitting UnOp Instructions
95 Step by Step Stack Execution
96 VM Execution
97 VM Expression Evaluation
98 VM Comparison Instructions
99 Generating Code for If Statements
100 Generating Then & Else Labels
101 VM Jumps & Branches
102 String Concat Instruction?
103 Global Memory Load & Store
104 Coding Globals Load & Store
105 Scope Depth
106 Starting & Ending Blocks
107 Local Variables & Stack Slots
108 Local Variables Code Generation
109 Local Variables at Runtime
110 Storing Globals by Slot Number
111 Program Symbols & Debug Info
112 Exercise: While Code Generation
113 Generating Code for While Statements
114 Register vs Stack VMs
115 Register-based Bytecode
116 CPython Bytecode Disassembly
117 Search Locals in Reverse Order
118 Function Code Generation
119 Activation Frames
120 Function Symbol Table
121 Compiling Function Declarations
122 Implementing JSR & RTS Instructions
123 Exercise: Function Parameters
124 Validating Function Arity & Arguments
125 Frame Pointer Offsets
126 Return Statements
127 Removing Inactive Frame Slots
128 Type Systems
129 Type Annotations
130 Shunting Yard for Simple Expressions
131 Exercise: Shunting Yard Evaluation
132 A Simple Shunting Yard Implementation
133 Shunting Yard & Parentheses
134 Shunting Yard & Right-Associativity
135 Pratt Parser
136 NUD, LED, & Binding Powers
137 Example Pratt Parsing Expression
138 Pratt Code (Without Precedence)
139 Pratt Code (Precedence & Parentheses)
140 Pratt Code (Right Associativity)
141 Pratt Code (Prefix Unary Minus)
142 Parsing Expression Grammar
143 Using a PEG Library
144 Optimizations & Transformations
145 Constant Folding & Propagation
146 Algebraic Simplifications
147 Dead Code Elimination
148 Loop Unrolling & Inlining
149 Branch Prediction & Vectorization
150 Tail Call & Peephole Optimization
151 LLVM IR
152 Function Definition in LLVM IR
153 Using Clang to Visualize LLVM IR
154 Integer & Float LLVM Instructions
155 SSA Form & Phi Function
156 LLVM Language Reference Manual
157 LLVM Load & Store Instructions
158 Installing Numba’s llvmlite
159 Adding a Module to LLVM
160 Adding a Function to LLVM
161 Loading & Storing Variables to LLVM
162 Calling External C Functions in LLVM
163 Emit LLVM IR for a Subset of Pinky
164 Visiting AST Nodes & Emitting LLVM IR
165 Emitting LLVM IR fadd Instruction
166 Emitting LLVM IR BinOps & UnOps
167 Compiling External C Print Functions
168 LLVM IR Assignments
169 Emitting LLVM IR for If Statements
170 Emitting LLVM IR for While Statements
171 Conclusion & Next Steps
Resolve the captcha to access the links!