WEBVTT 1 00:00:00.120 --> 00:00:02.799 You know, there was a time, not even the long ago, 2 00:00:02.799 --> 00:00:06.000 in the grand scheme of things, when writing assembly language 3 00:00:06.000 --> 00:00:10.160 by hand was considered this ultimate badge of honor for 4 00:00:10.199 --> 00:00:10.800 a programmer. 5 00:00:10.880 --> 00:00:14.119 Oh yeah, absolutely. The real hardcore engineers, right. 6 00:00:14.119 --> 00:00:17.960 And software engineers genuinely believed that a piece of software, 7 00:00:18.160 --> 00:00:23.120 you know, automatically generating machine code could never ever beat 8 00:00:23.199 --> 00:00:26.760 a skilled human who is just manually optimizing those memory 9 00:00:26.800 --> 00:00:28.359 registers and CPU cycles. 10 00:00:28.480 --> 00:00:30.199 Which makes sense for the time, I mean, they were 11 00:00:30.239 --> 00:00:31.879 working closer to the metal exactly. 12 00:00:32.240 --> 00:00:36.000 But fast forward to today, and modern compilers routinely generate 13 00:00:36.200 --> 00:00:40.079 highly optimized machine code that just completely blows handwritten assembly 14 00:00:40.119 --> 00:00:43.119 out of the water. Like we reached a point where 15 00:00:43.159 --> 00:00:45.960 the machine became vastly better at writing machine code than 16 00:00:45.960 --> 00:00:46.280 we are. 17 00:00:46.600 --> 00:00:49.759 The paradigm just shifted completely. I mean, efficiency used to 18 00:00:49.799 --> 00:00:53.920 be the primary argument against using high level languages early on. 19 00:00:54.039 --> 00:00:56.399 The fear was really that adding all these layers of 20 00:00:56.439 --> 00:00:59.840 abstraction between the programmer and the hardware would just result 21 00:00:59.880 --> 00:01:03.240 in bloated, sluggish execution. 22 00:01:02.960 --> 00:01:05.359 Right because you're adding middlemen exactly. 23 00:01:05.480 --> 00:01:08.920 But compiler technology along with it, just the sheer complexity 24 00:01:08.920 --> 00:01:13.799 of modern process or architectures advanced so aggressively. Humans can 25 00:01:13.840 --> 00:01:16.760 no longer keep the entire dependency graph and the cash 26 00:01:16.799 --> 00:01:20.040 locality and all the pipelining optimizations in their heads all 27 00:01:20.079 --> 00:01:22.879 at once. But you know, the compiler can. 28 00:01:23.280 --> 00:01:27.760 Welcome today's deep dive, we are unpacking the incredibly complex, 29 00:01:28.239 --> 00:01:33.599 highly mathematical translation pipeline that makes all of modern software possible. 30 00:01:33.920 --> 00:01:36.200 We're talking about the black box of compilers. 31 00:01:36.280 --> 00:01:38.439 It's a fascinating topic, it really is. 32 00:01:38.400 --> 00:01:40.280 And we're drawing from the concepts laid out in a 33 00:01:40.280 --> 00:01:43.159 really great textbook. It's called a Practical Approach to Compiler 34 00:01:43.200 --> 00:01:46.200 Construction by Des Watson, and the mission here for you 35 00:01:46.239 --> 00:01:50.319 listening is pretty straightforward. Understanding this hidden translation process is 36 00:01:50.400 --> 00:01:52.920 basically a shortcut to becoming a better problem solver and 37 00:01:52.959 --> 00:01:55.040 just a much more informed tech user overall. 38 00:01:55.120 --> 00:01:56.359 Yeah, because it strips away the. 39 00:01:56.280 --> 00:01:59.359 Mystery exactly, Because you know, when you understand how your 40 00:01:59.439 --> 00:02:02.760 human read code is structurally torn apart and then synthesized 41 00:02:02.760 --> 00:02:06.560 into native hardware instructions, you stop treating your tools like magic. 42 00:02:07.040 --> 00:02:10.319 You literally type words on a screen and somehow a 43 00:02:10.400 --> 00:02:14.400 processor routes electrons to execute your commands. Okay, so let's 44 00:02:14.439 --> 00:02:14.919 unpack this. 45 00:02:15.240 --> 00:02:19.280 Well, the compiler is essentially the fundamental bridge between abstract 46 00:02:19.439 --> 00:02:24.280 human thought and physical hardware execution. And to understand why 47 00:02:24.319 --> 00:02:27.000 that bridge is even necessary, we kind of have to 48 00:02:27.000 --> 00:02:29.400 look at the limitations of the nineteen forties, the. 49 00:02:29.400 --> 00:02:32.319 Dark ages of coding very much so. 50 00:02:32.400 --> 00:02:35.840 Programming back then literally meant writing raw machine code. It 51 00:02:35.879 --> 00:02:39.039 was an incredibly slow, highly error prone. 52 00:02:38.680 --> 00:02:41.199 Process because you were basically speaking binary right. 53 00:02:41.120 --> 00:02:44.159 Essentially, Yeah, you were forced to think exactly like the 54 00:02:44.199 --> 00:02:47.120 specific hardware architecture you were operating on. You were tracking 55 00:02:47.199 --> 00:02:49.439 individual memory locations completely manually. 56 00:02:49.680 --> 00:02:53.240 And then assembly languages came along and provided a slight buffer, 57 00:02:53.639 --> 00:02:56.680 you know, by introducing symbolic names instead of just raw numbers, 58 00:02:56.800 --> 00:02:59.479 but you were still fundamentally tied to whatever the hardware's 59 00:02:59.520 --> 00:03:00.000 architecture was. 60 00:03:00.639 --> 00:03:03.039 Right, if you wrote it for one machine, it lived 61 00:03:03.039 --> 00:03:06.159 on that machine. The real seismic shift happened in the 62 00:03:06.199 --> 00:03:10.319 nineteen fifties with the birth of high level languages. 63 00:03:09.879 --> 00:03:10.879 Like Fortran and Cobol. 64 00:03:10.960 --> 00:03:15.000 Right exactly, Suddenly you had Fortran, which was designed specifically 65 00:03:15.039 --> 00:03:19.719 for complex numerical mathematics, and then kobol, which was engineered 66 00:03:19.719 --> 00:03:21.000 for business data processing. 67 00:03:21.439 --> 00:03:24.039 So it became about the domain, not the hardware. 68 00:03:24.120 --> 00:03:28.039 Precisely, those high level languages introduced just a massive leap 69 00:03:28.080 --> 00:03:33.039 in abstraction. You were no longer micromanaging the hardware's exact state. 70 00:03:33.439 --> 00:03:35.680 You could focus entirely on the logic of the problem 71 00:03:35.759 --> 00:03:36.879 you were actually trying to solve. 72 00:03:37.080 --> 00:03:40.240 It kind of reminds me of ordering food at a restaurant. 73 00:03:40.599 --> 00:03:42.000 Okay, I like where this is going. 74 00:03:42.120 --> 00:03:44.800 Well, think about it. Using a high level language is 75 00:03:44.840 --> 00:03:47.240 like just sitting down and asking the waiter for a burger. 76 00:03:47.520 --> 00:03:50.240 That's the abstraction, right. You don't march into the kitchen 77 00:03:50.240 --> 00:03:53.000 and tell the chef exactly what temperature the grill needs 78 00:03:53.039 --> 00:03:55.919 to be and exactly what angle to slice the tomatoes at. 79 00:03:56.039 --> 00:03:58.280 That would be writing machine code. You just want the burger. 80 00:03:58.520 --> 00:04:01.479 That's actually a perfect analogy, and because you aren't in 81 00:04:01.520 --> 00:04:05.479 the kitchen, you get vastly better readability, drastically easier debugging, 82 00:04:05.840 --> 00:04:09.680 and crucially you get portability. You can take that same burger, 83 00:04:09.840 --> 00:04:12.560 order your source code, and run it in different kitchens, 84 00:04:12.759 --> 00:04:15.639 provided you have a translator or a compiler for that 85 00:04:15.680 --> 00:04:16.600 specific kitchen. 86 00:04:16.839 --> 00:04:21.600 But the downside originally anyway, was that perceived loss of control, 87 00:04:22.120 --> 00:04:24.519 like you couldn't easily go in and check a specific 88 00:04:24.560 --> 00:04:28.160 device status location or manipulate a raw memory address with 89 00:04:28.199 --> 00:04:29.480 the same freedom if you needed to. 90 00:04:29.759 --> 00:04:32.639 Yeah, that was the big fear. But as we established earlier, 91 00:04:32.639 --> 00:04:36.800 compiler optimization essentially rendered that concern totally obsolete for the 92 00:04:36.879 --> 00:04:39.680 vast majority of use cases. There is actually this golden 93 00:04:39.759 --> 00:04:42.079 rule mentioned in Watson's book, which is there is no 94 00:04:42.199 --> 00:04:44.639 need to optimize if the code is already fast enough. 95 00:04:44.720 --> 00:04:47.879 That makes total sense. I mean, developer time became significantly 96 00:04:47.879 --> 00:04:50.519 more expensive than CPU time exactly. 97 00:04:51.040 --> 00:04:54.720 The abstraction of a high level language optimizes for human 98 00:04:54.800 --> 00:04:58.600 problem solving speed if the resulting machine code meets the 99 00:04:58.600 --> 00:05:01.839 performance requirements of the app. Manually shaving off a few 100 00:05:01.879 --> 00:05:05.920 microseconds is just an irrational allocation of your engineering resources. 101 00:05:06.360 --> 00:05:08.639 So okay, if we are ordering the burger in this 102 00:05:08.800 --> 00:05:11.839 human readable format, how does the kitchen actually know what 103 00:05:11.920 --> 00:05:15.120 to do? The compiler's job is to translate that into 104 00:05:15.160 --> 00:05:18.519 specific hardware instructions. But it doesn't do it all at once, right, No. 105 00:05:18.639 --> 00:05:22.199 Not at all. Doesn't execute that translation in one massive, 106 00:05:22.319 --> 00:05:26.319 monolithic step. To manage the immense complexity of parsing all 107 00:05:26.360 --> 00:05:30.680 that syntax and generating native instructions, traditional compilers are structurally 108 00:05:30.680 --> 00:05:33.360 split into two very distinct phases, the front end and 109 00:05:33.399 --> 00:05:36.160 the back end. Exactly. The front end is entirely focused 110 00:05:36.199 --> 00:05:39.199 on analysis. It basically reads the source code you wrote, 111 00:05:39.279 --> 00:05:42.759 validates its structure, and translates it into what's called an 112 00:05:42.800 --> 00:05:44.759 intermediate representation or IR. 113 00:05:45.160 --> 00:05:47.160 So it's not even compiling to machine code yet. 114 00:05:47.240 --> 00:05:50.040 Yeah, not even close. The IR is a completely machine 115 00:05:50.040 --> 00:05:53.800 independent format. The front end just analyzes what the code 116 00:05:53.839 --> 00:05:58.160 logically means, entirely decoupled from the specific processor it's eventually 117 00:05:58.160 --> 00:05:58.720 going to run on. 118 00:05:58.839 --> 00:06:02.279 Okay, so once that intermedia representation is generated, then the 119 00:06:02.319 --> 00:06:03.439 back end takes over, right. 120 00:06:03.439 --> 00:06:06.120 The back end handles the synthesis. It takes that generic 121 00:06:06.199 --> 00:06:12.120 IR and synthesizes the highly optimized architecture specific machine code. 122 00:06:11.839 --> 00:06:15.120 Whether that's like an I eighty six Intel processor on 123 00:06:15.160 --> 00:06:18.680 a desktop, or an ARM chip and a smartphone. 124 00:06:18.240 --> 00:06:21.279 Or a specialized embedded system in a car. And this 125 00:06:21.360 --> 00:06:25.720 separation is a brilliant architectural decision because it solves the 126 00:06:25.759 --> 00:06:27.040 scaling problem. 127 00:06:26.720 --> 00:06:29.480 Oh right, the multiple languages problem, because if you have 128 00:06:29.639 --> 00:06:34.120 say ten programming languages and ten different processor architectures, a 129 00:06:34.199 --> 00:06:38.199 monolithic design would require writing one hundred entirely separate. 130 00:06:37.839 --> 00:06:41.199 Compilers exactly ten times ten, but with a separated front 131 00:06:41.279 --> 00:06:43.720 end and back end, you only write ten front ends 132 00:06:43.839 --> 00:06:46.720 to translate the ten languages into that shared IR, and 133 00:06:46.759 --> 00:06:48.800 then you write ten back ends to translate the IR 134 00:06:48.839 --> 00:06:50.600 into the ten hardware architectures. 135 00:06:50.680 --> 00:06:53.560 So you reduce the workload from ten times ten to 136 00:06:53.639 --> 00:06:56.600 ten plus ten one hundred down to twenty. That is 137 00:06:56.680 --> 00:06:57.879 incredibly efficient. 138 00:06:58.040 --> 00:07:01.040 It's massive. If a manufactured or releases a brand new 139 00:07:01.079 --> 00:07:04.199 silicon architecture tomorrow, they only have to write a single 140 00:07:04.240 --> 00:07:08.079 new back end and they instantly get support for ccplus 141 00:07:08.120 --> 00:07:10.680 plus Java and any other language that already has a 142 00:07:10.720 --> 00:07:12.920 front end producing that standard IR. 143 00:07:13.279 --> 00:07:16.480 That is so smart. But wait, we should also touch 144 00:07:16.519 --> 00:07:20.680 on the alternative route here, right, because not everything precompiles 145 00:07:20.759 --> 00:07:23.800 directly to machine code like that. What about interpreters and 146 00:07:23.920 --> 00:07:27.800 virtual machines like the Java virtual machine, Right. 147 00:07:27.720 --> 00:07:30.360 That's a very important distinction. Instead of a back end 148 00:07:30.399 --> 00:07:34.120 synthesizing native hardware machine code ahead of time, a compiler 149 00:07:34.160 --> 00:07:35.800 can output a sort of virtual. 150 00:07:35.480 --> 00:07:37.560 Machine code bycode, basically. 151 00:07:37.279 --> 00:07:41.240 Exactly bycode the Java compiler stops at bytcode. Then a 152 00:07:41.279 --> 00:07:44.279 totally separate piece of software, which is the interpreter, runs 153 00:07:44.279 --> 00:07:46.879 on the host machine and translates that bycode into native 154 00:07:46.879 --> 00:07:50.120 instructions on the fly as the program is actually executing. 155 00:07:50.399 --> 00:07:53.879 But wait, if interpretation is inherently slower because it has 156 00:07:53.920 --> 00:07:56.480 to read and translate the code on the fly at runtime, 157 00:07:57.120 --> 00:08:00.759 why do so many modern languages use virtual machines, why 158 00:08:00.800 --> 00:08:01.920 take that performance hit? 159 00:08:02.279 --> 00:08:05.560 Well, if we connect this to the bigger picture, that 160 00:08:05.759 --> 00:08:08.959 slight hit in runtime efficiency is a deliberate trade off, 161 00:08:09.720 --> 00:08:14.319 and it's for two major advantages. The first is ultimate portability. 162 00:08:14.720 --> 00:08:17.480 You compile the code once and it will execute on 163 00:08:17.600 --> 00:08:20.680 literally any device running the virtual machine, regardless of the 164 00:08:20.759 --> 00:08:25.319 underlying hardware. Run anywhere, exactly, run anywhere. And the second advantage, 165 00:08:25.319 --> 00:08:29.319 which is often more critical today, is safety. The virtual 166 00:08:29.360 --> 00:08:32.120 machine acts as a highly controlled sandbox, oh. 167 00:08:32.120 --> 00:08:34.600 Because it's interpreting the code dynamically, so it can catch 168 00:08:34.600 --> 00:08:35.600 things precisely. 169 00:08:35.960 --> 00:08:39.440 It can enforce runtime constraints that a raw native binary 170 00:08:39.559 --> 00:08:42.600 just can't. If a pre compiled native executable tries to 171 00:08:42.639 --> 00:08:45.799 access a restricted memory block, the hardware might just attempt 172 00:08:45.799 --> 00:08:48.080 the operation and cause a catastrophic. 173 00:08:47.519 --> 00:08:49.120 System faull a total crash. 174 00:08:49.279 --> 00:08:52.480 Right, But the interpreter monitors the virtual machine code as 175 00:08:52.480 --> 00:08:56.559 it runs, it performs bounds checking and validates operations before 176 00:08:56.600 --> 00:08:58.679 they ever physically touch the hardware, so. 177 00:08:58.600 --> 00:09:02.840 It creates a protective buffer against like militious instructions are 178 00:09:02.879 --> 00:09:04.200 really bad memory leaks. 179 00:09:04.279 --> 00:09:04.919 Yeah exactly. 180 00:09:04.960 --> 00:09:07.279 Okay, that makes sense, But let's rewind back to the 181 00:09:07.279 --> 00:09:10.799 main compilation pipeline for a second, because before the front 182 00:09:10.919 --> 00:09:14.080 end can even generate that intermediate representation we talked about, 183 00:09:14.480 --> 00:09:17.000 it has to parse the raw text you typed. Like 184 00:09:17.240 --> 00:09:21.120 computers are notoriously terrible at guessing what humans mean. 185 00:09:21.240 --> 00:09:25.679 They have zero intuition, absolutely zero, which is why compiling 186 00:09:25.759 --> 00:09:30.559 requires an incredibly strict formalization of the language. Compilers operate 187 00:09:30.639 --> 00:09:33.320 on absolute mathematical rigidity. 188 00:09:33.399 --> 00:09:36.559 So a programming language has to strictly define its syntax, 189 00:09:36.600 --> 00:09:39.120 which is the structure, and its semantics, which is the 190 00:09:39.159 --> 00:09:41.159 actual meaning of those structures, right. 191 00:09:41.480 --> 00:09:44.120 And to define the syntax, language designers use what are 192 00:09:44.120 --> 00:09:46.679 called metal languages. The most common one is bacis nar 193 00:09:46.799 --> 00:09:49.799 form or BNF and its extended variants. 194 00:09:49.879 --> 00:09:51.960 And this is where it gets really interesting, because these 195 00:09:51.960 --> 00:09:55.320 metal languages mapp directly to the linguistic frameworks established by 196 00:09:55.320 --> 00:09:57.440 Noam Chomsky back in the nineteen fifties. 197 00:09:57.759 --> 00:10:02.440 Yes, no M Chomsky. He classified grammars into a strict hierarchy, 198 00:10:02.960 --> 00:10:06.080 and for the core structural analysis of a programming language, 199 00:10:06.399 --> 00:10:09.200 compilers rely heavily on Chomsky Type two. 200 00:10:09.120 --> 00:10:11.440 Grammars, which are known as context free grammar. 201 00:10:11.639 --> 00:10:14.720 Exactly, context free grammars and the implementation of a context 202 00:10:14.720 --> 00:10:17.759 free grammar is what allows the compiler to resolve structural 203 00:10:17.840 --> 00:10:19.080 hierarchy natively. 204 00:10:19.360 --> 00:10:21.360 I love this part. Let's look at the example from 205 00:10:21.399 --> 00:10:25.720 the source material. Consider a really simple mathematical expression in code, 206 00:10:25.759 --> 00:10:27.360 like one plus two times three. 207 00:10:27.480 --> 00:10:29.039 Okay, one plus two times three. Right. 208 00:10:29.360 --> 00:10:32.879 The compiler doesn't have some external, you know, math module. 209 00:10:32.960 --> 00:10:36.200 It consults to remember the order of operations. It's not 210 00:10:36.240 --> 00:10:39.759 looking up a textbook. The precedence of multiplication over edition 211 00:10:40.039 --> 00:10:43.919 is literally structurally hard coded into the grammar rules of 212 00:10:43.960 --> 00:10:44.799 the language itself. 213 00:10:44.879 --> 00:10:46.120 It's baked right in. Yeah. 214 00:10:46.519 --> 00:10:49.720 It's like how English grammar tells us that adjectives generally 215 00:10:49.720 --> 00:10:52.759 come before nouns. The structure dictates the meaning. 216 00:10:52.799 --> 00:10:56.120 Exactly when the parser reads that expression. It builds a 217 00:10:56.159 --> 00:11:00.440 literal data structure in memory call a parse tree. Because 218 00:11:00.480 --> 00:11:03.120 the BNF rules for multiplication are defined at a deeper 219 00:11:03.159 --> 00:11:06.600 nesting level than the rules for addition, The parser inherently 220 00:11:06.639 --> 00:11:09.879 groups the two times three into a distinct child branch 221 00:11:09.919 --> 00:11:11.000 of the tree, and then. 222 00:11:10.919 --> 00:11:13.960 The addition operation sits at the parent node, basically waiting 223 00:11:13.960 --> 00:11:15.879 for that child branch to finish its math. 224 00:11:16.159 --> 00:11:19.360 Right. The parser cannot evaluate the addition until the multiplication 225 00:11:19.440 --> 00:11:23.080 node resolves. It physically enforces the order of operations through 226 00:11:23.120 --> 00:11:24.480 the design of the data structure. 227 00:11:24.720 --> 00:11:27.399 That is so cool, So how does it build that tree? 228 00:11:27.759 --> 00:11:31.399 Well, parsers construct this tree using one of two primary strategies, 229 00:11:31.840 --> 00:11:34.919 top down or bottom up. A top down parser starts 230 00:11:34.919 --> 00:11:36.720 at the very root of the tree, which is the 231 00:11:36.759 --> 00:11:39.759 axiom of a valid program, and it attempts to expand 232 00:11:39.759 --> 00:11:41.399 the grammar rules downward. 233 00:11:41.240 --> 00:11:44.639 Substituting variables until it perfectly matches the actual sequence of 234 00:11:44.720 --> 00:11:46.519 characters in the source code exactly. 235 00:11:46.679 --> 00:11:48.840 And then a bottom up parser approaches it from the 236 00:11:48.879 --> 00:11:52.320 exact opposite direction. It reads the raw sequence in the code, 237 00:11:52.600 --> 00:11:56.679 groups small segments into basic grammar rules, and collapses them upward. 238 00:11:56.879 --> 00:12:00.679 So it basically shifts tokens onto a stack and reduces 239 00:12:00.720 --> 00:12:03.759 them into larger and larger grammatical components. 240 00:12:03.279 --> 00:12:06.519 Right until the entire stack collapses into that single root 241 00:12:06.600 --> 00:12:09.200 node of a valid program, and if it fails to 242 00:12:09.279 --> 00:12:11.759 reach that route, well, it throws the syntax er. 243 00:12:12.000 --> 00:12:14.799 But wait, how does the parser even know that one, two, 244 00:12:14.840 --> 00:12:16.679 three is in number and the plus sign is an 245 00:12:16.720 --> 00:12:19.919 operator because it doesn't read the source code character by character. 246 00:12:20.080 --> 00:12:23.159 Err right, it definitely doesn't. If a context free grammar 247 00:12:23.200 --> 00:12:27.559 parser had to evaluate every individual space and letter and 248 00:12:27.639 --> 00:12:30.679 digit just to determine where a word starts and ends, 249 00:12:31.120 --> 00:12:33.440 the state management would just be massively inefficient. 250 00:12:33.559 --> 00:12:36.120 Yeah, the parse tree would be overwhelmingly huge just to 251 00:12:36.120 --> 00:12:39.240 figure out how to spell a single variable name exactly. 252 00:12:39.639 --> 00:12:42.600 So to solve that, the front end outsources the character 253 00:12:42.679 --> 00:12:46.679 level reading to its very first subphase. This is lexical analysis. 254 00:12:46.799 --> 00:12:49.600 The lexical analyzer. I kind of think of it as 255 00:12:49.639 --> 00:12:53.000 the bouncer at a clubdoor. The bouncer, yeah, like it 256 00:12:53.039 --> 00:12:55.519 acts as a filter between the raw source text and 257 00:12:55.559 --> 00:12:59.480 the parser. The bouncer consumes the raw character stream, checks IDs, 258 00:12:59.639 --> 00:13:03.120 meaning it groups letters into words. It throws out the trash, 259 00:13:03.440 --> 00:13:05.559 which would be the comments in the useless white space, 260 00:13:06.080 --> 00:13:09.000 and it only lets the VIP tokens into the club 261 00:13:09.080 --> 00:13:10.480 to see the syntax parser. 262 00:13:10.639 --> 00:13:12.759 That's a great way to visualize it. Let's take a 263 00:13:12.759 --> 00:13:16.960 standard loop declaration like while open bracket eye less than 264 00:13:17.120 --> 00:13:20.720 or equal to one hundred. The lexical analyzer iterates over 265 00:13:20.759 --> 00:13:25.320 the raw ASKI values. It identifies the sequence whil e, 266 00:13:25.720 --> 00:13:29.799 and it emits a single categorized token, the keyword while right. 267 00:13:29.879 --> 00:13:32.120 It doesn't pass five letters to the parser. It passes 268 00:13:32.200 --> 00:13:33.360 one token exactly. 269 00:13:33.399 --> 00:13:36.120 Then it reads the open parenthesis and emits a bracket token. 270 00:13:36.480 --> 00:13:39.559 It recognizes the eye and emits an identifier token. 271 00:13:39.679 --> 00:13:42.200 And it also has to handle multi character operators right Like, 272 00:13:42.240 --> 00:13:44.720 when it sees the less than sign, it doesn't instantly 273 00:13:44.759 --> 00:13:46.639 just stit out an operator token good point. 274 00:13:46.639 --> 00:13:48.639 No, it has to check the next character, seeing the 275 00:13:48.679 --> 00:13:51.120 equal sign right after it, it groups them together into 276 00:13:51.120 --> 00:13:54.919 a single logical less than or equal to operator token, 277 00:13:55.360 --> 00:13:57.879 and finally it groups the one zero zero into an 278 00:13:57.879 --> 00:13:58.679 integer token. 279 00:13:58.960 --> 00:14:02.399 So by the time this stream reaches the VIP area 280 00:14:02.480 --> 00:14:06.440 the syntax parser, the parser just sees a clean sequence 281 00:14:06.480 --> 00:14:10.080 of five pre defined structural components. It never has to 282 00:14:10.080 --> 00:14:12.639 worry about the spelling or if there were extra spaces. 283 00:14:12.840 --> 00:14:15.960 But this raises an important question right, because spacing can 284 00:14:16.000 --> 00:14:21.720 actually introduce significant complexity for the lexical analyzer itself, particularly 285 00:14:21.720 --> 00:14:23.360 regarding what we call look ahead issues. 286 00:14:23.480 --> 00:14:24.559 Look ahead issues. 287 00:14:24.720 --> 00:14:28.799 Yeah, The analyzer frequently has to buffer characters and read 288 00:14:28.840 --> 00:14:31.759 ahead of its current position just to determine the correct 289 00:14:31.759 --> 00:14:34.360 token category. Like if it reads the digits one, two, three, four, 290 00:14:34.759 --> 00:14:36.960 it cannot immediately emit an integer token. 291 00:14:37.080 --> 00:14:39.279 It must look ahead because if the next character is 292 00:14:39.320 --> 00:14:41.879 a decimal point, it realizes, oh wait, I'm building a 293 00:14:41.879 --> 00:14:43.240 floating point number exactly. 294 00:14:43.399 --> 00:14:46.759 Have to continue buffering. Yeah, and early language design actually 295 00:14:46.799 --> 00:14:49.840 produced some notoriously difficult look ahead scenarios. 296 00:14:49.879 --> 00:14:52.120 Oh, this brings up the four tren horror story from 297 00:14:52.159 --> 00:14:52.480 the book. 298 00:14:52.559 --> 00:14:55.159 Yes, four trend is the classic example here. Yeah, because 299 00:14:55.200 --> 00:14:58.600 early specifications of FORO tran dictated that spaces had literally 300 00:14:58.759 --> 00:15:03.200 zero syntactic meaning they were completely ignored by the compiler, which. 301 00:15:03.000 --> 00:15:06.759 Sounds fine until you realize it forces the lexical analyzer 302 00:15:06.799 --> 00:15:08.559 into a highly ambiguous state. 303 00:15:08.639 --> 00:15:12.360 A very dangerous state. Consider a four tran loop initialization 304 00:15:12.519 --> 00:15:17.039 looks like this, do space five space i equals one 305 00:15:17.200 --> 00:15:20.399 comma ten. The intent here is to loop the variable 306 00:15:20.440 --> 00:15:21.559 I from one to ten. 307 00:15:21.639 --> 00:15:24.440 Right, So the tokens should be the keyword. Do the 308 00:15:24.519 --> 00:15:27.360 label five, the variable i the assignment operator, and the 309 00:15:27.480 --> 00:15:29.600 range values one in ten exactly? 310 00:15:30.080 --> 00:15:33.039 But what if the programmer accidentally types a period instead 311 00:15:33.080 --> 00:15:35.399 of a comma. Oh no, yeah, so it becomes do 312 00:15:35.600 --> 00:15:38.840 five I equals one point ten. The entire token structure just. 313 00:15:38.799 --> 00:15:40.759 Collapses because spaces are ignored. 314 00:15:40.960 --> 00:15:44.200 Right, because spaces are completely ignored, The lexical analyzer reads 315 00:15:44.279 --> 00:15:46.279 right past the do, past the five, and past the i. 316 00:15:46.720 --> 00:15:48.519 It hits the equal sign and then sees the float 317 00:15:48.519 --> 00:15:49.080 one point. 318 00:15:48.919 --> 00:15:51.200 Ten, so it realizes this is not a loop declaration 319 00:15:51.279 --> 00:15:52.080 at all, exactly. 320 00:15:52.159 --> 00:15:54.480 It realizes it's an assignment, So it squishes those first 321 00:15:54.519 --> 00:15:57.960 characters all together and categorizes do five I as a single, 322 00:15:58.159 --> 00:16:01.480 brand new variable identifier and just assigns it the floating 323 00:16:01.519 --> 00:16:02.679 point value of one point ten. 324 00:16:02.879 --> 00:16:06.279 That is wild, a single typo of a period instead 325 00:16:06.320 --> 00:16:10.240 of a comma completely changes the grammar of the entire line. 326 00:16:10.279 --> 00:16:13.200 The lexical analyzer has to look way ahead in the 327 00:16:13.279 --> 00:16:16.480 character stream, scanning all the way down to that comma 328 00:16:16.600 --> 00:16:20.360 or period before it can definitively branch its logic and 329 00:16:20.440 --> 00:16:24.080 categorize that initial doo as either a reserved keyword for 330 00:16:24.120 --> 00:16:27.200 a loop or just the start of a variable name. 331 00:16:27.279 --> 00:16:30.559 Which perfectly illustrates why the lexical analyzer is kept strictly 332 00:16:30.600 --> 00:16:35.240 separate from the syntax parser modularity and efficiency. By absorbing 333 00:16:35.240 --> 00:16:38.000 all that messy complexity of character buffering and white space 334 00:16:38.000 --> 00:16:41.519 stripping and look ahead resolution, the lexical analyzer frees up 335 00:16:41.519 --> 00:16:44.799 the parser to operate strictly on clean, high level grammar. 336 00:16:45.039 --> 00:16:47.840 So if this lexical bouncer has to be incredibly fast 337 00:16:47.879 --> 00:16:50.639 and efficient to process hundreds of thousands of raw characters, 338 00:16:50.919 --> 00:16:52.320 how do we actually build it. 339 00:16:52.559 --> 00:16:55.200 Well, we use the simplest, most restrictive grammar rule book 340 00:16:55.240 --> 00:16:57.000 available in the Chomsky hierarchy. 341 00:16:56.639 --> 00:16:57.639 Which is type three. 342 00:16:57.919 --> 00:17:00.919 Yes Chomsky Type three grammars better no too most programmers 343 00:17:00.960 --> 00:17:01.840 as regular. 344 00:17:01.519 --> 00:17:04.720 Expressions, AH rejects everyone's favorite, right. 345 00:17:05.039 --> 00:17:07.319 We use context free grammars the type two for the 346 00:17:07.359 --> 00:17:11.680 parser because the parser needs to understand nested recursive structures 347 00:17:12.200 --> 00:17:16.640 like math operations inside parentheses. But the lexical analyzer doesn't 348 00:17:16.640 --> 00:17:17.839 care about nesting at all. 349 00:17:18.000 --> 00:17:19.960 It just needs to know if a flat string of 350 00:17:20.039 --> 00:17:22.880 characters matches a specific pattern exactly. 351 00:17:23.480 --> 00:17:26.519 A regular expression is just a highly compact definition of 352 00:17:26.559 --> 00:17:29.440 a search pattern. You can define a valid identifier with 353 00:17:29.480 --> 00:17:32.039 a really simple rule like it must begin with a 354 00:17:32.119 --> 00:17:35.559 letter followed by zero or more letters or digits. 355 00:17:35.880 --> 00:17:38.400 But the real power of a regular expression isn't just 356 00:17:38.480 --> 00:17:41.720 the syntax of the pattern itself, right, it's how the 357 00:17:41.799 --> 00:17:44.279 compiler executes that pattern mathematically. 358 00:17:44.440 --> 00:17:48.200 Yes, any regular expression can be systematically transformed into a 359 00:17:48.240 --> 00:17:51.759 deterministic finite state machine or a transition diagram. 360 00:17:51.799 --> 00:17:52.920 Okay, break that down for us. 361 00:17:52.960 --> 00:17:56.519 Sure. The transition diagram basically operates through strict state progression. 362 00:17:56.960 --> 00:17:59.640 You initiate the machine at state one. You consume the 363 00:17:59.759 --> 00:18:02.519 very first character from the source stream. If that character 364 00:18:02.519 --> 00:18:06.119 satisfies the transition condition for your rejects pattern, the machine 365 00:18:06.119 --> 00:18:06.799 progresses to. 366 00:18:06.759 --> 00:18:09.200 State two, and then you consume the next character. 367 00:18:09.039 --> 00:18:12.680 Right, and the rules dictate the next state transition. Depending 368 00:18:12.720 --> 00:18:15.200 on the character, you might loop back to state one, 369 00:18:15.440 --> 00:18:17.240 you might stay in state two, or you might move 370 00:18:17.279 --> 00:18:18.160 forward to state three. 371 00:18:18.440 --> 00:18:21.680 And if the token string ends and the machine happens 372 00:18:21.720 --> 00:18:24.960 to be resting on what's called a designated accepting state, 373 00:18:25.440 --> 00:18:28.279 then the sequence is mathematically proven to be a valid 374 00:18:28.319 --> 00:18:30.240 token of that category exactly. 375 00:18:30.640 --> 00:18:33.640 And conversely, if it encounters an unexpected character and no 376 00:18:33.799 --> 00:18:36.839 valid transition exists for it, the machine just halts and 377 00:18:36.880 --> 00:18:38.079 throws a lexical error. 378 00:18:38.319 --> 00:18:42.039 And the architectural advantage of this deterministic finite state machine 379 00:18:42.079 --> 00:18:45.599 is that it guarantees linear efficiency big o EVN right, 380 00:18:45.640 --> 00:18:48.920 big O event because the machine never backtracks, it never 381 00:18:48.960 --> 00:18:52.440 second guesses its previous state. It consumes each character and 382 00:18:52.480 --> 00:18:56.000 the source code exactly once, executes its state transition, and 383 00:18:56.079 --> 00:18:58.400 moves forward. It's incredibly fast. 384 00:18:58.480 --> 00:19:01.640 It is the absolute fastest theoretical mechanism a computer can 385 00:19:01.759 --> 00:19:06.200 use to process sequential text and writing these state machines manually, 386 00:19:06.319 --> 00:19:09.480 like mapping out the transitions for every possible asse character 387 00:19:09.839 --> 00:19:14.279 would be a sprawling, unmaintainable mess of conditional logic. 388 00:19:14.400 --> 00:19:15.759 So nobody does that by hand. 389 00:19:16.079 --> 00:19:20.640 Oh, definitely not. Compiler engineers utilize software generator tools. You 390 00:19:20.720 --> 00:19:23.319 feed the tool a list of regular expressions that define 391 00:19:23.359 --> 00:19:26.799 your language as tokens, and the software automatically computes all 392 00:19:26.799 --> 00:19:30.240 the state transitions and generates the highly optimized C code 393 00:19:30.440 --> 00:19:32.359 representing that finite state machine. 394 00:19:32.680 --> 00:19:35.480 So what does this all mean for you listening right now? 395 00:19:36.279 --> 00:19:40.480 These algorithms, the regular expressions, the finite state machines. They 396 00:19:40.519 --> 00:19:43.799 aren't just for massive compiler projects at big tech companies. 397 00:19:44.160 --> 00:19:46.799 If you've ever used a find and replace function or 398 00:19:46.839 --> 00:19:49.599 scrape data from a document, you are using the exact 399 00:19:49.759 --> 00:19:52.839 same underlying computer science magic exactly. 400 00:19:53.359 --> 00:19:57.200 Learning how a compiler constructs these structures fundamentally alters how 401 00:19:57.240 --> 00:20:01.480