Goal: Implement a programming language

Compiling and running C code

gcc -o hello hello.c
./hello

• Why do we use two separate commands?
• Does your processor run C code directly?

What does GCC do?

• Converts source code into a runnable program.

Two ways to implement a programming language

1. Compilation: Translate to machine code to run on the CPU.
2. Interpretation: Simulate the program’s instructions.

Compilation

A compiler translates your source code to machine code.

Compiler correctness

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

Interpretation

An interpreter simulates the actions of source code.

Interpreter correctness

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

Illustrating language implementation

Getting “1+2” to run on our machine.

Compiler approach

Translate the expression “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);
  // print the addition instruction
  printf("  add %%rbx, %%rax\n");
}

Interpreter approach

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);
}

Key difference between compilation and interpretation

• Compiler: Prints out the machine code for addition.
• Interpreter: Performs the addition operation.

Extending the interpreter

Interpreting exponents, e.g., “2^8”?

No machine instruction or C instruction for exponentiation.

Interpreter pseudocode

read left operand
read right operand
read operator

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

Full example for + and ^

File: language.c

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

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

int ascii_to_int(char c) { return 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 = ascii_to_int(left);
  int rightnum = ascii_to_int(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;
  }
}

COP-5621 Compiler Construction

Take this course if you want to learn more about how programming languages are defined and implemented.

Compiler Internals

• Front-end: Processes input language (tokenisation, parsing, etc.).
• Back-end: Generates output language (e.g., emitting assembly code).

The “middle”-end

Many compilers use an intermediate language.

Why an intermediate representation?

Multiple front-ends and back-ends

Classic phases of a compiler

Symbols versus meaning

1 + 2 3

6 / 2(1 + 2)

一加二乘三

What gives symbols meaning?

• Moon versus the finger pointing at the moon
• “The map is not the territory”

ASCII versus machine code

• od
• gcc -S
• ASCII table

Syntax trees

Human language

“The boy went to the store”

Syntax: groups of words

• 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.”

• Who/what went? What word goes with “went”?

What does “store” mean?

“The store is closed.”

“Squirrels store acorns for the winter”.

Meaning also depends on structure

Arithmetic expressions

9 + 3 - 2

Compiling arithmetic expression

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

Evaluating the tree

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

Ambiguity

1 + 2 * 3

• What is the meaning, i.e., the result, of this expression?
• What are the two typical ways this can be interpreted?

Parsing

• When speaking, we don’t say “noun phrase starts here”, “subject is here.”
• So how do we figure out syntactic structure?

How is source code represented?

Parsing infers structure

• Parsing infers structure using word order and groupings, i.e., syntax.

Formal grammars

Terminals

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

Non-terminals

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

Productions

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

Starting symbol

• The first non-terminal in the syntax tree.

Constructs can be nested

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

Example: arithmetic expressions

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

Deriving a tree

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

Defining an interpreter

• Walk the tree.
• Evaluate each node of the tree.
• Define the computation for each grammar production.

Expression interpreter rules

• Assume we have implemented the following interpreter functions:
  • add(), sub(), mult(), div() to perform addition, subtraction, multiplication, and division computations.
  • ascii_to_int() to convert the ASCII character value to an integer representation.

Specifying the interpreter

Define the 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 = ascii_to_int(N.value) }
N -> 0      { N.value = "0" }
N -> 1      { N.value = "1" }
N -> 2      { N.value = "2" }
...
N -> 9      { N.value = "9" }

Defining a compiler

• Similar tree-walking approach.
• Generate code instead of computing the result.

Compile infix to postfix

Assume we have a function concat() for joining 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" }