The Last Step Before Code Compiles

Added: 2026-05-25

[00:00:00]This video is sponsored by Let's Get Rusty.

[00:00:04]In the last video, we saw how a parser produces an abstract syntax tree. At this point, we know that the program conforms to the syntactic rules of the language, but that alone doesn't mean the program actually makes sense according to the semantics of the language. There is still a whole lot of things to check before we can say, "Yes, this program is actually correct." That is what semantic analysis is for, the last step in the analysis phase of a compiler. Hi, and welcome to Premature Abstraction. This is the fourth video of a series where you learn all about compilers, one of the oldest and still most important topics in computer science. The goal is that by the end, you'll even be able to write one yourself. So, please subscribe if you don't want to miss that. So, what kind of checks are we talking about? Let's start with a subtle one. When designing a grammar, we sometimes take shortcuts.

[00:00:51]We keep it simpler and accept some programs that are technically invalid because enforcing everything in the grammar alone would make it unnecessarily complicated. Semantic analysis is where we catch those. For example, a break statement should only appear inside a loop or a switch. The grammar usually allows break anywhere.

[00:01:08]Checking the context is the semantic analyzer's job. Similarly, when you call a function, the number of arguments you pass should match what the function expects. Again, the grammar doesn't usually enforce that. It just says, "A function call is an identifier followed by a list of expressions in parentheses." Or consider an assignment like 5 = x. The grammar typically just says, "An assignment is an expression followed by an equal sign followed by another expression." It doesn't distinguish between expressions you can assign to and expressions you can only read from. These are sometimes called L-values and R-values. The left side of an assignment has to be something like a variable or an array element, not a literal or a function call. Another major responsibility is checking that names are used correctly. In most languages, you have to declare a variable before you can use it. And in many, you also have to initialize it before you can read from it. These are two separate tags, by the way.

[00:01:59]A variable can be declared but not yet initialized, and using it in that state might be an error, or at least a warning. Some languages even allow redeclaring a variable in the same scope, which shadows the previous one.

[00:02:10]Others treat that as an error. This is where the symbol table that was started during lexing really comes [music] in handy. The semantic analyzer uses it to keep track of what has been declared and with what type.

[00:02:22]Closely related to declarations is the concept of scopes. A scope defines the region of the program where a name is visible. Most languages use block scoping. A variable declared inside a block is not visible outside of it.

[00:02:35]But the details can vary quite a bit.

[00:02:37]For example, Python has some famously unintuitive scoping rules. A variable assigned inside an if block is still visible after the block ends, because Python, for example, scopes to functions, not to blocks in general.

[00:02:48]That surprises a lot of people when coming from a C-like language. Scopes can also be nested, and when an inner scope declares a name that already exists in an outer scope, that's called shadowing. Some languages allow it freely, others emit a warning, and some forbid it entirely. The semantic analyzer has to track all of that correctly. In practice, this is often handled by giving the symbol table a stack-like structure. When the analyzer enters a new scope, it pushes a new frame. When it leaves, it pops it again.

[00:03:15]That way, lookups naturally find the innermost declaration first, and shadowed names are restored when their scope ends. Now, before we move on, let me take a moment to talk about this video's sponsor, Let's Get Rusty. If you're a developer, you've probably heard Rust mentioned a lot lately, and for good reason. Companies like AWS, Microsoft, and Google have been heavily investing in Rust for performance-and-safety-critical code.

[00:03:36]So, if you want to get paid to build fast, reliable software, whether that's back-end infrastructure, robotics, or even blockchain, Rust is a great language to have in your toolkit. Let's Get Rusty offers Rust training for individuals and teams, with a big focus on practical skills and helping people move into Rust roles. They've already had thousands of devs master Rust. The best part is that they've got a new cohort starting next month already and spots are limited. So, if you're curious, check out letsgetrusty.com/startwithabstraction or click the link in the pinned comment below this video.

[00:04:06]Now, we get to the big one, type checking. This is probably the most substantial part of semantic analysis.

[00:04:12]At its core, type checking means verifying that operations are applied to compatible types. The semantic analyzer checks, are the operands of an operator valid? You can add two numbers, but can you add two structs? Do the arguments in a function call match the parameter types? Does the return value of a function match its declared return type?

[00:04:30]And then there's the question of implicit type casts. Many languages automatically convert between certain types like widening an integer to a float. Others are very strict about this. The semantic analyzer needs to know what conversions are allowed and insert them where needed.

[00:04:45]An interesting question within type checking is, when are two types considered the same? There are two main schools of thought. The first one is name equivalence, also called nominal typing. Two types are the same only if they have the same name. So, even if two structs have exactly the same fields, they are different types if they have different names. Java and C++ work this way. The second is structural equivalence, also called structural typing. Here, two types are the same if they have the same structure, so the same fields with the same types. Some definitions also require the same order, but in practice most structurally typed languages like Go interfaces and TypeScript don't. But, both approaches have their quirks. With structural typing, things like recursive structs or array length can make equivalence checks surprisingly tricky. And what about type aliases? If you write type meters equals double, is the meters type exchangeable with double later? In some languages, yes, in others, no.

