12
\$\begingroup\$

I have been doing projects from the book The Elements of Computing Systems. Under the scope of project 10 and project 11, I had to implement a compiler for a (toy) programming language called Jack (its grammar can be found here). The compiler translates Jack code into Virtual Machine instructions (all Virtual Machine commands can be found here).

My code contains occasional free() statements, but my primary memory management strategy was not to release any memory, as the program works only for a couple of seconds.

I have added the most relevant parts of the compiler below. The full code can be found here

lexer.h

#ifndef COMPILER_TOKENIZER_H
#define COMPILER_TOKENIZER_H

#include <stdio.h>
#include <stdbool.h>
#include "util.h"

typedef enum {
  KEYWORD,
  SYMBOL,
  IDENTIFIER,
  INT_CONST,
  STRING_CONST
} TokenType;

typedef enum {
  CLASS,
  METHOD,
  FUNCTION,
  CONSTRUCTOR,
  INT,
  BOOLEAN,
  CHAR,
  VOID,
  VAR,
  STATIC,
  FIELD,
  LET,
  DO,
  IF,
  ELSE,
  WHILE,
  RETURN,
  TRUE,
  FALSE,
  cNULL,
  THIS
} KeyWord;

typedef enum KeywordConst {
  KC_TRUE,
  KC_FALSE,
  KC_NULL,
  KC_THIS
} KeywordConst;

typedef struct {
  FILE *inStream;
  bool hasMoreTokens;
  Vector *tokens;
  int current;
  int end;
  int lineNumber;
} Tokenizer;

typedef struct {
  TokenType tokenType;
  KeyWord keyword;
  char *intValue;
  char *identifier;
  char symbol;
  char *stringValue;
} Token;


Tokenizer *new_tokenizer(char *path);
TokenType advance(Tokenizer *tokenizer);
Token *lookahead(Tokenizer *tokenizer);

TokenType get_token_type(Tokenizer *tokenizer);
KeyWord get_keyword(Tokenizer *tokenizer);
char get_symbol(Tokenizer *tokenizer);
char *get_identifier(Tokenizer *tokenizer);
char *get_int(Tokenizer *tokenizer);
char *get_string(Tokenizer *tokenizer);
char *keyword_to_string(KeyWord keyWord);
KeywordConst keyword_to_keywordConst(KeyWord keyWord);

bool is_equal_to(int actual, int expected);
bool is_one_of(int actual, int nOfElements, ...);

bool is_int(Tokenizer *tokenizer);
bool is_str(Tokenizer *tokenizer);
bool is_identifier(Tokenizer *tokenizer);
bool is_class(Tokenizer *tokenizer);
bool is_class_var_dec(Tokenizer *tokenizer);
bool is_this_symbol(Tokenizer *tokenizer, char expected);
bool is_subroutine(Tokenizer *tokenizer);
bool is_type(Tokenizer *tokenizer);
bool is_var_dec(Tokenizer *tokenizer);
bool is_keyword_constant(Tokenizer *tokenizer);
bool is_op(Tokenizer *tokenizer);
bool is_unary_op(Tokenizer *tokenizer);
bool is_term(Tokenizer *tokenizer);

void raise_error(Tokenizer *tokenizer);
char *expect_identifier(Tokenizer *tokenizer);
char *expect_class(Tokenizer *tokenizer);
char expect_symbol(Tokenizer *tokenizer, char symbol);
KeyWord expect_keyword_n(Tokenizer *tokenizer, int n, ...);
char *expect_type(Tokenizer *tokenizer);

#endif //COMPILER_TOKENIZER_H

lexer.c

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <libgen.h>
#include <ctype.h>
#include <string.h>
#include <zconf.h>
#include "lexer.h"

static Map *keywords_table;

static Map *new_keyword_map();
static void add_next_token(Tokenizer *tokenizer);

Tokenizer *new_tokenizer(char *path) {
  FILE *inStream = fopen(path, "r");

  if (inStream == NULL) {
    exit(EXIT_FAILURE);
  }

  Tokenizer *tokenizer = malloc(sizeof(Tokenizer));
  tokenizer->inStream = inStream;
  tokenizer->hasMoreTokens = true;
  tokenizer->tokens = new_vec();
  tokenizer->current = -1;
  tokenizer->end = -1;
  tokenizer->lineNumber = 1;

  keywords_table = new_keyword_map();
  return tokenizer;
}

// ------------------------------- New methods --------------------------
Token *peek(Tokenizer *tokenizer) {
  return vec_get(tokenizer->tokens, tokenizer->end);
}

TokenType get_token_type(Tokenizer *tokenizer) {
  return ((Token *) vec_get(tokenizer->tokens, tokenizer->current))->tokenType;
}

KeyWord get_keyword(Tokenizer *tokenizer) {
  return ((Token *) vec_get(tokenizer->tokens, tokenizer->current))->keyword;
}

char get_symbol(Tokenizer *tokenizer) {
  return ((Token *) vec_get(tokenizer->tokens, tokenizer->current))->symbol;
}

char *get_identifier(Tokenizer *tokenizer) {
  return ((Token *) vec_get(tokenizer->tokens, tokenizer->current))->identifier;
}

char *get_int(Tokenizer *tokenizer) {
  return ((Token *) vec_get(tokenizer->tokens, tokenizer->current))->intValue;
}

char *get_string(Tokenizer *tokenizer) {
  return ((Token *) vec_get(tokenizer->tokens, tokenizer->current))->stringValue;
}

Token *lookahead(Tokenizer *tokenizer) {
  add_next_token(tokenizer);
  tokenizer->current--;
  return peek(tokenizer);
}

void close_tokenizer(Tokenizer *tokenizer) {
  if (tokenizer->inStream != NULL) {
    fclose(tokenizer->inStream);
    tokenizer->inStream = NULL;
  }

  free(tokenizer);
}

static Token *new_token(TokenType tokenType) {
  Token *token = malloc(sizeof(Token));
  token->tokenType = tokenType;
  return token;
}

static void add_token(Tokenizer *tokenizer, Token *token) {
  vec_push(tokenizer->tokens, token);
  tokenizer->current++;
  tokenizer->end++;
}

static bool had_to_catch_up_with_last_pos(Tokenizer *tokenizer) {
  if (tokenizer->current < tokenizer->end) {
    tokenizer->current = tokenizer->end;
    return true;
  }
  return false;
}

TokenType advance(Tokenizer *tokenizer) {
  add_next_token(tokenizer);
  return get_token_type(tokenizer);
}

