Dragon and Tiger/C books are the first ones I think about while anybody speaks about compiler implementing.

The advantage of Appel's book is the presence of the manual on using Boehm GC which will be required while we step forward from core C to other languages.

https://www.cs.princeton.edu/~appel/modern/c/

please write example for llvm frontend
and generating normal exe elf file

Firstly,

Thanks for the interesting project, especially for documenting it.

It's not easy to find developers who like to build compilers.

You might find this project interesting:
https://github.com/ApolloVM/apollovm_dart

I am currently in the process of developing the memory allocator that will be employed for object allocation when ApolloVM compiles to WebAssembly.

Best regards.

cg.c line 80

// Load a value from a variable into a register.
// Return the number of the register
int cgloadglob(int id) {
  // Get a new register
  int r = alloc_register();

  // Print out the code to initialise it
  switch (Gsym[id].type) {
    case P_CHAR:
      fprintf(Outfile, "\tmovzbq\t%s(%%rip), %s\n", Gsym[id].name,
	      reglist[r]);
      break;
    case P_INT:
      fprintf(Outfile, "\tmovzbl\t%s(\%%rip), %s\n", Gsym[id].name,
	      reglist[r]);
      break;
    case P_LONG:
    case P_CHARPTR:
    case P_INTPTR:
    case P_LONGPTR:
      fprintf(Outfile, "\tmovq\t%s(\%%rip), %s\n", Gsym[id].name, reglist[r]);
      break;
    default:
      fatald("Bad type in cgloadglob:", Gsym[id].type);
  }
  return (r);
}

When I run this code. It got segment faults. The code above always used 64bit register for any type variables.
Type P_CHAR maybe should use movb instruction to load from global to breglist[r], or use movzbq to reglist[r].
Type P_INT maybe should use movl instruction to load from global to *dreglist[r].

Or if you want to call printint(long), mov dreglist[r] to %rdi, maybe you need instruction cltq.
I think there maybe some errors in this function. It maybe be

// load a value from a variable into a register.
// return the number of the register
int cgloadglob(int id) {
  // get a new register
  int r = alloc_register();

  // print out the code to initialize it
  switch (Gsym[id].type) {
    case P_CHAR:
      fprintf(Outfile, "\tmovzbq\t%s(\%%rip), %s\n", Gsym[id].name, reglist[r]);
      break;
    case P_INT:
      fprintf(Outfile, "\tmovl\t%s(\%%rip), %s\n", Gsym[id].name, dreglist[r]);
      fprintf(Outfile, "\tcltq\n");
      break;
    case P_LONG:
    case P_CHARPTR:
    case P_INTPTR:
    case P_LONGPTR:
      fprintf(Outfile, "\tmovq\t%s(\%%rip), %s\n", Gsym[id].name, reglist[r]);
      break;
    default:
      fatald("Bad type in cgloadglob:", Gsym[id].type);
  }

  return r;
}

Thanks!

First of all: Not really a big deal ;) Just needed some extra time to understand what is going on:

// Return an AST tree whose root is a '+' or '-' binary operator
struct ASTnode *additive_expr(void) {
  struct ASTnode *left, *right;
  int tokentype;
  // Get the left sub-tree at a higher precedence than us
  left = multiplicative_expr();
  // If no tokens left, return just the left node
  tokentype = Token.token;
  if (tokentype == T_EOF)
    return (left);
  // Loop working on token at our level of precedence
  while (1) {
    // Fetch in the next integer literal
    scan(&Token);
    // Get the right sub-tree at a higher precedence than us
    right = multiplicative_expr();
    // Join the two sub-trees with our low-precedence operator
    left = mkastnode(arithop(tokentype), left, right, 0);
    // And get the next token at our precedence
    tokentype = Token.token;
    if (tokentype == T_EOF)
      return (left);
  }

  // Return whatever tree we have created
  return (left);
}

From: https://github.com/DoctorWkt/acwj/tree/master/03_Precedence

I think the last return is never reached because the condition in the while loop is always true and there is nothing else that should trigger a break.

Why I am creating an issue: Maybe I am wrong and there is something that would trigger a break. Just want to double check

PS: Really nice guide overall ! Thanks a lot

I notice that some function will return (1) ,not return 1,why do that?

Hello, I am a developer from China.
Now, i am following your project to study.
I like your project very much.
Excuse me, can I translate and repost your project to my blog.
Looking forward to your reply.
Thanks !

