The Toolchain

What make is for

Your compiler is nine source files that produce eight intermediate files and one executable. Rebuilding all of it after changing one line is slow and, worse, it is the kind of slow that makes you stop rebuilding. make reads a description of what depends on what, compares timestamps, and re-runs only the commands whose inputs have changed.

The anatomy of a rule

target : prerequisites
<TAB>recipe

Three parts. The target is a file to be produced. The prerequisites are the files it is made from. The recipe is the shell command that makes it. make runs the recipe when the target is missing, or when any prerequisite is newer than the target.

ast.o : ast.c ast.h
	gcc -g -Wall -c ast.c

Makefile:12: *** missing separator.  Stop.

Variables

CC     = gcc
CFLAGS = -g -Wall
OBJS   = lex.yy.o parser.tab.o main.o ast.o symtab.o semantic.o codegen.o tac.o

minicompiler : $(OBJS)
	$(CC) $(CFLAGS) -o minicompiler $(OBJS)

Defined with =, used with $(NAME). Worth doing for anything repeated: changing CFLAGS in one place then applies to every compile.

Automatic variables

Inside a recipe, make defines several variables for you. Three are worth knowing:

ast.o : ast.c ast.h
	$(CC) $(CFLAGS) -c $< -o $@

Pattern rules

One rule for a whole class of files. % matches any stem:

%.o : %.c
	$(CC) $(CFLAGS) -c $< -o $@

That single rule builds every .o from its .c. You still add specific rules to declare extra prerequisites — header files, mostly — and the two combine:

semantic.o : semantic.c semantic.h ast.h symtab.h trace.h

Note there is no recipe on that line: it adds prerequisites to the target, and the pattern rule supplies the command. Getting the header dependencies right is what makes make rebuild correctly after you edit an .h file — and getting them wrong produces the maddening bug where the build succeeds but the binary behaves as though your change never happened.

Phony targets

Some targets are not files. clean never produces a file called clean, so if a file by that name ever appeared, make clean would decide there was nothing to do. Declaring it phony prevents that:

clean :
	rm -f $(TARGET) $(OBJS) lex.yy.c parser.tab.c parser.tab.h

.PHONY : all clean test

The course Makefile, line by line

Here is what your compiler's Makefile is actually saying:

CC     = gcc                     # the compiler to use
LEX    = flex
YACC   = bison
CFLAGS = -g -Wall                # debug symbols, and all warnings

TARGET = minicompiler
OBJS   = lex.yy.o parser.tab.o main.o ast.o symtab.o semantic.o codegen.o tac.o

all : $(TARGET)                  # the DEFAULT target — first in the file

$(TARGET) : $(OBJS)              # link everything into the executable
	$(CC) $(CFLAGS) -o $(TARGET) $(OBJS)

lex.yy.c : scanner.l parser.tab.h   # NOTE the second prerequisite
	$(LEX) scanner.l

parser.tab.c parser.tab.h : parser.y
	$(YACC) -d parser.y

Errors, and what they mean

Flags worth knowing

make            # build the first target
make test       # build and run a named target
make clean      # delete what make produced
make -n         # DRY RUN: print the commands without running them
make -B         # rebuild everything, ignoring timestamps
make -j4        # run four recipes at once — exposes missing dependencies
make -d         # explain every decision (very verbose)

make -n is the one to reach for when a build does something you did not expect: it shows exactly which commands would run, in order, without running them.

The mental model

Git confuses people because four different places hold your work, and most commands move things between two of them. Learn the four and most of the confusion goes away.

git status reports where everything currently sits. When something is confusing, run it first — it is the single most useful command in Git, and it usually suggests the command you want next.

First-time setup

git config --global user.name  "Your Name"
git config --global user.email "you@example.com"
git config --global init.defaultBranch main

The name and email are stamped into every commit you make, permanently. Set them before your first commit rather than after.

The daily loop

git status                    # what has changed?
git add ast.c ast.h           # stage specific files
git add -A                    # or stage everything, including deletions
git commit -m "add createBinOp and wire it into the grammar"
git push                      # send commits to GitHub

git pull                      # get teammates' commits before you start work
git log --oneline -10         # recent history
git diff                      # what have I changed but not staged?
git diff --cached             # what is staged and about to be committed?

What must never be committed

Build artifacts. They are large, they change on every build, and they conflict constantly because everyone's differ. In this course that means:

*.o                 # object files
minicompiler        # the executable
lexer
lex.yy.c            # generated by flex — regenerate, do not store
parser.tab.c        # generated by bison
parser.tab.h
parser.output
*.s                 # assembly your compiler emitted while testing
*.tac
.DS_Store

Put those in a file named .gitignore at the top of the repository and commit that. One is provided in your starter code.

git rm --cached minicompiler
git rm -r --cached *.o
git commit -m "stop tracking build artifacts"

Check what you are about to publish before you push:

git ls-files | grep -E '\.o$|minicompiler|lex\.yy\.c|parser\.tab\.'

Anything that prints is tracked and should not be.

Working as a CLC team

Your assignment requires a private repository with the instructor added as a collaborator. The setup, once, by one team member:

1. Create the repository on GitHub — the green New button, or gh repo create team-compiler --private. Choose Private.
2. Add your teammates and the instructor. Repository → Settings → Collaborators → Add people. They each get an email invitation which they must accept.
3. Push the starter code:

   cd student/topic-2-minimal-compiler
   git init
   git add -A
   git commit -m "starter code"
   git branch -M main
   git remote add origin https://github.com/YOURNAME/team-compiler.git
   git push -u origin main

4. Everyone else clones it:

   git clone https://github.com/YOURNAME/team-compiler.git

Dividing the work

Divide by phase, not by file. Each phase has a clean interface, so each person owns a boundary, can work without blocking the others, and has something coherent to explain in their video. Dividing by file gives everyone a piece of everything and nobody an account of anything.

Merge conflicts

Two people changed the same lines. Git stops and marks the file:

<<<<<<< HEAD
    $$ = createBinOp('+', $1, $3);
=======
    $$ = createBinOp('+', $1, $3); free($2);
>>>> origin/main

Everything between <<<< and ==== is yours; everything between ==== and >>>> is theirs. Edit the file so it contains what you actually want — often a combination — delete all three marker lines, then:

git add parser.y
git commit

Undoing things

Authentication

GitHub stopped accepting passwords over HTTPS in 2021. Two options:

Commit messages

Your commit history is evidence of how the work was divided, and a single commit named final is evidence of the opposite. A usable message says what changed and why:

bad:   update
       fixed stuff
       asdf

good:  add array indexing to the grammar and AST
       fix $ra not being saved, which broke all nested calls
       add zero-iteration test for while; it was passing by luck

What flex does

You give it patterns and actions; it writes a C function called yylex() that reads characters and runs the action of whichever pattern matches. The theory — regular expressions, NFA, DFA, and the two rules that break ties — is in the Topic 1 lecture notes. This is the mechanics.

The three sections

%{
  /* C code copied verbatim near the top of lex.yy.c:
     includes, globals, helper functions the actions call */
#include "parser.tab.h"
%}

%option noyywrap
%option yylineno

digit   [0-9]
letter  [a-zA-Z_]
id      {letter}({letter}|{digit})*

%%
"int"        { return INT; }
{id}         { yylval.str = strdup(yytext); return ID; }
[ \t\n]+     { /* skip whitespace: no return, so scanning continues */ }
.            { fprintf(stderr, "bad character '%s'\n", yytext); }
%%

/* user code: copied verbatim to the bottom */

Writing rules

A rule is a pattern, whitespace, then an action in braces. Two hard formatting rules:

• The pattern must start in column 1. An indented line in the rules section is treated as C code to be copied out, not as a rule.
• The action must start on the same line as the pattern.

Patterns

Quote anything with punctuation in it. "+" matches a plus sign; a bare + is the one-or-more operator and will not do what you want.

What an action can use

Options

Columns, which flex does not track

yylineno is maintained for you. Columns are not, and a line number alone is not an exact location on a line holding three statements. Keep a counter yourself, and advance it in every action — including the ones that produce no token:

static int col = 1;

static void advance(const char *s, int n) {
    for (int i = 0; i < n; i++) {
        if (s[i] == '\n')      { col = 1; }
        else if (s[i] == '\t') { col += 4; }
        else                    { col++; }
    }
}

Forget to call it from the block-comment rule and every line number after the first multi-line comment is wrong — with no error to tell you.

Talking to bison

The two tools meet in one file. Bison's -d flag writes parser.tab.h, which defines the token numbers and the yylval union. The scanner includes it:

%{
#include "parser.tab.h"
%}

This is why the Makefile makes lex.yy.c depend on parser.tab.h, and why running flex before bison on a clean tree fails with undeclared identifiers.