static void add_next_token(Tokenizer *tokenizer) {
  if (!tokenizer->hasMoreTokens) {
    return;
  }

  if (had_to_catch_up_with_last_pos(tokenizer)) return;

  while (true) {
    int chr = getc(tokenizer->inStream);

    if (chr == EOF) {
      tokenizer->hasMoreTokens = false;
      break;
    }

    if (chr == '\n') {
      tokenizer->lineNumber++;
      continue;
    }

    // remove comments if they are present
    if (chr == '/') {
      int chrSecond = getc(tokenizer->inStream);

      if (chrSecond == '/') {
        while (getc(tokenizer->inStream) != '\n');
        tokenizer->lineNumber++;
        continue;
      } else if (chrSecond == '*') {
        int tmp1 = getc(tokenizer->inStream);
        if (tmp1 == '\n') tokenizer->lineNumber++;

        while (true) {
          int tmp2 = getc(tokenizer->inStream);
          if (tmp2 == '\n') tokenizer->lineNumber++;
          if (tmp1 == '*' && tmp2 == '/') break;
          tmp1 = tmp2;
        };

        continue;
      } else {
        ungetc(chrSecond, tokenizer->inStream);
      }
    }

    if (chr == '"') {
      StringBuilder *tmpSb = new_sb();

      int tmp;
      while ((tmp = getc(tokenizer->inStream)) != '"') {
        sb_add(tmpSb, tmp);
      };

      Token *token = new_token(STRING_CONST);
      token->stringValue = sb_get(tmpSb);
      add_token(tokenizer, token);

      free(tmpSb);
      break;
    }

    if (strchr("{}()[].,;+-*/&|<>=~", chr) != NULL) {
      Token *token = new_token(SYMBOL);
      token->symbol = chr;
      add_token(tokenizer, token);
      break;
    }

    // identifier or keyword
    if (isalpha(chr) || chr == '_') {
      StringBuilder *tmpStr = new_sb();
      int tmp = chr;
      while (isalpha(tmp) || tmp == '_' || isdigit(tmp)) {
        sb_add(tmpStr, tmp);
        tmp = getc(tokenizer->inStream);
      }

      char *str = sb_get(tmpStr);
      KeyWord curKeyWord = (KeyWord) map_geti(keywords_table, str, -1);

      Token *token;
      // is_equal_to if a keyword
      if (curKeyWord != -1) {
        token = new_token(KEYWORD);
        token->keyword = curKeyWord;
      } else {
        token = new_token(IDENTIFIER);
        token->identifier = str;
      }

      add_token(tokenizer, token);

      free(tmpStr);
      ungetc(tmp, tokenizer->inStream);
      break;
    }

    if (isdigit(chr)) {
      StringBuilder *tmpSb = new_sb();

      int tmp = chr;
      while (isdigit(tmp)) {
        sb_add(tmpSb, tmp);
        tmp = getc(tokenizer->inStream);
      };

      Token *token = new_token(INT_CONST);
      token->intValue = sb_get(tmpSb);
      add_token(tokenizer, token);

      free(tmpSb);
      ungetc(tmp, tokenizer->inStream);
      break;
    }

    if (isspace(chr)) {
      continue;
    }
  }
}

static Map *new_keyword_map() {
  Map *map = new_map();
  map_puti(map, "class", CLASS);
  map_puti(map, "constructor", CONSTRUCTOR);
  map_puti(map, "function", FUNCTION);
  map_puti(map, "method", METHOD);
  map_puti(map, "field", FIELD);
  map_puti(map, "static", STATIC);
  map_puti(map, "var", VAR);
  map_puti(map, "int", INT);
  map_puti(map, "char", CHAR);
  map_puti(map, "boolean", BOOLEAN);
  map_puti(map, "void", VOID);
  map_puti(map, "true", TRUE);
  map_puti(map, "false", FALSE);
  map_puti(map, "null", cNULL);
  map_puti(map, "this", THIS);
  map_puti(map, "let", LET);
  map_puti(map, "do", DO);
  map_puti(map, "if", IF);
  map_puti(map, "else", ELSE);
  map_puti(map, "while", WHILE);
  map_puti(map, "return", RETURN);
  return map;
}

char *keyword_to_string(KeyWord keyWord) {
  switch (keyWord) {
    case CLASS:
      return "class";
    case STATIC:
      return "static";
    case FIELD:
      return "field";
    case INT:
      return "int";
    case CHAR:
      return "char";
    case BOOLEAN:
      return "boolean";
    case CONSTRUCTOR:
      return "constructor";
    case FUNCTION:
      return "function";
    case METHOD:
      return "method";
    case VOID:
      return "void";
    case VAR:
      return "var";
    case LET:
      return "let";
    case IF:
      return "if";
    case ELSE:
      return "else";
    case WHILE:
      return "while";
    case DO:
      return "do";
    case RETURN:
      return "return";
    case cNULL:
      return "null";
    case THIS:
      return "this";
    case TRUE:
      return "true";
    case FALSE:
      return "false";
    default:
      xprintf("%i is not specified in keyword_to_string", keyWord);
      exit(EXIT_FAILURE);
  }
}

KeywordConst keyword_to_keywordConst(KeyWord keyWord) {
  switch (keyWord) {
    case cNULL:
      return KC_NULL;
    case THIS:
      return KC_THIS;
    case TRUE:
      return KC_TRUE;
    case FALSE:
      return KC_FALSE;
    default:
      xprintf("%s is not specified in keyword_to_keywordConst", keyword_to_string(keyWord));
      exit(EXIT_FAILURE);
  }
}

bool is_equal_to(int actual, int expected) {
  return expected == actual;
}

bool is_one_of(int actual, int nOfElements, ...) {
  va_list argp;
  va_start(argp, nOfElements);

  while (nOfElements--) {
    int expected = va_arg(argp, int);
    if (actual == expected) {
      va_end(argp);
      return true;
    }
  }
  va_end(argp);

  return false;
}

bool is_int(Tokenizer *tokenizer) {
  return is_equal_to(get_token_type(tokenizer), INT_CONST);
}

bool is_str(Tokenizer *tokenizer) {
  return is_equal_to(get_token_type(tokenizer), STRING_CONST);
}

bool is_identifier(Tokenizer *tokenizer) {
  return is_equal_to(get_token_type(tokenizer), IDENTIFIER);
}

bool is_class(Tokenizer *tokenizer) {
  return is_equal_to(get_keyword(tokenizer), CLASS);
}

bool is_class_var_dec(Tokenizer *tokenizer) {
  return is_one_of(get_keyword(tokenizer), 2, STATIC, FIELD);
}

bool is_this_symbol(Tokenizer *tokenizer, char expected) {
  return is_equal_to(get_symbol(tokenizer), expected);
}

bool is_subroutine(Tokenizer *tokenizer) {
  return is_one_of(get_keyword(tokenizer), 3, CONSTRUCTOR, FUNCTION, METHOD);
}

bool is_type(Tokenizer *tokenizer) {
  return is_identifier(tokenizer) || is_one_of(get_keyword(tokenizer), 3, INT, CHAR, BOOLEAN);
}

bool is_var_dec(Tokenizer *tokenizer) {
  return is_equal_to(get_keyword(tokenizer), VAR);
}

bool is_keyword_constant(Tokenizer *tokenizer) {
  return is_one_of(get_keyword(tokenizer), 4, TRUE, FALSE, cNULL, THIS);
}

bool is_op(Tokenizer *tokenizer) {
  return is_one_of(get_symbol(tokenizer), 9, '+', '-', '*', '/', '&', '|', '<', '>', '=');
}

bool is_unary_op(Tokenizer *tokenizer) {
  return is_one_of(get_symbol(tokenizer), 2, '-', '~');
}

bool is_term(Tokenizer *tokenizer) {
  return is_one_of(get_token_type(tokenizer), 2, INT_CONST, STRING_CONST)
         || is_keyword_constant(tokenizer)
         || is_identifier(tokenizer)
         || is_unary_op(tokenizer)
         || is_this_symbol(tokenizer, '(');
}

