Introduction

This online book is currently being written. This is not the final version. feedback form

This book is packed with content that is too much to include in one book. In this book, we will create a program that converts source code written in C language into assembly language, that is, a C compiler. The compiler itself is also developed using C. The immediate goal is to be able to self-host, i.e. compile its own source code with a homebrew compiler.

In this book, I decided to explain various topics in a progressive manner throughout the book, so as not to make the explanation of compilers too difficult. Here's why:

Compilers can be conceptually divided into multiple stages: parsing, intermediate passes, and code generation. A common textbook approach is to explain each topic in chapters, but books with this approach tend to become too narrow and deep in the middle, making it difficult for readers to follow.

Also, with the development method of creating each stage, it is not possible to run the compiler until all stages are completed, so it is difficult to notice if there is a definite mistake in your understanding or code until the whole stage starts working. The downside is that you can't. In the first place, you don't really know what the next stage's input is expected to be until you create it yourself, so you don't really know what to output in the previous stage. Another problem is that it's hard to stay motivated because you can't compile any code at all until it's finished.

In this book, I decided to take a different approach to avoid that trap. Early in the book, you will implement a ``proprietary language'' with a very simple language specification. The language is so simple that you don't need to know much about how to write a compiler to implement it. After that, the reader will continue to add functions to the "proprietary language" through this book, and will eventually develop it into something that is consistent with C.

In such an incremental development method, you create a compiler step by step, making small commits. With this development method, the compiler is always in some sense "complete" at every commit. At one stage it may be able to do nothing more than a calculator level, at another stage it may be a very limited subset of C, and at another stage it may be a language that can almost be called C. The point is that at every stage, we aim for a language with reasonable specifications that match the level of completion at that point. During development, we do not emphasize only some functions to make it look like C language.

We will also explain data structures, algorithms, and computer science knowledge in stages according to the development stage.

Incremental development achieves the goal that, at any point in time while reading this book, the reader has a complete knowledge of how to create a reasonable language at that level. This is much better than the state where only some topics of compiler creation are extremely detailed. By the time you finish reading this book, you will be well-versed in all the topics.

This book also explains how to write large programs from scratch. The skill of creating large programs is a unique skill that is different from learning data structures and algorithms, but I don't think there are many books that explain such things. Also, even if someone explains it to you, you won't really know whether a development method is good or bad unless you actually experience it. This book is designed so that the process of developing your own language into C language will give you practical experience of a good development method.

If the author's plan is successful, by reading this book, readers will not only learn about techniques for creating compilers and the CPU instruction set, but also learn how to break down large programs into small steps and create them little by little. You'll learn testing techniques, version control techniques, and even how to prepare for an ambitious project like writing a compiler.

The intended audience for this book is ordinary C programmers. You don't need to be a super C programmer who knows the C language specification well. It is sufficient that you understand pointers and arrays, and that you can at least take some time to read small C programs written by others.

When writing this book, I tried not only to explain the language specifications and CPU specifications, but also to explain as much as possible why such designs were chosen. We have also interspersed columns about compilers, CPUs, the computer industry, and its history that will interest readers, making it an enjoyable read.

Creating a compiler is a lot of fun. In the beginning, my home-made language could only do ridiculously simple things, but as I continued to develop it, it quickly grew to resemble C language to the point that even I was surprised, and it started working as if by magic. Become. During actual development, I am often surprised that large test code that I didn't think would compile well at the time compiles without errors and works perfectly correctly. Such code cannot be easily understood by oneself even when looking at the compiled assembly. Sometimes I even feel like my compiler has more intelligence than I, the author. A compiler is a program that, even if you know how it works, you still wonder why it works so well. I'm sure you too will fall in love with its charm.

So, without further ado, let's jump into the world of compiler development with the author!

Conventions used in this book

Functions, expressions, commands, etc. are displayed in monospaced fonts, such as in mainthe text .foo=3make

Code that spans multiple lines is displayed in a frame using a monospaced font, as shown below.

int main() {
  printf("Hello world!\n");
  return 0;
}

If the boxed code is a shell command that is meant to be typed verbatim by the user, a $line starting with represents a prompt. $Type the rest of that line ( $but not the rest) into the shell. $The other lines represent the output from the command you entered. For example, the block below makeis an example of what happens when the user enters the string and presses Enter. makeThe output from the command make: Nothing to be done for `all'.is:

$ make
make: Nothing to be done for `all'.

Development environment assumed in this book

This book assumes a 64-bit Linux environment running on a so-called ordinary PC such as Intel or AMD. Please install development tools such as gcc and make in advance according to the distribution you are using. If you are using Ubuntu, you can install the commands used in this book by running the following command.

$ sudo apt update
$ sudo apt install -y gcc make git binutils libc6-dev

Although macOS is fairly compatible with Linux at the assembly source level, it is not fully compatible (specifically, a feature called "static linking" is not supported). Although it's possible to create a C compiler for macOS using the information in this book, if you try it you'll likely run into a number of minor incompatibilities. It is not recommended to simultaneously learn techniques for creating a C compiler and the differences between macOS and Linux. When something doesn't work, it's hard to know which understanding is wrong.

Therefore, this book does not cover macOS. On macOS, please use some kind of virtual environment to prepare a Linux environment. If this is your first time preparing a Linux virtual environment, please refer to Appendix 3 , which summarizes how to create a development environment using Docker .

Windows is not compatible with Linux at the assembly source level. However, with Windows 10, it is possible to run Linux on Windows like one application, and by using this, you can proceed with development on Windows. An application called Windows Subsystem for Linux (WSL) is that Linux-compatible environment. When implementing the contents of this book on Windows, please install WSL and proceed with development within it.

About the author

Rui Ueyama ( @rui314 ). He is the original author and current maintainer of the high-speed linker lld, which is used as the standard linker for creating executable files in many OSes and projects, including Android (version Q or later), FreeBSD (12 or later), Nintendo Switch, Chrome, and Firefox . (Therefore, there is a high possibility that the binary created by the tool I wrote is already on your computer.) He is also the author of the compact C compiler 8cc . I mainly write essays about software in notes .

Machine language and assembler

In this chapter, the goal is to get a rough idea of ​​the components that make up a computer and what kind of code should be output from the C compiler we create. I will not go into details about specific CPU instructions yet. It is important to understand the concept first.

CPU and memory

The components that make up a computer can be broadly divided into CPU and memory. Memory is a device that can hold data, and a CPU is a device that performs some processing while reading and writing from that memory.

Conceptually, memory appears to the CPU as a huge array of randomly accessible bytes. When the CPU accesses memory, it specifies the information about which byte of memory it wants to access using a number, and that number is called an "address." For example, "read 8 bytes of data from address 16" means to read 8 bytes of data from the 16th byte of memory that looks like an array of bytes. The same thing is sometimes called "reading 8 bytes of data from address 16."

Both the programs that the CPU executes and the data that those programs read and write reside in memory. The CPU retains the "address of the currently executing instruction" inside the CPU, reads the instruction from that address, does what is written there, and then reads and executes the next instruction. We are doing this. The address of the instruction currently being executed is called the " program counter " (PC) or the " instruction pointer " (IP). The format of the program that the CPU executes is called "machine code. "

The program counter does not necessarily advance linearly to the next instruction. A type of CPU instruction called a branch instruction allows you to set the program counter to any address other than the next instruction. This function enables if statements, loops, etc. Setting the program counter to a location other than the next instruction is called "jumping" or "branching."

In addition to the program counter, the CPU also has a small data storage area. For example, Intel and AMD processors have 16 areas that can hold 64-bit integers. This area is called a " register ". Memory is an external device to the CPU, and reading and writing from it takes some time, but registers exist inside the CPU and can be accessed without delay.

Many machine languages ​​have a format that performs some operation using the values ​​of two registers, and then writes the results back to the registers. Therefore, when a program is executed, the CPU reads data from memory into registers, performs some operations between registers, and writes the results back to memory. Masu.

The instructions of a specific machine language are collectively called the " instruction set architecture " (ISA) or "instruction set." There is not just one type of instruction set, and you can design it as you like for each CPU. However, the same program cannot run without compatibility at the machine language level, so there are not many variations in the instruction set. PCs use an instruction set called x86-64 from Intel and its compatible chip maker AMD . Although x86-64 is one of the major instruction sets, it is not the only one that dominates the market. For example, iPhone and Android use an instruction set called ARM.

What is an assembler?

Machine language is read directly by the CPU, so only the convenience of the CPU is taken into consideration, not the ease of use by humans. Writing such machine code with a binary editor is not impossible, but it is a very difficult task. That's when the assembler was invented . Assembly is a language that has almost a one-to-one correspondence with machine language, but it is much easier to read for humans than machine language.

For compilers that output native binaries rather than virtual machines or interpreters, the goal is usually to output assembly. Even compilers that appear to directly output machine language often start an assembler in the background after outputting assembly. The C compiler created in this book also outputs assembly.

Converting assembly code into machine language is sometimes called "compiling," but it is also sometimes called "assembling " to emphasize that the input is assembly.

You may have seen assembly before. If you haven't seen Assembly, now is a good time to take a look. objdumpLet's use a command to disassemble an appropriate executable file and display the machine language contained in that file as assembly. Below lsis the result of disassembling the commands.

$ objdump -d -M intel /bin/ls
/bin/ls:     file format elf64-x86-64

Disassembly of section .init:

0000000000003d58 <_init@@Base>:
  3d58:  48 83 ec 08           sub    rsp,0x8
  3d5c:  48 8b 05 7d b9 21 00  mov    rax,QWORD PTR [rip+0x21b97d]
  3d63:  48 85 c0              test   rax,rax
  3d66:  74 02                 je     366a <_init@@Base+0x12>
  3d68:  ff d0                 call   rax
  3d6a:  48 83 c4 08           add    rsp,0x8
  3d6e:  c3                    ret
...

In my environment, lsa command contains about 20,000 machine language instructions, so the disassembled result will be nearly 20,000 lines long. I have only posted the first part here.

Assembly basically consists of one line per machine code. For example, consider the following line:

  3d58:  48 83 ec 08           sub    rsp,0x8

What does this line mean? 3d58 is the memory address containing the machine code. In other words, lswhen the command is executed, the instruction on this line will be placed at address 0x3d58 in memory, and this instruction will be executed when the program counter is 0x3d58. The next four hexadecimal numbers are the actual machine code. The CPU reads this data and executes it as an instruction. sub rsp,0x8This is the assembly that corresponds to the machine language instructions. The CPU instruction set will be explained in a separate chapter, but this instruction is to subtract 8 from a register called RSP.

C and its assembler counterpart

simple example

To get an idea of ​​what kind of output the C compiler is producing, let's compare the C code and the corresponding assembly code. As the simplest example, consider the following C program.

int main() {
  return 42;
}

Given the file in which this program is written , you can verify that it actually returns 42 by test1.ccompiling it as follows :main

$ cc -o test1 test1.c
$ ./test1
$ echo $?
42

In C, mainthe value returned by a function is the exit code for the entire program. Although the program's exit code is not displayed on the screen, it is implicitly set in the shell variable $?, so you can see the command's exit code by displaying immediately after the command $?ends . echocan. You can see that 42 is returned correctly here.

Now, the assembly program corresponding to this C program is as follows.

.intel_syntax noprefix
.globl main
main:
        mov rax, 42
        ret