[00:05:40]Type systems can go much further than basic checking. Inheritance adds complexity because you need to verify that a subtype can be used where a supertype is expected, and it opens up a can of worms about type variance between composite types. Nullability is another dimension. Languages like Kotlin distinguish nullable from non-nullable types, and it supports smart casts where the compiler narrows the type after a null check. Other languages like Rust don't have null at all. Then there's type inference. In many modern languages, you don't have to write out every type explicitly. The compiler can figure out the type of a variable from the value assigned to it or deduce the return type of a function from its body.

[00:06:17]This is convenient as it almost gives the ergonomics of a dynamically typed language while still having type safety, but it means the semantic analyzer has to do significantly more work behind the scenes. Most languages also have generics, which adds yet another layer.

[00:06:30]When a function or a type is parameterized, the semantic analyzer has to verify that the type parameter is used consistently and that any constraints on it are satisfied.

[00:06:39]Combined with inheritance and variance, [music] this can make type checking surprisingly difficult. Some type systems are even undecidable in theory, meaning there are programs where the compiler could loop forever trying to check the types. One thing worth highlighting is how type checkers handle complex nested expressions. Consider a declaration like this. A naive approach would just evaluate each subexpression in isolation and report a mismatch at the end, but that's not very helpful. The naive type checker might look at this from the bottom up. It evaluates the array literal, finds mixed types, and reports something vague like "array contains incompatible types." That's technically correct but not very helpful. The problem is that it cannot know which of the two types is the correct one. A smarter approach would be to go top-down as well. The type checker sees that the array is declared as int and pushes that expectation onto every element of the array. Now, when it encounters three, it can say something much more useful like "the third element was expected to be an int because the array is declared as int but is a string." This technique is called prototyping. The expected type is pushed down into a subexpression before it's fully evaluated. The word prototype shows up in another context, too. In languages like C, you can declare a function's name and type signature before its full definition appears. This lets the compiler check calls to that function immediately and later verify that the actual definition matches. It's a different mechanism, but the underlying idea is similar. Register what you expect now and then verify it later.

[00:08:03]Semantic analysis also involves some control flow checks. A common one is whether every control path in a function returns a value. If a function is declared to return an integer, but one branch of an if statement doesn't have a return, that's an error. Well, at least in languages that require this. Python, for example, doesn't. It just returns none in this case. Rust also takes this idea even further. Blocks and control flow constructs are expressions that have a type. So, an if else isn't just checked for whether both branches return. They must return the same type.

[00:08:33]The same goes for match arms and even bare blocks. This means the type system and control flow analysis are deeply intertwined.

[00:08:41]Function overloading is another topic the semantic analyzer has to deal with.

[00:08:45]Some languages forbid it entirely.

[00:08:47]Others allow multiple functions with the same name as long as the parameter types differ. The semantic analyzer then has to figure out which version of the function is being called based on the argument types. In some languages, overload resolution only considers parameter types, but others, like Swift, also take the return type into account.

[00:09:05]And that makes things considerably more complicated because the compiler may need to check the surrounding context to figure out which overload was intended.

[00:09:12]In extreme cases, this requires multiple passes over the tree.

[00:09:17]Some of the most interesting semantic checks [music] are language specific.

[00:09:20]Rust is a great example. Its borrow checker enforces strict ownership rules, ensuring that references don't outlive the data they point to, and that mutable and immutable references don't coexist.

[00:09:31]Lifetimes make these guarantees explicit, and unsafe blocks let you opt out of some checks, but only in clearly marked sections. Other languages have their own rules. Modifiers like static, private, or const are all enforced during semantic analysis. Sometimes these exist to help the compiler optimize, but more often they exist to help the programmer prevent accidental access or mutate things that shouldn't change. So, now that we have collected a big list of checks that we want to do, you may wonder, how would you go about actually implementing this without creating horrible spaghetti code? The answer is surprisingly simple in principle. You just walk the tree multiple times. The semantic analyzer visits each node, checks the relevant rules, and collects information along the way. In practice, you define a visitor per check that you want to do, which keeps the analysis logic clean and modular.

[00:10:18]Under the hood, it's the visitor pattern, a design pattern where you define what you want to do for each kind of node, while the tree traversal itself is handled independently. [music] Before we wrap up, I also want to take a moment to thank everyone supporting the channel on Patreon. Your support helps me keep the series going, and I really appreciate that. If you'd like to join them, the link is in the description.

[00:10:37]Let's zoom out and look at the full analysis pipeline so far. The lexer checks the words using regular [music] expressions to break the source code into tokens. The parser checks the grammar using a formal grammar to build the syntax tree. And semantic analysis checks the meaning, enforcing the actual rules of the language that go beyond syntax. So, at this point, we know that the program is correct. It conforms to the rules of the language, the types match, the names are resolved, the control flow makes sense. From here on, the compiler's job shifts from checking to transforming and optimizing. And that's what's coming up next.

[00:11:11]This has been premature abstraction.

[00:11:13]Thank you for watching.