void raise_error(Tokenizer *tokenizer) {
  xprintf("Wrong token at line %i\n", tokenizer->lineNumber);
  xprintf("TokenType %i", get_token_type(tokenizer));
  exit(EXIT_FAILURE);
}

char *expect_identifier(Tokenizer *tokenizer) {
  if (is_identifier(tokenizer)) {
    char *identifier = get_identifier(tokenizer);
    advance(tokenizer);
    return identifier;
  }
  raise_error(tokenizer);
}


char *expect_class(Tokenizer *tokenizer) {
  if (is_class(tokenizer)) {
    advance(tokenizer);
    return "class";
  }
  raise_error(tokenizer);
}

char expect_symbol(Tokenizer *tokenizer, char symbol) {
  if (is_this_symbol(tokenizer, symbol)) {
    advance(tokenizer);
    return symbol;
  }
  raise_error(tokenizer);
}

KeyWord expect_keyword_n(Tokenizer *tokenizer, int n, ...) {
  va_list expectedArgs;
  va_start(expectedArgs, n);;
  KeyWord actualKeyWord = get_keyword(tokenizer);
  while (n--) {
    int expected = va_arg(expectedArgs, int);
    if (actualKeyWord == expected) {
      va_end(expectedArgs);
      advance(tokenizer);
      return actualKeyWord;
    }
  }

  va_end(expectedArgs);
  raise_error(tokenizer);
}

char *expect_type(Tokenizer *tokenizer) {
  // 'int' | 'char' | 'boolean' | className
  if (get_identifier(tokenizer)) {
    char *identifier = get_identifier(tokenizer);
    advance(tokenizer);
    return identifier;
  }

  KeyWord keyWord = get_keyword(tokenizer);
  switch (keyWord) {
    case INT:
    case CHAR:
    case BOOLEAN:
      advance(tokenizer);
      return keyword_to_string(keyWord);
    default:
      raise_error(tokenizer);
  }

}

parser.h

#ifndef COMPILER_PARSER_H
#define COMPILER_PARSER_H

#include "lexer.h"
#include "symbol_table.h"

typedef struct Class {
  char *name;
  SymbolTable *gTable;
  Vector *functions;
} Class;

typedef struct Function {
  char *name;
  KeyWord funcKind;
  char *returnType;
  SymbolTable *lTable;
  Vector *statements;
} Function;

enum TermType {
  TERM_INT,
  TERM_STR,
  TERM_KEYWORD,
  TERM_VAR,
  TERM_ARRAY,
  TERM_SUB_CALL,
  TERM_EXPR_PARENS,
  TERM_TERM_PAIR
} TermType;

typedef struct Term {
  enum TermType type;
  union {
    char *integer;
    char *str;
    KeywordConst kConst;
    char *varName;
    struct Array *array;
    struct SubroutineCall *subCall;
    struct Expression *expr;
    struct TermPair *termPair;
  };
} Term;

typedef struct TermPair {
  char op;
  struct Term *term;
} TermPair;

typedef struct Expression {
  Term *firstTerm;
  Vector *termPairs;
} Expression;

typedef struct SubroutineCall {
  enum SubCallType {
    PLAIN_SUB_CALL,
    TARGET_SUB_CALL
  } type;
  char *target;
  char *subroutineName;
  struct ExpressionList *exprList;
} SubroutineCall;

typedef struct ExpressionList {
  Vector *expressions;
} ExpressionList;

typedef struct Array {
  char *varName;
  struct Expression *expr;
} Array;

typedef struct WhileStatement {
  Expression *expr;
  Vector *stmts;
} WhileStmt;

typedef struct ReturnStatement {
  Expression *expr;
} ReturnStmt;

typedef struct IfStatement {
  Expression *expr;
  Vector *ifStmts;
  Vector *elseStmts;
} IfStmt;

typedef struct LetStatement {
  enum LetType {
    LET_TYPE_PLAIN,
    LET_TYPE_ARRAY,
  } type;
  char *name;
  Expression *firstExpr;
  Expression *secondExpr;
} LetStmt;

typedef struct DoStatement {
  SubroutineCall *call;
} DoStmt;

typedef struct Statement {
  enum {
    RETURN_STMT,
    WHILE_STMT,
    IF_STMT,
    DO_STMT,
    LET_STMT
  } type;
  union {
    ReturnStmt *retStmt;
    WhileStmt *whileStmt;
    IfStmt *ifStmt;
    LetStmt *letStmt;
    DoStmt *doStmt;
  };
} Statement;


Class *build_ast(Tokenizer *tokenizer);

#endif //COMPILER_PARSER_H

parser.c

#include <stdlib.h>
#include <zconf.h>
#include "parser.h"

static Class *parse_class();
static void parse_class_var_dec(Tokenizer *tokenizer, SymbolTable *gTable);
static Function *parse_subroutine(Tokenizer *tokenizer, Class *class);
static void parse_var_dec(Tokenizer *tokenizer, Function *func);
static void parse_param_list(Tokenizer *tokenizer, Function *func, char *className);
static void parse_subroutine_body(Tokenizer *tokenizer, Function *func);
static Vector *parse_statements(Tokenizer *tokenizer);
static ReturnStmt * parse_return(Tokenizer *tokenizer);
static DoStmt *parse_do(Tokenizer *tokenizer);
static WhileStmt *parse_while(Tokenizer *tokenizer);
static IfStmt *parse_if(Tokenizer *tokenizer);
static LetStmt *parse_let(Tokenizer *tokenizer);
static Expression *parse_expression(Tokenizer *tokenizer);
static ExpressionList *parse_expression_list(Tokenizer *tokenizer);
static SubroutineCall *parse_subroutine_call(Tokenizer *tokenizer);
static Term *parse_term(Tokenizer *tokenizer);

static void print_funcs(Vector *funcs);
static void print_expr(Expression *expr);
static void print_exprs(Vector *exprs);
static void print_subcall(SubroutineCall *subCall);
static void print_stmts(Vector *stmts);

Class *build_ast(Tokenizer *tokenizer) {
  Class *class = parse_class(tokenizer);

  // for debugging purposes
  // xprintf("class name: %s\n", class->name);
  // print_symbol_table(class->gTable);
  // print_funcs(class->functions);

  return class;
}

static Class *new_class(char *className) {
  Class *class = malloc(sizeof(Class));
  class->gTable = init_table();
  class->functions = new_vec();
  class->name = className;
  return class;
}

static Function *new_function(KeyWord funcKind, char *funcName, char *returnType) {
  Function *func = malloc(sizeof(Function));
  func->funcKind = funcKind;
  func->name = funcName;
  func->lTable = init_table();
  func->returnType = returnType;
  func->statements = NULL;
  return func;
}

static void print_term(Term *term) {
  switch (term->type) {
    case TERM_INT:
      xprintf("%s", term->integer);
      break;
    case TERM_STR:
      xprintf("%s", term->str);
      break;
    case TERM_KEYWORD:
      xprintf("%i", term->kConst);
      break;
    case TERM_VAR:
      xprintf("%s", term->varName);
      break;
    case TERM_EXPR_PARENS: {
      xprintf("(");
      print_expr(term->expr);
      xprintf(")");
      break;
    }
    case TERM_TERM_PAIR: {
      TermPair *pair = term->termPair;
      xprintf("%c", pair->op);
      print_term(pair->term);
      break;
    }
    case TERM_SUB_CALL: {
      print_subcall(term->subCall);
      break;
    }
    case TERM_ARRAY: {
      xprintf("%s[", term->array->varName);
      print_expr(term->array-> expr);
      xprintf("]");
      break;
    }
    default:
      break;
  }
}