mainThis assembly defines a global label , mainfollowed by the code for the function. Here, we set the value 42 in a register called RAX and mainthen return. There are a total of 16 registers that can store integers, including RAX, but the promise is that when the function returns, the value in RAX will be the return value of the function, so here we will store the value in RAX. I am setting it.

Let's actually assemble and run this assembly program. The assembly file extension .sis , so try writing the assembly code above test2.sand running the following command.

$ cc -o test2 test2.s
$ ./test2
$ echo $?
42

42 is now the exit code, just like in C.

Roughly speaking, a C compiler is a program that outputs assembly like test1.c, when it reads C code like .test2.s

Example with function call

As a slightly more complex example, let's look at how code with function calls is translated into assembly.

A function call is different from a simple jump; after the called function finishes, you must return to the place you were originally executing. The address that was originally executed is called the "return address." If there is only one level of function calls, the return address can be stored in an appropriate register on the CPU, but since function calls can be made as deep as desired, the return address must be stored in memory. The return address is actually stored on a stack in memory.

A stack can be implemented using only one variable that holds the address of the top of the stack. The storage area that holds the top of the stack is called the "stack pointer." To support programming using functions, x86-64 supports a register dedicated to the stack pointer and instructions that use that register. Putting data on the stack is called "push," and taking out data from the stack is called "pop."

Now, let's look at an example of a function call. Consider the following C code.

int plus(int x, int y) {
  return x + y;
}

int main() {
  return plus(3, 4);
}

The assembly corresponding to this C code looks like this:

.intel_syntax noprefix
.globl plus, main

plus:
        add rsi, rdi
        mov rax, rsi
        ret

main:
        mov rdi, 3
        mov rsi, 4
        call plus
        ret

The first line is an instruction that specifies the assembly grammar. The second line .globl, starting with , tells assembly that the two functions `` and `` are visible to the entire program, not file scope plus. mainYou can ignore this for now.

mainPlease take a look first . mainIn C, pluskara is called with arguments. The assembler has a convention that the first argument is placed in the RDI register and the second argument is placed in the RSI register, so the mainvalues ​​are set accordingly in the first two lines of .

callis an instruction that calls a function. Specifically call:

• callretpushes the address of the next instruction (in this case ) onto the stack
• calljump to the address given as an argument to

Therefore, callonce the instruction is executed, the CPU pluswill start executing the function.

plusLook at the functions. plusThe function has three instructions.

addis an instruction that performs addition. In this case, the result of adding the RSI and RDI registers is written to the RSI register. Since x86-64 integer arithmetic instructions usually only accept two registers, the result will be saved by overwriting the value of the first argument register.

The return value from the function is to be stored in RAX. Therefore, since we want to store the addition result in RAX, we need to copy the value from RSI to RAX. movWe're doing it here using commands. movis an abbreviation for move, but it actually does not move data, but simply copies it.

plusAt the end of the function, retwe call and return from the function. Specifically ret:

• pop an address from the stack
• jump to that address

In other words ret, callit is an instruction that undoes what has been done and resumes execution of the calling function. is defined as the opposite callcommand .ret

plusWhat you see when you return from mainis retthe command. The original C code was supposed to return plusthe return value as is . mainHere, plusthe return value is stored in RAX, so by mainreturning as is, mainyou can use it as the return value.

Summary of this chapter

This chapter provided an overview of how a computer works internally and what a C compiler should do. When you look at assembly or machine language, it looks like a jumbled mass of data that is far removed from C, but many readers may have thought that it actually reflects the structure of C more directly than you might think. .

This book hasn't explained much about specific machine language yet, so I do objdumpn't think you know the meaning of the individual instructions in the assembly code displayed in , but each instruction doesn't do much. I think you can imagine it. At this stage of this chapter, it is enough to get a sense of that.

The main points of this chapter are summarized below in bullet points.

• The CPU executes programs by reading and writing memory.
• Both the program executed by the CPU and the data handled by that program are stored in memory, and the CPU reads machine language instructions from memory in order and executes the instructions.
• The CPU has a small storage area called registers, and many machine languages ​​are defined as operations between registers.
• Assembly is a language that makes machine language easier to read for humans, and C compilers usually output assembly.
• C functions are also functions in assembly.
• Function calls are implemented using a stack

Creating a calculator-level language

In this chapter, the first step in writing a C compiler is to support arithmetic operations and other arithmetic operators so that you can compile expressions such as:

30 + (4 - 2) * -5

This may seem like a simple goal, but it is actually quite difficult. Numerical formulas have a structure in which the expression in parentheses takes precedence, or multiplication takes precedence over addition, and unless you understand this in some way, you will not be able to perform calculations correctly. However, the formula given as input is just a flat string of characters, not structured data. In order to correctly evaluate an expression, it is necessary to analyze the sequence of characters and successfully derive the hidden structure.

These parsing problems are quite difficult to solve without any prior knowledge. In fact, these problems were once thought to be difficult problems, and intensive research was conducted and various algorithms were developed, especially from the 1950s to the 1970s. Thanks to that work, parsing is now a fairly simple problem once you know how to do it.

This chapter describes one of the most common parsing algorithms, recursive descent parsing. The C/C++ compilers that you use every day, such as GCC and Clang, also use recursive descent parsing.

The need to read text with some kind of structure often arises when programming, not just with compilers. The techniques you will learn in this chapter can be used directly for such problems. It is no exaggeration to say that the syntax analysis techniques you will learn in this chapter are techniques that will last a lifetime. Read this chapter to understand algorithms and add parsing skills to your programmer's toolbox.

Step 1: Create a language that compiles one integer

Consider the simplest subset of the C language. What kind of language do you imagine? mainIs it a language that only has functions? Or maybe a language consisting of only one expression? Ultimately, I think it's fair to say that a language consisting of only one integer is the simplest subset imaginable.

In this step, let's implement the simplest language first.

The program you create in this step is a compiler that reads a number from input and outputs an assembly that exits with that number as the program's exit code. So the input is simply 42a string like , and when you read it you create a compiler that outputs assembly like this:

.intel_syntax noprefix
.globl main

main:
        mov rax, 42
        ret

.intel_syntax noprefixis an assembler command for selecting the Intel notation used in this book from among the multiple assembly writing methods. Please be sure to include this line at the beginning of the compiler you will create this time. The other lines are as explained in the previous chapter.

At this point, the reader may think, ``This program cannot be called a compiler.'' I honestly think so too. However, this program accepts a language consisting of a single number as input and outputs code corresponding to that number, so by definition it is a fine compiler. Even a simple program like this can quickly become quite complex if you modify it, so let's complete this step first.

This step is actually very important from the overall development procedure. This is because we will use what we create in this step as a skeleton for future development. In this step, in addition to creating the compiler itself, we also create a build file (Makefile), automated tests, and set up a git repository. Let's look at each of these tasks one by one.

The C compiler created in this book is called 9cc. cc is an abbreviation for C compiler. The number 9 doesn't have any particular meaning, but the C compiler I created before was called 8cc, so I decided to name it 9cc because it's the next work. Of course, you can give it any name you like. However, don't think too much about the name in advance and be unable to start writing the compiler. You can change names later, including GitHub repositories, so there is no problem starting with any name.

mov rbp, rsp   // Intel
mov %rsp, %rbp // AT&T

mov rax, 8     // Intel
mov $8, %rax   // AT&T

mov [rbp + rcx * 4 - 8], rax // Intel
mov %rax, -8(rbp, rcx, 4)    // AT&T

Creating the compiler body

Normally we give input to the compiler as a file, but since we don't want to open and read the file, we'll give the code directly as the first argument to the command. A C program that reads the first argument as a number and embeds it in the assembly of a fixed phrase can be easily written as follows.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");
  printf("  mov rax, %d\n", atoi(argv[1]));
  printf("  ret\n");
  return 0;
}

9ccCreate an empty directory and 9cc.ccreate a file in it with the above content. Then, run 9cc as shown below and check the operation.

$ cc -o 9cc 9cc.c
$ ./9cc 123 > tmp.s

The first line 9cc.ccompiles and 9cccreates an executable file. The second line 123passes the input to 9cc to generate an assembly and tmp.swrites it to the file. tmp.sLet's check the contents.

$ cat tmp.s
.intel_syntax noprefix
.globl main
main:
  mov rax, 123
  ret

As you can see, it's generated well. You can create an executable file by passing the assembly file created in this way to an assembler.

In Unix, cc(or gcc) is a front end for many languages, not just C and C++, and it determines the language based on the extension of a given file and starts the compiler or assembler. I am. Therefore, just like when compiling 9cc, you can assemble it by passing an .sassembler file with the extension to . ccThe following is an example of assembling and running the generated executable file.

$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
123

In the shell, the exit code of the previous command $?can be accessed as a variable. In the example above, the number 123 is displayed, which is the same argument given to 9cc. That means it's working fine. Try giving a number other than 123 in the range 0 to 255 (Unix process exit codes are supposed to be 0 to 255) and see if 9cc actually works.

Creating automated tests

Many readers may have never written tests for hobby programming, but in this book we will write code to test new code each time we extend the compiler. Writing tests may seem tedious at first, but you'll soon start to appreciate them. If you don't write test code, you'll end up having to run the same tests by hand every time to check the operation, but doing it by hand is much more troublesome.

I think a lot of the impression that writing tests is tedious stems from the fact that test frameworks are exaggerated and the philosophy of testing is sometimes dogmatic. For example, testing frameworks like JUnit have a variety of useful functions, but they take time to install and learn how to use. Therefore, this chapter does not introduce such testing frameworks. Instead, I'm going to write a very simple handwritten "test framework" in shell scripts and use it to write my tests.

test.shBelow is a shell script for testing . The shell function asserttakes two arguments, an input value and an expected output value, and does what it does: actually assemble the 9cc result and compare the actual result to the expected value. In the shell script, assertafter defining the function, I use it to verify that both 0 and 42 compile correctly.

#!/bin/bash
assert() {
  expected="$1"
  input="$2"

  ./9cc "$input" > tmp.s
  cc -o tmp tmp.s
  ./tmp
  actual="$?"

  if [ "$actual" = "$expected" ]; then
    echo "$input => $actual"
  else
    echo "$input => $expected expected, but got $actual"
    exit 1
  fi
}

assert 0 0
assert 42 42

echo OK

test.shCreate it with the above content and chmod a+x test.shrun it to make it executable. Let's actually test.shrun it. If no errors occur, the following will display and exit test.sh.OK

$ ./test.sh
0 => 0
42 => 42
OK

If an error occurs, will test.shnot OKbe displayed. Instead test.sh, it displays the expected and actual values ​​for the failed test, as shown below.

$ ./test.sh
0 => 0
42 expected, but got 123

When you want to debug a test script, -xrun the script with the bash option. -xWith this option, bash will display a trace of the execution as shown below.

$ bash -x test.sh
+ assert 0 0
+ expected=0
+ input=0
+ cc -o 9cc 9cc.c
+ ./9cc 0
+ cc -o tmp tmp.s
+ ./tmp
+ actual=0
+ '[' 0 '!=' 0 ']'
+ assert 42 42
+ expected=42
+ input=42
+ cc -o 9cc 9cc.c
+ ./9cc 42
+ cc -o tmp tmp.s
+ ./tmp
+ actual=42
+ '[' 42 '!=' 42 ']'
+ echo OK
OK

