3
\$\begingroup\$

Many people tell me that C++ is a significantly better language for writing compilers than JavaScript is. So, I've decided to rewrite the compiler for AEC (the programming language I've made) from JavaScript to C++ before extending it to be able to target WebAssembly (right now, it's only capable of targeting x86). So far, I've only rewritten the tokenizer and the parser, and I was wondering if you could give me some advice on how I can do that better.
File AECforWebAssembly.cpp:

#define NDEBUG
#include "parser.cpp"
#include "tests.cpp"
#include "tokenizer.cpp"
#include <iostream>
using namespace std;

int main(int argc, char **argv) {
  cout << "Running the tests..." << endl;
  runTests();
  cout << "All the tests passed." << endl;
  return 0;
}

File parser.cpp:

#include "TreeNode.cpp"
#include <algorithm>

std::vector<TreeNode>
TreeNode::applyBinaryOperators(std::vector<TreeNode> input,
                               std::vector<std::string> operators,
                               Associativity associativity) {
  using std::regex;
  using std::regex_match;
  for (int i = associativity == left ? 0 : int(input.size()) - 1;
       associativity == left ? i < int(input.size()) : i >= 0;
       i += associativity == left ? 1 : -1) {
    if (std::count(operators.begin(), operators.end(), input[i].text) and
        !input[i].children.size()) {
      if (!i or i == int(input.size()) - 1) {
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: The binary operator \"" << input[i].text
                  << "\" has less than two operands." << std::endl;
        return input;
      }
      if (!regex_match(
              input[i - 1].text,
              regex("(^(\\d|_|[a-z]|[A-Z])*$)|(^(\\d|_|[a-z]|[A-Z])+\\.("
                    "\\d|_|[a-z]|[A-Z])*$)")) and
          !input[i - 1].children.size() and input[i - 1].text.back() != '(') {
        std::cerr << "Line " << input[i - 1].lineNumber << ", Column "
                  << input[i - 1].columnNumber
                  << ", Parser error: Unexpected token \"" << input[i - 1].text
                  << "\"." << std::endl;
      }
      if (!regex_match(
              input[i + 1].text,
              regex("(^(\\d|_|[a-z]|[A-Z])*$)|(^(\\d|_|[a-z]|[A-Z])+\\.("
                    "\\d|_|[a-z]|[A-Z])*$)")) and
          !input[i + 1].children.size() and input[i - 1].text.back() != '(') {
        std::cerr << "Line " << input[i + 1].lineNumber << ", Column "
                  << input[i + 1].columnNumber
                  << ", Parser error: Unexpected token \"" << input[i - 1].text
                  << "\"." << std::endl;
      }
      input[i].children.push_back(input[i - 1]);
      input[i].children.push_back(input[i + 1]);
      input.erase(input.begin() + i + 1);
      input.erase(input.begin() + i - 1);
      i += associativity == left ? -1 : 1;
    }
  }
  return input;
}

std::vector<TreeNode> TreeNode::parseExpression(std::vector<TreeNode> input) {
#ifndef NDEBUG
  std::cerr << "DEBUG: Beginning to parse the array of tokens: "
            << JSONifyArrayOfTokens(input) << std::endl;
#endif
  auto parsedExpression = input;
  for (unsigned int i = 0; i < parsedExpression.size(); i++)
    if (parsedExpression[i].text.back() == '(' and
        !parsedExpression[i].children.size()) {
      unsigned int firstParenthesis = i;
      unsigned int nextParenthesis = i + 1;
      unsigned int counterOfOpenParentheses = 1;
      while (counterOfOpenParentheses) {
        if (nextParenthesis >= parsedExpression.size()) {
          std::cerr << "Line " << parsedExpression[i].lineNumber << ", Column "
                    << parsedExpression[i].columnNumber
                    << ", Parser error: The parenthesis is not closed!"
                    << std::endl;
          break;
        }
        if (parsedExpression[nextParenthesis].text.back() == '(')
          counterOfOpenParentheses++;
        if (parsedExpression[nextParenthesis].text == ")")
          counterOfOpenParentheses--;
        nextParenthesis++;
      }
      std::vector<TreeNode> nodesThatTheRecursionDealsWith;
      for (unsigned int i = firstParenthesis + 1; i < nextParenthesis - 1;
           i++) // Don't include the parentheses in the expression passed to the
                // recursion, otherwise you will end up in an infinite loop.
        nodesThatTheRecursionDealsWith.push_back(parsedExpression[i]);
      nodesThatTheRecursionDealsWith =
          parseExpression(nodesThatTheRecursionDealsWith);
      if (nodesThatTheRecursionDealsWith.size() > 1 and
          parsedExpression[i].text == "(") {
        std::cerr << "Line " << nodesThatTheRecursionDealsWith[1].lineNumber
                  << ", Column "
                  << nodesThatTheRecursionDealsWith[1].columnNumber
                  << ", Parser error: Unexpected token \""
                  << nodesThatTheRecursionDealsWith[1].text << "\"."
                  << std::endl;
      }
      for (auto iterator = nodesThatTheRecursionDealsWith.begin();
           iterator < nodesThatTheRecursionDealsWith.end(); iterator++)
        if (iterator->text == ",") { // Multi-argument function
          iterator--;
          nodesThatTheRecursionDealsWith.erase(iterator + 1);
        }
      if (parsedExpression[i].text ==
          "(") { // If it's not a function, but only a parenthesis, delete it.
        parsedExpression.erase(parsedExpression.begin() + firstParenthesis,
                               parsedExpression.begin() + nextParenthesis);
        parsedExpression.insert(parsedExpression.begin() + i,
                                nodesThatTheRecursionDealsWith.begin(),
                                nodesThatTheRecursionDealsWith.end());
      } else { // If it's the name of a function, don't delete it.
        parsedExpression.erase(parsedExpression.begin() + firstParenthesis + 1,
                               parsedExpression.begin() + nextParenthesis);
        parsedExpression[i].children.insert(
            parsedExpression[i].children.begin(),
            nodesThatTheRecursionDealsWith.begin(),
            nodesThatTheRecursionDealsWith.end());
      }
    }
  for (unsigned int i = 0; i < parsedExpression.size(); i++)
    if (parsedExpression[i].text.back() == '[' and
        parsedExpression[i].children.size() == 0) // Array indices
    {
      unsigned int nameOfTheArray = i;
      unsigned int counterOfArrayNames = 1;
      unsigned int closedBracket = nameOfTheArray + 1;
      while (counterOfArrayNames) {
        if (closedBracket >= parsedExpression.size()) {
          std::cerr << "Line " << parsedExpression[i].lineNumber << ", Column "
                    << parsedExpression[i].columnNumber
                    << ", Parser error: The index of the array \""
                    << parsedExpression[i].text.substr(
                           0, parsedExpression[i].text.size() - 1)
                    << "\" is not closed by \"]\"." << std::endl;
          break;
        }
        if (parsedExpression[closedBracket].text == "]")
          counterOfArrayNames--;
        if (parsedExpression[closedBracket].text.back() == '[')
          counterOfArrayNames++;
        closedBracket++;
      }
      closedBracket--;
      std::vector<TreeNode> nodesThatTheRecursionDealsWith;
      for (unsigned int i = nameOfTheArray + 1; i < closedBracket;
           i++) // Again, it's important not to include brackets in the array
                // that's passed to the recursion.
        nodesThatTheRecursionDealsWith.push_back(parsedExpression[i]);
      nodesThatTheRecursionDealsWith =
          parseExpression(nodesThatTheRecursionDealsWith);
      if (nodesThatTheRecursionDealsWith.size() == 0) {
        std::cerr << "Line " << parsedExpression[i].lineNumber << ", Column "
                  << parsedExpression[i].columnNumber
                  << ", Parser error: Array index of the array \""
                  << parsedExpression[i].text.substr(
                         0, parsedExpression[i].text.size() -
                                1) // Don't print the '[' character at the end
                                   // of the array name (as the array name is
                                   // visible to the parser).
                  << "\" is empty!" << std::endl;
        break;
      }
      if (nodesThatTheRecursionDealsWith.size() > 1) {
        std::cerr << "Line " << nodesThatTheRecursionDealsWith[1].lineNumber
                  << ", Column "
                  << nodesThatTheRecursionDealsWith[1].columnNumber
                  << ", Parser error: Unexpected token \""
                  << nodesThatTheRecursionDealsWith[1].text << "\"!"
                  << std::endl;
      }
      parsedExpression[i].children.insert(
          parsedExpression[i].children.begin(),
          nodesThatTheRecursionDealsWith.begin(),
          nodesThatTheRecursionDealsWith.end());
      parsedExpression.erase(
          parsedExpression.begin() + nameOfTheArray +
              1, // It's important to exclude the name of the array from the
                 // portion about to be erased.
          parsedExpression.begin() + closedBracket +
              1 // And it's also important to include the closing bracket into
                // the portion about to be erased.
      );
    }
  for (unsigned int i = 0; i < parsedExpression.size(); i++)
    if (parsedExpression[i].text == "{") // Array initializer
    {
      unsigned int openCurlyBrace = i;
      unsigned int closedCurlyBrace = i + 1;
      unsigned int curlyBracesCounter = 1;
      while (curlyBracesCounter) {
        if (closedCurlyBrace >= parsedExpression.size()) {
          std::cerr << "Line " << parsedExpression[i].lineNumber << ", Column "
                    << parsedExpression[i].columnNumber
                    << ", Parser error: The curly brace \"{\" isn't closed!"
                    << std::endl;
          break;
        }
        if (parsedExpression[closedCurlyBrace].text == "}")
          curlyBracesCounter--;
        if (parsedExpression[closedCurlyBrace].text == "{")
          curlyBracesCounter++;
        closedCurlyBrace++;
      }
      closedCurlyBrace--;
      std::vector<TreeNode> nodesThatTheRecursionDealsWith(
          parsedExpression.begin() + openCurlyBrace + 1,
          parsedExpression.begin() +
              closedCurlyBrace); // We aren't in JavaScript, let's use the
                                 // features of C++, such as the iterator range
                                 // constructors...
      nodesThatTheRecursionDealsWith =
          parseExpression(nodesThatTheRecursionDealsWith);
      nodesThatTheRecursionDealsWith.erase(
          std::remove_if(nodesThatTheRecursionDealsWith.begin(),
                         nodesThatTheRecursionDealsWith.end(),
                         [](TreeNode node) { return node.text == ","; }),
          nodesThatTheRecursionDealsWith.end()); //...and lambda functions.
#ifndef NDEBUG
      std::cerr << "DEBUG: After std::remove_if, we are dealing with: "
                << JSONifyArrayOfTokens(nodesThatTheRecursionDealsWith)
                << std::endl;
#endif
      parsedExpression[openCurlyBrace].children.insert(
          parsedExpression[openCurlyBrace].children.begin(),
          nodesThatTheRecursionDealsWith.begin(),
          nodesThatTheRecursionDealsWith.end());
      parsedExpression.erase(parsedExpression.begin() + openCurlyBrace + 1,
                             parsedExpression.begin() + closedCurlyBrace + 1);
      parsedExpression[openCurlyBrace].text = "{}";
    }
  for (int i = parsedExpression.size() - 1; i >= 0;
       i--) // The unary "-" operator.
    if (parsedExpression[i].text == "-" and
        i != int(parsedExpression.size()) - 1 and
        parsedExpression[i].children.size() == 0 and
        (!i or
         (!std::regex_match(parsedExpression[i - 1].text,
                            std::regex("(^(\\d|_|[a-z]|[A-Z])*$)|(^(\\d|_|[a-z]"
                                       "|[A-Z])+\\.(\\d|_|[a-z]|[A-Z])*$)")) and
          parsedExpression[i - 1].text.back() != '(' and
          parsedExpression[i - 1].children.size() == 0))) {
      parsedExpression[i].children.push_back(
          TreeNode("0", parsedExpression[i].lineNumber,
                   parsedExpression[i].columnNumber));
      parsedExpression[i].children.push_back(parsedExpression[i + 1]);
      parsedExpression.erase(parsedExpression.begin() + i + 1);
    }
  std::vector<std::vector<std::string>> leftAssociativeBinaryOperators(
      {{"*", "/"}, {"-", "+"}, {"<", ">", "="}, {"and"}, {"or"}});
  parsedExpression =
      applyBinaryOperators(parsedExpression, {"."}, Associativity::right);
  for (unsigned int i = 0; i < leftAssociativeBinaryOperators.size(); i++)
    parsedExpression = applyBinaryOperators(parsedExpression,
                                            leftAssociativeBinaryOperators[i],
                                            Associativity::left);
  for (int i = parsedExpression.size() - 1; i >= 0;
       i--) // The ternary conditional "?:" operator (it's right-associative).
    if (parsedExpression[i].text == ":") {
      if (i == int(parsedExpression.size()) - 1) {
        std::cerr << "Line " << parsedExpression[i].lineNumber << ", Column "
                  << parsedExpression[i].columnNumber
                  << ", Parser error: The ternary operator \"?:\" has less "
                     "than three operands."
                  << std::endl;
        break;
      }
      int colon = i;
      int questionMark = i - 1;
      int colonCounter = 1;
      while (colonCounter) {
        if (questionMark < 0) {
          std::cerr << "Line " << parsedExpression[colon].lineNumber
                    << ", Column " << parsedExpression[colon].columnNumber
                    << ", Parser error: Unexpected token \":\"!" << std::endl;
          break;
        }
        if (parsedExpression[questionMark].text == "?")
          colonCounter--;
        if (parsedExpression[questionMark].text == ":")
          colonCounter++;
        questionMark--;
      }
      questionMark++;
      if (!questionMark) {
        std::cerr << "Line " << parsedExpression[questionMark].lineNumber
                  << ", Column " << parsedExpression[questionMark].columnNumber
                  << ", Parser error: The ternary operator \"?:\" has less "
                     "than three operands."
                  << std::endl;
        break;
      }
      std::vector<TreeNode> nodesThatTheRecursionDealsWith;
      for (int i = questionMark + 1; i < colon; i++)
        nodesThatTheRecursionDealsWith.push_back(parsedExpression[i]);
      nodesThatTheRecursionDealsWith =
          parseExpression(nodesThatTheRecursionDealsWith);
      if (nodesThatTheRecursionDealsWith.size() > 1) {
        std::cerr << "Line " << nodesThatTheRecursionDealsWith[1].lineNumber
                  << ", Column "
                  << nodesThatTheRecursionDealsWith[1].columnNumber
                  << ", Parser error: Unexpected token \""
                  << nodesThatTheRecursionDealsWith[1].text << "\"!"
                  << std::endl;
        break;
      }
      if (nodesThatTheRecursionDealsWith.size() == 0) {
        std::cerr << "Line " << parsedExpression[questionMark].lineNumber
                  << ", Column " << parsedExpression[questionMark].columnNumber
                  << ", Parser error: The ternary operator \"?:\" has less "
                     "than three operands!"
                  << std::endl;
        break;
      }
      parsedExpression[questionMark].text = "?:";
      parsedExpression[questionMark].children.push_back(
          parsedExpression[questionMark - 1]); // Condition
      parsedExpression[questionMark].children.push_back(
          nodesThatTheRecursionDealsWith[0]); // Then-clause
      parsedExpression[questionMark].children.push_back(
          parsedExpression[colon + 1]); // Else-clause
      parsedExpression.erase(parsedExpression.begin() + questionMark - 1);
      parsedExpression.erase(parsedExpression.begin() + questionMark,
                             parsedExpression.begin() + colon + 1);
      i = questionMark;
    }
  parsedExpression =
      applyBinaryOperators(parsedExpression, {":="}, Associativity::right);
#ifndef NDEBUG
  std::cerr << "DEBUG: Returning the array: "
            << JSONifyArrayOfTokens(parsedExpression) << std::endl;
#endif
  return parsedExpression;
}

std::vector<TreeNode>
TreeNode::parseVariableDeclaration(std::vector<TreeNode> input) {
  auto inputWithParenthesesParsed = parseExpression(input);
  if (input.size() < 2) {
    std::cerr << "Line " << inputWithParenthesesParsed[0].lineNumber
              << ", Column " << inputWithParenthesesParsed[0].columnNumber
              << ", Parser error: Unexpected token \""
              << inputWithParenthesesParsed[0].text << "\"!" << std::endl;
    return inputWithParenthesesParsed;
  }
  for (unsigned i = 0; i < inputWithParenthesesParsed.size(); i++)
    if (inputWithParenthesesParsed[i].text == ":=") // Initial assignments.
    {
      TreeNode nodeWithVariableName =
          inputWithParenthesesParsed[i]
              .children[0]; // Let's assume the parser has done a good job thus
                            // far.
      TreeNode NodeWithAssignment = inputWithParenthesesParsed[i].children[1];
      TreeNode temporaryNode =
          TreeNode(":=", inputWithParenthesesParsed[i].lineNumber,
                   inputWithParenthesesParsed[i].columnNumber);
      temporaryNode.children.push_back(NodeWithAssignment);
      nodeWithVariableName.children.push_back(temporaryNode);
      inputWithParenthesesParsed[i] = nodeWithVariableName;
    }
  inputWithParenthesesParsed.erase(
      std::remove_if(inputWithParenthesesParsed.begin(),
                     inputWithParenthesesParsed.end(),
                     [](TreeNode node) { return node.text == ","; }),
      inputWithParenthesesParsed.end());
  inputWithParenthesesParsed[0].children.insert(
      inputWithParenthesesParsed[0].children.begin(),
      inputWithParenthesesParsed.begin() + 1, inputWithParenthesesParsed.end());
  inputWithParenthesesParsed.erase(inputWithParenthesesParsed.begin() + 1,
                                   inputWithParenthesesParsed.end());
  return inputWithParenthesesParsed;
}

std::vector<TreeNode> TreeNode::parse(std::vector<TreeNode> input) {
  typedef std::vector<TreeNode> TreeNodes;
#ifndef NDEBUG // Well, constructors and all those object-oriented things in C++
               // are only useful if you know what you're doing. If you don't,
               // you are shooting yourself in the foot, like I did here.
  if (input.size()) {
    std::cerr << "DEBUG: Basic data type sizes are:\n";
    for (auto i = input[0].basicDataTypeSizes.begin();
         i != input[0].basicDataTypeSizes.end(); i++)
      std::cerr << "DEBUG: " << i->first << "\t" << i->second << '\n';
    std::flush(std::cerr);
  }
#endif
  for (unsigned i = 0; i < input.size(); i++)
    if (input[i].basicDataTypeSizes.count(input[i].text) and
        input[i].children.empty()) { // Declaration of a variable of a basic
                                     // type (Integer32...).
#ifndef NDEBUG
      std::cerr << "DEBUG: Parsing a variable declaration at line "
                << input[i].lineNumber << " of the type " << input[i].text
                << "." << std::endl;
#endif
      unsigned int typeName = i;
      unsigned int semicolon = i + 1;
      while (true) {
        if (semicolon >= input.size()) {
          std::cerr << "Line " << input[typeName].lineNumber << ", Column "
                    << input[typeName].columnNumber
                    << ", Parser error: Expected a semi-colon to end the "
                       "variable declaration of type "
                    << input[typeName].text << "!" << std::endl;
          break;
        }
        if (input[semicolon].text == ";")
          break;
        semicolon++;
      }
      TreeNodes nodesThatTheRecursionDealsWith(input.begin() + typeName,
                                               input.begin() + semicolon);
      nodesThatTheRecursionDealsWith =
          parseVariableDeclaration(nodesThatTheRecursionDealsWith);
      input[typeName] = nodesThatTheRecursionDealsWith[0];
      input.erase(input.begin() + typeName + 1, input.begin() + semicolon);
    } else if (input[i].text == "InstantiateStructure" and
               input[i].children.empty()) {
      if (i == input.size() - 1) {
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: Unexpected end of file!" << std::endl;
        return input;
      }
      unsigned int typeName = i;
      unsigned int semicolon = i + 1;
      while (true) {
        if (semicolon >= input.size()) {
          std::cerr << "Line " << input[typeName].lineNumber << ", Column "
                    << input[typeName].columnNumber
                    << ", Parser error: Expected a semicolon to end the "
                       "variable declaration of type "
                    << input[typeName + 1].text << "!" << std::endl;
          break;
        }
        if (input[semicolon].text == ";")
          break;
        semicolon++;
      }
      TreeNodes nodesThatTheRecursionDealsWith(input.begin() + typeName + 1,
                                               input.begin() + semicolon);
      nodesThatTheRecursionDealsWith =
          parseVariableDeclaration(nodesThatTheRecursionDealsWith);
      input[typeName].children.push_back(nodesThatTheRecursionDealsWith[0]);
      input.erase(input.begin() + typeName + 1, input.begin() + semicolon);
    } else if (input[i].text == "Function") {
      if (i == input.size() - 1) {
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: Unexpected end of file!" << std::endl;
        return input;
      }
      if (input[i + 1].text.back() != '(' or input[i + 1].text.size() == 1) {
        std::cerr << "Line " << input[i + 1].lineNumber << ", Column "
                  << input[i + 1].columnNumber
                  << ", Parser error: Expected a function name instead of \""
                  << input[i + 1].text << "\"!" << std::endl;
        return input;
      }
      unsigned int functionName = i + 1;
      unsigned int endOfFunctionSignature = i + 2;
      unsigned int counterOfParentheses = 1;
      while (counterOfParentheses) {
        if (endOfFunctionSignature >= input.size()) {
          std::cerr << "Line " << input[functionName].lineNumber
                    << ", Column: " << input[functionName].columnNumber
                    << ", Parser error: Parenthesis in \""
                    << input[functionName].text << "\" not closed!";
          break;
        }
        if (input[endOfFunctionSignature].text == ")")
          counterOfParentheses--;
        if (input[endOfFunctionSignature].text.back() == '(')
          counterOfParentheses++;
        endOfFunctionSignature++;
      }
      TreeNodes functionArguments(input.begin() + functionName + 1,
                                  input.begin() + endOfFunctionSignature - 1);
      input.erase(input.begin() + functionName + 1,
                  input.begin() + endOfFunctionSignature);
      TreeNodes argument;
      for (unsigned int i = 0; i < functionArguments.size() + 1; i++) {
        if (i == functionArguments.size() or functionArguments[i].text == ",") {
          input[functionName].children.push_back(
              parseVariableDeclaration(argument)[0]);
          argument = TreeNodes();
        } else
          argument.push_back(functionArguments[i]);
      }
      if (functionName > input.size() - 5) {
        std::cerr
            << "Line " << input[functionName].lineNumber << ", Column "
            << input[functionName].columnNumber
            << ", Parser error: Expected a function declaration of the format "
               "\"Function function_name(argument list) Which Returns "
               "type_name Does\" or \"Function function_name(argument list) "
               "Which Returns type_name Is External;\"!"
            << std::endl;
        return input;
      }
      if (input[functionName + 1].text != "Which") {
        std::cerr << "Line " << input[functionName + 1].lineNumber
                  << ", Column " << input[functionName + 1].columnNumber
                  << ", Parser error: Expected \"Which\" instead of \""
                  << input[functionName + 1].text << "\"!" << std::endl;
        return input;
      }
      if (input[functionName + 2].text != "Returns") {
        std::cerr << "Line " << input[functionName + 2].lineNumber
                  << ", Column " << input[functionName + 2].columnNumber
                  << ", Parser error: Expected \"Returns\" instead of \""
                  << input[functionName + 2].text << "\"!" << std::endl;
        return input;
      }
      input[functionName - 1].children.push_back(input[functionName]);
      input[functionName + 2].children.push_back(input[functionName + 3]);
      input[functionName - 1].children.push_back(input[functionName + 2]);
      if (input[functionName + 4].text == "Is") // External function
      {
        if (input[functionName + 5].text != "External") {
          std::cerr << "Line " << input[functionName + 5].lineNumber
                    << ", Column " << input[functionName + 5].columnNumber
                    << ", Parser error: Expected \"External\" instead of \""
                    << input[functionName + 5].text << "\"!" << std::endl;
          return input;
        }
        if (input[functionName + 6].text != ";") {
          std::cerr << "Line " << input[functionName + 6].lineNumber
                    << ", Column " << input[functionName + 6].columnNumber
                    << ", Parser error: Expected \";\" instead of \""
                    << input[functionName + 5].text << "\"!" << std::endl;
          return input;
        }
        input[functionName - 1].children.push_back(input[functionName + 5]);
        input.erase(
            input.begin() + functionName,
            input.begin() + functionName +
                7); // Delete all up to, and including, the semicolon ";".
      } else if (input[functionName + 4].text ==
                 "Does") // Function implemented in this file (right here).
      {
        unsigned int endOfTheFunction = functionName + 5;
        while (true) {
          if (endOfTheFunction >= input.size()) {
            std::cerr << "Line " << input[functionName + 4].lineNumber
                      << ", Column " << input[functionName + 5].columnNumber
                      << ", Parser error: The end of the function is not "
                         "marked with \"EndFunction\"."
                      << std::endl;
            break;
          }
          if (input[endOfTheFunction].text == "EndFunction")
            break;
          endOfTheFunction++;
        }
        TreeNodes nodesThatTheRecursionDealsWith(
            input.begin() + functionName + 5, input.begin() + endOfTheFunction);
        nodesThatTheRecursionDealsWith = parse(nodesThatTheRecursionDealsWith);
        input[functionName + 4].children.insert(
            input[functionName + 4].children.begin(),
            nodesThatTheRecursionDealsWith.begin(),
            nodesThatTheRecursionDealsWith.end());
        input[functionName - 1].children.push_back(input[functionName + 4]);
        input.erase(input.begin() + functionName,
                    input.begin() + endOfTheFunction +
                        1); // Because now it's all supposed to be the children
                            // of the "Function" node.
      } else {
        std::cerr << "Line " << input[functionName + 4].lineNumber
                  << ", Column " << input[functionName + 4].columnNumber
                  << ", Parser error: Expected either \"Is\" or \"Does\" "
                     "instead of \""
                  << input[functionName + 4].text << "\"." << std::endl;
        return input;
      }
    } else if (input[i].text == "While" and input[i].children.empty()) {
      auto iteratorOfTheLoopToken =
          std::find_if(input.begin(), input.end(),
                       [](TreeNode node) { return node.text == "Loop"; });
      if (iteratorOfTheLoopToken == input.end())
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: There is a \"While\" token without its "
                     "corresponding \"Loop\" token!"
                  << std::endl;
      TreeNodes condition(input.begin() + i + 1, iteratorOfTheLoopToken);
      condition = parseExpression(condition);
      if (condition.size() == 0) {
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: No expression between \"While\" and "
                     "\"Loop\" tokens!"
                  << std::endl;
        condition.push_back(
            TreeNode("0", input[i].lineNumber, input[i].columnNumber));
      }
      if (condition.size() > 1)
        std::cerr << "Line " << condition[1].lineNumber << ", Column "
                  << condition[1].columnNumber
                  << ", Parser error: Unexpected token \"" << condition[1].text
                  << "\"" << std::endl;
      input[i].children.push_back(condition[0]);
      if (iteratorOfTheLoopToken ==
          input.end()) // If there is no "Loop" token...
      {
        input.erase(input.begin() + i + 1, input.end());
        return input;
      }
      auto iteratorOfTheEndWhileToken = iteratorOfTheLoopToken;
      unsigned int counterOfWhileLoops = 1;
      do {
        iteratorOfTheEndWhileToken++;
        if (iteratorOfTheEndWhileToken == input.end())
          break;
        if (iteratorOfTheEndWhileToken->text == "While")
          counterOfWhileLoops++;
        if (iteratorOfTheEndWhileToken->text == "EndWhile")
          counterOfWhileLoops--;
      } while (counterOfWhileLoops);
      if (iteratorOfTheEndWhileToken == input.end())
        std::cerr << "Line " << iteratorOfTheLoopToken->lineNumber
                  << ", Column " << iteratorOfTheLoopToken->columnNumber
                  << ", Parser error: There is a \"Loop\" token without a "
                     "corresponding \"EndWhile\" token."
                  << std::endl;
      TreeNodes nodesThatTheRecursionDealsWith(iteratorOfTheLoopToken + 1,
                                               iteratorOfTheEndWhileToken);
      nodesThatTheRecursionDealsWith = parse(nodesThatTheRecursionDealsWith);
      iteratorOfTheLoopToken->children.insert(
          iteratorOfTheLoopToken->children.begin(),
          nodesThatTheRecursionDealsWith.begin(),
          nodesThatTheRecursionDealsWith.end());
      input[i].children.push_back(*iteratorOfTheLoopToken);
      input.erase(
          input.begin() + i + 1,
          iteratorOfTheEndWhileToken == input.end()
              ? iteratorOfTheEndWhileToken
              : iteratorOfTheEndWhileToken +
                    1); // If the "EndWhile" token exists, delete it now.
    } else if (input[i].text == "Return" and input[i].children.empty()) {
      auto iteratorOfTheSemicolon =
          std::find_if(input.begin() + i, input.end(),
                       [](TreeNode node) { return node.text == ";"; });
      if (iteratorOfTheSemicolon == input.end())
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: The return statement is not terminated "
                     "with a semicolon."
                  << std::endl;
      TreeNodes expression(input.begin() + i + 1, iteratorOfTheSemicolon);
      expression = parseExpression(expression);
      if (expression.size() > 1)
        std::cerr << "Line " << expression[1].lineNumber << ", Column "
                  << expression[1].columnNumber
                  << ", Parser error: Unexpected token \"" << expression[1].text
                  << "\"" << std::endl;
      if (expression.size())
        input[i].children.push_back(
            expression[0]); // The function can return nothing at all, the
                            // parser must not segfault then!
      input.erase(input.begin() + i + 1, (iteratorOfTheSemicolon == input.end())
                                             ? iteratorOfTheSemicolon
                                             : iteratorOfTheSemicolon + 1);
    } else if (input[i].text == "If" and input[i].children.empty()) {
      auto iteratorPointingToTheThenToken =
          std::find_if(input.begin() + i, input.end(),
                       [](TreeNode node) { return node.text == "Then"; });
      if (iteratorPointingToTheThenToken == input.end())
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: There is a \"If\" without a "
                     "corresponding \"Then\"!"
                  << std::endl;
      TreeNodes condition(input.begin() + i + 1,
                          iteratorPointingToTheThenToken);
      condition = parseExpression(condition);
      if (condition.empty()) {
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: No expression between \"If\" and "
                     "\"Then\" tokens!"
                  << std::endl;
        condition.push_back(
            TreeNode("0", input[i].lineNumber, input[i].columnNumber));
      }
      if (condition.size() > 1)
        std::cerr << "Line " << condition[1].lineNumber << ", Column "
                  << condition[1].columnNumber
                  << ", Parser error: Unexpected token \"" << condition[1].text
                  << "\"!" << std::endl;
      input[i].children.push_back(condition.front());
      if (iteratorPointingToTheThenToken ==
          input.end()) // If there is no "Then"...
      {
        input.erase(input.begin() + i + 1, input.end());
        return input;
      }
      auto iteratorPointingToTheEndIfToken = iteratorPointingToTheThenToken;
      int counterOfIfBranches = 1;
      do {
        iteratorPointingToTheEndIfToken++;
        if (iteratorPointingToTheEndIfToken == input.end()) {
          std::cerr << "Line " << iteratorPointingToTheThenToken->lineNumber
                    << ", Column "
                    << iteratorPointingToTheThenToken->columnNumber
                    << ", Parser error: There is a \"Then\" token without the "
                       "corresponding \"EndIf\" token!"
                    << std::endl;
          break;
        }
        if (iteratorPointingToTheEndIfToken->text == "EndIf")
          counterOfIfBranches--;
        if (iteratorPointingToTheEndIfToken->text == "If")
          counterOfIfBranches++; // Don't look for "Then" tokens, because they
                                 // also come after the "ElseIf" statements.
      } while (counterOfIfBranches);
      auto iteratorPointingToTheElseIfToken = iteratorPointingToTheThenToken;
      counterOfIfBranches = 0;
      while (iteratorPointingToTheElseIfToken <
             iteratorPointingToTheEndIfToken) {
        if (!counterOfIfBranches and
            iteratorPointingToTheElseIfToken->text == "ElseIf")
          break; // If the "ElseIf" is referring to the "If" token at
                 // "input[i]", rather than to some nested "If" (which it does if
                 // "counterOfIfBranches" is non-zero).
        if (iteratorPointingToTheElseIfToken->text == "If")
          counterOfIfBranches++;
        if (iteratorPointingToTheElseIfToken->text == "EndIf")
          counterOfIfBranches--;
        iteratorPointingToTheElseIfToken++;
      }
      if (iteratorPointingToTheElseIfToken <
          iteratorPointingToTheEndIfToken) { // If there is an "ElseIf"
                                             // referring to this "If".
        TreeNodes nodesThatTheRecursionDealsWith(
            iteratorPointingToTheThenToken + 1,
            iteratorPointingToTheElseIfToken);
        nodesThatTheRecursionDealsWith = parse(nodesThatTheRecursionDealsWith);
        iteratorPointingToTheThenToken->children.insert(
            iteratorPointingToTheThenToken->children.begin(),
            nodesThatTheRecursionDealsWith.begin(),
            nodesThatTheRecursionDealsWith.end());
        input[i].children.push_back(*iteratorPointingToTheThenToken);
        iteratorPointingToTheElseIfToken->text = "Else";
        nodesThatTheRecursionDealsWith =
            TreeNodes(iteratorPointingToTheElseIfToken,
                      iteratorPointingToTheEndIfToken == input.end()
                          ? iteratorPointingToTheEndIfToken
                          : iteratorPointingToTheEndIfToken + 1);
        nodesThatTheRecursionDealsWith[0].text = "If";
        nodesThatTheRecursionDealsWith = parse(nodesThatTheRecursionDealsWith);
        iteratorPointingToTheElseIfToken->children.insert(
            iteratorPointingToTheElseIfToken->children.begin(),
            nodesThatTheRecursionDealsWith.begin(),
            nodesThatTheRecursionDealsWith.end());
        input[i].children.push_back(
            *iteratorPointingToTheElseIfToken); // Will appear as the "Else"
                                                // token to the compiler.
        input.erase(
            input.begin() + i + 1,
            iteratorPointingToTheEndIfToken == input.end()
                ? input.end()
                : iteratorPointingToTheEndIfToken +
                      1); // If there is an "EndIf" token, delete it as well.
      } else // No "ElseIf" token, but maybe there is an "Else" token. Let's
             // search for it!
      {
        auto iteratorPointingToTheElseToken = iteratorPointingToTheThenToken;
        counterOfIfBranches = 0;
        while (iteratorPointingToTheElseToken <
               iteratorPointingToTheEndIfToken) {
          if (!counterOfIfBranches and
              iteratorPointingToTheElseToken->text == "Else")
            break;
          if (iteratorPointingToTheElseToken->text == "If")
            counterOfIfBranches++;
          if (iteratorPointingToTheElseToken->text == "EndIf")
            counterOfIfBranches--;
          iteratorPointingToTheElseToken++;
        }
        if (iteratorPointingToTheElseToken <
            iteratorPointingToTheEndIfToken) // If there is an "Else" token...
        {
          TreeNodes nodesThatTheRecursionDealsWith(
              iteratorPointingToTheThenToken + 1,
              iteratorPointingToTheElseToken);
          nodesThatTheRecursionDealsWith =
              parse(nodesThatTheRecursionDealsWith);
          iteratorPointingToTheThenToken->children =
              nodesThatTheRecursionDealsWith;
          input[i].children.push_back(*iteratorPointingToTheThenToken);
          nodesThatTheRecursionDealsWith =
              TreeNodes(iteratorPointingToTheElseToken + 1,
                        iteratorPointingToTheEndIfToken);
          nodesThatTheRecursionDealsWith =
              parse(nodesThatTheRecursionDealsWith);
          iteratorPointingToTheElseToken->children =
              nodesThatTheRecursionDealsWith;
          input[i].children.push_back(*iteratorPointingToTheElseToken);
          input.erase(input.begin() + i + 1,
                      iteratorPointingToTheEndIfToken == input.end()
                          ? input.end()
                          : iteratorPointingToTheEndIfToken + 1);
        } else { // There is neither an "Else" nor an "ElseIf" token, so we can
                 // simply pass the tokens between (but not including) "Then" and
                 // "EndIf" token.
          TreeNodes nodesThatTheRecursionDealsWith(
              iteratorPointingToTheThenToken + 1,
              iteratorPointingToTheEndIfToken);
          nodesThatTheRecursionDealsWith =
              parse(nodesThatTheRecursionDealsWith);
          iteratorPointingToTheThenToken->children =
              nodesThatTheRecursionDealsWith;
          input[i].children.push_back(*iteratorPointingToTheThenToken);
          input.erase(input.begin() + i + 1,
                      iteratorPointingToTheEndIfToken == input.end()
                          ? input.end()
                          : iteratorPointingToTheEndIfToken + 1);
        }
      }
    } else { // Assume that what follows is an expression, presumably including
             // a ":=".
      auto iteratorPointingToTheNextSemicolon =
          std::find_if(input.begin() + i, input.end(),
                       [](TreeNode node) { return node.text == ";"; });
      if (iteratorPointingToTheNextSemicolon == input.end())
        std::cerr << "Line " << input[i].lineNumber << ", Column "
                  << input[i].columnNumber
                  << ", Parser error: The expression starting with \""
                  << input[i].text << "\" is not ended in a semicolon!"
                  << std::endl;
      TreeNodes expression(input.begin() + i,
                           iteratorPointingToTheNextSemicolon);
      expression = parseExpression(expression);
      if (expression.size() > 1)
        std::cerr << "Line " << expression[1].lineNumber << ", Column "
                  << expression[1].columnNumber
                  << ", Parser error: Unexpected token \"" << expression[1].text
                  << "\"!" << std::endl;
      input.erase(
          input.begin() + i,
          (iteratorPointingToTheNextSemicolon != input.end())
              ? iteratorPointingToTheNextSemicolon + 1
              : iteratorPointingToTheNextSemicolon); // If there is a semicolon
                                                     // terminating the
                                                     // expression, delete it
                                                     // together with the
                                                     // expression.
      input.insert(input.begin() + i, expression.begin(), expression.end());
      i += expression.size() - 1;
    }
  return input;
}

File tests.cpp:

#include "TreeNode.cpp"

struct test { // When the debugger doesn't work, "cassert" doesn't help a lot.
  std::string input, expectedResult;
};

void tokenizerTests() {
  std::vector<test> tests(
      {{"\"/*Comment inside a string*/\"",
        "['\"/*Comment inside a string*/\"']"},
       {"5+5", "['5','+','5']"},
       {"5+5=10", "['5','+','5','=','10']"},
       {"structureName.structureMember/3.14159265359",
        "['structureName','.','structureMember','/','3.14159265359']"},
       {"sin(pi/2)=1", "['sin(','pi','/','2',')','=','1']"},
       {"'A'+2='C'", "['65','+','2','=','67']"},
       {"a:=a+1; //Some random comment.\nb:=b-1;",
        "['a',':=','a','+','1',';','b',':=','b','-','1',';']"},
       {"/*This should be tokenized into\nan empty string*/", "[]"},
       {"a/*Randomly\ninserted\ncomment.*/+/*Another\nrandom\ncomment*/b",
        "['a','+','b']"},
       {"array_name:={1,1+1,1+1+1}", "['array_name',':=','{','1',',','1','+','"
                                     "1',',','1','+','1','+','1','}']"}});
  for (unsigned int i = 0; i < tests.size(); i++) {
    std::string result =
        TreeNode::JSONifyArrayOfTokens(TreeNode::tokenize(tests[i].input));
    if (result != tests[i].expectedResult) {
      std::cerr << "Internal compiler error: Tokenizer test failed: \""
                << tests[i].input << "\" tokenizes into \"" << result
                << "\" instead of to \"" << tests[i].expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
  }
}

void simpleParserTests() {
  std::vector<test> tests(
      {{"5+3", "(+ 5 3)"},
       {"2+3*4", "(+ 2 (* 3 4))"},
       {"2+2<5 and 3.14159265359<3.2",
        "(and (< (+ 2 2) 5) (< 3.14159265359 3.2))"},
       {"1-2-3-4", "(- (- (- 1 2) 3) 4)"},
       {"a:=b:=c", "(:= a (:= b c))"},
       {"3.14.16", "(. 3.14 16)"},
       {"1*(2+3)", "(* 1 (+ 2 3))"},
       {"pow(2+2/*A nonsensical expression,\nbut good for "
        "testing the parser.*/,sin(pi/2))",
        "(pow (+ 2 2) (sin (/ pi 2)))"},
       {"some_procedure()", "some_procedure("},
       {"abs(function_returning_pi()-pi)<1/1000",
        "(< (abs (- function_returning_pi( pi)) (/ 1 1000))"},
       {"not(d=0)?c/d:0", "(?: (not (= d 0)) (/ c d) 0)"},
       {"(2+2>5?3+3<7?1:0-2:2+2-4<1?0:2+2<4?0-1:0-3)",
        "(?: (> (+ 2 2) 5) (?: (< (+ 3 3) 7) 1 (- 0 2)) (?: (< (- (+ 2 2) 4) "
        "1) 0 (?: (< (+ 2 2) 4) (- 0 1) (- 0 3))))"},
       {"(2+2>5?3+3<7?1:-2:2+2-4<1?0:2+2<4?-1:-3)",
        "(?: (> (+ 2 2) 5) (?: (< (+ 3 3) 7) 1 (- 0 2)) (?: (< (- (+ 2 2) 4) "
        "1) 0 (?: (< (+ 2 2) 4) (- 0 1) (- 0 3))))"},
       {"some_array[i+1]", "(some_array (+ i 1))"},
       {"array_pointer:={1,1+1,1+1+1}",
        "(:= array_pointer ({} 1 (+ 1 1) (+ (+ 1 1) 1)))"}});
  for (unsigned int i = 0; i < tests.size(); i++) {
    std::string result =
        TreeNode::parseExpression(TreeNode::tokenize(tests[i].input))[0]
            .getLispExpression();
    if (result != tests[i].expectedResult) {
      std::cerr << "Internal compiler error: Basic parser test failed: \""
                << tests[i].input << "\" parses into \"" << result
                << "\" instead of to \"" << tests[i].expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
  }
}

void interpreterTests() {
  std::vector<test> tests(
      {{"1+2*3", "7"},
       {"(1+2)*3", "9"},
       {"(2+2=4)?2:0", "2"},
       {"mod(5,2)", "1"},
       {"(2+2>5?3+3<7?1:-2:2+2-4<1?0:2+2<4?-1:-3)+('A'+2='C'?0:-1)", "0"}});
  for (unsigned int i = 0; i < tests.size(); i++) {
    std::string result = std::to_string(
        TreeNode::parseExpression(TreeNode::tokenize(tests[i].input))[0]
            .interpretAsACompileTimeConstant());
    if (result != tests[i].expectedResult) {
      std::cerr << "Internal compiler error: Interpreter test failed: \""
                << tests[i].input << "\" interprets into \"" << result
                << "\" instead of to \"" << tests[i].expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
  }
}

void parsingVariableDeclarationsTests() {
  std::vector<test> tests(
      {{"Integer32 some_array[80*23],array_width:=80,array_height:=23",
        "(Integer32 (some_array (* 80 23)) (array_width (:= 80)) (array_height "
        "(:= 23)))"}});
  for (unsigned int i = 0; i < tests.size(); i++) {
    std::string result = TreeNode::parseVariableDeclaration(
                             TreeNode::tokenize(tests[i].input))[0]
                             .getLispExpression();
    if (result != tests[i].expectedResult) {
      std::cerr << "Internal compiler error: Parser test failed: \""
                << tests[i].input << "\" parses into \"" << result
                << "\" instead of to \"" << tests[i].expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
  }
}

void parserTests() {
  std::vector<test> tests(
      {{"Integer32 some_array[80*23],array_width:=80,array_height:=23;",
        "(Integer32 (some_array (* 80 23)) (array_width (:= 80)) (array_height "
        "(:= 23)))"},
       {"Function log(CharPointer string) Which Returns Nothing Is External;",
        "(Function (log (CharPointer string)) (Returns Nothing) External)"},
       {"Function foo(Integer32 a:=0, Integer32 c) Which Returns Nothing Does "
        "//Nonsense "
        "code, but useful to see if the parser is capable of parsing simple "
        "functions.\n"
        "Integer32 b;\n"
        "b:=a+1;\n"
        "EndFunction",
        "(Function (foo (Integer32 (a (:= 0))) (Integer32 c)) (Returns "
        "Nothing) (Does "
        "(Integer32 b) (:= b (+ a 1))))"},
       {"Function factorial(Integer32 n) Which Returns Integer64 Does "
        "Integer64 counter:=1,result:=1;"
        "While counter<n or counter=n Loop "
        "result:=result*counter;"
        "EndWhile "
        "Return result;"
        "EndFunction",
        "(Function (factorial (Integer32 n)) (Returns Integer64) (Does "
        "(Integer64 (counter (:= 1)) (result (:= 1))) (While (or (< counter n) "
        "(= counter n)) (Loop (:= result (* result counter)))) (Return "
        "result)))"},
       {"Function gcd(Integer32 a, Integer32 b) Which Returns Integer32 Does "
        "//Euclidean Algorithm\n"
        "While not(b=0) Loop\n"
        "If a>b Then\n"
        "a:=a-b;\n"
        "Else\n"
        "b:=b-a;\n"
        "EndIf\n"
        "EndWhile\n"
        "Return a;\n"
        "EndFunction",
        "(Function (gcd (Integer32 a) (Integer32 b)) (Returns Integer32) (Does "
        "(While (not (= b 0)) (Loop (If (> a b) (Then (:= a (- a b))) "
        "(Else (:= b (- b a)))))) (Return a)))"},
       {"If a<b and a<c Then //This is semantically very wrong (an "
        "if-statement outside of a function), but it should still parse.\n"
        "If a>0 Then Return a; Else Return 0; EndIf\n"
        "ElseIf b<a and b<c Then\n"
        "If b>0 Then Return b; Else Return 0; EndIf\n"
        "Else\n"
        "If c>0 Then Return c; Else Return 0; EndIf\n"
        "EndIf",
        "(If (and (< a b) (< a c)) (Then "
        "(If (> a 0) (Then (Return a)) (Else (Return 0)))) "
        "(Else (If (and (< b a) (< b c)) (Then "
        "(If (> b 0) (Then (Return b)) (Else (Return 0)))) "
        "(Else "
        "(If (> c 0) (Then (Return c)) (Else (Return 0)))))))"}});
  for (unsigned int i = 0; i < tests.size(); i++) {
    std::string result = TreeNode::parse(TreeNode::tokenize(tests[i].input))[0]
                             .getLispExpression();
    if (result != tests[i].expectedResult) {
      std::cerr << "Internal compiler error: Parser test failed: \""
                << tests[i].input << "\" parses into \"" << result
                << "\" instead of to \"" << tests[i].expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
  }
}

void runTests() {
  tokenizerTests();
  simpleParserTests();
  interpreterTests();
  parsingVariableDeclarationsTests();
  parserTests();
}

File tokenizer.cpp:

#include "TreeNode.cpp"

std::vector<TreeNode> TreeNode::tokenize(std::string input) {
#ifndef NDEBUG
  std::cerr << "DEBUG: Tokenizing the string \"" << input << "\"..."
            << std::endl;
#endif
  using std::regex;
  using std::regex_match;
  using std::string;
  using std::to_string;
  auto tokenizedExpression = std::vector<TreeNode>();
  int currentLine = 1, currentColumn = 1;
  bool areWeInAString = false, areWeInAComment = false;
  string stringDelimiter, commentDelimiter;
  try {
    for (unsigned int i = 0; i < input.size(); i++) {
#ifndef NDEBUG
      std::cerr << "DEBUG: Now we are tokenizing the character #" << i << ": '"
                << input[i] << "'." << std::endl;
      if (areWeInAString)
        std::cerr << "DEBUG: We are in a string." << std::endl;
      if (areWeInAComment)
        std::cerr << "DEBUG: We are in a comment." << std::endl;
#endif
      if (tokenizedExpression.size() == 0) {
        if (input.size() - i > 2 and
            (input.substr(i, 2) == "//" or input.substr(i, 2) == "/*")) {
          areWeInAComment = true;
          commentDelimiter = input.substr(i, 2);
          tokenizedExpression.push_back(TreeNode(string(), 1, 1));
          currentColumn++;
          continue;
        }
        tokenizedExpression.push_back(TreeNode(input.substr(i, 1), 1, 1));
        currentColumn++;
        if (input[i] == '"' or input[i] == '\'') {
          areWeInAString = true;
          stringDelimiter = input.substr(i, 1);
        }
      } else if ((input[i] == '"' or input[i] == '\'') and !areWeInAComment) {
        if (areWeInAString and stringDelimiter == input.substr(i, 1) and
            (i == 0 or input[i - 1] != '\\')) {
          tokenizedExpression.back().text.push_back(input[i]);
          tokenizedExpression.push_back(
              TreeNode(string(), currentLine, currentColumn));
          currentColumn++;
          areWeInAString = false;
        } else {
          currentColumn++;
          areWeInAString = true;
          stringDelimiter = input.substr(i, 1);
          tokenizedExpression.push_back(
              TreeNode(input.substr(i, 1), currentLine, currentColumn));
        }
      } else if (input.size() - i > 2 and
                 (input.substr(i, 2) == "//" or input.substr(i, 2) == "/*") and
                 !areWeInAString and !areWeInAComment) {
        areWeInAComment = true;
        commentDelimiter = input.substr(i, 2);
      } else if (input[i] == '\n') { // If we came to the end of a line.
        if (areWeInAString) {
          std::cerr << "Line " << currentLine << ", Column "
                    << tokenizedExpression.back().columnNumber
                    << ", Tokenizer error: Unterminated string literal!"
                    << std::endl;
          areWeInAString = false;
        }
        if (areWeInAComment and commentDelimiter == "//")
          areWeInAComment = false;
        else if (areWeInAComment) {
          currentLine++;
          currentColumn = 1;
          continue;
        }
        currentLine++;
        currentColumn = 1;
        tokenizedExpression.push_back(
            TreeNode(string(), currentLine, currentColumn));
      } else if (regex_match(input.substr(i, 1),
                             regex("\\s")) and
                 !areWeInAString and
                 !areWeInAComment) { // If we came to some other whitespace.
        currentColumn++;
        tokenizedExpression.push_back(
            TreeNode(string(), currentLine, currentColumn));
      } else if (regex_match(input.substr(i, 1), regex("\\d|[a-z]|[A-Z]|_")) and
                 regex_match(
                     tokenizedExpression.back().text,
                     regex("(^(\\d|_|[a-z]|[A-Z])*$)|(^(\\d|_|[a-z]|[A-Z])+\\.("
                           "\\d|_|[a-z]|[A-Z])*$)")) and
                 !areWeInAString and !areWeInAComment) // Names and numbers
      {
        currentColumn++;
        tokenizedExpression.back().text += input[i];
      } else if (input[i] == '.' and
                 regex_match(tokenizedExpression.back().text,
                             regex("^\\d+$")) and
                 !areWeInAString and
                 !areWeInAComment) // If we are currently
                                   // tokenizing a number, a dot
                                   // character is a decimal point.
      {
        currentColumn++;
        tokenizedExpression.back().text += input[i];
      } else if (!areWeInAString and !areWeInAComment) {
        currentColumn++;
        tokenizedExpression.push_back(
            TreeNode(input.substr(i, 1), currentLine, currentColumn));
      } else if (areWeInAString and !areWeInAComment) {
        currentColumn++;
        tokenizedExpression.back().text += input[i];
      } else if (areWeInAComment and commentDelimiter == "/*" and
                 input.size() - i > 2 and input.substr(i, 2) == "*/" and
                 !areWeInAString) {
        areWeInAComment = false;
        currentColumn += 2;
        tokenizedExpression.push_back(
            TreeNode(string(), currentLine, currentColumn));
        i++;
      } else if (!areWeInAString and areWeInAComment) {
        currentColumn++;
      } else {
        std::cerr << "Line " << currentLine << ", Column " << currentColumn
                  << ", Internal compiler error: Tokenizer is in the "
                     "forbidden state!"
                  << std::endl;
      }
    }
    for (auto iterator = tokenizedExpression.begin();
         iterator < tokenizedExpression.end(); iterator++)
      if (iterator->text.size() == 3 and iterator->text.substr(0, 1) == "'" and
          iterator->text.substr(2, 1) == "'")
        iterator->text = std::to_string(int(iterator->text[1]));
    for (auto iterator = tokenizedExpression.begin();
         iterator < tokenizedExpression.end();
         iterator++) // Turn escape sequences into numbers.
      if (iterator->text == "'\\n'")
        iterator->text = to_string(int('\n'));
      else if (iterator->text == "'\\t'")
        iterator->text = to_string(int('\t'));
      else if (iterator->text == "'\\''")
        iterator->text = to_string(int('\''));
      else if (iterator->text == "'\\\\'")
        iterator->text = to_string(int('\\'));
    for (auto iterator = tokenizedExpression.begin();
         iterator < tokenizedExpression.end(); iterator++)
      if (regex_match(iterator->text, regex("^\\s*$"))) // Delete empty nodes.
      {
        iterator--;
        tokenizedExpression.erase(iterator + 1);
      }
    for (unsigned int i = 1; i < tokenizedExpression.size(); i++)
      if ((tokenizedExpression[i].text ==
               "(" or // Mark the names of functions...
           tokenizedExpression[i].text ==
               "[") and //...and arrays with ending '(' or '['
          regex_match(
              tokenizedExpression[i - 1].text.substr(0, 1), //...for the parser.
              regex("_|[a-z]|[A-Z]"))) {
        tokenizedExpression[i - 1].text += tokenizedExpression[i].text;
        tokenizedExpression.erase(tokenizedExpression.begin() + i);
      }
    for (unsigned int i = 1; i < tokenizedExpression.size(); i++)
      if (tokenizedExpression[i].text == "=" and
          tokenizedExpression[i - 1].text ==
              ":") // The ":=" assignment operator.
      {
        tokenizedExpression[i - 1].text = ":=";
        tokenizedExpression.erase(tokenizedExpression.begin() + i);
      }
  } catch (std::regex_error &error) {
    std::cerr << "Internal compiler error in tokenizer: " << error.what() << ":"
              << error.code() << std::endl;
    return std::vector<TreeNode>();
  }
#ifndef NDEBUG
  std::cerr << "DEBUG: Finished tokenizing the string \"" << input << "\"."
            << std::endl;
#endif
  return tokenizedExpression;
}

File TreeNode.cpp:

#include <iostream>
#include <map>
#include <regex>
#include <string>
#include <vector>

#pragma once

class TreeNode {
  enum Associativity { left, right };
  static std::vector<TreeNode>
  applyBinaryOperators(std::vector<TreeNode> input,
                       std::vector<std::string> operators,
                       Associativity associativity);

public:
  std::map<std::string, int> basicDataTypeSizes;
  std::vector<TreeNode> children;
  std::string text;
  int lineNumber, columnNumber;
  TreeNode() {
    basicDataTypeSizes["Integer32"] = 4;
    basicDataTypeSizes["Character"] = 1;
    basicDataTypeSizes["Decimal32"] = 4;
    basicDataTypeSizes["Integer64"] = 8;
    basicDataTypeSizes["Decimal64"] = 8;
    basicDataTypeSizes["Integer16"] = 2;
    for (auto iterator = basicDataTypeSizes.begin();
         iterator != basicDataTypeSizes.end(); iterator++)
      if (iterator->first.find("Pointer") == std::string::npos)
        basicDataTypeSizes[iterator->first + "Pointer"] =
            4; // JavaScript (WebAssembly) virtual machine is 32-bit (pointers
               // being 32 bits or 4 bytes long), unless somebody switches to
               // the 64-bit mode (which is rarely done).
    lineNumber = columnNumber = 0;
  }
  TreeNode(std::string newText, int newLine, int newColumn) {
    *this = TreeNode(); // For some weird reason, just "TreeNode()" won't do the
                        // trick.
    text = newText;
    lineNumber = newLine;
    columnNumber = newColumn;
  }
  static std::vector<TreeNode>
  tokenize(std::string input); // See "tokenizer.cpp" for the implementation.
  static std::string JSONifyArrayOfTokens(
      std::vector<TreeNode> tokenizedString) { // For debugging the tokenizer.
    std::string ret = "[";
    if (!tokenizedString.size())
      return "[]";
    for (unsigned int i = 0; i < tokenizedString.size(); i++)
      if (i != tokenizedString.size() - 1)
        ret += "'" + tokenizedString[i].text + "',";
      else
        ret += "'" + tokenizedString[i].text + "']";
    return ret;
  }
  static std::vector<TreeNode> parse(
      std::vector<TreeNode> input); // See "parser.cpp" for the implementation.
  static std::vector<TreeNode> parseExpression(
      std::vector<TreeNode> input); // Made public for debugging purposes.
  std::string
  getLispExpression() { // Again, for debugging purposes (and maybe, some day, I
                        // will want to compile my language to Lisp).
    if (children.size() == 0)
      return text;
    std::string LispExpression = "(" +
                                 ((text.back() == '(' or text.back() == '[')
                                      ? (text.substr(0, text.size() - 1))
                                      : (text)) +
                                 " ";
    for (unsigned int i = 0; i < children.size(); i++)
      if (i == children.size() - 1)
        LispExpression += children[i].getLispExpression() + ")";
      else
        LispExpression += children[i].getLispExpression() + " ";
    return LispExpression;
  }
  int interpretAsACompileTimeConstant() {
    if (std::regex_match(text, std::regex("^\\d+$")))
      return std::stoi(text);
    if (text == "+")
      return children[0].interpretAsACompileTimeConstant() +
             children[1].interpretAsACompileTimeConstant();
    if (text == "-")
      return children[0].interpretAsACompileTimeConstant() -
             children[1].interpretAsACompileTimeConstant();
    if (text == "*")
      return children[0].interpretAsACompileTimeConstant() *
             children[1].interpretAsACompileTimeConstant();
    if (text == "/")
      return children[0].interpretAsACompileTimeConstant() /
             children[1].interpretAsACompileTimeConstant();
    if (text == "?:")
      return children[0].interpretAsACompileTimeConstant()
                 ? children[1].interpretAsACompileTimeConstant()
                 : children[2].interpretAsACompileTimeConstant();
    if (text == "mod(")
      return children[0].interpretAsACompileTimeConstant() %
             children[1].interpretAsACompileTimeConstant();
    if (text == "<")
      return children[0].interpretAsACompileTimeConstant() <
             children[1].interpretAsACompileTimeConstant();
    if (text == ">")
      return children[0].interpretAsACompileTimeConstant() >
             children[1].interpretAsACompileTimeConstant();
    if (text == "=")
      return children[0].interpretAsACompileTimeConstant() ==
             children[1].interpretAsACompileTimeConstant();
    std::cerr << "Line " << lineNumber << ", Column " << columnNumber
              << ", Interpreter error: \"" << text
              << "\" isn't a valid token in a compile-time integer constant."
              << std::endl;
    return 0;
  }
  static std::vector<TreeNode>
  parseVariableDeclaration(std::vector<TreeNode> input);
};

```
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Can you include a description of your programming language? Searching for "AEC" on Esolangs returns nothing for me. \$\endgroup\$
    – L. F.
    Jul 27, 2020 at 5:02
  • \$\begingroup\$ @L.F. Why would it be an esolang? It's a BASIC-like programming language, just without a GOTO statement. \$\endgroup\$ Jul 27, 2020 at 14:06
  • \$\begingroup\$ I don't know where to go, so I went to esolang. Do you have a more detailed specification of AEC beyond "BASIC-like"? cuz that would probably help reviewers greatly. \$\endgroup\$
    – L. F.
    Jul 27, 2020 at 14:34

1 Answer 1

2
\$\begingroup\$

Here are a number of things that may help you improve your code.

Separate interface from implementation

It makes the code somewhat longer for a code review, but it's often very useful to separate the interface from the implementation. In C++, this is usually done by putting the interface into separate .h files and the corresponding implementation into .cpp files. It helps users (or reviewers) of the code see and understand the interface and hides implementation details. The other important reason is that you might have multiple source files including the .h file but only one instance of the corresponding .cpp file. In other words, split your existing .cpp file into a .h file and a .cpp file. The current code #includes .cpp files which is incorrect and leads to problems.

Use include guards

There should be an include guard in each .h file. That is, start the file with:

#ifndef TREENODE_H
#define TREENODE_H
// file contents go here
#endif // TREENODE_H

The use of #pragma once is a common extension, but it's not in the standard and thus represents at least a potential portability problem. See SF.8 Also, it should never go in a .cpp file per the advice above.

Omit unused variables

Because argc and argv are unused, you could use the alternative form of main:

int main ()

Don't use std::endl when '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Use const where practical

I would not expect the tokenize or JSONifyArrayOfTokens routines to alter the data structures passed to them and indeed they do not. You should make this expectation explicit by using the const keyword:

static std::vector<TreeNode> tokenize(const std::string& input);
static std::string JSONifyArrayOfTokens(const std::vector<TreeNode>& tokenizedString);

Similarly, the interpretAsACompileTimeConstant() function does not alter the underlying object, so it should also be declared const. The syntax is a little different for this:

int interpretAsACompileTimeConstant() const;

Not only will the code become more robust, but it will also likely run faster because it can avoid making temporary copies.

Improve your constructors

The TreeNode class has this constructor:

TreeNode::TreeNode(std::string newText, int newLine, int newColumn) {
    *this = TreeNode(); // For some weird reason, just "TreeNode()" won't do the
                        // trick.
    text = newText;
    lineNumber = newLine;
    columnNumber = newColumn;
}

A more modern style for your constructor might be this:

TreeNode::TreeNode(std::string newText, int newLine, int newColumn) :
    text{newText},
    lineNumber{newLine},
    columnNumber{newColumn}
{}

The basicDataTypeSizes and children member elements will automatically be initialized to empty containers.

Use "range for" and simplify your code

Having test code is good, both for you to make sure your code works, and also for reviewers to better understand what you intend. However, these tests could be simplfied a great deal. Here's one of the tests as it exists now, complete with the tests definition:

struct test { 
  std::string input, expectedResult;
};

void tokenizerTests() {
  std::vector<test> tests(
      {{"\"/*Comment inside a string*/\"",
        "['\"/*Comment inside a string*/\"']"},
       {"5+5", "['5','+','5']"},
       {"5+5=10", "['5','+','5','=','10']"},
       {"structureName.structureMember/3.14159265359",
        "['structureName','.','structureMember','/','3.14159265359']"},
       {"sin(pi/2)=1", "['sin(','pi','/','2',')','=','1']"},
       {"'A'+2='C'", "['65','+','2','=','67']"},
       {"a:=a+1; //Some random comment.\nb:=b-1;",
        "['a',':=','a','+','1',';','b',':=','b','-','1',';']"},
       {"/*This should be tokenized into\nan empty string*/", "[]"},
       {"a/*Randomly\ninserted\ncomment.*/+/*Another\nrandom\ncomment*/b",
        "['a','+','b']"},
       {"array_name:={1,1+1,1+1+1}", "['array_name',':=','{','1',',','1','+','"
                                     "1',',','1','+','1','+','1','}']"}});
  for (unsigned int i = 0; i < tests.size(); i++) {
    std::string result =
        TreeNode::JSONifyArrayOfTokens(TreeNode::tokenize(tests[i].input));
    if (result != tests[i].expectedResult) {
      std::cerr << "Internal compiler error: Tokenizer test failed: \""
                << tests[i].input << "\" tokenizes into \"" << result
                << "\" instead of to \"" << tests[i].expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
  }
}

There are a number of ways this could be improved. First, you could use the C++11 "range for" for the loop:

for (const auto& thisTest : tests) {
    std::string result =
        TreeNode::JSONifyArrayOfTokens(TreeNode::tokenize(thisTest.input));
    if (result != thisTest.expectedResult) {
      std::cerr << "Internal compiler error: Tokenizer test failed: \""
                << thisTest.input << "\" tokenizes into \"" << result
                << "\" instead of to \"" << thisTest.expectedResult << "\"!"
                << std::endl;
      std::exit(1);
    }
}

If you're using a C++17 compiler, the code can be even nicer:

for (const auto& [input, expected] : tests) {
    std::string result = TreeNode::JSONifyArrayOfTokens(TreeNode::tokenize(input));
    if (result != expected) {
      std::cerr << "Internal compiler error: Tokenizer test failed: \""
                << input << "\" tokenizes into \"" << result
                << "\" instead of to \"" << expected << "\"!"
                << std::endl;
      std::exit(1);
    }
}

Don't Repeat Yourself (DRY)

The tests are all doing the same thing. That is, they apply some transformation to the input code and verify that the output is what was expected. Rather than repeating that same code multiple times, better would be to consolidate it into a single location:

class TestCollection {
    std::string name;
    std::string (*func)(const std::string&);
    struct test {
        std::string input; 
        std::string expectedResult;
    };
    std::vector<test> tests;
public:
    TestCollection(std::string name, std::string (*func)(const std::string&), std::vector<test> tests) : name{name}, func{func}, tests{tests} {}
    bool operator()() const {
        bool result{true};
        for (const auto& [input, expected] : tests) {
            std::string result = func(input);
            if (result != expected) {
                result = false;
                std::cerr << "Internal compiler error: " << name << " failed: \""
                << "with input \"" << input 
                << "\", expected \"" << expected << "\" but got \"" << result << "\"!\n";
            }
        }
        return result;
    }
};

Using this, the tests each become data structures:

TestCollection parsingVariableDeclarationsTests{"Variable declarations parser test",
    [](const std::string& input) -> std::string { 
        return TreeNode::parseVariableDeclaration( TreeNode::tokenize(input))[0]
                             .getLispExpression();
    },
      {{"Integer32 some_array[80*23],array_width:=80,array_height:=23",
        "(Integer32 (some_array (* 80 23)) (array_width (:= 80)) (array_height "
        "(:= 23)))"}}
};

The overall test function then becomes:

bool runTests() {
  return tokenizerTests() 
    && simpleParserTests() 
    && interpreterTests() 
    && parsingVariableDeclarationsTests()
    && parserTests();
}

Note also that the function returns a boolean value instead of calling exit(1).

Make data members private

None of the data members of the TreeNode class need to be public, so they ought to be made private.

Avoid the use of iso646 keywords

The alternate keywords "or", "and", etc. still exist in C++, but you should probably not use them. Instead use || and &&. See BFS shortest path program for more detail.

Write efficient code

I was surprised by how slowly this code ran until I looked more closely. Here's just one clause from the tokenizer:

} else if (regex_match(input.substr(i, 1), regex("\\d|[a-z]|[A-Z]|_")) and
           regex_match(
               tokenizedExpression.back().text,
               regex("(^(\\d|_|[a-z]|[A-Z])*$)|(^(\\d|_|[a-z]|[A-Z])+\\.("
                     "\\d|_|[a-z]|[A-Z])*$)")) and
           !areWeInAString and !areWeInAComment) // Names and numbers
{
    currentColumn++;
    tokenizedExpression.back().text += input[i];
} 

There is a lot going on here, and most of it is extremely inefficient. First, all four of the clauses in the if have to be true to execute the lines below. However, the simple boolean value comparisons are much faster to execute than the regex_match functions. For that reason, it would likely be more efficient to reorder them so that the "cheap" tests are done first.

Next, let's look at each regex_match individually. The first inefficiency is that a temporary string is created via input.substr(i, 1). That requires a memory allocation and subsequent deallocation all to simply get a single character. The next inefficiency is that a dynamic regex is created (and destroyed) each time. Third, using a regex for a single character is almost never an efficient solution. So let's rewrite the first clause:

(std::isalnum(input[i]) || input[i] == '_')

The next clause is this:

regex_match(tokenizedExpression.back().text,
   regex("(^(\\d|_|[a-z]|[A-Z])*$)|(^(\\d|_|[a-z]|[A-Z])+\\.("
         "\\d|_|[a-z]|[A-Z])*$)")) 

This is looking at the last word in the tree to decide if it might be an identifier. This complex regex is created and destroyed for every call and that last word is rescanned anew for every character in the input string. That's very inefficient! A better way to do it would be to keep track of the last token's type and simply check that. If it could be an identifier, for instance if we had scanned the "Inte" portion of "Integer32" then it still could be an identifier after we add the qualified character. In other words, just as with the booleans areWeInAString and areWeInAComment, you could keep a boolean inId and rewrite the entire if clause like this:

  } else if (!areWeInAString 
            && !areWeInAComment 
            && (std::isalnum(input[i]) || input[i] == '_')
            && (inId || (tokenizedExpression.back().text.size() == 0)))
  {

Doing so on my machine drops the execution time from 2.520 seconds to 0.544 seconds, for a 5x speedup.

Rethink the approach

Tokenizing like this is often much better done via a state machine. See this answer for an example of how this can be done. A state machine makes the code neater and easier to reason about as well as much faster than using regex in many cases.

Summary

I haven't had time to go through the parser, but this should give you plenty to work on for now. C++ is indeed a very useful and efficient language, but it requires some expertise to use it effectively. I'd recommend this book if you haven't already studied the language much.

\$\endgroup\$

Your Answer

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

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