static void print_subcall(SubroutineCall *subCall) {
  enum SubCallType type = subCall->type;
  if (type == PLAIN_SUB_CALL) {
    xprintf("%s(", subCall->subroutineName);
    if (subCall->exprList != NULL) {
      print_exprs(subCall->exprList->expressions);
    }
    xprintf(")");
  } else {
    xprintf("%s.%s(", subCall->target, subCall->subroutineName);
    if (subCall->exprList != NULL) {
      print_exprs(subCall->exprList->expressions);
    }
    xprintf(")");
  }
}

static void print_expr(Expression *expr) {
  print_term(expr->firstTerm);

  if (expr->termPairs == NULL) return;

  for (int i = 0; i < expr->termPairs->len; i++) {
    TermPair *pair = vec_get(expr->termPairs, i);
    xprintf(" %c ", pair->op);
    print_term(pair->term);
  }
}

static void print_exprs(Vector *exprs) {
  for (int i = 0; i < exprs->len; i++) {
    Expression *expr = vec_get(exprs, i);
    print_expr(expr);

    if (i != exprs->len - 1) {
      xprintf(", ");
    }
  }
}

static void print_stmt(Statement *stmt) {
  switch (stmt->type) {
    case RETURN_STMT: {
      xprintf("return ");
      Expression *expr = stmt->retStmt->expr;
      if (expr != NULL) {
        print_expr(stmt->retStmt->expr);
      }
      xprintf("\n");
      break;
    }
    case LET_STMT: {
      xprintf("let %s", stmt->letStmt->name);
      if (stmt->letStmt->type == LET_TYPE_ARRAY) {
        xprintf("[");
        print_expr(stmt->letStmt->firstExpr);
        xprintf("]");
      }
      xprintf(" = ");
      print_expr(stmt->letStmt->secondExpr);
      xprintf("\n");
      break;
    }
    case IF_STMT: {
      xprintf("if ( ");
      print_expr(stmt->ifStmt->expr);
      xprintf(") {\n");
      print_stmts(stmt->ifStmt->ifStmts);
      xprintf("}\n");
      if (stmt->ifStmt->elseStmts != NULL) {
        xprintf("else {\n");
        print_stmts(stmt->ifStmt->elseStmts);
        xprintf("}\n");
      }
      break;
    }
    case WHILE_STMT: {
      xprintf("while (");
      print_expr(stmt->whileStmt->expr);
      xprintf(") {\n");
      print_stmts(stmt->whileStmt->stmts);
      xprintf("}\n");
      break;
    }
    case DO_STMT: {
      xprintf("do ");
      print_subcall(stmt->doStmt->call);
      xprintf("\n");
      break;
    }
    default:
      break;
  }
}

static void print_stmts(Vector *stmts) {
  for (int i = 0; i < stmts->len; i++) {
    Statement *stmt = vec_get(stmts, i);
    print_stmt(stmt);
  }
}

static void print_funcs(Vector *funcs) {
  for (int i = 0; i < funcs->len; i++) {
    Function *func = vec_get(funcs, i);
    xprintf("--------------------------------\n");
    xprintf("func name: %s; func kind: %s; return type: %s\n", func->name, keyword_to_string(func->funcKind), func->returnType);
    print_symbol_table(func->lTable);
    print_stmts(func->statements);
  }
}

static Class *parse_class(Tokenizer *tokenizer) {
  // 'class' className '{' classVarDec* subroutineDec* '}'
  advance(tokenizer);
  expect_class(tokenizer);
  char *className = expect_identifier(tokenizer);
  expect_symbol(tokenizer, '{');
  Class *class = new_class(className);

  while (is_class_var_dec(tokenizer)) {
    parse_class_var_dec(tokenizer, class->gTable);
  }

  while (is_subroutine(tokenizer)) {
    vec_push(class->functions, parse_subroutine(tokenizer, class));
  }

  expect_symbol(tokenizer, '}');

  // check to see if there are tokens that have not been compiled
  if (tokenizer->hasMoreTokens) raise_error(tokenizer);
  return class;
}

static void parse_class_var_dec(Tokenizer *tokenizer, SymbolTable *gTable) {
  // ( 'static' | 'field' ) type varName ( ',' varName)* ';'
  KeyWord keyWord = expect_keyword_n(tokenizer, 2, STATIC, FIELD);
  Kind curKind = transformToKind(keyWord);
  char *type = expect_type(tokenizer);
  char *varName = expect_identifier(tokenizer);
  define(gTable, varName, type, curKind);

  while (is_this_symbol(tokenizer, ',')) {
    expect_symbol(tokenizer, ',');
    varName = expect_identifier(tokenizer);
    define(gTable, varName, type, curKind);
  }

  expect_symbol(tokenizer, ';');
}

static Function *parse_subroutine(Tokenizer *tokenizer, Class *class) {
  // ('constructor' | 'function' | 'method') ('void' | type) subroutineName '(' parameterList ')' subroutineBody
  KeyWord funcKind = expect_keyword_n(tokenizer, 3, CONSTRUCTOR, FUNCTION, METHOD);
  char *returnType;
  if (is_equal_to(get_keyword(tokenizer), VOID)) {
    returnType = keyword_to_string(expect_keyword_n(tokenizer, 1, VOID));
  } else {
    returnType = expect_type(tokenizer);
  }

  char *funcName = expect_identifier(tokenizer);
  Function *func = new_function(funcKind, funcName, returnType);

  expect_symbol(tokenizer, '(');
  parse_param_list(tokenizer, func, class->name);
  expect_symbol(tokenizer, ')');
  parse_subroutine_body(tokenizer, func);
  return func;
}

static void parse_var_dec(Tokenizer *tokenizer, Function *func) {
  // 'var' type varName ( ',' varName)* ';'
  expect_keyword_n(tokenizer, 1, VAR);
  char *varType = expect_type(tokenizer);
  char *varName = expect_identifier(tokenizer);
  define(func->lTable, varName, varType, KIND_VAR);

  while(is_this_symbol(tokenizer, ',')) {
    expect_symbol(tokenizer, ',');
    varName = expect_identifier(tokenizer);
    define(func->lTable, varName, varType, KIND_VAR);
  }

  expect_symbol(tokenizer, ';');
}

static void parse_param_list(Tokenizer *tokenizer, Function *func, char *className) {
  // ((type varName) ( ',' type varName)*)?
  if (is_one_of(func->funcKind, 1, METHOD)) {
    define(func->lTable, "this", className, KIND_ARG);
  }

  if (!is_type(tokenizer)) return;
  char *paramType = expect_type(tokenizer);
  char *paramName = expect_identifier(tokenizer);
  define(func->lTable, paramName, paramType, KIND_ARG);

  while(is_this_symbol(tokenizer, ',')) {
    expect_symbol(tokenizer, ',');
    paramType = expect_type(tokenizer);
    paramName = expect_identifier(tokenizer);
    define(func->lTable, paramName, paramType, KIND_ARG);
  }
}