The "testing framework" we use throughout this book is simply a shell script like the one above. This script may seem too simple compared to a full-fledged testing framework such as JUnit, but the simplicity of this shell script is balanced with the simplicity of 9cc itself, so That's preferable. Automated testing is all about running the code you've written in one go and mechanically comparing the results, so it's important to test it first without thinking too much about it.

Build with make

Throughout this book, you will build 9cc hundreds or even thousands of times. The work of creating a 9cc executable file and then running the test script is the same every time, so it is convenient to leave it to a tool. Commands are commonly used for these purposes make.

When run, make Makefilereads the file named in the current directory and executes the commands written in it. Makefileconsists of a rule ending with a colon and a sequence of commands for that rule. The following Makefileis to automate the commands you want to run in this step.

CFLAGS=-std=c11 -g -static

9cc: 9cc.c

test: 9cc
        ./test.sh

clean:
        rm -f 9cc *.o *~ tmp*

.PHONY: test clean

Create the above file 9cc.cin the same directory with the name . MakefileThen, makejust by running 9cc will be created, make testand by running , you will be able to run the test. Since make can understand file dependencies, there is no need to run 9cc.cafter changing and make testbefore running . makeOnly if the executable file 9cc is older than 9cc.c, make will build 9cc before running the tests.

make cleanThis is a rule for deleting temporary files. You can create temporary files rmmanually , but it would be troublesome if you accidentally delete a file you don't want to delete, Makefileso I decided to write something like this as a utility.

Please Makefilenote that when writing , Makefilethe indent must be a tab character. 4 or 8 spaces will result in an error. This is just bad syntax, but make is an old tool developed in the 1970s, and has traditionally been this way.

ccBe sure -staticto pass the option . This option is explained in the chapter called Dynamic Linking . You don't need to think much about what this option means right now.

Version control with git

This book uses git as the version control system. Throughout this book, we will create a compiler step by step, and for each step, please create a git commit and write a commit message. The commit message can be in Japanese, so please make sure to include a one-line summary of what has actually changed. If you want to write more than one line of detailed explanation, leave one blank line after the first line and write the explanation after that.

Git only performs version control on files that you manually generate. Files generated as a result of running 9cc can be generated again by executing the same command, so there is no need to include them under version control. In fact, including such files makes the changes per commit unnecessarily long, so they should be removed from version control and not included in the repository.

In git .gitignore, you can write patterns for files to be excluded from version control in a file called .git. 9cc.cCreate a directory with the following content in the same directory as .gitignoregit and set it to ignore temporary files, editor backup files, etc.

*~
*.o
tmp*
a.out
9cc

If this is your first time using Git, tell Git your name and email address. The name and email address you tell git here will be recorded in the commit log. Below is an example of setting the author's name and email address. Readers, please enter your name and email address.

$ git config --global user.name "Rui Ueyama"
$ git config --global user.email "ruiu@cs.stanford.edu"

To make a commit with git, you first git addneed to add the file that has changed. Since this is our first commit, we will first git initcreate a git repository and then git addadd all the files we have created so far.

$ git init
Initialized empty Git repository in /home/ruiu/9cc
$ git add 9cc.c test.sh Makefile .gitignore

Then git commitcommit.

$ git commit -m "整数1つをコンパイルするコンパイラを作成"

-mOptionally specify a commit message. -mIf there are no options, gitlaunches the editor. git log -pYou can check that the commit was successful by running the following :

$ git log -p
commit 0942e68a98a048503eadfee46add3b8b9c7ae8b1 (HEAD -> master)
Author: Rui Ueyama <ruiu@cs.stanford.edu>
Date:   Sat Aug 4 23:12:31 2018 +0000

    整数1つをコンパイルするコンパイラを作成