Debugging a scanner

flex scanner.l              # writes lex.yy.c
flex -d scanner.l           # trace: prints every rule that fires

Or simply put a printf in the actions temporarily. The instructor's Topic 1 lexer prints a token table, which is the same idea made permanent — and a token table is by far the fastest way to see what your scanner is actually doing.

What bison does

You give it a grammar with actions; it writes a C function called yyparse() that calls yylex() for tokens and runs your action each time it recognizes a rule. The theory — context-free grammars, shift-reduce parsing, LALR, and where conflicts come from — is in the Topic 2 lecture notes. This is the mechanics.

The four sections

%{
  /* C copied verbatim: includes, globals, forward declarations */
#include "ast.h"
extern int yylex(void);
void yyerror(const char *s);
ASTNode *root = NULL;
%}

%union {                       /* the possible types of a symbol's value */
    int num;
    char *str;
    struct ASTNode *node;
}

%token <num> NUM               /* NUM carries an int   */
%token <str> ID                /* ID carries a string  */
%token INT PRINT               /* these carry nothing  */
%type  <node> expr stmt        /* non-terminals carry AST nodes */

%left '+' '-'                  /* precedence, lowest first */
%left '*' '/'

%%
stmt : ID '=' expr ';'   { $$ = createAssign($1, $3); free($1); }
     ;
expr : expr '+' expr     { $$ = createBinOp('+', $1, $3); }
     | NUM               { $$ = createNum($1); }
     ;
%%

void yyerror(const char *s) { fprintf(stderr, "line %d: %s\n", yylineno, s); }

$$ and $1: where values come from

Inside an action, $n is the value of the nth symbol on the right of the rule, and $$ is the value this rule produces. Count the symbols including the punctuation:

stmt : ID   '='   expr   ';'
       $1    $2     $3     $4     ->  $$

The types come from the %union and the %token / %type declarations. If you forget to declare a non-terminal's type, you get:

$$ of 'expr' has no declared type

The fix is a %type <node> expr line. This is the second most common bison error after conflicts.

Precedence and associativity

%left  '+' '-'      /* declared FIRST  = binds loosest */
%left  '*' '/'
%right UMINUS       /* declared LAST   = binds tightest */

• Later declarations bind tighter. The order of these lines is the entire precedence specification.
• %left makes a - b - c group as (a - b) - c; %right would give a - (b - c), which is a different number.
• %nonassoc makes a < b < c a syntax error rather than something surprising.

%prec

A rule takes the precedence of its last terminal, which is wrong for unary minus — the rule '-' expr would inherit binary minus. %prec overrides it:

expr : '-' expr %prec UMINUS   { $$ = createBinOp('u', $2, NULL); }

Conflicts

A shift/reduce conflict means the parser reached a point where it could either take another token or complete a rule, and one token of lookahead does not decide. Bison shifts, warns, and carries on. A reduce/reduce conflict means two rules could both be completed — nearly always a genuine grammar bug.

bison -d -v parser.y        # -v writes parser.output

Open parser.output and find the state named in the warning. It shows the items — productions with a dot marking how much has been seen — and exactly which two actions competed:

State 42

    stmt -> IF '(' expr ')' stmt .          [ELSE]
    stmt -> IF '(' expr ')' stmt . ELSE stmt

    ELSE  shift, and go to state 57
    ELSE  [reduce using rule 12 (stmt)]

The bracketed action is the one bison discarded. Learning to read this once saves an evening in Topic 5, where the dangling-else conflict arrives on schedule.

Error recovery

error is a built-in token that matches wherever the parser is lost. An error production catches the mistake in a rule that knows what was being parsed, so it can say something useful:

assign : ID '=' expr ';'    { $$ = createAssign($1, $3); free($1); }
       | ID '=' expr error  { fprintf(stderr,
                                "line %d: missing ';' after assignment to '%s'\n",
                                yylineno, $1);
                              free($1); $$ = NULL; yyerrok; }
       ;

yyerrok tells bison to resume normal parsing rather than staying in error mode. Without it, the next few real errors are suppressed.

Debugging a parser

%define parse.trace          /* in the declarations section */

/* then, in main.c: */
extern int yydebug;
yydebug = 1;

This prints every shift, every reduce, and every state transition. It is verbose and it is the fastest way to find out why a particular input is not parsing the way you expect — you can watch the stack in the trace and compare it against the shift-reduce table in the Topic 2 notes.

Errors, and what they mean