static void parse_subroutine_body(Tokenizer *tokenizer, Function *func) {
  // subroutineBody ('{' varDec* statements '}')
  expect_symbol(tokenizer, '{');

  while(is_var_dec(tokenizer)) {
    parse_var_dec(tokenizer, func);
  }

  func->statements = parse_statements(tokenizer);
  expect_symbol(tokenizer, '}');
}

//*============================  Statements ============================ */

static Vector *parse_statements(Tokenizer *tokenizer) {
  Vector *statements = new_vec();
  Statement *stmt;

  KeyWord keyWord = get_keyword(tokenizer);
  while(is_one_of(keyWord, 5, LET, IF, WHILE, DO, RETURN)) {
    stmt = malloc(sizeof(Statement));
    switch (keyWord) {
      case LET: {
        stmt->type = LET_STMT;
        stmt->letStmt = parse_let(tokenizer);
        break;
      }
      case IF: {
        stmt->type = IF_STMT;
        stmt->ifStmt = parse_if(tokenizer);
        break;
      }
      case WHILE: {
        stmt->type = WHILE_STMT;
        stmt->whileStmt = parse_while(tokenizer);
        break;
      }
      case DO:
        stmt->type = DO_STMT;
        stmt->doStmt = parse_do(tokenizer);
        break;
      case RETURN:
        stmt->type = RETURN_STMT;
        stmt->retStmt = parse_return(tokenizer);
        break;
      default:
        raise_error(tokenizer);
        break;
    }

    vec_push(statements, stmt);
    keyWord = get_keyword(tokenizer);
  }

  return statements;
}

static LetStmt *parse_let(Tokenizer *tokenizer) {
  //  'let' varName ( '[' expression ']' )? '=' expression ';'
  expect_keyword_n(tokenizer, 1, LET);

  LetStmt *letStmt = malloc(sizeof(LetStmt));
  letStmt->name = expect_identifier(tokenizer);

  if (is_this_symbol(tokenizer, '[')) {
    expect_symbol(tokenizer, '[');
    letStmt->firstExpr = parse_expression(tokenizer);
    letStmt->type = LET_TYPE_ARRAY;
    expect_symbol(tokenizer, ']');
  } else {
    letStmt->firstExpr = NULL;
    letStmt->type = LET_TYPE_PLAIN;
  }

  expect_symbol(tokenizer, '=');
  letStmt->secondExpr = parse_expression(tokenizer);
  expect_symbol(tokenizer, ';');

  return letStmt;
}

static IfStmt *parse_if(Tokenizer *tokenizer) {
  //  'if' '(' expression ')' '{' statements '}' ( 'else' '{' statements '}' )?
  expect_keyword_n(tokenizer, 1, IF);

  IfStmt *ifStmt = malloc(sizeof(IfStmt));

  expect_symbol(tokenizer, '(');
  ifStmt->expr = parse_expression(tokenizer);
  expect_symbol(tokenizer, ')');

  expect_symbol(tokenizer, '{');
  ifStmt->ifStmts = parse_statements(tokenizer);
  expect_symbol(tokenizer, '}');

  ifStmt->elseStmts = NULL;
  if (is_equal_to(get_keyword(tokenizer), ELSE)) {
    expect_keyword_n(tokenizer, 1, ELSE);
    expect_symbol(tokenizer, '{');
    ifStmt->elseStmts = parse_statements(tokenizer);
    expect_symbol(tokenizer, '}');
  }

  return ifStmt;
}

static WhileStmt *parse_while(Tokenizer *tokenizer) {
  // 'while' '(' expression ')' '{' statements '}'
  expect_keyword_n(tokenizer, 1, WHILE);

  WhileStmt *whileStmt = malloc(sizeof(WhileStmt));

  expect_symbol(tokenizer, '(');
  whileStmt->expr = parse_expression(tokenizer);
  expect_symbol(tokenizer, ')');

  expect_symbol(tokenizer, '{');
  whileStmt->stmts = parse_statements(tokenizer);
  expect_symbol(tokenizer, '}');
  return whileStmt;
}

static DoStmt *parse_do(Tokenizer *tokenizer) {
  // 'do' subroutineCall ';'
  DoStmt *doStmt = malloc(sizeof(DoStmt));
  expect_keyword_n(tokenizer, 1, DO);
  doStmt->call = parse_subroutine_call(tokenizer);
  expect_symbol(tokenizer, ';');
  return doStmt;
}

static ReturnStmt *parse_return(Tokenizer *tokenizer) {
  // 'return' expression? ';'
  ReturnStmt *retStmt = malloc(sizeof(ReturnStmt));
  retStmt->expr = NULL;

  expect_keyword_n(tokenizer, 1, RETURN);
  if (is_term(tokenizer)) {
    retStmt->expr = parse_expression(tokenizer);
  }

  expect_symbol(tokenizer, ';');
  return retStmt;
}

//*============================  Expressions ============================ */

static Expression *parse_expression(Tokenizer *tokenizer) {
  // term (op term)*
  Expression *expr = malloc(sizeof(Expression));
  expr->firstTerm = parse_term(tokenizer);
  expr->termPairs = NULL;

  if (!is_op(tokenizer)) {
    return expr;
  }

  expr->termPairs = new_vec();

  while (is_op(tokenizer)) {
    TermPair *pair = malloc(sizeof(TermPair));

    pair->op = get_symbol(tokenizer);
    advance(tokenizer);

    pair->term = parse_term(tokenizer);
    vec_push(expr->termPairs, pair);
  }

  return expr;
}

static ExpressionList *parse_expression_list(Tokenizer *tokenizer) {
  // (expression ( ',' expression)* )?
  if (!is_term(tokenizer)) {
    return NULL;
  }

  ExpressionList *exprList = malloc(sizeof(ExpressionList));
  exprList->expressions = new_vec();
  vec_push(exprList->expressions, parse_expression(tokenizer));

  while (is_this_symbol(tokenizer, ',')) {
    expect_symbol(tokenizer, ',');
    vec_push(exprList->expressions, parse_expression(tokenizer));
  }

  return exprList;
}

static SubroutineCall *parse_subroutine_call(Tokenizer *tokenizer) {
  SubroutineCall *call = malloc(sizeof(SubroutineCall));

   char *name = expect_identifier(tokenizer);

  // subroutine call (name + expressionList)
  if (is_this_symbol(tokenizer, '(')) {
    call->type = PLAIN_SUB_CALL;
    call->subroutineName = name;
    expect_symbol(tokenizer, '(');
    call->exprList = parse_expression_list(tokenizer);
    expect_symbol(tokenizer, ')');
    return call;
  }

  // subroutine call (name + name + expressionList)
  if (is_this_symbol(tokenizer, '.')) {
    expect_symbol(tokenizer, '.');
    call->type = TARGET_SUB_CALL;
    call->target = name;
    call->subroutineName = expect_identifier(tokenizer);
    expect_symbol(tokenizer, '(');
    call->exprList = parse_expression_list(tokenizer);
    expect_symbol(tokenizer, ')');
    return call;
  }

  raise_error(tokenizer);
}

