Welcome to the deep dive. Today, we're tackling something fundamental yet often unseen in the world of coding. The compiler. Think of it as the architect behind the scenes, taking your human readable instructions and blueprinting them into the precise machine language your computer understands precisely.
And for this deep dive, we're not just talking about compilers conceptually. We're getting into the initial stages of building our own. Our mission is to really dissect the core transformations required to compile even the most well the simplest see programs.
And to guide this architectural exploration, we'll be using excerpts from Writing a C Compiler as our foundational text. It's our guide as we uncover how source code undergoes its initial metamorphosis into executable form. Okay, let's unpack this, let's do it. Our compiler construction starts with establishing a modular pipeline of four key stages.
That's right. Yeah, even for the simplest stuff like maybe not even Hello World, maybe just returning a number, will be setting up a four pass structure. The first of.
These is the lex lexer or tokenizer.
Right or tokenizer, Yeah, same thing.
So the lexer's fundamental task is to scan our c code and break it down into its essential components, right like identifying the individual building blocks before you start assembling them exactly.
These smallest meaningful units are the tokens. Think about curly braces, defining scope, the summit, colon, ending statements, see words like int right, int return, and then the identifiers you create for functions, variables. All of these are distinct tokens. The lexer read your code character by character and groups them intelligently.
I see, so a basic line like into main return thirty two would be segmented into tokens int main return thirty two taxes.
Enter exactly that sequence.
Okay, what's the next step after this initial segmentation.
Following tokenization gives the parser? It takes that linear sequence of tokens.
Just a list basically just a list.
And imposes a hierarchical structure. It constructs what's known as an abstract syntax tree or at an AST.
Okay, so instead of just a flat list, we get a structured representation that shows how these tokens relate to each other.
Precisely. Think of it as moving from say a list of ingredients to an actual recipe.
Oh nice analogy.
The AST is this tree like structure that embodies the grammatical rules of C and reveals the program's operational flow. It's a format that lets the compiler analyze and well understand the codes intent much better than just that stream of.
Tokens, right, because just having a list of words doesn't tell you the sentence structure of the meaning exactly. So, for our example in Maine return thirty two, what would the AST look like in its simplest form.
In a simplified view, the root might be a program node, okay. Descending from that, you'd have a function node for Maine. Inside the function there'd be a return node, and finally, connected to return, a constant node holding the value.
There So it visually organizes the program's components and their relationships. Function contains a return statement which returns a.
Constant exactly captures that structure.
Interesting, Now the compiler has this structured tree. What happens next in the transformation.
This is where the translation to a lower level language begins. The code generation pass takes the AST the tree we just spilled, yes, that tree, and translates it into assembly language instruction assembly.
Okay, that's much closer to the hardware, right exactly.
And it's important to understand at this stage the compiler isn't directly writing out like a human readable assembly text file. Oh okay, it's still manipulating data structures internally. It's creating an in memory representation of these assembly instructions.
So the creation of the actual DOTS file comes later.
Yes, that's the job of the fourth initial pass code emission, right. This pass takes the in memory assembly representation what just created and finally writes it out, serializes it into a file, usually with the dot extension.
And that S file is what the assembler and linker use later on.
That's the one they take that and produce your final executable program.
It seems like a considerable number of steps for such a basic program, you know, return thirty two. Why not a more direct approach.
That's a really fair question. Again, it might seem like overkill for these tiny examples, but establishing this multipass architecture right from the start gives us huge advantages later. By separating concerns lexical analysis here, syntax there, cogen over here, modularity exactly, modularity, we create a more maintainable system. Imagine trying to translate I don't know, a complex novel straight into another language without first understanding the grammar and structure.
Yeah, that would be a mess.
It would be incredibly hard. This separation lets us handle more complexity later without having to rip everything up and start again. It's really about building a scalable foundation that.
Makes a lot of sense planning for future complexity. Okay, speaking of assembly language, can we actually peek under the hood see what a real compiler like GCC generates for a simple C program.
That's an excellent idea. It helps ground this discussion. For a simple program like in main return two saved us say return two dot C. You can use GCC with some specific commandline flags gccss and f and O. A secret is unwine tables FCF protection none, return two dot e t whoa.
Okay, lots of flags there, but the key is mesh s ash.
This is the main one telling it to stop after compilation and output assembly. The others just simplify the output a bit for our purposes.
Got it, And what's the output look like?
This command generates a file probably return two dots. With the assembly for that C program, you'll likely see something really simple like dot globalmine, dot main, dot movell two dollars percent ax red.
Okay, that's definitely not c what's going on.
Here, Let's break it down. The syntax is AT and T assembly syntax common on Linux and mac os. That first line dot global main that starts with a period, right, That means it's an assembler directive. It's an instruction for the assembler itself, not the CPU docl WI main just makes the main symbol visible outside this.
File, a symbol like a label or a name for a place in memory.
Precisely. Here, Maine is a symbol representing the starting address of our main function. The compiler doesn't know the final address yet. The linker figures that out later. Ah.
The linker's job resolving symbols exactly.
It resolves them assigns actual memory locations. If code refers to Maine, the linker patches in the real address. That's called relocation.
So Maine on the next line is just marking the spot the start of the code exactly.
It's the label. Then move two dollars percent ax. That's a real instruction.
MOLL move long thirty two bit.
Yep thirty two bit integer two dollars means the literal value.
Too an immediate value, right, and percent.
X is a register, a small fast storage spot inside the CPU. So this instruction puts the value too into the percent ax register.
Okay, but y percent x specifically convention.
In many standard ways, functions call each other calling conventions, the percent x register is designated to hold the function's return value.
Oh okay, So because our C code returns two, we put.
Two in percent acts so whoever called main can find the result.
There makes sense. And the last line writ.
Just means return tells the CPU to go back to where main was called from. So yeah, those four lines are the complete assembly for a tiny C program.
That's surprisingly direct.
Cool.
So when we compile a C program, even with our own simple compiler, what's the typical sequence of operations overall?
Right? So while our first compiler focuses mainly on that compilation to assembly.
Step step two, in the usual process, Yeah, the standard.
C process has a few phases. First, there's pre processing.
Handling hashtag include and macros and stuff.
Exactly Commands like GCCE do this. It often outputs a DITI file.
Then comes compilation proper our focus generating the didass assembly file correct?
Then in a full setup you have assembly and linking usually just GCC assembly file. Oh, output file.
Takes the dot S file, makes machine code, links libraries.
And gives you the final executable. Right. Our initial compiler will sort of stub out that last step, relying on the system's assembler and linker. Gotcha.
And for our own compiler driver, the command line tool we're building, how should.
That behave, good question. It should take the path to a C source file like your compiler paths to program dot C. If it works, success, it should create an executable in the same directory, same name, but no dot C. So pats a program and exit with code zero. And if it fails, non zero exit code and crucially no output files, no executable, clean failure.
Clear rules. And I saw mentions of lex and parse options in the notes.
Uh yeah, those are mostly for testing and debugging. Our compiler lexmis just run the lexer.
And stop check tokenizing, right, and.
Parse runs the lexer and parser builds the AST then stops. Neither should create any output files, they just check those stages internally.
Okay, that makes sense for development. All right, we've got a solid high light picture. The four passes the standard GCC flow. Let's dive deeper into the lexer and pulser. Now they're the first big hurdle in building our own right absolutely.
Chapter two of the guide digs into building these starting with the lexer. As we said, its job is finding tokens, and one simplifying assumption we make early on is that our c files only use ASKI characters.
Just standard ask you for now sensible starting point. How do we actually test if our lexer is doing the right thing.
The guide provides a test compiler tool, which is super helpful. It comes with test programs. In test chapter two, you'll find directories like invalid.
Lex programs that should fail the lexer.
Exactly, bad tokens, weird characters, and then invalid parts and valid directories. For later stages. You test the lexer specifically using dot test compiler path toward compiler chapter two stage lex.
Okay, So that command runs our compiler inlex only mode against those test cases and checks if it accepts or rejects them correctly.
That's the idea. It verifies the pass feel behavior. It doesn't necessarily check the exact stream of tokens for the valid files.
Though, ah so for that level of detail, we'd need our own unit tests.
Precisely, you'd write tests to feed it valid code and assert that the token list matches exactly what you expect, and feed it invalid code to check the error messages.
Got it? Any key implementation tips for the lexer itself, Yes.
A couple of important ones. First, when you see something that looks like an identifier, a sequence of letters, numbers, underscores like maine or my variable right your logic. Maybe your rejects will probably also match keywords like int or return. The efficient way is first recognize it as a generic identifier. Then check if that identifier happens to be on the list of reserved keywords.
Ah, don't try to make the initial pattern, distinguish them, identify, then.
Classify exactly two steps. The other thing is, don't rely only on white space to split tokens. Oh right, think about main. That's three tokens main and no white space separating them. If you just split on spaces, you'd get it wrong.
Point Okay, So the lexer spins out tokens. Then the parser steps in to build the ast exactly.
The parser takes that flat stream and gives it structure hierarchy based on the C grammar. The AST is the data structure holding that hierarchy.
We saw the simple AST for return thirty two. What about something slightly more complex, like an if statement. How does the hierarchy show up there?
Okay, good example. Let's say you have if ab return two plus two. Right, the top AST node might be an if node. This if node would have say, two main children, one for the condition.
Ab, which itself might be structured.
Oh yeah, that condition could be a binary op node for with this own children for the variable A and the variable b.
Okay, and the other child of the if.
That would be the then block return two plus two. That could be a return node, and its child would be another binary op node for the plus with two constant children both holding to wow.
Okay, So the tree really mirrors the nesting and the logic if conditioned then and the condition the then part have their own little subtrees.
Decisely, it captures that structure directly, which is what the next stages need now. To define these AST structures formally and importantly in a language neutral way, the guide introduces something called ASDL.
Asdl zephyr abstract syntax description language.
That's the one. It's just a formal way to write down what our AST nodes look like.
Okay, So what does the ASDL look like for our super simple C subset in chapter two?
It's pretty minimal. It's like program program function definition, function definition, function, identify your name, statement, body, return next, sovisp.
Okay, let's decode that a program is just a program node containing one function definition. Yep, A function definition is a function node. It has a name, which is an identifier type, and a body which is a statement type.
Right, and those words name and body are just field names helpful labels.
Gotcha. Then a statement can only be a return node containing an x expression for now, yes, and an x can only be a constant node holding an int.
That's it for chapter two. Identifier and int are like built in ASDL types.
So when we implement this, say in Python or Rust or drava, will create classes or data types that match this ASDL structure exactly.
Functional languages might use algebraic data types. OP languages might use abstract classes and inheritance. The guide mentioned some idioms and points to more reading if you want to go deeper into implementation strategies.
Okay, but the ASDL defines the structure, but it doesn't tell the parser which tokens in what order make up say a function definition. Right, it doesn't mention the ind keyword or the parentheses or braces.
That is a crucial distinction. You're absolutely right. The AST is abstract. It leaves out the syntactic sugar like semicolons embraces. The parser needs a concrete map of the token sequences.
Which is where the formal grammar comes.
In, exactly, using a notation called backus nair form or BNF BNF.
Okay, what's the BNF for this simplecy it mirrors.
The ASDL pretty closely. The program function I identify return expeed a statement return expediment, and then it clarifies the terminals identifier an identify your token and in a constant.
Token then okay, So things in angle brackets like this are non terminals. They correspond to our AST node types.
Yes, grammatical categories.
And things in quotes like this are terminals. The actual tokens the lexer gives.
Us exactly the literal tokens we expect to see. The bn F spells out the exact sequence and int token. Then an identifier token then art rcedo a statement right, and the.
Question mark definitions are just clarifying what kind of token identifier and in refer to. So the BNF is the parser's rulebook for matching token sequences to build the AST nodes defined by the asdo.
You've got it perfect summary. The guide also shows how you'd extend bn F like adding an if statement rules ifpanis statement l statement the brackets mean the l's part is optional neat Okay.
So we have tokens, the ASDL defining the target AST and the BNF grammar as a rule book. How does the parser actually do the parsing? What's the technique?
The guide introduces a common technique called recursive descent parsing.
Recursive dissent sounds intriguing.
The basic idea is simple, For each non terminal symbol in the BNF grammar, like program function statement, you write a corresponding parsing function.
Okay, a function for each rule.
Pretty much, and these functions often call each other, mirroring the structure of the grammar. That's the recursive part.
Ah okay, So how would parse statement work based on our simple grammar?
Well, the rule is statement return x biller. So the par statement function would first look for a return token. Okay, if it finds one, it consumes it. Then it needs to parson x, so it would call another function, maybe parsex.
Which would handle parsing the integer constant in our.
Case, right parsiicus would return the constant ast node, then parsated, but looks for the final token, consumes that, consumes that, and if everything worked, it bundles up the constant node returned by parsis inside a new return ast node and returns that got it.
The guide showed some pseudocode with an expect helper function.
Yeah. Expect is useful. It basically means check if the next token is x, consume it if yes, raise an error if no.
And these functions consume tokens as they go, So if parse program finishes and there are still tokens left over.
That usually means there's extra stuff that doesn't fit the grammar. A syntax error makes sense.
The guide mentioned predictive parsers and backtracking briefly too.
Yeah. For more complex grammars where a rule might have multiple options like if versus return for statement, the parser might need to peek ahead at the next token to decide which path to take predictive or try one path and backtrack if it fails.
But for our simple start, direct recursive descent works well.
And testing the parser same tool.
YEP test compiler path where you're compiler chapter two stage pars. It checks against the invalid pars and valid tests again. Writing your own tests to check the structure of the output AST is super helpful for debugging and the implementation tips where write a pretty printer for the ASD definitely helps visualize the tree and give good error messages.
Crucial expected but found return online five column ten is way better than just syntax error.
Absolutely okay. So source DAN lexer, the DAN pokins, the met parser, DAN cast. We have the tree. What's next?
Now we hit cogeneration. This pass takes that c language AST.
The one the parser is built.
Exactly and transforms it into our target by sixty four assembly instructions, but again not as text yet. We represent the assembly program as another internal data.
Structure first another AST, an assembly AST precisely.
The guide calls it that. To keep things clear, it has its own ASDL definition two.
Okay, what does the assembly ASDL look like?
It's also quite simple for now. Program function definition function identify our name, instruction instructions instructions op src, opern and dst ret oper im in register.
Okay, interesting parallels. Program has a function definition. A function has a name, but instead of a C statement body, it has instruction a list of instructions.
The astrisk means a list or sequence.
And the instruction types are mauve or reht and their operations can be immediate, a constant or a register.
That's it for now, and initially, the only register we care about is percent ax for the return value. The code generator walks the cast and for each node it figures out the equivalent assembly instructions and builds up this assembly AST.
The guide had a table mapping cast nodes to assembly AST constructs like return in C becomes a mauv register than are ret in assembling.
Right, and constant int in the cast becomes in in the assembly AST.
So it's a translation step building a new tree that represents the assembly code needed exactly.
And you can see how one C statement return maps to two assembly instructions movel and ret. That becomes more common as things get complex.
Okay, assembly AST constructed in memory. The final step of the initial four passes code emission.
Take that assembly AST we just built and write it out to the s text file.
Finally the text file.
Finally the text file. And since the assembly AST structure closely matches actual assembly syntax, this cast is usually quite straightforward. You just traverse the assembly AST and put the text for each node.
Another table in the guide showed the formatting function name instructions becomes dot global name, then name than the text for each instruction each On.
The new line, Yeah, mov A sarvisctst becomes move, srcdst, rep becomes REHT, register becomes percent x, mint becomes NT.
Just translating the assembly AST nodes into their standard text representation.
Pretty much a direct translation.
Yeah, and remembering that mac OS needs the underscore prefix on the global name like Maine.
Right, that platform detail needs to be handled by the emitter.
Okay. And then to test the whole thing lexer parser codegen code emitter, we run test compiler without the stage flags.
Exactly test compiler path toward your compiler. Chapter two. That command will one run your compiler on the test c files to generate S files. Two use the system's GCC. We're Clang to assemble and link those STS files into executables. Three. Run those executables. Four compare their exit codes to the exit codes produced by compiling the original C files directly with GCC.
So it verifies the end to end behavior. Does our compiler produce assembly that results in a program doing the same thing at least in terms of exit code as GCC.
That's the goal for this stage. It's the final check that all four passes are working together correctly for these simple programs.
Wow. Okay, so in this deep dive, we've really laid out the blueprint for a compiler's first steps. Yeah, lexingcode into tokens, parsing tokens into that crucial abstracts and text tree, generating an intermediate assembly representation from that tree, and finally emitting that assembly into a text file. It's fascinating to see how these stages transform the code step by step.
Absolutely and like we said, while it seems like a for just returning a number, this structured multi pass approach is really the key. It's the foundation we need to start handling more complex sea features like operators, variables, control flow in our next deep dives.
It definitely gives you a much deeper appreciation for what's happening when you just type gccmiprogram dot c okay. Thinking about these basic steps, how do they scale, How does this foundation handle the sheer complexity of say, the Linux kernel source code, and what are the really tricky sea features that will challenge this simple pipeline later on. Definitely something to chew on.
Indeed, plenty more complexity ahead.
Thanks for joining us for this deep dive