English | MP4 | AVC 1920×1080 | AAC 44KHz 2ch | 140 Lessons (23h 48m) | 4.37 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 Logical And & Logical Or
48 Short-Circuit Evaluation
49 Testing Expressions
50 REPL
51 Alphabets, Languages, & Grammars
52 Chomsky Grammar Hierarchy
53 A Program as a List of Statements
54 Parsing Print Statements
55 Interpreting Print Statements
56 PrintLn Statements (Exercise)
57 PrintLn Statements & Escape Chars
58 If Statements
59 Identifiers & Assignments
60 Program State & Memory
61 The Environment Class
62 Environment Load & Store (Exercise)
63 Global & Local Variables
64 While Statement (Exercise)
65 While Statements
66 For Statements
67 Stringifying Booleans & Integers
68 Mandelbrot Set (Exercise)
69 Mandelbrot Set Script in Pinky
70 Compiler-Compilers
71 Functions in Pinky
72 Function Model
73 Parsing Function Declaration
74 Parsing Function Call
75 Interpreting Function Declaration
76 Interpreting Function Call
77 Expressions as Statements?
78 Max. Number of Params (Exercise)
79 Max. Number of Params
80 Parsing Return Statements
81 Interpreting Return Statements
82 Fixing Params as Local Variables
83 Local Variables & Shadowing
84 Dragon Curve
85 Simplified Cosine & Sine Functions
86 Code Generation & VMs
87 Example of Stack Instructions
88 Adding Classes for Compiler & VM
89 Emitting Push Instructions
90 Emitting BinOp Instructions
91 Exercise: Formatting our Code
92 Formatting our Instructions
93 Emitting UnOp Instructions
94 Step by Step Stack Execution
95 VM Execution
96 VM Expression Evaluation
97 VM Comparison Instructions
98 Generating Code for If Statements
99 Generating Then & Else Labels
100 VM Jumps & Branches
101 String Concat Instruction?
102 Global Memory Load & Store
103 Coding Globals Load & Store
104 Scope Depth
105 Starting & Ending Blocks
106 Local Variables & Stack Slots
107 Local Variables Code Generation
108 Local Variables at Runtime
109 Storing Globals by Slot Number
110 Program Symbols & Debug Info
111 Exercise: While Code Generation
112 Generating Code for While Statements
113 Register vs Stack VMs
114 Register-based Bytecode
115 CPython Bytecode Disassembly
116 Search Locals in Reverse Order
117 Function Code Generation
118 Activation Frames
119 Function Symbol Table
120 Compiling Function Declarations
121 Implementing JSR & RTS Instructions
122 Exercise: Function Parameters
123 Validating Function Arity & Arguments
124 Frame Pointer Offsets
125 Return Statements
126 Removing Inactive Frame Slots
127 Type Systems
128 Type Annotations
129 Shunting Yard for Simple Expressions
130 Exercise: Shunting Yard Evaluation
131 A Simple Shunting Yard Implementation
132 Shunting Yard & Parentheses
133 Shunting Yard & Right-Associativity
134 Pratt Parser
135 NUD, LED, & Binding Powers
136 Example Pratt Parsing Expression
137 Pratt Code (Without Precedence)
138 Pratt Code (Precedence & Parentheses)
139 Pratt Code (Right Associativity)
140 Pratt Code (Prefix Unary Minus)
Resolve the captcha to access the links!