static Term *parse_term(Tokenizer *tokenizer) {
  // integerConstant | stringConstant | keywordConstant |
  // varName | varName '[' expression ']' | subroutineCall | '(' expression ')' | unaryOp term
  Term *term = malloc(sizeof(Term));

  if (is_int(tokenizer)) {
    term->type = TERM_INT;
    term->integer = get_int(tokenizer);
    advance(tokenizer);
    return term;
  }

  if (is_str(tokenizer)) {
    term->type = TERM_STR;
    term->str = get_string(tokenizer);
    advance(tokenizer);
    return term;
  }

  if (is_keyword_constant(tokenizer)) {
    term->type = TERM_KEYWORD;
    term->kConst = keyword_to_keywordConst(get_keyword(tokenizer));
    advance(tokenizer);
    return term;
  }

  if (is_this_symbol(tokenizer, '(')) {
    expect_symbol(tokenizer, '(');
    term->type = TERM_EXPR_PARENS;
    term->expr = parse_expression(tokenizer);
    expect_symbol(tokenizer, ')');
    return term;
  }

  if (is_unary_op(tokenizer)) {
    term->type = TERM_TERM_PAIR;
    term->termPair = malloc(sizeof(TermPair));
    term->termPair->op = get_symbol(tokenizer);
    advance(tokenizer);
    term->termPair->term = parse_term(tokenizer);
    return term;
  }

  if (!is_identifier(tokenizer)) {
    raise_error(tokenizer);
  }

  // means it is either subroutineCall or varName or varName + expressionList
  Token *token = lookahead(tokenizer);
  if (token->tokenType == SYMBOL) {
    // varName + expression
    if (token->symbol == '[') {
      char *name = expect_identifier(tokenizer);
      expect_symbol(tokenizer, '[');
      Expression *expr = parse_expression(tokenizer);
      expect_symbol(tokenizer, ']');

      Array *array = malloc(sizeof(Array));
      array->varName = name;
      array->expr = expr;

      term->type = TERM_ARRAY;
      term->array = array;
      return term;
    }

    // subroutineCall
    if (token->symbol == '(' || token->symbol == '.') {
      term->type = TERM_SUB_CALL;
      term->subCall = parse_subroutine_call(tokenizer);
      return term;
    }
  }

  // varName
  term->type = TERM_VAR;
  term->varName = expect_identifier(tokenizer);
  return term;
}

compilation_engine.h

#ifndef COMPILER_COMPILATION_ENGINE_H
#define COMPILER_COMPILATION_ENGINE_H

#include <stdio.h>
#include "util.h"
#include "lexer.h"
#include "symbol_table.h"
#include "vm_writer.h"
#include "parser.h"

typedef struct {
  VMwriter *writer;
  Class *ast;
  Function *curFunc;
  int labelCounter;
} CompilationEngine;

CompilationEngine *new_engine(char *fileName, Class *class);
void compile_file(CompilationEngine *engine);

#endif //COMPILER_COMPILATION_ENGINE_H

compilation_engine.c

#include <stdlib.h>
#include <zconf.h>
#include <ctype.h>
#include <string.h>
#include "compilation_engine.h"
#include "lexer.h"


CompilationEngine *new_engine(char *fileName, Class *class) {
  CompilationEngine *engine = malloc(sizeof(CompilationEngine));
  engine->writer = init_vmWriter(fileName);
  engine->ast = class;
  engine->curFunc = NULL;
  engine->labelCounter = 0;
  return engine;
}

/*============================ Compile routines ============================ */

static void compile_subroutine(CompilationEngine *engine, Function *func);
static void compile_expression(CompilationEngine *engine, Expression *expr);
static void compile_subroutineCall(CompilationEngine *engine, SubroutineCall *call);
static void compile_term(CompilationEngine *engine, Term *term);
static void compile_statement(CompilationEngine *engine, Statement *stmt);
static void compile_subroutineBody(CompilationEngine *engine, Vector *stmts);
static void compile_return(CompilationEngine *engine, ReturnStmt *stmt);
static void compile_do(CompilationEngine *engine, DoStmt *stmt);
static void compile_if(CompilationEngine *engine, IfStmt *stmt);
static void compile_let(CompilationEngine *engine, LetStmt *stmt);
static void compile_while(CompilationEngine *engine, WhileStmt *stmt);
static void compile_expression_list(CompilationEngine *engine, ExpressionList *list);
static void compile_operator(CompilationEngine *engine, char op);
static void compile_unary_operator(CompilationEngine *engine, char op);
static Segment kind_to_segment(Kind kind);
static int find_index(CompilationEngine *engine, char *identName);
static Kind find_kind(CompilationEngine *engine, char *identName);
static char *find_type(CompilationEngine *engine, char *identName);
static void alloc_mem(CompilationEngine *engine, int nwords);

void compile_file(CompilationEngine *engine) {
  Class *class = engine->ast;
  Vector *funcs = class->functions;

  for (int i = 0; i < funcs->len; i++) {
    Function *func = vec_get(funcs, i);
    compile_subroutine(engine, func);
  }
}

static void compile_subroutine(CompilationEngine *engine, Function *func) {
  write_func(engine->writer, engine->ast->name, func->name, varCount(func->lTable, KIND_VAR));
  Vector *stmts = func->statements;
  engine->curFunc = func;
  compile_subroutineBody(engine, stmts);
}

static void compile_subroutineBody(CompilationEngine *engine, Vector *stmts) {
  if (engine->curFunc->funcKind == CONSTRUCTOR) {
    alloc_mem(engine, varCount(engine->ast->gTable, KIND_FIELD));
    write_pop_i(engine->writer, SEGMENT_POINTER, 0);
  }

  if (engine->curFunc->funcKind == METHOD) {
    write_push_i(engine->writer, SEGMENT_ARG, 0);
    write_pop_i(engine->writer, SEGMENT_POINTER, 0);
  }

  for (int i = 0; i < stmts->len; i++) {
    Statement *stmt = vec_get(stmts, i);
    compile_statement(engine, stmt);
  }
}

static void compile_statement(CompilationEngine *engine, Statement *stmt) {
  switch (stmt->type) {
    case LET_STMT:
      compile_let(engine, stmt->letStmt);
      break;
    case IF_STMT:
      compile_if(engine, stmt->ifStmt);
      break;
    case WHILE_STMT:
      compile_while(engine, stmt->whileStmt);
      break;
    case RETURN_STMT:
      compile_return(engine, stmt->retStmt);
      break;
    case DO_STMT:
      compile_do(engine, stmt->doStmt);
      break;
    default:
      xprintf("%i, this statement is not implemented", stmt->type);
      exit(EXIT_FAILURE);
  }
}

char *new_label(char *label, int salt) {
  StringBuilder *sb = new_sb();
  sb_concat_strings(sb, 1, label);
  sb_append_i(sb, salt);
  return sb_get(sb);
}

static void compile_if(CompilationEngine *engine, IfStmt *stmt) {
  char *elseLabel = new_label("IF_FALSE", engine->labelCounter);
  char *endLabel = new_label("IF_END", engine->labelCounter);
  engine->labelCounter++;

  compile_expression(engine, stmt->expr);
  write_arithmetic(engine->writer, NOT);
  write_if(engine->writer, elseLabel);

  compile_subroutineBody(engine, stmt->ifStmts);
  write_goto(engine->writer, endLabel);

  write_label(engine->writer, elseLabel);
  if (stmt->elseStmts != NULL) {
    compile_subroutineBody(engine, stmt->elseStmts);
  }

  write_label(engine->writer, endLabel);
}