The following 2 lines are updated based on the use of ;

It's better to mention that otherwise may take some time for reader to find the issue

Where is the whole bnf grammar？I need it, thank you! Maybe I am not carefully enough to find it ...

  if (condition is true) 
    perform this first block of code
  else
    perform this other block of code

In readme, you write it like the following.

       perform the opposite comparison
       jump to L1 if true
       perform the first block of code
       jump to L2
L1:
       perform the other block of code
L2:

But there seems some wrong in jump to L1 if true. Do you mean jump to L1 if false ?

Hi, first off I want to say thank you for all the work you've put into this project. I've been following along in my spare time, made it to the end of the book, and have thoroughly enjoyed it. I've added a few features of my own like varargs ... arguments, anonymous unions inside structs, more robust support for '++' and '--' operators (like s.var++ and ++s.var).

In adding these features and changing the codebase, I've uncovered a little issue. Take this example code:

#include <stdio.h>

int mycall(int a, int b, int c, int d, int e) {
  return (1);
}

int main(void) {
  int i;
  i = 10;
  /**
  * Bug in output of next line. Naive solution:
   * for every argument node that contains a function call, we push all argument
   * registers to the stack before generating asm for the call and pop them off after.
   */
  printf("%d, %d, %d\n", i, mycall(1, 2, 3, 4, 5), i); // expect: 10,1,10, got 10,1,4
  return (0);
}

Running this gives improper output as the call to mycall clobbers the argument register rcx used to store the value of the 4th parameter to printf.

I could send a PR but I expect my codebase differs from yours to a large extent now, so it would be easier for you to patch this your way than it would be for me to port the patch over.

Thanks again 😃

after introducing array, code generator for arm seems not changed.
And make armtest,input20 also fails with Segmentation fault.
I guess function cgglobsym in cg_arm.c requires change.

Hi There,
There might be an issue with movzbl in section 15_Pointers_pt1 and onward.
Attaching the issue.15.txt for detail description. Thx!!!
Regards
David
P.S.: I am a newbie hence my report can be totally wrong.

issue.15.txt

I may be missing something here, but I think there's a typo in the code to check function parameters vs a prototype...

It looks as though the type for each argument is matched against the type of the function (Symtable[id].type), not the parameter in the prototype (which would be indexed by param_id)

How does the spilling mechanism ensure that when a register is spilled that that same register isn't needed in the expression with the newly acquired register?
Hypothetical example (I know this would be optimized away): Say we have an expression that requires two free registers and there is only one

1 + 2:
======
movl $1, %r11d
// then lets say %r11 is the next one to be spilled
pushq    %r11
// now the other operand gets loaded into %r11
movl   $2, %r11d
// the add expression now uses the same register twice but it shouldn't
add   %r11d,%r11d
popq  %r11

how does the compiler ensure that this doesn't happen? I couldn't find any code that reloads the value if it's used in an operand. But it could happen that the spilled value is needed in an operation before it is reloaded.
Does the compiler just assume that these cases are rare or are they avoided somehow?

This is probably a problem with my system. Starting from 05_Statements I'm getting the error:

data.h:10:9: error: unknown type name ‘FILE’
   10 | extern_ FILE *Infile;                   // Input and output files
      |         ^~~~
data.h:11:9: error: unknown type name ‘FILE’
   11 | extern_ FILE *Outfile;
      |         ^~~~
data.h:13:19: error: ‘TEXTLEN’ undeclared here (not in a function)
   13 | extern_ char Text[TEXTLEN + 1];         // Last identifier scanned
      |                   ^~~~~~~
data.h:14:30: error: ‘NSYMBOLS’ undeclared here (not in a function)
   14 | extern_ struct symtable Gsym[NSYMBOLS]; // Global symbol table

Can anyone point me to the right direction. Thank you.

Hi again 😺

You're probably aware of this already, but the scanner is too eager with scanning the '-' character as being part of an integer instead of an operand. For example:

#include <stdio.h>

int main() {
  printf("%d\n",1-1); // can't parse this, as scanner scans this as 2 consecutive T_INTLITs
  return (0);
}

Thanks,

Test failed from 13-20.

The error message is
incorrect register %r8' used with l' suffix

It seems that movzbl can only use 32-bit registers?