diff --git a/9cc.c b/9cc.c
new file mode 100644
index 0000000..e6e4599
--- /dev/null
+++ b/9cc.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(int argc, char **argv) {
+  if (argc != 2) {
...

Finally, let's upload the git repository we created so far to GitHub . There's no particular reason to upload to GitHub, but there's also no reason not to, and GitHub is useful as a backup for your code. To upload to GitHub, create a new repository (in this example, I created the repository using rui314user ) and add it as a remote repository with the following command:9cc

$ git remote add origin git@github.com:rui314/9cc.git

Then, git pushrunning will push the contents of your repository to GitHub. git pushAfter running GitHub, try opening GitHub in a browser and verify that your source code has been uploaded.

This completes the first step of creating the compiler. The compiler in this step is too simple to be called a compiler, but it is a fine program that includes all the elements necessary for a compiler. From now on, we will continue to enhance the functionality of this compiler, and although it may be hard to believe, we will develop it into a fine C compiler. Enjoy the completion of the first step.

Step 2: Create a compiler that can add and subtract

In this step, we will extend the compiler we created in the previous step so that it accepts expressions that include additions and subtractions, such as and , rather 42than just values ​​such as .2+115+20-4

5+20-4You could calculate an expression like at compile time and 21embed the resulting number (in this case) in the assembly, but that would make it look like an interpreter rather than a compiler, so you could do the addition and subtraction. When you need to output the assembly you do. The assembly instructions for addition and addsubtraction subare and. addtakes two registers, adds their contents, and writes the result to the register of its first argument. is the same subas addUsing these instructions, 5+20-4you can compile as follows:

.intel_syntax noprefix
.globl main

main:
        mov rax, 5
        add rax, 20
        sub rax, 4
        ret

In the above assembly, movwe set RAX to 5, then add 20 to RAX, and then subtract 4. retThe value of RAX at the time it is executed 5+20-4should be 21. Let's run it and check it out. tmp.sSave the above file , assemble it, and try running it.

$ cc -o tmp tmp.s
$ ./tmp
$ echo $?
21

21 was displayed correctly as shown above.

Now, how should I create this assembly file? If we consider this expression involving addition and subtraction as a "language," this language can be defined as follows.

• There is one number at the beginning
• It is followed by zero or more "terms"
• A term is something +that has a number after it, or -something that has a number after it.

If you translate this definition into C code, you will get a program like this:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  if (argc != 2) {
    fprintf(stderr, "引数の個数が正しくありません\n");
    return 1;
  }

  char *p = argv[1];

  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");
  printf("  mov rax, %ld\n", strtol(p, &p, 10));

  while (*p) {
    if (*p == '+') {
      p++;
      printf("  add rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    if (*p == '-') {
      p++;
      printf("  sub rax, %ld\n", strtol(p, &p, 10));
      continue;
    }

    fprintf(stderr, "予期しない文字です: '%c'\n", *p);
    return 1;
  }

  printf("  ret\n");
  return 0;
}

The program is a little longer, but retthe lines in the first half are the same as before. Code for reading terms is added in the middle. This time, the program is not just for reading a single number, so after reading a number, we need to know how far it has read. atoiSince this does not return the number of characters read, you atoiwill not know where to start reading the next section. Therefore, strtolwe used functions from the C standard library.

strtolreads the number, then updates the pointer in its second argument to point to the character after the last character read. Therefore, after reading a number, if the next character is +, -then pshould point to that character. The above program takes advantage of this fact by whilereading the terms one after another in a loop, and outputting one line of assembly each time it reads one term.

Now, let's run this modified version of the compiler. 9cc.cAfter updating the file, makeyou can create a new 9cc file by simply running . An example of execution is shown below.

$ make
$ ./9cc '5+20-4'
.intel_syntax noprefix
.globl main
main:
  mov rax, 5
  add rax, 20
  sub rax, 4
  ret

It looks like the assembly is being output successfully. To test this new feature, test.shlet's add a test line like this:

assert 21 "5+20-4"

Once you've done this, commit your changes to git. To do so, run the following command:

$ git add test.sh 9cc.c
$ git commit

git commitWhen you run , the editor will start, so write ``Add addition and subtraction'', save it, and exit the editor. git log -pTry using the command to confirm that the commit is happening as expected. Once you finally git pushrun and push the commit to GitHub, this step is complete!

Step 3: Introduce tokenizer

The compiler created in the previous step has one drawback. If the input contains blank characters, an error will occur at that point. 5 - 3For example , if you give a string with spaces like the following , a space character will be found where you are trying to read +or, -and compilation will fail.

$ ./9cc '5 - 3' > tmp.s
予期しない文字です: ' '

There are several ways to resolve this issue. One obvious method is to skip the whitespace characters before attempting to read or +. -There's nothing particularly wrong with this approach, but in this step we'll take a different approach to solving the problem. The method is to split the input into words before reading the expression.

Just like Japanese and English, mathematical formulas and programming languages ​​can be thought of as consisting of sequences of words. 5+20-4For example , you can think of it as being made up of five words: , 5, , . This "word" is called a " token ." The white space between tokens only exists to separate the tokens, and is not part of the word. So it would be natural to remove whitespace characters when splitting a string into token sequences. Dividing a string into a string of tokens is called " tokenizing ."+20-4

There are other benefits to separating strings into token sequences. When an expression is divided into tokens, the tokens can be classified and given types. For example , +``ya '' is a symbol such as -``as you see'' , and the string ``on the other hand'' means the numerical value 123. By interpreting each token of the input instead of just splitting it into strings when tokenizing, you have less to think about when consuming a string of tokens.+-123

In the current grammar for expressions that allow addition and subtraction, there are three types of tokens: , , and numeric +. -Furthermore, for compiler implementation reasons, it is better to define one special type to represent the end of a token sequence (just as a string ends with '\0'). Let's make the tokens a linked list connected by pointers so that we can handle input of arbitrary length.

Although it is a bit long, I will post below an improved version of the compiler that introduces a tokenizer.

#include <ctype.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// トークンの種類
typedef enum {
  TK_RESERVED, // 記号
  TK_NUM,      // 整数トークン
  TK_EOF,      // 入力の終わりを表すトークン
} TokenKind;

typedef struct Token Token;

// トークン型
struct Token {
  TokenKind kind; // トークンの型
  Token *next;    // 次の入力トークン
  int val;        // kindがTK_NUMの場合、その数値
  char *str;      // トークン文字列
};

// 現在着目しているトークン
Token *token;

// エラーを報告するための関数
// printfと同じ引数を取る
void error(char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

// 次のトークンが期待している記号のときには、トークンを1つ読み進めて
// 真を返す。それ以外の場合には偽を返す。
bool consume(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    return false;
  token = token->next;
  return true;
}

// 次のトークンが期待している記号のときには、トークンを1つ読み進める。
// それ以外の場合にはエラーを報告する。
void expect(char op) {
  if (token->kind != TK_RESERVED || token->str[0] != op)
    error("'%c'ではありません", op);
  token = token->next;
}

// 次のトークンが数値の場合、トークンを1つ読み進めてその数値を返す。
// それ以外の場合にはエラーを報告する。
int expect_number() {
  if (token->kind != TK_NUM)
    error("数ではありません");
  int val = token->val;
  token = token->next;
  return val;
}

bool at_eof() {
  return token->kind == TK_EOF;
}

// 新しいトークンを作成してcurに繋げる
Token *new_token(TokenKind kind, Token *cur, char *str) {
  Token *tok = calloc(1, sizeof(Token));
  tok->kind = kind;
  tok->str = str;
  cur->next = tok;
  return tok;
}

// 入力文字列pをトークナイズしてそれを返す
Token *tokenize(char *p) {
  Token head;
  head.next = NULL;
  Token *cur = &head;

  while (*p) {
    // 空白文字をスキップ
    if (isspace(*p)) {
      p++;
      continue;
    }

    if (*p == '+' || *p == '-') {
      cur = new_token(TK_RESERVED, cur, p++);
      continue;
    }

    if (isdigit(*p)) {
      cur = new_token(TK_NUM, cur, p);
      cur->val = strtol(p, &p, 10);
      continue;
    }

    error("トークナイズできません");
  }

  new_token(TK_EOF, cur, p);
  return head.next;
}

int main(int argc, char **argv) {
  if (argc != 2) {
    error("引数の個数が正しくありません");
    return 1;
  }

  // トークナイズする
  token = tokenize(argv[1]);

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");

  // 式の最初は数でなければならないので、それをチェックして
  // 最初のmov命令を出力
  printf("  mov rax, %d\n", expect_number());

  // `+ <数>`あるいは`- <数>`というトークンの並びを消費しつつ
  // アセンブリを出力
  while (!at_eof()) {
    if (consume('+')) {
      printf("  add rax, %d\n", expect_number());
      continue;
    }

    expect('-');
    printf("  sub rax, %d\n", expect_number());
  }

  printf("  ret\n");
  return 0;
}

The code is not very short, about 150 lines, but it doesn't do anything too tricky, so you should be able to read it by reading from the top.

Let me explain some programming techniques used in the code above.

• tokenI decided to represent the token string read by the parser using a global variable . The parser tokenreads the input by walking through a linked list. This style of programming using global variables may not seem like a clean style. However, in practice, it is often easier to read the parser code by treating the input token sequence as a stream like standard input, as we are doing here. Therefore, we have adopted such a style here.
• tokenI divided the code that directly touches the code into functions such consumeas , and prevented expectother functions from directly touching it.token
• tokenizeThe function is building a linked list. When constructing a linked list, you can simplify the code headby creating a dummy element, connecting new elements to it, and head->nextreturning at the end. This method headwastes most of the memory allocated to the element, but the cost of allocating local variables is almost zero, so you don't need to worry about it.
• callocmallocis a function that allocates memory just mallocUnlike , callocit zeroes out the allocated memory. Here, callocI decided to use ``to save the effort of zeroing out the elements.''

test.shThis improved version should now be able to skip whitespace, so let's add the following test to one line .

assert 41 " 12 + 34 - 5 "

The exit code of a Unix process is a number between 0 and 255, so when writing tests, make sure that the result of the entire expression falls within the range 0 to 255.

Adding the test files to your git repository completes this step.

Step 4: Improve error messages

With the compiler we have created so far, if the input is grammatically incorrect, the only thing we can tell is that there is an error somewhere. Let's try to improve that problem in this step. Specifically, we will be able to display an intuitive error message like the one below.

$ ./9cc "1+3++" > tmp.s
1+3++
    ^ 数ではありません

$ ./9cc "1 + foo + 5" > tmp.s
1 + foo + 5
    ^ トークナイズできません

In order to display such an error message, we need to be able to tell which byte of input the error occurs. To do this, user_inputlet's save the entire program string in a variable named variable, and define a new error display function that receives a pointer to the middle of the string. The code is shown below.

// 入力プログラム
char *user_input;

// エラー箇所を報告する
void error_at(char *loc, char *fmt, ...) {
  va_list ap;
  va_start(ap, fmt);

  int pos = loc - user_input;
  fprintf(stderr, "%s\n", user_input);
  fprintf(stderr, "%*s", pos, " "); // pos個の空白を出力
  fprintf(stderr, "^ ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, "\n");
  exit(1);
}

error_atThe pointer it receives is a pointer to the middle of a string that represents the entire input. By taking the difference between that pointer and the pointer pointing to the beginning of the input, you can tell which byte of input the error is located, so you can mark it prominently ^.

argv[1]This step is completed by updating the code user_inputto save the error("数ではありません")code to .error_at(token->str, "数ではありません")

A practical-level compiler should also write tests for the behavior when there are errors in the input, but as of now error messages are only output to aid debugging, there is no need to write tests at this stage. It doesn't matter if you don't have it.

if ((err = ReadyHash(&SSLHashSHA1, &hashCtx)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &clientRandom)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &serverRandom)) != 0)
    goto fail;
if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
    goto fail;
    goto fail;
if ((err = SSLHashSHA1.final(&hashCtx, &hashOut)) != 0)
    goto fail;

Grammar description method and recursive descent parsing

Now, we would like to add multiplication/division and precedence parentheses, namely , to the language, but there is one big technical challenge to doing so *. This is because there is a rule that multiplication and division must be calculated first in an expression. For example, the expression should be interpreted as , not as . These rules about which operators "stick together" first are called " operator precedence . "/()1+2*31+(2*3)(1+2)*3

How should we handle operator precedence? The compiler we've created so far just reads the token sequence from the beginning and outputs the assembly, so if you simply extend it and add and, you'll end up compiling *it as ./1+2*3(1+2)*3

Existing compilers are naturally good at handling operator precedence. The compiler's parsing is very powerful and can interpret any complex code correctly as long as it follows the syntax. The behavior of this compiler may give the impression that it has an intellectual ability that surpasses that of humans, but in reality, computers do not have the ability to read text like humans, so parsing is performed only by some mechanical mechanism. There should be. How exactly does it work?

In this chapter, let's take a break from coding and learn some parsing techniques. This chapter describes parsing techniques in the following order:

1. First understand the final goal by knowing the data structure of the parser's output.
2. Learn the rules that define grammar rules
3. Learn techniques for writing parsers based on rules that define grammar rules

Representation of grammatical structure using tree structure

In programming language parser implementations, the input is usually a flat sequence of tokens and the output is a tree representing a nested structure. The compiler created in this book also follows that structure.

In the C language, grammatical elements such as ifand whilecan be nested. Representing something like this in a tree structure is a natural way to represent it.

Numerical formulas have a structure in which things inside parentheses are calculated first, and multiplication and division are calculated before addition and subtraction. Although this kind of structure may not look like a tree at first glance, it is actually a very simple way to represent the structure of an expression. For example 1*(2+3), the expression can be thought of as being represented by the following tree.

If we adopt the rule of sequentially calculating from the end of the tree, the above tree will represent the formula 1 multiplied by 2+3. In other words, in the above tree, 1*(2+3)the specific calculation order of is expressed in the tree itself.

Here's another example. The tree below 7-3-3is a tree that represents.

In the above tree, the result of applying the rule that "subtraction must be calculated from the left" is explicitly expressed in the form of a tree. In other words, the above tree (7-3)-3 = 1represents the expression , 7-(3-3) = 7not the expression . If it were the latter expression, the tree representing it would be deeper to the right rather than to the left.

Operators that must be calculated from the left are called "left associative" operators, and operators that must be calculated from the right are called "right associative" operators. In C, =most operators are defined as left associative, except for assignment.

In a tree structure, you can express an expression as long as you want by making the tree deeper. The next tree 1*2+3*4*5is the tree that represents.

A tree like the one above is called a "syntax tree. " In particular, a syntax tree that is expressed as compactly as possible without leaving redundant elements such as parentheses for grouping in the tree is called an ``abstract syntax tree'' (AST ) . All of the above syntax trees can be called abstract syntax trees.

Since the abstract syntax tree is an internal representation of the compiler, it may be defined as appropriate for implementation purposes. However, since arithmetic operators such as addition and multiplication are defined as operations on two sides, a left-hand side and a right-hand side, it would be natural for any compiler to create a binary tree. On the other hand, it would be natural to represent expressions in the body of a function, which can be executed in sequence and have any number of expressions, as a tree with all child elements flat.

The goal in parsing is to construct an abstract syntax tree. The compiler first parses the input token sequence into an abstract syntax tree, which in turn converts into assembly.

Defining grammar using production rules

Now, let's learn how to write syntax in programming languages. Most of the syntax of programming languages ​​is defined using production rules . Production rules are rules that recursively define grammars.

Let's think about natural language for a moment. In Japanese, grammar has a nested structure. For example, if you replace the noun ``flower'' in the sentence ``flowers are beautiful'' with the noun phrase ``red flower,'' the sentence becomes correct, and if you further expand ``red'' into ``a little red''. However, it is still a correct sentence. You can also put it inside another sentence, like ``I thought the little red flowers were pretty.''

These grammars are defined as, ``A 'sentence' consists of a 'subject' and a 'predicate',' or 'A 'noun phrase' consists of a 'noun' or an 'adjective' followed by a 'noun phrase.'” Let's think of it as something defined as a rule like this. Then, by using a ``sentence'' as a starting point and developing it according to the rules, it is possible to create an infinite number of valid sentences within the defined grammar.

Or, conversely, by thinking about the expansion procedure that matches an existing sentence, you can think about what kind of structure that string has.

The above ideas were originally devised for natural languages, but because they have a high affinity with data handled by computers, production rules are used in various areas of computers, including programming languages.

Description of production rules using BNF

One notation for describing production rules in a compact and easy-to-understand manner is BNF ( Backus–Naur form ) and its extended version, EBNF ( Extended BNF ). In this book, we will explain the syntax of C using EBNF. This section first describes BNF and then describes extensions to EBNF.

In BNF, each production rule is A = α₁α₂⋯expressed in the form. This means that the symbol can be expanded into A. is a sequence of zero or more symbols, which can contain both symbols that cannot be expanded further and symbols that can be expanded further (coming on the left side in some production).α₁α₂⋯α₁α₂⋯

A symbol that cannot be expanded further is called a " terminal symbol", and a symbol that appears on the left side of any production rule and can be expanded is called a " nonterminal symbol". Grammars defined by such production rules are generally called ``context free grammars.' '

A nonterminal symbol may match multiple productions. For example, A = α₁if A = α₂there are both rules, it means that it can be expanded either way .Aα₁α₂

The right-hand side of the production rule can be empty. In such a rule, the symbol on the left side will be expanded to a zero-length symbol string (i.e., to nothing). However, if the right-hand side is omitted, it becomes difficult to understand the meaning, so in such cases, the standard BNF rule is to write ε (epsilon) on the right-hand side as a symbol to indicate that there is nothing . This book also uses this rule.

Strings are enclosed in double quotes and "foo"written as follows. Strings are always terminal.

The above are the basic BNF rules. In addition to BNF rules, EBNF allows you to write complex rules concisely using the following symbols.

For example A = ("fizz" | "buzz")*, Ais a string in which "fizz"or "buzz"is repeated zero or more times, i.e.

• ""
• "fizz"
• "buzz"
• "fizzfizz"
• "fizzbuzz"
• "buzzfizz"
• "buzzbuzz"
• "fizzfizzfizz"
• "fizzfizzbuzz"
• ...

can be expanded to either.

simple production rules

As an example of writing a grammar using EBNF, consider the following production rule.

expr = num ("+" num | "-" num)*

numis defined somewhere as a symbol representing a numerical value. In this grammar, there is one exprfirst word, followed by zero or more " to , or and ". This rule actually represents the grammar of addition and subtraction expressions.num+num-num

By starting from expr and expanding it, you can create a string of arbitrary additions and subtractions, for example a string like .1 Please check the expansion results below.10+542-30+2

expr → num → "1"

expr → num "+" num
     → "10" "+" "5"

expr → num "-" num "+" num
     → "42" "-" "30" "+" "2"

In addition to using arrows to represent each expansion order, these expansion steps can also be represented in a tree structure. The syntax tree for the above expression is shown below.

By representing it in a tree structure, it is now easier to understand which nonterminal symbol is expanded into which symbol.

A syntax tree like the one shown above, which includes all the tokens in the input and has a perfect one-to-one match to the grammar, is sometimes called a "concrete syntax tree . " This term is often used to contrast with abstract syntax trees.

Note that in the above concrete syntax tree, the rule that addition and subtraction are calculated from the left is not expressed in the form of a tree. In the grammar explained here, such a rule is not expressed using EBNF, but is written as a proviso in the language specification that ``Addition and subtraction are calculated from the left first.'' Become. The parser takes both EBNF and the disclaimer into account, reads the token sequence representing the expression, and constructs an abstract syntax tree that appropriately represents the evaluation order of the expression.

Therefore, in the above grammar, the concrete syntax tree represented by EBNF and the abstract syntax tree output from the parser only roughly match. It is possible to define a grammar so that the abstract and concrete syntax trees have as much of the same structure as possible, but this would make the grammar redundant and make it difficult to understand how to write a parser. The above grammar is an easy-to-use method of expressing grammar that strikes a balance between the rigor of formal grammar description and the ease of understanding supplemented by natural language.

Expressing operator precedence using production rules

Production rules are very powerful tools for expressing grammar. Operator precedence can also be expressed in production rules by devising the grammar. Its syntax is shown below.

expr = mul ("+" mul | "-" mul)*
mul  = num ("*" num | "/" num)*

The previous rule expanded exprdirectly to , but now the rule expands to via . This is the production rule for multiplication and division, and when performing addition and subtraction, is used as a single component. In this grammar, the rule that multiplication and division come first is naturally expressed in the syntax tree. Let's look at some concrete examples.numexprmulnummulexprmul

In the above tree structure, multiplication always appears closer to the end of the tree than addition. In reality, there is no rule to return multo expr``,'' so there is no way to create a tree with addition under multiplication.However, with such a simple rule, priorities can be expressed well as a tree structure. feels quite strange. Readers are encouraged to check that the syntax tree is correct by actually comparing the production rules with the syntax tree.

Productions involving recursion

With generative grammars, recursive grammars can also be written normally. Below is a grammar production rule that adds precedence parentheses to the four arithmetic operations.

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

Comparing the above grammar with the previous grammar, we can see that , or or can now appear numwhere it was allowed before . In other words, in this new grammar, expressions enclosed in parentheses will be treated with the same ``stickiness'' as single numbers. Let's look at an example.primarynum"(" expr ")"

The following tree 1*2is the syntax tree for.

The following tree 1*(2+3)is the syntax tree for.

Comparing the two trees, we can see that only the expansion result of multhe right branch of is different. primaryThe rule that appears at the end of the expansion result primaryis that it can be expanded to a single number or to any expression enclosed in parentheses, which is clearly reflected in the tree structure. . Isn't it a bit impressive that you can also handle parentheses' precedence with such a simple production rule?

recursive descending parsing

Given the production rules of the C language, by expanding them one after another, it is possible to mechanically generate any C program that is correct from the perspective of the production rules. But what we want to do with 9cc is actually the opposite. I am given a C program as a string from an external source, and I would like to know the expansion procedure that results in an input string when expanded, or the structure of the syntax tree that results in a string that is the same as the input.

In fact, for certain types of production rules, if a rule is given, it is possible to mechanically write code to find a syntax tree that matches the sentence generated from that rule. The ``recursive descent parsing method'' described here is one such technique.

As an example, let's consider the grammar of the four arithmetic operations. I will repost the grammar of the four arithmetic operations.

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

The basic strategy when writing a parser using recursive descent parsing is to map each of these nonterminal symbols directly to each function. Therefore, the parser will have three functions expr, mul, and . primaryEach function parses a sequence of tokens as its name suggests.

Let's think about it in concrete terms. The input passed to the parser is a sequence of tokens. Since we want to create and return an abstract syntax tree from the parser, let's define the types of nodes in the abstract syntax tree. The node types are shown below.

// 抽象構文木のノードの種類
typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // 整数
} NodeKind;

typedef struct Node Node;

// 抽象構文木のノードの型
struct Node {
  NodeKind kind; // ノードの型
  Node *lhs;     // 左辺
  Node *rhs;     // 右辺
  int val;       // kindがND_NUMの場合のみ使う
};

lhsrhsmeans left-hand side and right-hand side, respectively

Let's also define a function to create a new node. There are two types of arithmetic operations in this grammar: binary operators that accept left and right sides, and numbers, so we will prepare two functions for each of these two types.

Node *new_node(NodeKind kind, Node *lhs, Node *rhs) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = kind;
  node->lhs = lhs;
  node->rhs = rhs;
  return node;
}

