Compiler Basics
Compilers
COP-3402

Can your processor run C code?

gcc -o hello hello.c
./hello

gcc takes source code and converts it to a runnable program.

Two main implementation techniques

Compilers and Interpreters

The compiler translates your source instructions to machine code.

The machine code should have the same outputs that the source program would.

The interpreter simulates the actions of the source instructions.

The interpreted program should have the same outputs that the source program would.

Getting "1+2" to run on our machine.

Translate "1+2" to machine code.

// read the source code
char left = getchar();
char operator = getchar();
char right = getchar();

// generate assembly code that performs the addition
if ('+' == operator) {
  printf("  mov $%c, %%rax\n", left);
  printf("  mov $%c, %%rbx\n", right);
  printf("  add %%rbx, %%rax\n");  // print the addition instruction
}

Interpret the result of "1+2".

// read the source code
char left = getchar();
char operator = getchar();
char right = getchar();

// compute the result of the addition
if ('+' == operator) {
  int leftnum = left - '0';
  int rightnum = right - '0';
  int result = leftnum + rightnum;  // perform addition
  printf("%d\n", result);
}

• Compiler program: prints out the machine code for addition
• Interpreter program: perform the addition operation

Interpreting exponents, e.g., "2^8"?

No machine instruction or C instruction for exponentiation.

read left operand
read right operand
read operator

if operator == "^":
  result = 1
  for i = 1 to right operand:
    result = result * left operand
  print result

language.c

/**
  gcc -o language language.c
  echo "1+2" | ./language
  echo "2^8" | ./language
*/

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

#define CHAR2INT(c) ((c) - '0')

int main() {
  char left = getchar();
  char operator = getchar();
  char right = getchar();

  printf("input: %c%c%c\n", left, operator, right);

  printf("compiler\n");
  switch (operator) {
  case '+':
    printf("  mov $%c, %%rax\n", left);
    printf("  mov $%c, %%rbx\n", right);
    printf("  add %%rbx, %%rax\n");
    break;
  case '^':
    printf("  mov $%c, %%rbx\n", left);
    printf("  mov $%c, %%rcx\n", right);
    printf("  mov $1, %%rax\n");
    printf("loop:\n");
    printf("  cmp $0, %%rcx\n");
    printf("  jle end\n");
    printf("  imul %%rbx, %%rax\n");
    printf("  sub $1, %%rcx\n");
    printf("  jmp loop\n");
    printf("end:\n");
    break;
  }
  printf("\n");

  printf("interpreter\n");
  int leftnum = CHAR2INT(left);
  int rightnum = CHAR2INT(right);
  int result;
  switch (operator) {
  case '+':
    result = leftnum + rightnum;
    printf("%d\n", result);
    break;
  case '^':
    result = 1;
    for (; rightnum > 0; rightnum--) {
      result *= leftnum;
    }
    printf("%d\n", result);
    break;
  }
}

If you want to learn more about how programming languages are defined and implemented.

(Diagram)

Many compilers use an intermediate language

Dragon book

• Moon vs. finger pointing at the moon
• "The map is not the territory"

• od
• gcc -S
• ASCII table

"The boy went to the store"

• One sentence type:
  • subject phrase, verb phrase, object phrase

Syntactic structure captures relationships between words

"The boy leaving behind his friend went to the store."

"The store is closed"

"Squirrels store acorns for the winter".

9 + 3 - 2

What is the assembly code version of "9 + 3 - 2"?

• Post order traversal
• Leaf nodes: value of the number symbol
• Inner nodes: value is result of operation on child values

1 + 2 * 3

How is source code represented?

Parsing infers structure using word order and groupings

Define what we need by syntax

• Words or tokens
• What you see or hear, e.g., C source code

• Names of syntactic structures, e.g., verb phrase, expression, function definition
• Not uttered explicitly

• Rules mapping nonterminals to their contents
• Defines legal groupings of symbols in the language
• Written using an arrow nonterminal -> symbol1 symbol2 ...

• The first nonterminal in the syntax tree

• For example, E -> E + num
  • Expressions may contains other expressions
  • E.g., 9 + 3 - 2 nests 9 + 3 inside of the subtraction operation

E -> E + E
E -> E - E
E -> E * E
E -> E / E
E -> N
N -> 0
N -> 1
N -> 2
N -> 3
N -> 4
N -> 5
N -> 6
N -> 7
N -> 8
N -> 9

• Find a sequence of rule applications that
  • Begins with the start symbol
  • Ends with the string

• Assume we have the following interpreter functions implemented
  • add, sub, mult, div to perform addition, subtraction, multiplication, and division computations
  • ascii2int to convert the ASCII character value to an integer represetation

Define computation for each grammar construct

E -> E + E  { E.value = add(E1.value, E2.value) }
E -> E - E  { E.value = sub(E1.value, E2.value) }
E -> E * E  { E.value = mult(E1.value, E2.value) }
E -> E / E  { E.value = div(E1.value, E2.value) }
E -> N      { E.value = ascii2int(N.value) }
N -> 0      { N.value = "0" }
N -> 1      { N.value = "1" }
N -> 2      { N.value = "2" }
...
N -> 9      { N.value = "9" }

Assume we have string concat function to join any number of strings.

E -> E + E  { E.value = concat(E1.value, E2.value, "+") }
E -> E - E  { E.value = concat(E1.value, E2.value, "-") }
E -> E * E  { E.value = concat(E1.value, E2.value, "*") }
E -> E / E  { E.value = concat(E1.value, E2.value, "/") }
E -> N      { E.value = N.value }
N -> 0      { N.value = "0" }
N -> 1      { N.value = "1" }
N -> 2      { N.value = "2" }
...
N -> 9      { N.value = "9" }