int cgloadglob(int id) {
//...
    case P_INT:
      fprintf(Outfile, "\tmovzbl\t%s(\%%rip), %s\n", Gsym[id].name,
	      reglist[r]);
//...

should reglist[r] be changed to dreglist[r] ?
The test passed when I made this change

I believe the precedence of arithmetic operations must have greater value than
ones of comparison operator. (In OpPrec[])

For example, if input was,

print 1 + 2 < 4

then the output assembly is,

	.text
.LC0:
	.string	"%d\n"
printint:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	%edi, -4(%rbp)
	movl	-4(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC0(%rip), %rdi
	movl	$0, %eax
	call	printf@PLT
	nop
	leave
	ret

	.globl	main
	.type	main, @function
main:
	pushq	%rbp
	movq	%rsp, %rbp
	movq	$1, %r8
	movq	$2, %r9
	movq	$4, %r10
	cmpq	%r10, %r9
	setl	%r10b
	andq	$255,%r10
	addq	%r8, %r10
	movq	%r10, %rdi
	call	printint
	movl $0, %eax
	popq %rbp
	ret

As you can see, they calculate 1 + (2 < 4), not (1 + 2) < 4

Both lines should be changed to

 if (Gsym[i].stype == S_VARIABLE || Gsym[i].stype == S_ARRAY)

should be changed to

 case 1:
 case 4:
    fprintf(Outfile, "%s:\n\t.zero\t%d\n", Gsym[id].name, Gsym[id].size * typesize);
    break;

Hi, thanks for creating this git. I have learned a lot from reading through here. I don't usually use Linux so learning makefile and compiling/linking is difficult. I am using vs to write the files and ubuntu with gcc under windows to follow along and compile. I am having trouble understanding how you are linking the input27b.c and the relation. The input27a.c should be the source file right, that gets turned into out.s which is the assembly(gas) of our source, then how is input27b.c and printint.c connected?? you never went into how this works.

I am using source.txt as input27a.c. and renamed input27b.c to params.c. I am getting all kinds of errors in the terminal that says not referenced. Basically linking problem. I know that comp1 is our program and its reading the source. I had no problem with my makefile until this tutorial. it would link the printint.c in the earlier tutorials and hasnt caused any problems until I tried linking the input27b.c(params.c) file.

Any help would be appreciated!!!

This project is excellent! I learn a lot from it. But I am curious why not generate intermediate code in your project? Will it look a little "incomplete" ?

After introducing new tokens, many places need modification of course.
It's not hard for someone to realize we need to change defs.h and scan.c, but some files are easily ignored at first.

For example the following change, this one really took me a lot of time to figure out why my code wasn't working as expected 😭

The variable breglist is declared here but not mentioned, and just shows up from nowhere in the doc.

IMO it would better to mention the b-suffix somewhere before breglist appears in the journey.

For example, the global symbol table has a max number of entries, I've been implementing everything dynamically and reallocing as necessary, however I am worried that I have missed some important reason for statically allocating memory.

When running the below code, it results in an infinite loop. The increment expression isn't evaluated when the continue jumps to the start of the loop. I've fixed this is in my version of the compiler by giving for statements their own A_FOR node, and generating an Lnext label that's passed on to the statement body as a start label. This label is generated at the bottom of the compound statement before the generation of the code for the increment expression.

#include <stdio.h>
int main() {
  int i;
  for (i = 0; i < 10; i++) {
    if (i == 5) {
      continue;
    } else {
      printf("i: %d\n", i);
    }
  }
  printf("i: %d\n", i);
  return (0);
}

Hi, thanks for the excellent content of the book! I have really learned a lot from it.

However, when I was reading Part 3: Operator Precedence, the error message came from input03 confused me.

syntax error on line 1, token 5          # input03 result

According to the code in expr.c, token 5 should stand for token type = T_INTLIT (in this case, which is 5 in enum). The error message is a little misleading for me since it's unaligned to other common error messages.
Will it be better if set the error message to syntax error on line 1 token 2, token type 5 by adding a global variable to track the pointed token?

Same issue also on

Thanks again😃

Thank you for sharing your course. I am sophomore student,what prerequisite knowledge should i have?

Trying to compile this code:

struct node
{
        int count;
        struct node *left;
} words[14];

Makes cwj (at least the one from chapter 62) hang forever. This seems to be caused by cgglobsym having an inner loop accidentally use the same i for looping, overwriting the value of the one intended for the outer loop (and since the loop bound for the inner loop is lower than the outer loop's bound, i will never reach the outer loop's bound).

Firstly, thank you for sharing this great compiler writing jounery, I'm rather interested!

I'm in chapter 4 (generating assembly code), and trying to follow the code.

Here's the out assembly codes (saved in file "out.s"):

	.text
LC0:
	.string	"%d\n"
_printint:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$16, %rsp
	movl	%edi, -4(%rbp)
	movl	-4(%rbp), %eax
	movl	%eax, %esi
	leaq	LC0(%rip), %rdi
	movl	$0, %eax
	call	printf@PLT
	nop
	leave
	ret

	.globl	_main
_main:
	pushq	%rbp
	movq	%rsp, %rbp
	movq	$2, %r8
	movq	$3, %r9
	movq	$5, %r10
	imulq	%r9, %r10
	addq	%r8, %r10
	movq	$8, %r8
	movq	$3, %r9
	movq	%r8,%rax
	cqo
	idivq	%r9
	movq	%rax,%r8
	subq	%r8, %r10
	movq	%r10, %rdi
	call	_printint
	movl	$0, %eax
	popq	%rbp
	ret

When running it with

cc -o out out.s

, it complained with

out.s:13:2: error: unsupported symbol modifier in branch relocation
 call printf@PLT
 ^

How is the error happened and how to fix it?

Thanks in advance!

PS:

1. I am using macOS Catalina 10.15.2
2. cc version is

Apple clang version 11.0.0 (clang-1100.0.33.17)
Target: x86_64-apple-darwin19.2.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

3. The souce codes are compiled with
   cc -o comp1 -g cg.c expr.c gen.c main.c scan.c tree.c

My test file demo.c are as follow.

int main()
{
    int a;
    char c;
    a = 1;
    c = a;
    return (1);
}

I run make, then excute command ./compl ./demo.c.
Output displays Segmentation fault.

I guess some bugs in in function binexpr() of file expr.c.

      // Ensure the right's type matches the left
      right = modify_type(right, left->type, 0);
      if (left == NULL)        // <-  bug
        fatal("Incompatible expression in assignment");

correct it if (right == NULL), and then the program run correctly.

the comparison operators have higher precedence than multiply and divide?

The expression '10 * 3 > 2 * 5' means '10 * 1 * 5= 15' ???

I don't agree with that. C Operator Precedence table is in descending precedence. That means comparison operators has lower precedence than mul and div.

int foo;
void foo();

On GCC, this gives:

test.c:2:6: error: ‘foo’ redeclared as different kind of symbol
    2 | void foo() {}
      |      ^~~
test.c:1:5: note: previous declaration of ‘foo’ with type ‘int’
    1 | int foo;
      |     ^~~

cwj compiles the file without an error when it probably should error (it already errors if, say, the second declaration is char foo;, so it seems easy to do this with a function redefinition too)

https://github.com/DoctorWkt/acwj/blob/14e9397369dcd428ee7ba6dcf290407403f4c4e7/08_If_Statements/cgn.c#L157C68-L157C68

movzb cannot be recognised by nasm, it should be substituted by movzx according to the nasm doc.

MOVZX            reg16,mem                386 
MOVZX            reg16,reg8               386 
MOVZX            reg32,rm8                386 
MOVZX            reg32,rm16               386 
MOVZX            reg64,rm8                X86_64,LONG 
MOVZX            reg64,rm16               X86_64,LONG 

What I got

# make test2
cc -o parser2 -g expr2.c interp.c main.c scan.c tree.c
(./parser2 input01; \
 ./parser2 input02; \
 ./parser2 input03; \
 ./parser2 input04; \
 ./parser2 input05)
15
29
syntax error on line 1, token 1
Unrecognised character . on line 3
Unrecognised character a on line 1

And what is in Readme

The parser2's result on input03 is with a wrong token type, it should be 5, not 1. The following is the content of input03

12 34 + -56 * / - - 8 + * 2

Now the parse2 reports error on token + whose enum value equals 1. It should reports on 34 instead, with enum value 5, because the position of which shoude be an operator.

On the preceding code, the operator is checked after parsing the right sub tree. I think the check action should be done first with this code to get a right result.

 // Loop working on token at our level of precedence 
 while (1) { 
   // Check if the middle position is an operator
   int precedence = arithop(tokentype);

   // Fetch in the next integer literal 
   scan(&Token); 
  
   // Get the right sub-tree at a higher precedence than us 
   right = multiplicative_expr(); 
  
   // Join the two sub-trees with our low-precedence operator 
   left = mkastnode(precedence, left, right, 0); 

In the file cg.c at the line 176 you defined the following array for the inverted jump instructions:

// List of inverted jump instructions,
// in AST order: A_EQ, A_NE, A_LT, A_GT, A_LE, A_GE
static char *invcmplist[] = { "jne", "je", "jge", "jle", "jg", "jl" };

I think you inverted the jump instructions for greater/less than and greater/less equal.

In your code A_LT defines his inverse as "jge" and A_LE as "jg" and the same is with A_GT and A_GE which are respectively defined as "jle" and "jl".

Looking on various documentation online you can find that JL is defined as Jump short if Less and JLE as Jump short if Less or Equal. The same applies for the greater than/equal jumps, JG and JGE.

This means you defined the inverse for A_LT (less than) the jump if less or equal than and for A_LE (less equal) the jump if less than. As mentioned above the same error is done for the greater than/equal jumps.

The array should then be corrected as following:

// List of inverted jump instructions,
// in AST order: A_EQ, A_NE, A_LT, A_GT, A_LE, A_GE
static char *invcmplist[] = { "jne", "je", "jg", "jl", "jge", "jle" };

I've looked through all the parts of the tutorial and the error is still present in the last part (62 Cleanup).

There is no need to call freestaticsyms() in do_compile() function. Because we already had clear_symtable() before we parse the source file. And clear_symtable() will clear all syms in Globhead chain.

In part 17 it says at the bottom: "our test program that doesn't work". Does this get fixed in another part? Wondering if I can move on and it get fixed or if I need to continue fixing something here. When doing part 17 it broke a previous test. It has a problem with longs in the print statement of test 11 and I wondered if whatever caused test 16 to not work was of the same problem. The only two tests that do not work are 11 and 16 right now so it looks hopeful. Someone should put a disclaimer on all the tutorials that are not complete without further parts so we know which ones compile without errors. I looked into the next part to see if anything was mentioned to fix the doesn't work test of 16 but nothing was mentioned unless I didn't read far enough.

In expr.c file:

static struct ASTnode *primary(void) {
...
id = findglob(Text);
if (id == -1)
fatals("Unknown variable", Text);

if (Gsym[id].stype == S_ARRAY)
    n = mkastleaf(A_ADDR, Gsym[id].type, id);
else if (Gsym[id].stype != S_VARIABLE)
    fatals("Wrong stype of identifier", Text);

...
}

I tired to port the compiler to Windws but there are some errors:

Generated out.s does not compile correctly on Windows.

GAS(the AT&T asm) on Windows don't work identical, it have a little difference about psedo-ops. So I wrote a cg.c for NASM.

It passes the compiling stage, but it still faces a runtime error.
It seems because of something called shadow storage on Windows:

The x64 Application Binary Interface (ABI) uses a four-register fast-call calling convention by default. Space is allocated on the call stack as a shadow store for callees to save those registers.
https://docs.microsoft.com/en-us/cpp/build/x64-calling-convention?view=msvc-170

the x64 calling convention on Windows it very different (and hard to understand for me), do you have any idea on fixing this?

Under the context of https://github.com/DoctorWkt/acwj/tree/master/12_Types_pt1#building-binary-expressions-comparing-types:

...
// Same types, they are compatible
  if (*left == *right) { *left = *right = 0; return (1);
  }
  // Voids not compatible with anything
  if ((*left == P_VOID) || (*right == P_VOID)) return (0);
...

What if left == right and left/right is void? Isn't void incompatible with anything (including itself)?

I am having problems with the if statement printing out the lower number as shown in read me. I am using the ex. input given.

What I don't get is that in the main function, it calls compound statements. In compound, we have the option for T_INT which would call the variable declaration function. which is actually just initializing not declaring.
int i;

so there is no need for assignment at this point of course.

In the compound is the T_IDENT which calls the assignment function which we need for declaring but there is no relation to the actual T_INTLIT.

i = 6;

or am I missing something???

1. if (!inttype(ltype) && !ptrtype(rtype)) should be if (!inttype(rtype) && !ptrtype(rtype)) in modify_type().
2. Now now should be Not now in README file.

test