Node *new_node_num(int val) {
  Node *node = calloc(1, sizeof(Node));
  node->kind = ND_NUM;
  node->val = val;
  return node;
}

Now, let's write a parser using these functions and data types. +is -a left associative operator. The function that parses left associative operators is written as a pattern as follows:

Node *expr() {
  Node *node = mul();

  for (;;) {
    if (consume('+'))
      node = new_node(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_node(ND_SUB, node, mul());
    else
      return node;
  }
}

consumeis the function defined in the previous step that reads forward one token in the input and returns true if the next token in the input stream matches the argument.

exprPlease read the function carefully. expr = mul ("+" mul | "-" mul)*You can see that this production rule is mapped directly to function calls and loops. In the abstract syntax tree returned by the above exprfunction, the operators are left associative, meaning that the branches to the left of the returned node are deeper.

exprmulLet's also define the functions used by the function . *Yamo /is a left associative operator, so it can be written using the same pattern. The function is shown below.

Node *mul() {
  Node *node = primary();

  for (;;) {
    if (consume('*'))
      node = new_node(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_node(ND_DIV, node, primary());
    else
      return node;
  }
}

The function call relationship in the code above mul = primary ("*" primary | "/" primary)*corresponds directly to the production rule.

Finally, primarylet's define the function. primarySince it is not a left-associative operator that is primary = "(" expr ")" | numread primaryby .

Node *primary() {
  // 次のトークンが"("なら、"(" expr ")"のはず
  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

  // そうでなければ数値のはず
  return new_node_num(expect_number());
}

Now that we have all the functions, can we really parse the token string? Although it may not be obvious at first glance, you can use this group of functions to properly parse token sequences. As an example, 1+2*3consider the expression .

The first thing to be called expris . exprIt begins reading the input assuming that the expression is the whole (which in this case it is). Then, a function call is made like expr→ mul→ , the token is read, and a syntax tree representing 1 is returned as the return value.primary1expr

Then the expression exprin becomes true, so the token is consumed and is called again. The remaining inputs at this stage are:consume('+')+mul2*3

mulprimaryis called as before and 2reads the token, but this time mulit does not return immediately. mulThe expression in consume('*')becomes true, so calls mulagain and reads the token. The result is a syntax tree representing kara .primary3mul2*3

At the destination expr, the syntax tree representing 1 and 2*3the syntax tree representing 1 are combined 1+2*3to construct a syntax tree representing , which exprbecomes the return value of . 1+2*3In other words , it was parsed correctly .

The diagram below shows the function calling relationship and the tokens read by each function. In the diagram below, there is a layer of , which represents a call to read the entire input 1+2*3. There are two above , but they represent a call to and another that reads .exprexprexprmul12*3mul

A slightly more complex example is shown below. The figure below 1*2+(3+4)shows the function calling relationship when parsing.

For programmers who are not familiar with recursion, recursive functions like the one above may seem confusing. Honestly, even for me, who is supposed to be very familiar with recursion, it feels like a kind of magic that this kind of code works. Recursive code feels strange even when you know how it works, and that's probably what it is. Try tracing the code in your head over and over again to make sure it works properly.

The parsing method that maps one production rule to one function as described above is called "recursive descending parsing." In the above parser, only one token is read ahead to decide which function to call or return, but a recursive descent parser that reads only one token in advance is (1) It is called a parser. Also, a grammar that can be written by an LL(1) parser is called an LL(1) grammar.

stack machine

In the previous chapter, we explained the algorithm for converting a sequence of tokens into an abstract syntax tree. By choosing a grammar that takes operator precedence into account, it is now possible to create an abstract syntax tree whose branches are always at the top of the tree compared to ``ya' *' . How should I convert it to assembly? This chapter explains how./+-

First, let's consider why it cannot be converted to assembly in the same way as addition and subtraction. Compilers that can perform addition and subtraction use RAX as a result register and perform additions and subtractions there. In other words, the compiled program retained only one intermediate calculation result.

However, when multiplication and division are involved, there is no guarantee that there will be only one intermediate calculation result. Consider 2*3+4*5 as an example. In order to perform addition, both sides must be calculated, so 2*3 and 4*5 must be calculated before addition. In other words, in this case, the entire calculation cannot be performed unless two intermediate calculation results can be stored.

A computer called a " stack machine " can easily perform calculations like this . Let's move away from the abstract syntax tree created by the parser and learn about the stack machine.

Stack machine concept

A stack machine is a computer that has a stack as a data storage area. Therefore, in a stack machine, the two basic operations are "pushing onto the stack" and "popping from the stack." A push puts a new element on top of the stack. Pop removes an element from the top of the stack.

Arithmetic instructions in a stack machine operate on the elements at the top of the stack. For example, a stack machine ADDinstruction pops two elements from the top of the stack, adds them, and pushes the result onto the stack (to avoid confusion with x86-64 instructions, the virtual stack machine instruction (written in all capital letters). In other words, ADDis an instruction that replaces two elements at the top of the stack with the single element that results from adding them together.

SUBThe , MUL, DIVinstruction ADDis an instruction that replaces two elements at the top of the stack with a single element obtained by subtracting, multiplying, or dividing them.

PUSHThe instruction shall push the argument elements onto the top of the stack. Although not used here, you POPcan also consider an instruction that removes an element from the top of the stack and discards it.

Now, let's consider calculating 2*3+4*5 using these instructions. Using the stack machine defined above, you should be able to calculate 2*3+4*5 with the following code.

// 2*3を計算
PUSH 2
PUSH 3
MUL

// 4*5を計算
PUSH 4
PUSH 5
MUL

// 2*3 + 4*5を計算
ADD

Let's take a closer look at this code. Assume that the stack already contains some value. The value is not important here, so we display it with a “…”. The stack is assumed to run from top to bottom in the diagram.

The first two PUSHpush 2 and 3 onto the stack, so MULby the time the next one is executed, the state of the stack is as follows:

MULremoves the two values ​​at the top of the stack, 3 and 2, and pushes the product of their multiplication, 6, onto the stack. Therefore, MULafter execution, the state of the stack will be as follows:

The next PUSHone pushes 4 and 5, so MULjust before the second one runs, the stack should look like this:

If you run here MUL, it will remove 5 and 4 and replace them with 20, which is the result of multiplying them. So MULafter running:

Notice how the calculation results for 2*3 and 4*5 are neatly placed on the stack. ADDRunning in this state will calculate 20+6 and push the result onto the stack, so the stack should eventually be in the following state:

If we assume that the stack machine's calculation result is the value remaining at the top of the stack, then 26 is the result of 2*3+4*5, which means that the formula has been calculated correctly.

Stack machines can calculate not only this expression, but any expression that has multiple intermediate results. With the stack machine, any subexpression can be successfully compiled in the above way, as long as it honors the promise that executing it leaves a single element on the stack.

Compile to stack machine

This section describes how to convert an abstract syntax tree into stack machine code. If you can do that, you will be able to parse an expression consisting of four arithmetic operations, assemble an abstract syntax tree, compile it into a stack machine using x86-64 instructions, and execute it. In other words, it will be possible to write a compiler that can perform the four arithmetic operations.

In a stack machine, when you compute a subexpression, one value of the result, whatever it is, remains on the top of the stack. For example, consider the tree below.

A``ya B'' is an abstract representation of a subtree, and actually means a node of some type. However, the specific type or shape of the tree is not important when compiling this entire tree. To compile this tree, do the following:

1. Compile the left subtree
2. Compile the right subtree
3. Outputs code that replaces two values ​​on the stack with the result of adding them together

After executing the code in #1, no matter what the specific code is, there should be a single value on the top of the stack representing the result of the left subtree. Similarly, after running the code in 2, there should be a single value on the top of the stack representing the result of the right subtree. Therefore, in order to calculate the value of the entire tree, we just need to replace those two values ​​with their total value.

In this way, when compiling an abstract syntax tree to a stack machine, we think recursively and output assemblies as we descend the tree. Although it may seem a bit difficult for readers who are not familiar with the concept of recursion, it is a standard technique when working with self-similar data structures such as trees.

Let's consider the example below.

The function that performs the code generation receives the root node of the tree.

Following the steps above, the first thing the function does is compile the left subtree. In other words, we will be compiling the number 2. The result of calculating 2 is 2, so the compilation result of that subtree is PUSH 2.

The code generation function then attempts to compile the right subtree. This will recursively compile the left side of the subtree, and the result PUSH 3will be output. Next we will compile the right side of the subtree, PUSH 4which will output:

The code generation function then returns to the recursive call and outputs code that matches the type of the subtree operator. The first output is code that replaces the two elements at the top of the stack with their product. Next, the code that replaces the two elements at the top of the stack with their sum is output. The result will be the assembly below.

PUSH 2
PUSH 3
PUSH 4
MUL
ADD

Using this method, abstract syntax trees can be mechanically reduced to assembly.

How to create a stack machine on x86-64

So far we have been talking about virtual stack machines. The actual x86-64 is a register machine, not a stack machine. x86-64 operations are usually defined to operate between two registers, not the two values ​​at the top of the stack. So in order to use stack machine techniques on x86-64, you need to emulate the stack machine in some sense with a register machine.

Emulating a stack machine with a register machine is relatively easy. What would be one instruction on a stack machine can be implemented using multiple instructions.

Let's explain a specific method for doing so.

First, prepare one register that points to the top element of the stack. This register is called the stack pointer. If you want to pop the two values ​​at the top of the stack, take the two elements pointed to by the stack pointer and change them by the amount of the element you removed the stack pointer from. Similarly, when pushing, all you have to do is change the value of the stack pointer and write to the memory area it points to.

The x86-64 RSP register is designed to be used as a stack pointer. pushInstructions like `` in x86-64' pop' implicitly use RSP as a stack pointer, modify its value, and access the memory pointed to by RSP. Therefore, when using the x86-64 instruction set like a stack machine, it is straightforward to use RSP as a stack pointer. Now, 1+2let's compile the expression using x86-64 as a stack machine. Below is the x86-64 assembly.

// 左辺と右辺をプッシュ
push 1
push 2

// 左辺と右辺をRAXとRDIにポップして足す
pop rdi
pop rax
add rax, rdi

// 足した結果をスタックにプッシュ
push rax

Since x86-64 does not have an instruction to ``add the two elements pointed to by RSP,'' you need to load them into a register, perform the addition, and then push the result back onto the stack. That's what the above addcommand does.

Similarly, 2*3+4*5if you try to implement it on x86-64, it will look like this:

// 2*3を計算して結果をスタックにプッシュ
push 2
push 3

pop rdi
pop rax
mul rax, rdi
push rax

// 4*5を計算して結果をスタックにプッシュ
push 4
push 5

pop rdi
pop rax
mul rax, rdi
push rax

// スタックトップの2つの値を足す
// つまり2*3+4*5を計算する
pop rdi
pop rax
add rax, rdi
push rax

In this way, by using x86-64 stack manipulation instructions, you can run code that is quite similar to a stack machine even on x86-64.

The following genfunction implements this method as a C function.

void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

  printf("  pop rdi\n");
  printf("  pop rax\n");

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n");
}

Although this is not a particularly important point when it comes to parsing or code generation, the idivcode above uses instructions with a tricky specification, so let's explain them.

idivis an instruction that performs signed division. If x86-64 idivhad a straightforward specification, I idiv rax, rdiwould have written the above code as originally written, but such a division instruction that takes two registers does not exist on x86-64. Instead, idivimplicitly takes RDX and RAX, treats them together as a 128-bit integer, divides it by the 64-bit value of the argument register, puts the quotient in RAX, and puts the remainder in RDX. It is designed to be set to . cqoBy using the instruction, the 64-bit value in RAX can be expanded to 128 bits and set in RDX and RAX, so in the code above, is called before calling idiv.cqo

Well, this concludes the explanation of stack machines. By now, you should be able to perform complex parsing and translate the resulting abstract syntax tree into machine code. Let's go back to writing a compiler to put that knowledge to use!

Step 5: Create a language that can perform four arithmetic operations

In this chapter, we will modify the compiler created in the previous chapters and extend it so that it can handle expressions of four arithmetic operations that include precedence parentheses. All the necessary parts are included, so there is only a small amount of new code to write. mainTry modifying the compiler functions to use the newly created parser and code generator. The code should look like the one below.

int main(int argc, char **argv) {
  if (argc != 2) {
    error("引数の個数が正しくありません");
    return 1;
  }

  // トークナイズしてパースする
  user_input = argv[1];
  token = tokenize(user_input);
  Node *node = expr();

  // アセンブリの前半部分を出力
  printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");

  // 抽象構文木を下りながらコード生成
  gen(node);

  // スタックトップに式全体の値が残っているはずなので
  // それをRAXにロードして関数からの返り値とする
  printf("  pop rax\n");
  printf("  ret\n");
  return 0;
}

At this point, expressions consisting of addition, subtraction, multiplication, and priority parentheses should compile correctly. Let's add some tests.

assert 47 '5+6*7'
assert 15 '5*(9-6)'
assert 4 '(3+5)/2'

For convenience of explanation, up to this point, the flow of the story has been as if , were implemented all at once, but in reality, it would be better to avoid implementing them all at once *. Since there was originally a function that could perform addition and subtraction, first try introducing an abstract syntax tree and a code generator using it without breaking that function. Since we are not adding new functionality at that time, no new tests are needed. After that, please implement , , and including tests./()*/()

Step 6: Unary plus and unary minus

A subtraction -operator can 5-3not only be written between two terms, as in , but also before a single term, as in . -3Similarly, +operators +3can be written by omitting the left-hand side. An operator like this that takes only one term is called a "unary operator. " On the other hand, an operator that takes two terms is called a binary operator.

+In addition to and , there are other unary operators in C , such as -retrieving a pointer &and dereferencing a pointer , but in this step we will only implement and .*+-

Unary +and unary have the same symbol as -binomial +and -, but have different definitions. Binary -is defined as an operation that subtracts the right side from the left side, but -since unary has no left side in the first place, the binary -definition does not make sense as it is. In C, a unary -is defined as an operation that reverses the sign of the right-hand side. A unary +operator is an operator that returns the right-hand side as is. This is an operator that doesn't really need to be used, but it -exists when there is a unary.

+It -is appropriate to think that there are multiple operators with the same name, with similar but different definitions, called unary and binary operators. Whether it is unary or binary depends on the context. The new grammar containing the unary +/ -looks like this:

expr    = mul ("+" mul | "-" mul)*
mul     = unary ("*" unary | "/" unary)*
unary   = ("+" | "-")? primary
primary = num | "(" expr ")"

The new grammar above unaryadds a new nonterminal symbol, and mulnow primaryuses unary, instead of . X?is an EBNF syntax for an element that is optional, i.e. Xoccurs zero or once. unary = ("+" | "-")? primaryAccording to the rule, unarythe nonterminal symbol , +which may -or may not have one , primaryindicates that it is followed by .

-3Check that expressions such as and match the new syntax -(3+5). The syntax tree is shown -3*+5below .-3*+5

Let's change the parser to follow this new grammar. As usual, parser changes should be completed by mapping the grammar directly to function calls. unaryThe function to parse is shown below.

Node *unary() {
  if (consume('+'))
    return primary();
  if (consume('-'))
    return new_node(ND_SUB, new_node_num(0), primary());
  return primary();
}

Here, I decided to replace , and , +xat the parsing stage. Therefore, no code generator changes are required for this step.x-x0-x

This step is completed by writing a few tests and checking them in along with the code that adds the unary +/ . -When writing tests, try to keep the test results in the range 0-255. -10+20An expression like this -uses a single term but the overall value is a positive number, so please use this kind of test.

Step 7: Comparison operators

In this section, we implement , <, <=, >, >=, ==. !=Although these comparison operators appear to have special meaning, +they -are actually ordinary binary operators that take two integers and return one, just like and. +Just as returns the result of adding both sides, for example, ==returns 1 if both sides are the same, and 0 if they are different.

Tokenizer changes

The symbol tokens we've been dealing with so far have all been one character in length, and we've assumed that in our code, but in order to ==handle comparison operators such as , we need to generalize the code. Let's store lena member in a structure so that we can store the length of a string in a token . TokenThe new structure type is shown below.

struct Token {
  TokenKind kind; // トークンの型
  Token *next;    // 次の入力トークン
  int val;        // kindがTK_NUMの場合、その数値
  char *str;      // トークン文字列
  int len;        // トークンの長さ
};

This change requires changes to functions such as and to improve them so that they take strings instead of characters consume. expectHere's an example with some changes:

bool consume(char *op) {
  if (token->kind != TK_RESERVED ||
      strlen(op) != token->len ||
      memcmp(token->str, op, token->len))
    return false;
  token = token->next;
  return true;
}

When tokenizing a symbol that consists of multiple characters, the longer tokens must be tokenized first. For example, if the rest of the string >starts with , if you check the possibility that it starts with without first checking the possibility that strncmp(p, ">=", 2)it is , as in It will be nized.>=>>=>=

new grammar

To add support for comparison operators to the parser, consider what the grammar would look like with the addition of comparison operators. If you write the operators that have appeared so far in order of priority from lowest to highest, it will look like this:

1. == !=
2. < <= > >=
3. + -
4. * /
5. unary +unary-
6. ()

Precedence can be expressed in a generative grammar, where operators with different precedence map to different nonterminals. exprIf we mulconsider the grammar in the same way as , the new grammar with the addition of comparison operators will be as follows.

expr       = equality
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | "(" expr ")"

equalityThe ==dove represents !=, relational, , . These nonterminals can be directly mapped to functions using patterns that parse left-associative operators.<<=>>=

Note that in the above grammar, and are separated equalityto indicate that the entire expression is . I could have written the right -hand side of `` directly on the right-hand side of ``, but I think the above syntax is probably easier to read.exprequalityexprequality

Assembly code generation

On x86-64, comparisons are done using the cmp instruction. The code that pops two integers from the stack, performs a comparison, and sets RAX to 1 if they are identical, and 0 otherwise, looks like this:

pop rdi
pop rax
cmp rax, rdi
sete al
movzb rax, al

The code is a bit voluminous for a short assembly, so let's walk through the code step-by-step.

The first two lines pop the value off the stack. The third line compares the popped values. Where do the comparison results go? On x86-64, the result of a compare instruction is set in a special " flags register ." The flag register is a register that is updated every time an integer operation or comparison operation instruction is executed, and contains bits that indicate whether the result is 0, bits that indicate whether an overflow has occurred, bits that indicate whether the result is less than 0, etc. have.

The flag register is not a normal integer register, so if you want to set the comparison result in RAX, you need to copy the specific bits of the flag register to RAX. Commands do that sete. The instruction sets 1 in the specified register (AL in this case) if the values ​​in the two registers examined by the previous instruction are the same sete. cmpOtherwise set to 0.

AL is a new register name that has not appeared so far in this book, but AL is actually just another register that points to the lower 8 bits of RAX. Therefore sete, when you set a value in AL, RAX will also be updated automatically. However, when updating RAX via AL, the upper 56 bits remain at their original value, so if you want to set the entire RAX to 0 or 1, the upper 56 bits must be cleared to zero. Commands do that movzb. seteIt would be nice if the instruction could write directly to RAX, but since the setespecification is such that only 8-bit registers can be taken as arguments, the comparison instruction uses two instructions like this to set a value to RAX. Become.

seteYou can implement other comparison operators by using other instructions instead of . <So setl, try to <=use setlethen !=.setne

>and >=does not need to be supported by the code generator. Please replace both sides in the parser and read it <as .<=

Separate compilation and linking

Up until this stage, development had proceeded with a file structure consisting of only one C file and one test shell script. There's nothing wrong with this structure, but since the source code is getting longer and longer, I decided to split it into multiple C files to make it easier to read. In this step, we will split one file, 9cc.c, into the following five files.

• 9cc.h: header file
• main.c: mainfunction
• parse.c: parser
• codegen.c: code generator

mainSince the function is small, I could have put it in another C file, but since it doesn't belong to either of these semantically parse.c, codegen.cI decided to separate it into a separate file.

This chapter explains the concept of separate compilation and its significance, and then explains the specific steps.

What is separate compilation?

Separate compilation and its necessity

Separate compilation means writing a program by dividing it into multiple source files and compiling them separately. With split compilation, the compiler reads fragments of the program and outputs the corresponding fragments, rather than the entire program. A file that contains program fragments that cannot be executed on its own is called an " object file " (extension: ). .oIn split compilation, the object files are finally joined together to create a single file. A program that combines object files into one executable file is called a linker.

Let's understand why we need separate compilation. Actually, technically there is no necessity to split the source. If you give the compiler all the source code at once, it is theoretically possible for the compiler to output a complete executable without the aid of a linker.

However, such an approach requires that the compiler really know all the code that the program uses. For example, printfstandard library functions such as are usually functions written in C by the standard library author, but in order to avoid the linking step, it is necessary to provide the source code of such functions as input to the compiler every time. I'm coming. Compiling the same function over and over again is often just a waste of time. Therefore, standard libraries are usually distributed in the form of precompiled object files, so you don't have to recompile them each time. In other words, even a program consisting of one source code is actually using separate compilation as long as it uses the standard library.

Without separate compilation, changing just one line would require recompiling the entire code. Compiling code with a length of tens of thousands of lines can take several tens of seconds. A large project may have over 10 million lines of source code, so if you compile it as a single unit, it will take more than a day. Memory is also required in units of 100 GiB. Such a build procedure is unrealistic.

Another problem is that simply writing all functions and variables in one file makes it difficult for humans to manage.

Separate compilation is necessary for the reasons mentioned above.

The necessity of header files and their contents

With split compilation, the compiler sees only one part of the program's code, but the compiler cannot compile even the smallest piece of the program. For example, consider the following code.

void print_bar(struct Foo *obj) {
  printf("%d\n", obj->bar);
}

In the above code, if you know the type of struct Foo, you can output the assembly corresponding to this code, but otherwise you will not be able to compile this function.

When compiling separately, each C file must contain enough information to compile each individual C file. However, if you write all the code written in separate files, it will no longer be a separate compilation, so you will need to be selective about the information to some extent.

As an example, consider what information needs to be included in order to output code that calls a function in another C file. The compiler requires the following information:

• In the first place, we need information that an identifier is the name of a function.
• The function call code output by the compiler sets the arguments in registers in a certain order and calluses an instruction to jump to the beginning of another function. Depending on the argument type, it may also convert an integer to a floating point number. You should also display an error message if the type or number of arguments is incorrect. Therefore, we need the number of arguments for a function and the types of each argument.
• Whatever happens in the called function will simply return to the caller eventually, so the code of the called function is not needed when compiling the calling function.
• callThe address to jump to is not known when compiling separately, but the assembler outputs an callinstruction to jump to address 0 and writes a message in the object file saying ``The Xth byte of the object file is You can leave the information "Correct by address". The linker looks at this information, determines the layout of the executable file, and then performs binary patching on the program fragments to modify the jump destination address (this operation is called ``relocating''). Therefore, although the name of the function is required for separate compilation, the address of the function is not required.

Putting the above requirements together, { ... }we have enough information to call the function as long as we omit the function body. A function without the body of the function is called a "declaration" of the function. The declaration only tells the compiler the type and name; it does not contain the code for the function. For example, below strncmpis the declaration of:

int strncmp(const char *s1, const char *s2, size_t n);

By looking at the above line, the compiler strncmpcan learn about the existence of and its type. A declaration that includes function code is called a "definition. "

externAdd a keyword that represents the declaration to the function declaration ,

extern int strncmp(const char *s1, const char *s2, size_t n);

However, in the case of functions, declarations and definitions can be distinguished by omitting the function body, so it is not necessary extern.

Note that you only need to know the type of the argument, so the name can be omitted in the declaration, but it is common to write the name in the declaration to make it easier for humans to understand.

Consider struct types as another example. If there are two or more C files that use the same structure, you must write a declaration for the same structure in each C file. If a structure is used only in one C file, other C files do not need to know about its existence.

In C, the declarations needed when compiling other C files are written together in a header file (with the extension ). If you write a declaration in , and write it in another C file that requires it , the line will be replaced with the contents of the file..hfoo.h#include "foo.h"#includefoo.h

typedefetc. are also used to tell the compiler type information. If these are used in multiple C files, they must be written in the header file.

The compiler does not output any assembly when it reads the declaration. A declaration is the information necessary to use a function or variable contained in another file, and does not itself define the function or variable.

Based on the story of split compilation up to this point, you can understand what is actually being done when people say, ``When using , I will write it down as a spell.' printf' #include <stdio.h>The C standard library is passed implicitly to the linker so that the linker printfcan link object files containing function calls to create an executable file. On the other hand, the compiler printfdoesn't know anything about it by default. is not a built-in function, and there is no specification that standard library header files are automatically loaded, so the compiler does not know anything about it printfimmediately after startup. printfFrom this state, by including the header file that comes with the C standard library, printfthe compiler can learn about the existence of and its type, and printfcan compile the function call.

link error

When the object files are finally assembled and passed to the linker, they must contain just enough information to construct the program as a whole.

If a program foocontains only function declarations and no definitions, the individual C files, fooincluding the code that calls them, can be compiled normally. However, when the linker finally tries to create a complete program, there is no fooway to fix it because the address that should be fixed foois missing, resulting in an error.

Errors that occur when linking are called link errors .

Linking errors will also occur if multiple object files contain the same function or variable. As a linker, I don't really know which one to choose if there are duplicates. Duplicate errors like this often occur when you write the wrong definition in a header file. This is because header files are included in multiple C files, so if a header file has a definition, it will be in the same state as having duplicate definitions written in multiple C files. To resolve this kind of error, write only the declaration in the header file, and move the substance to one C file.

Declaration and definition of global variables

Our compiler doesn't yet have global variables, so we don't have assembly examples for them yet, but global variables are almost the same as functions at the assembly level. Therefore, like functions, global variables also have a distinction between definitions and declarations. If the body of a variable is duplicated in multiple C files, it usually results in a linking error.

Global variables are allocated in non-executable memory areas by default, so jumping there will cause your program to crash with a segmentation fault, but other than that there is essentially no difference between data and code. At runtime, you can read the function as data like a global variable, or you can execute the data as code by changing the memory attributes to allow execution and jumping to the data.

Let's verify with some actual code that both functions and global variables are essentially just data that resides in memory. In the code below, mainthe identifier is defined as a global variable. mainThe content is x86-64 machine language.

char main[] = "\x48\xc7\xc0\x2a\x00\x00\x00\xc3";

foo.cLet's save the above C code in a file, compile objdumpit, and check the contents using . objdumpBy default, the contents of global variables are only displayed in hexadecimal, but you -Dcan pass an option to force the data to be disassembled as code.

$ cc -c foo.c
$ objdump -D -M intel foo.o
Disassembly of section .data:

0000000000000000 <main>:
   0:   48 c7 c0 2a 00 00 00    mov    rax,0x2a
   7:   c3                      ret

The default behavior of data being mapped to non-executable areas -Wl,--omagiccan be changed at compile time by passing the option . Let's generate an executable file using this option.

$ cc -static -Wl,--omagic -o foo foo.o

Functions and variables are just labels in assembly and belong to the same namespace, so the linker doesn't care which are functions and which are data when combining multiple object files. So maineven if is defined as data at the C level, mainthe link will succeed just as if is a function.

Let's run the generated file.

$ ./foo
$ echo $?
42

As shown above, the value 42 is correctly returned. mainThe contents of the global variable were executed as code.

In C syntax, if it is a global variable, externit becomes a declaration if you add . Below foois the declaration of a global variable of type int.

extern int foo;

fooWhen writing a program that includes , the above line should be written in the header file. fooThen, define it in one of the C files . Below foois the definition of.

int foo;

Note that in C, global variables for which no initialization expression is given are initialized to 0, so such variables are semantically equivalent to being initialized to 0 , {0, 0, ...}etc. "\0\0\0\0..."Same as .

int foo = 3When writing an initialization expression like this, write the initialization expression only in the definition. A declaration only tells the compiler the type of a variable, so no specific initialization expression is required. Since the compiler does not specifically output assembly when it sees the declaration of a global variable, it does not need to know how its contents are initialized on the spot.

If the initialization expression is omitted, the declaration and definition of a global variable externare simply the presence or absence of the variable, so they look similar, but the declaration and definition are different. Please understand this clearly here.

char main[] = "\xf0\x0f\xc7\xc8";

C standard library and archive files

Step 8: File splitting and Makefile changes

Split files

Try splitting the file using the configuration shown at the beginning of this chapter. 9cc.hThat is a header file. Depending on the structure of the program, one file may be prepared for each file, but there is no particular harm in having extra declarations, so there is no need to manage dependencies in such detail here .c. .hthere is no. 9cc.hPrepare one file and #include "9cc.h"include it in all C files.

Makefile changes

Now that we've changed the program to multiple files, Makefilelet's also update it. The example below Makefilecompiles and links all .c files located in the current directory to create an executable file called 9cc. It is assumed that there is only one file, 9cc.h, as a project header file, and that all .c files include that header file.

CFLAGS=-std=c11 -g -static
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

9cc: $(OBJS)
        $(CC) -o 9cc $(OBJS) $(LDFLAGS)

$(OBJS): 9cc.h

test: 9cc
        ./test.sh

clean:
        rm -f 9cc *.o *~ tmp*

.PHONY: test clean

MakefileNote that the indentation of must be a tab character.

make is a highly functional tool, and you don't necessarily need to be proficient Makefileat using it, but being able to read the above will be useful in many situations. Therefore, in this section Makefilewe will explain the above.

MakefileIn , zero or more command lines separated by colons and indented by tabs constitute a rule. The name before the colon is called the "target." Zero or more file names after the colon are called dependent files.

make fooWhen you run , makeit footries to create a file called . If the specified target file already exists, makereruns the target rule only if the target file is older than the dependent file. This enables behavior such as regenerating binaries only when the source code changes.

.PHONYis a special name used to represent a dummy target. make testAfter all make clean, testI cleandon't do it to create a file, but I don't usually know makethat, so if testthere cleanis a file with a name by accident, make testnothing make cleanwill be done. I'll put it away. .PHONYBy specifying such a dummy target, it does not mean that you really want to create a file with that name, but rather that the rule's command should be executed regardless of whether the specified target file exists or not . makecan be conveyed to .

CFLAGSand SRCSare OBJSvariables.

CFLAGSis a variable recognized by make's built-in rules, and describes the command line options to be passed to the C compiler. Here we are passing the following flags:

• -std=c11: Tell that the source code is written in C11, the latest C standard.
• -g: Output debug information
• -static: Static link

SRCSThe one used on the right side of wildcardis a function provided by make, which is expanded to the file name that matches the function argument. $(wildcard *.c)is currently main.c parse.c codegen.cbeing expanded.

OBJSThe right-hand side uses variable substitution rules to generate a value that replaces .c in SRC with .o. SRCSBecause it main.c parse.c codegen.cis, OBJSit main.o parse.o codegen.obecomes.

With these things in mind, make 9cclet's trace what happens when we run . Since make attempts to generate the target specified as an argument, 9cccreating the file is the final goal of the command (if there is no argument, the first rule is chosen, so in this case 9cc is not specified). (optional). make does this by walking through dependencies and attempting to build missing or outdated files.

9ccA dependent file is a file .cthat corresponds to a file in the current directory .o. .oIf a file remains from a previous run of make .cand has a newer timestamp than the corresponding file, make won't bother running the same command again. Runs the compiler to generate the file only .oif the file does not exist or is .cnewer ..o

$(OBJS): 9cc.hThe rule says that all .ofiles depend on . 9cc.hTherefore, 9cc.hif you change it, all .ofiles will be recompiled.

Functions and local variables

In this chapter, we will implement functions and local variables. We also implement a simple control structure. After completing this chapter, you will be able to compile code like this:

// mからnまでを足す
sum(m, n) {
  acc = 0;
  for (i = m; i <= n; i = i + 1)
    acc = acc + i;
  return acc;
}

main() {
  return sum(1, 10); // 55を返す
}

Although there is still a gap between the above code and C, I think it can be said that it has come quite close to C.

Step 9: One character local variable

Up to the previous chapter, we were able to create a compiler for a language that can perform four arithmetic operations. In this section, we'll add functionality to the language to allow the use of variables. Specifically, the goal is to be able to compile multiple statements containing variables as follows.

a = 3;
b = 5 * 6 - 8;
a + b / 2;

Let's use the result of the last expression as the calculation result for the entire program. I think you could say that this language has a much more ``real language'' feel to it than a language that only uses four arithmetic operations.

In this chapter, we will first explain how to implement variables, and then we will implement variables incrementally.

Variable area on the stack

Variables in C exist in memory. You can say that a variable is a memory address with a name. By naming memory addresses, you can express things like ``accessing a variable'' instead of ``accessing address 0x6080 in memory.' a'

However, a function's local variables must exist separately for each function call. Considering only the convenience of implementation, it seems easy to fix the address, for example, ``place the flocal variable of the function at address 0x6080'', but in that case it will work fine when called recursively. not. In C, local variables are placed on the stack so that each function call has a separate local variable.af

Let's consider the contents of the stack using a concrete example. Suppose you have a function with aa local variable and some other function calls it. The function call instruction puts the return address on the stack, so the top of the stack when is called will contain that return address. In addition to that, it is assumed that the stack originally contains some value. The specific value is not important here, so we will represent it with "...". If you make a diagram, it will look like this:bffcallf

If you create a layout like the one above, you can access both the RSP+8 value aand the RSP value . bThe memory area that is secured for each function call is called a "function frame" or "activation record."

The number of bytes to change in RSP and the order in which variables are placed in the area secured in this way are not visible to other functions, so they are determined appropriately based on the compiler implementation. It's okay.

Basically, local variables are implemented as simple things like this.

However, this method has one drawback, so the actual implementation would use one more register. Recall that in our compiler (and in other compilers as well) RSP may change while the function is running. 9cc pushes/pops the calculation results in the middle of the formula onto the stack using RSP, so the RSP value changes frequently. Therefore, it acannotb

A common way to solve this is to have a register separate from RSP that always points to the start of the current function frame. Such a register is called a ``base register,'' and the value contained therein is called a ``base pointer.'' By convention, x86-64 uses the RBP register as the base register.

The base pointer must not change during function execution (that's why we have a base pointer). You can't just call another function from a function and have a different value when it returns, so you need to save the original base pointer for each function call and write it back before returning. .

The figure below shows the state of the stack when calling a function using a base pointer. Suppose that a function with xlocal variables calls . While running, the stack looks like this:ygfg

In this way, you can always access the address aRBP-8 and RBP-16. bIf we consider specifically the assembly that creates this stack state, the compiler should output the following assembly at the beginning of each function.

push rbp
mov rbp, rsp
sub rsp, 16

The standard instructions that the compiler outputs at the beginning of a function are called a "prologue. " Note that 16 actually needs to be a value that matches the number and size of variables for each function.

Let's confirm that when we execute the above code with RSP pointing to the return address, the expected function frame is created. The stack status for each instruction is shown below.

When returning from a function, write back the original value to RBP, make RSP point to the return address, and call an instruction (the instruction is an instruction that pops an address from the stack and jumps to it ret) ret. . The code to do this can be written simply as follows:

mov rsp, rbp
pop rbp
ret

The standard instructions that the compiler outputs at the end of a function are called an "epilogue. "

The state of the stack when running the epilogue is shown below. The stack area below the address pointed to by RSP can no longer be considered invalid data, so it is omitted in the diagram.

Thus, by executing the epilogue, gthe state of the calling function's stack is restored. callThe instruction callpushes the address of the instruction following itself onto the stack. The epilogue retpops that address and jumps there, causing the function to resume execution callat the next instruction . gThis behavior is completely consistent with the behavior of functions as we know them.

This is how function calls and function local variables are implemented.

Tokenizer changes

Now that you know how to implement variables, let's start implementing them. However, supporting an arbitrary number of variables quickly becomes too difficult, so we decided to limit the variables in this step to a single lowercase letter, so variable is RBP-8, variable is RBP-16, and variable is RBP a- b24 c. , and so on, all variables are assumed to always exist. Since there are 26 characters in the alphabet, if we decide to push down RSP by 26 x 8, or 208 bytes, when calling the function, we will be able to reserve space for all single-character variables.

Let's implement it now. First, let's modify the tokenizer so that it can tokenize single-character variables in addition to the previous grammar elements. To do this, we need to add a new token type. Since the variable name strcan be read from the member, Tokenthere is no need to add a new member to the type. As a result, the token type is:

enum {
  TK_RESERVED, // 記号
  TK_IDENT,    // 識別子
  TK_NUM,      // 整数トークン
  TK_EOF,      // 入力の終わりを表すトークン
} TokenKind;

Modify the tokenizer TK_IDENTto create a token of type if it is a lowercase letter of the alphabet. ifYou should be able to add statements like the following to your tokenizer.

if ('a' <= *p && *p <= 'z') {
  cur = new_token(TK_IDENT, cur, p++);
  cur->len = 1;
  continue;
}

Parser changes

With recursive descent parsing, if you know the syntax, you can mechanically map it to a function call. Therefore, in order to think about changes that should be made to the parser, it is necessary to consider what the new syntax will look like when variable names (identifiers) are added.

identLet's call it an identifier . This numis a terminal symbol, just like . Variables can be used anywhere a number can be used, so if you write num``where was'' num | ident, you get a syntax that allows variables to be used in the same places as numbers.

In addition to that, we need to add an assignment expression to the grammar. Since variables cannot be assigned, a=1we want to create a grammar that allows expressions like . Here, a=b=1let's use a syntax that is compatible with C and can be written as follows.

Furthermore, I would like to be able to write multiple statements separated by semicolons, so the resulting new grammar would be as follows.

program    = stmt*
stmt       = expr ";"
expr       = assign
assign     = equality ("=" assign)?
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | ident | "(" expr ")"

First of 42;all a=b=2; a+b;please check that a program like Hayaya conforms to this grammar. After that, modify the parser you have created so far so that it can parse the above grammar. At this stage, a+1=5expressions like can also be parsed, which is correct behavior. Eliminating such semantically invalid expressions is done in the next pass. There's nothing particularly tricky about modifying the parser, and you should be able to do it just by mapping the grammar elements to function calls as before.

Since we are multiplying multiple expressions by separating them with semicolons, we need to save the multiple nodes as a result of the parsing somewhere. For now, please prepare the following global array and store the parsed result nodes there in order. If you fill the last node with NULL, you will be able to see where it ends. Some of the new code to be added is shown below.

Node *code[100];

Node *assign() {
  Node *node = equality();
  if (consume("="))
    node = new_node(ND_ASSIGN, node, assign());
  return node;
}

Node *expr() {
  return assign();
}

Node *stmt() {
  Node *node = expr();
  expect(";");
  return node;
}

void program() {
  int i = 0;
  while (!at_eof())
    code[i++] = stmt();
  code[i] = NULL;
}

The abstract syntax tree needs to be able to express a new ``node representing a local variable''. To do this, let's add a new type for the local variable and a new member for the node. For example, it should look like this: This data structure ND_LVARcauses the parser to create and return type nodes for identifier tokens.

typedef enum {
  ND_ADD,    // +
  ND_SUB,    // -
  ND_MUL,    // *
  ND_DIV,    // /
  ND_ASSIGN, // =
  ND_LVAR,   // ローカル変数
  ND_NUM,    // 整数
} NodeKind;

typedef struct Node Node;

// 抽象構文木のノード
struct Node {
  NodeKind kind; // ノードの型
  Node *lhs;     // 左辺
  Node *rhs;     // 右辺
  int val;       // kindがND_NUMの場合のみ使う
  int offset;    // kindがND_LVARの場合のみ使う
};

offsetis a member that represents the offset from the local variable's base pointer. Currently, variables aare RBP-8, bRBP-16..., etc., and local variables are in fixed positions determined by their names, so the offset can be determined at the parsing stage. Below ND_LVARis the code that reads the identifier and returns the type node.

Node *primary() {
  ...

  Token *tok = consume_ident();
  if (tok) {
    Node *node = calloc(1, sizeof(Node));
    node->kind = ND_LVAR;
    node->offset = (tok->str[0] - 'a' + 1) * 8;
    return node;
  }

  ...