static void compile_do(CompilationEngine *engine, DoStmt *stmt) {
  compile_subroutineCall(engine, stmt->call);
  // remove a value from the stack in order to avoid stackoverflow
  write_pop_i(engine->writer, SEGMENT_TEMP, 0);
}

static void compile_let(CompilationEngine *engine, LetStmt *stmt) {
  switch(stmt->type) {
    case LET_TYPE_PLAIN: {
      compile_expression(engine, stmt->secondExpr);
      int index = find_index(engine, stmt->name);
      Kind kind = find_kind(engine, stmt->name);
      write_pop_i(engine->writer, kind_to_segment(kind), index);
      break;
    }
    case LET_TYPE_ARRAY: {
      int index = find_index(engine, stmt->name);
      Kind kind = find_kind(engine, stmt->name);

      if (kind == KIND_NONE) {
        xprintf("%s is not defined", stmt->name);
        exit(EXIT_FAILURE);
      }

      compile_expression(engine, stmt->secondExpr);

      compile_expression(engine, stmt->firstExpr);
      write_push_i(engine->writer, kind_to_segment(kind), index);
      write_arithmetic(engine->writer, ADD);

      write_pop_i(engine->writer, SEGMENT_POINTER, 1);
      write_pop_i(engine->writer, SEGMENT_THAT, 0);
      break;
    }
    default:
      xprintf("unknown let statement type");
      exit(EXIT_FAILURE);
  }
}

static void compile_while(CompilationEngine *engine, WhileStmt *stmt) {
  char *whileStart = new_label("WHILE_START", engine->labelCounter);
  char *whileFalse = new_label("WHILE_FALSE", engine->labelCounter);
  engine->labelCounter++;

  write_label(engine->writer, whileStart);

  compile_expression(engine, stmt->expr);
  write_arithmetic(engine->writer, NOT);
  write_if(engine->writer, whileFalse);

  compile_subroutineBody(engine, stmt->stmts);
  write_goto(engine->writer, whileStart);

  write_label(engine->writer, whileFalse);
}

static void compile_return(CompilationEngine *engine, ReturnStmt *stmt) {
  Expression *expr = stmt->expr;
  if (expr != NULL) {
    compile_expression(engine, stmt->expr);
  } else {
    write_push_i(engine->writer, SEGMENT_CONST, 0);
  }
  write_return(engine->writer);
}

static void compile_expression(CompilationEngine *engine, Expression *expr) {
  compile_term(engine, expr->firstTerm);

  if (expr->termPairs == NULL) return;

  for (int i = 0; i < expr->termPairs->len; i++) {
    TermPair *pair = vec_get(expr->termPairs, i);
    compile_term(engine, pair->term);
    compile_operator(engine, pair->op);
  }
}

static void compile_subroutineCall(CompilationEngine *engine, SubroutineCall *call) {
  enum SubCallType type = call->type;

  int nArgs = 0;

  // method call
  if (type == PLAIN_SUB_CALL) {
    // push "this" value onto the stack
    write_push_i(engine->writer, SEGMENT_POINTER, 0);
    if (call->exprList != NULL) {
      nArgs = call->exprList->expressions->len;
      compile_expression_list(engine, call->exprList);
    }

    write_call(engine->writer, engine->ast->name, call->subroutineName, nArgs + 1);
    return;
  }

  if (call->exprList != NULL) {
    nArgs = call->exprList->expressions->len;
  }

  char *targetType = find_type(engine, call->target);

  // static function call
  if (targetType == NULL) {
    if (call->exprList != NULL) {
      compile_expression_list(engine, call->exprList);
    }

    write_call(engine->writer, call->target, call->subroutineName, nArgs);
    return;
  }

  int index = find_index(engine, call->target);
  Kind kind = find_kind(engine, call->target);

  // method call on a object instance
  if (kind == KIND_FIELD || kind == KIND_VAR || kind == KIND_STATIC) {
    // field Ball ball; ball.getVal();
    // must be a field of another object; therefore, this should be set
    // we take what we need from (this + index)
    write_push_i(engine->writer, kind_to_segment(kind), index);
    nArgs = nArgs + 1;
  }

  if (call->exprList != NULL) {
    compile_expression_list(engine, call->exprList);
  }

  write_call(engine->writer, targetType, call->subroutineName, nArgs);
}

static void compile_term(CompilationEngine *engine, Term *term) {
  switch (term->type) {
    case TERM_INT:
      write_push(engine->writer, SEGMENT_CONST, term->integer);
      break;
    case TERM_STR: {
      size_t len = strlen(term->str);
      write_push_i(engine->writer, SEGMENT_CONST, len);
      write_call(engine->writer, "String", "new", 1);
      for (int i = 0; i < len; i++) {
        char chr = term->str[i];
        write_push_i(engine->writer, SEGMENT_CONST, chr);
        write_call(engine->writer, "String", "appendChar", 2);
      }
      break;
    }
    case TERM_KEYWORD: {
      switch (term->kConst) {
        case KC_TRUE:
          write_push_i(engine->writer, SEGMENT_CONST, 1);
          write_arithmetic(engine->writer, NEG);
          break;
        case KC_NULL: case KC_FALSE:
          write_push_i(engine->writer, SEGMENT_CONST, 0);
          break;
        case KC_THIS:
          // push the starting location of an object instance onto the stack
          // only used in constructor for "return this"
          write_push_i(engine->writer, SEGMENT_POINTER, 0);
          break;
        default:
          xprintf("undefined TERM_KEYWORD");
          exit(EXIT_FAILURE);
      }
      break;
    }
    case TERM_VAR: {
      int index = find_index(engine, term->varName);
      Kind kind = find_kind(engine, term->varName);
      write_push_i(engine->writer, kind_to_segment(kind), index);
      break;
    }
    case TERM_EXPR_PARENS: {
      compile_expression(engine, term->expr);
      break;
    }
    case TERM_TERM_PAIR: {
      TermPair *pair = term->termPair;
      compile_term(engine, pair->term);
      compile_unary_operator(engine, pair->op);
      break;
    }
    case TERM_SUB_CALL: {
      compile_subroutineCall(engine, term->subCall);
      break;
    }
    case TERM_ARRAY: {
      int index = find_index(engine, term->array->varName);
      Kind kind = find_kind(engine, term->array->varName);

      if (kind == KIND_NONE) {
        xprintf("%s is not defined", term->array->varName);
        exit(EXIT_FAILURE);
      }

      compile_expression(engine, term->array->expr);
      write_push_i(engine->writer, kind_to_segment(kind), index);
      write_arithmetic(engine->writer, ADD);
      write_pop_i(engine->writer, SEGMENT_POINTER, 1);
      write_push_i(engine->writer, SEGMENT_THAT, 0);

      break;
    }
    default:
      break;
  }
}

static void compile_expression_list(CompilationEngine *engine, ExpressionList *list) {
  Vector *exprs  = list->expressions;
  for (int i = 0; i < exprs->len; i++) {
    Expression *expr = vec_get(exprs, i);
    compile_expression(engine, expr);
  }
}

static void compile_operator(CompilationEngine *engine, char op) {
  // Multiplication  and  division  are  handled  using  the  OS  functions
  // Math.multiply() and Math.divide()
  switch(op) {
    case '+':
      write_arithmetic(engine->writer, ADD);
      break;
    case '-':
      write_arithmetic(engine->writer, SUB);
      break;
    case '*':
      write_call(engine->writer, "Math", "multiply", 2);
      break;
    case '/':
      write_call(engine->writer, "Math", "divide", 2);
      break;
    case '&':
      write_arithmetic(engine->writer, AND);
      break;
    case '|':
      write_arithmetic(engine->writer, OR);
      break;
    case '<':
      write_arithmetic(engine->writer, LT);
      break;
    case '>':
      write_arithmetic(engine->writer, GT);
      break;
    case '=':
      write_arithmetic(engine->writer, EQ);
      break;
    default:
      exit(EXIT_FAILURE);
  }
}

static void compile_unary_operator(CompilationEngine *engine, char op) {
  switch(op) {
    case '~':
      write_arithmetic(engine->writer, NOT);
      break;
    case '-':
      write_arithmetic(engine->writer, NEG);
      break;
    default:
      xprintf("%c is not implemented in compile_unary_operator", op);
      exit(EXIT_FAILURE);
  }
}

static Segment kind_to_segment(Kind kind) {
  switch (kind) {
    case KIND_VAR:
      return SEGMENT_LOCAL;
    case KIND_ARG:
      return SEGMENT_ARG;
    case KIND_FIELD:
      return SEGMENT_THIS;
    case KIND_STATIC:
      return SEGMENT_STATIC;
    default:
      xprintf("%i not implemented in kind_to_segment", kind);
      exit(EXIT_FAILURE);
  }
}

static int find_index(CompilationEngine *engine, char *identName) {
  int index = indexOf(engine->curFunc->lTable, identName);
  if (index == NO_IDENTIFIER) {
    index = indexOf(engine->ast->gTable, identName);

    if (index == NO_IDENTIFIER) {
      xprintf("%s is not defined in class %s", identName, engine->ast->name);
      exit(EXIT_FAILURE);
    }
  }

  return index;
}

static Kind find_kind(CompilationEngine *engine, char *identName) {
  Kind kind = kindOf(engine->curFunc->lTable, identName);
  if (kind == KIND_NONE) {
    kind = kindOf(engine->ast->gTable, identName);

    if (kind == KIND_NONE) {
      xprintf("%s is not defined in class %s", identName, engine->ast->name);
      exit(EXIT_FAILURE);
    }
  }

  return kind;
}

static char *find_type(CompilationEngine *engine, char *identName) {
  char *type = typeOf(engine->curFunc->lTable, identName);
  if (type == NULL) {
    type = typeOf(engine->ast->gTable, identName);
    return type;
  }

  return type;
}

static void alloc_mem(CompilationEngine *engine, int nwords) {
  // Memory.alloc(size), where size is the number of words
  write_push_i(engine->writer, SEGMENT_CONST, nwords);
  write_call(engine->writer, "Memory", "alloc", 1);
}

Questions

  • How could I improve the code organization of the compiler? Should I have used other data and procedural abstractions?
  • Are there any C language features (or libraries) that I should have used, but did not?

If there any other comments or suggestions, please let me know!

\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

First, you tackled a tough problem and you obviously put a lot of effort into it. The code is well structured. The organization of the code seems fine.

My code contains occasional free() statements, but my primary memory management strategy was not to release any memory, as the program works only for a couple of seconds.

Two seconds is a lot of time, you could fill up a lot of memory.

You may want to look into compiler development tools such as lex, flex, yacc and bison that can be used to generate the lexical analyzer and the parser.

A minor nit about indentation, 2 spaces may be too small to see the logic.

Reserved Words as Variable Names

Some users might be using C++ to compile C, the user of a variable name that is keyword in C++ such as class in main.c might therefore be a problem.

Portability

Not all C compilers provide the function xprintf(). To write to stdout by default it might be better to use printf(). To print error messages it might be better to use fprintf(stderr, FMT, Args); The header files libgen.h and dirent.h are not common header files and may not be available on all systems, for example windows.

It might be better to make use of common function such as fopen() and to write code to navigate the file system and directory.

Avoid calling exit() From Lower Level Functions

There are a number of places where exit(EXIT_FAILURE) is called, this is not a good programming practice in C. It prevents the program from cleaning up after itself and can have side effects. If this was an operating system instead of a compiler it would bring the system down. A better way would be to call setjmp() in main.c and longjmp() where the error occurs.

Use Tables and Arrays

The extended switch/case statement in the function char *keyword_to_string(KeyWord keyWord) might be better implemented as indexing into an array. This would be just as easy to maintain and would improve performance of the program.

There are 2 ways this could be implemented, the first and prefered one would be an array of strings where the integer value of the KeyWord enum is used as an index into the array.

typedef enum {
    CLASS = 0,
    STATIC = 1,
    ...
    LASTKEYWORD
}

char *KeyWordToStringValues[] = {
    "class",
    "static",
    ...
}

char *keyword_to_string(KeyWord keyWord) {
    if (keyWord < LASTKEYWORD) {
        return KeyWordToStringValues[(int) keyWord];
    }
    else {
        xprintf("%i is not specified in keyword_to_string", keyWord);
        longjmp();
    }
}

The second method would be

typedef struct {
    KeyWord keyword;
    char *stringKeyWord;
} KeyWordToken;

KeyWordToken keyWordTokens[] = {
    {CLASS, "class"},
    {STATIC, "static"},
    ...
    {FALSE, "false"}
}

char *keyword_to_string(KeyWord keyWord) {
    int keyWordCount = sizeof(keyWordTokens) / sizeof(*keyWordTokens);
    if (keyWord < keyWordCount {
        int i;
        for (i = 0; i < keyWordCount; i++) {
            if (keyWordTokens[i].keyword == keyWord) {
                return KeyWordToStringValues[(int) keyWord];
            }
        }
    }
    else {
        xprintf("%i is not specified in keyword_to_string", keyWord);
        longjmp();
    }
}

Another place where arrays might be beneficial would be to replace the varargs implementation of the function bool is_one_of(int actual, int nOfElements, ...).

KeyWord VarDeclKeywords[] = {STATIC, FIELD};
KeyWord SubroutineKeywords[] = {CONSTRUCTOR, FUNCTION, METHOD};
KeyWord TypeKeywords[] = {INT, CHAR, BOOLEAN};

bool is_one_of(KeyWord keyword, Keyword members) {
    int membersCount = sizeof(members) / sizeof(*members);
    int i;
    for (i = 0; i < membersCount; i++) {
        if (keyword = members[i]) {
            return true;
        }
    }
    return false;
}

This improves performance because there is overhead involved in using va_list argp, va_start(argp, nOfElements), va_arg(argp, int). It also simplifies the implementation in 2 ways, because varargs isn't necessary and the count of items doesn't need to be included in the function call. The count of arguments is error prone as it is implemented.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your answer! I have a followup question. I considered using arrays for holding strings more extensively (and I use this approach in some places). What put me off is that I could not find a way to keep enums and arrays in one place, but still being able to export enums to other files. Is there any way to do that? \$\endgroup\$
    – almaveln
    Apr 8, 2019 at 20:35
  • \$\begingroup\$ @almaveln Create a header file for just the enum and a refrence to the array and include it where ever you need it. The reference for the array should be extern. Create the array in one C file. Remember in C all global variables are available throughout the executable. keyword.h and termtype.h would be examples. \$\endgroup\$
    – pacmaninbw
    Apr 8, 2019 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.