compiler.cpp

// <program> ::= <statement_list>
// <statement_list> ::= <statement> | <statement> <statement_list>
// <statement> ::= <var_decl> | <assignment> | <if_statement>
// <var_decl> ::= "take" <identifier> "=" <expression>
// <assignment> ::= <identifier> "=" <expression>
// <expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
// <term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>
// <factor> ::= <number> | <identifier> | "(" <expression> ")"
// <if_statement> ::= "?" <condition> "{" <statement_list> "}" [ ":" "{" <statement_list> "}" ]
// <condition> ::= <expression> <relop> <expression>
// <relop> ::= ">" | "<" | "==" | "!=" | ">=" | "<="
// <identifier> ::= [a-zA-Z][a-zA-Z0-9]*
// <number> ::= [0-9]+ ("." [0-9]+)?

// This is my syntax grammer

#include <iostream>
#include <string>
#include <vector>
#include <memory>
#include <map>
using namespace std;

// token formate
struct Token
{
    string type;
    string value;
};

// lexer
vector<Token> lexer(string code)
{
    vector<Token> tokens;

    int start = 0;
    int end = code.size();

    while (start < end)
    {
        while (start < end && isspace(code[start])) // it will remove starting blank space
        {
            start++;
        }

        if (start >= end)
            break;

        char currentChar = code[start];
        if (isalpha(currentChar))
        {
            string identifier;

            while (isalnum(code[start]) || code[start] == '_') // it will combine all characters
            {
                identifier += code[start++];
            }

            if (identifier == "take")
            {
                tokens.push_back({"KEYWORD", identifier});
            }
            else
            {
                tokens.push_back({"IDENTIFIER", identifier});
            }
        }
        else if (isdigit(currentChar))
        {
            string number;
            while (start < end && isdigit(code[start]))
            {
                number += code[start++];
            }
            tokens.push_back({"NUMBER", number});
        }
        else if (currentChar == '+')
        {
            tokens.push_back({"PLUS", "+"});
            start++;
        }
        else if (currentChar == '-')
        {
            tokens.push_back({"MINUS", "-"});
            start++;
        }
        else if (currentChar == '/')
        {
            tokens.push_back({"DIV", "/"});
            start++;
        }
        else if (currentChar == '*')
        {
            tokens.push_back({"MUL", "*"});
            start++;
        }
        else if (currentChar == '=')
        {
            tokens.push_back({"ASSIGN", "="});
            start++;
        }
        else if (currentChar == ';')
        {
            tokens.push_back({"SEMICOLON", ";"});
            start++;
        }
        else if (currentChar == '(')
        {
            tokens.push_back({"LPAREN", "("});
            start++;
        }
        else if (currentChar == ')')
        {
            tokens.push_back({"RPAREN", ")"});
            start++;
        }
        else if (currentChar == '{')
        {
            tokens.push_back({"LBRACE", "{"});
            start++;
        }
        else if (currentChar == '}')
        {
            tokens.push_back({"RBRACE", "}"});
            start++;
        }
        else if (currentChar == '<')
        {
            tokens.push_back({"LT", "<"});
            start++;
        }
        else if (currentChar == '>')
        {
            tokens.push_back({"GT", ">"});
            start++;
        }
        else if (currentChar == '!')
        {
            tokens.push_back({"NOT", "!"});
            start++;
        }
        else if (currentChar == ':')
        {
            tokens.push_back({"ELSE_CONDITION", ":"});
            start++;
        }
        else if (currentChar == '?')
        {
            tokens.push_back({"IF_CONDITION", "?"});
            start++;
        }
        else
        {
            throw runtime_error("invalid char");
        }
    }
    tokens.push_back({"EOF", " "});

    return tokens;
}

void printTokens(vector<Token> tokens)
{
    cout << "_________________________TOKENS__________________________" << endl;
    for (int i = 0; i < tokens.size(); i++)
    {
        cout << tokens[i].type << " : " << tokens[i].value << endl;
    }
}

struct ASTNode
{

    string type;
    string value;
    vector<unique_ptr<ASTNode>> children;

    ASTNode(string t, string v = "") : type(t), value(v) {};
};

class Parser
{
private:
    vector<Token> tokens;
    size_t currentIndex;

    Token peek()
    { // for taking one token value
        // cout << tokens[currentIndex] << endl;
        return currentIndex < tokens.size() ? tokens[currentIndex] : Token({"EOF", ""});
    }

    Token consume()
    { // increment the index of token
        // cout << tokens[currentIndex] << endl;
        return currentIndex < tokens.size() ? tokens[currentIndex++] : Token({"EOF", ""});
    }

    void matchToken(string type)
    {
        if (tokens[currentIndex].type != type)
        {
            throw runtime_error("Invalid token found in matchToken function " + tokens[currentIndex].value);
        }
        consume();
    }

public:
    explicit Parser(vector<Token> toks) : tokens(move(toks)), currentIndex(0) {};

    unique_ptr<ASTNode> parseProgram()
    { // starting node of our ast
        auto node = make_unique<ASTNode>("Program");
        node->children.push_back(parseStatementList());
        return node;
    }

    unique_ptr<ASTNode> parseStatementList()
    { // it will parse list of parser
        auto node = make_unique<ASTNode>("StatementList");

        while (currentIndex < tokens.size() && tokens[currentIndex].type != "EOF" && tokens[currentIndex].type != "RBRACE") // until EOF(end of file) and ")" brace
        {
            node->children.push_back(parseStatement()); // it will parse each statement
        }
        return node;
    }

    unique_ptr<ASTNode> parseStatement() // it will parse a statement
    {
        // take a=10;
        // KEYWORD IDENTIFIER ASSIGNMENT EXPRESSION SEMICOLON

        if (tokens[currentIndex].type == "KEYWORD" && tokens[currentIndex].value == "take")
        {
            // parse KEYWORD "take"

            return parseVariableDeclaration();
        }
        else if (tokens[currentIndex].type == "IDENTIFIER" && tokens[currentIndex + 1].type == "ASSIGN")
        { // a =
          // parse IDENTIFIER WITH ASSIGNMENT OR PARSE ASSIGNMENT

            return parseAssignment();
        }
        else if (tokens[currentIndex].type == "IF_CONDITION") // condition
        {

            // parse conditions
            return parseIFStatement();
        }
        throw runtime_error("Invalid statement :: " + peek().value);
    }

    unique_ptr<ASTNode> parseVariableDeclaration()
    { // take a = b*d ;
      // KEYWORD IDENTIFIER ASSIGNMENT EXPRESSION SEMICOLON

        matchToken("KEYWORD");   // take
        Token token = consume(); // incremented the index
        matchToken("ASSIGN");
        auto expression = parseExpression(); // parse expressions
        matchToken("SEMICOLON");

        auto node = make_unique<ASTNode>("Variable_Declaration");
        node->children.push_back(make_unique<ASTNode>("Identifer", token.value));
        node->children.push_back(move(expression));
        return node;
    }

    unique_ptr<ASTNode> parseAssignment()
    { // a=10;

        Token token = consume(); // incremented the index
        matchToken("ASSIGN");
        auto expression = parseExpression(); // parse expressions
        matchToken("SEMICOLON");

        auto node = make_unique<ASTNode>("Assignment");
        node->children.push_back(make_unique<ASTNode>("Identifer", token.value));
        node->children.push_back(move(expression));
        return node;
    }

    unique_ptr<ASTNode> parseIFStatement()
    {

        // ? condition ( statments ) : (statments )/
        matchToken("IF_CONDITION");            // ?
        auto condition = parseCondition();     // condition
        matchToken("LBRACE");                  // (
        auto thanblock = parseStatementList(); // statments
        matchToken("RBRACE");                  // )

        auto node = make_unique<ASTNode>("If_statement");
        node->children.push_back(move(condition));
        node->children.push_back(move(thanblock));

        if (peek().type == "ELSE_CONDITION")
        {                                          // else portion
            consume();                             // :
            matchToken("LBRACE");                  // (
            auto elseblock = parseStatementList(); // statments
            matchToken("RBRACE");                  // )
            node->children.push_back(move(elseblock));
        }
        return node;
    }

    unique_ptr<ASTNode> parseCondition()
    { //  a < b
      // EXPRESSION TOKEN EXPRESSION

        auto left = parseExpression();
        Token token = consume();
        auto right = parseExpression();

        auto node = make_unique<ASTNode>("Condition");
        node->children.push_back(move(left));
        node->value = token.value;
        node->children.push_back(move(right));

        return node;
    }

    unique_ptr<ASTNode> parseExpression()
    {
        // (a+b-c)

        auto left = parseTerms(); // parse plus and minus
        while (peek().type == "PLUS" || peek().type == "MINUS")
        {
            string op = consume().type;
            auto right = parseTerms();

            auto newNode = make_unique<ASTNode>(op);
            newNode->children.push_back(move(left));
            newNode->children.push_back(move(right));
            left = move(newNode);
        }
        return left;
    }

    unique_ptr<ASTNode> parseTerms()
    {
        // a*b/c

        auto left = parseFactors(); // parse ( and )

        while (peek().type == "MUL" || peek().type == "DIV")
        {
            string op = consume().type;
            auto right = parseFactors();

            auto newNode = make_unique<ASTNode>(op);
            newNode->children.push_back(move(left));
            newNode->children.push_back(move(right));
            left = move(newNode);
        }
        return left;
    }

    unique_ptr<ASTNode> parseFactors()
    {

        if (peek().type == "NUMBER")
        {

            auto node = make_unique<ASTNode>("Number", consume().value);
            return node;
        }
        else if (peek().type == "IDENTIFIER")
        {

            auto node = make_unique<ASTNode>("Identifier", consume().value);
            return node;
        }
        else if (peek().type == "LPAREN")
        { // ( expression )

            consume();
            auto expr = parseExpression();
            matchToken("RPAREN");
            return expr;
        }
        throw runtime_error("No factor found for " + peek().type);
    }
};

void printAST(const ASTNode *node, int depth = 0)
{
    if (!node)
        return;
    string indent(depth * 2, ' ');
    cout << indent << node->type;

    if (!node->value.empty())
    {
        cout << " (" << node->value << ")";
    }
    cout << endl;

    for (auto &child : node->children)
    {
        printAST(child.get(), depth + 1);
    }
}

class CodeGenerator
{
private:
    vector<string> assemblyCode;
    map<string, int> symbolTable;
    int memoryCounter = 0x10; // initial memory location
    int tempCounter = 0x12;
    int labelCounter = 0;

    int allocateMemory(string &identifier)
    {
        if (symbolTable.find(identifier) == symbolTable.end())
        {
            symbolTable[identifier] = memoryCounter++;
        }
        return symbolTable[identifier];
    }

    int allocateTemp()
    {
        return tempCounter++;
    }

    string getnewLabel()
    {
        return "L" + to_string(labelCounter++);
    }

public:
    void generateCode(ASTNode *node)
    {

        if (!node)
            return;

        if (node->type == "Program")
        {

            for (auto &child : node->children)
            {
                generateCode(child.get()); // it will run recursive if type == "program"
            }
        }

        else if (node->type == "StatementList")
        {
            for (auto &child : node->children)
            {
                generateCode(child.get()); // it will run recursive if type == "program"
            }
        }
        else if (node->type == "Variable_Declaration")
        {
            string identifier = node->children[0]->value;          // identifier
            int address = allocateMemory(identifier);              // memory allocation
            generateExpressionCode(node->children[1].get());       // generate the expression code
            assemblyCode.push_back("STA 0x" + to_string(address)); // store address value into the A
        }
        else if (node->type == "Assignment")
        {
            string identifier = node->children[0]->value; // identifier
            int address = allocateMemory(identifier);
            generateExpressionCode(node->children[1].get()); // generate the expression code
            assemblyCode.push_back("STA 0x" + to_string(address));
        }
        else if (node->type == "If_statement")
        {
            string endLabel = getnewLabel();
            string elseLabel = getnewLabel();

            generateConditionCode(node->children[0].get(), elseLabel);

            if (node->children.size() > 1)
            {
                generateCode(node->children[1].get());
            }
            // if (node->children.size() > 2)
            // {
            //     // assemblyCode.push_back("JMP " + endLabel);
            // }
            if (node->children.size() > 2)
            {
                assemblyCode.push_back(elseLabel + " :");
                generateCode(node->children[2].get());
            }
            else
            {
                assemblyCode.push_back(elseLabel + " :");
            }

            // assemblyCode.push_back(endLabel + " :");
        }
    }

    void generateExpressionCode(ASTNode *node)
    {
        if (!node)
            return;

        if (node->type == "Number")
        {
            assemblyCode.push_back("ldi A," + node->value); // load A
        }
        else if (node->type == "Identifier")
        {
            int address = symbolTable[node->value];
            assemblyCode.push_back("ldA 0x" + to_string(address)); // it will load identifier value into A
        }
        else if (node->type == "PLUS")
        {
            if (node->children[1]->type == "Identifier")
            {
                generateExpressionCode(node->children[0].get());
                int rightAddress = symbolTable[node->children[1]->value];
                assemblyCode.push_back("ADD 0x" + to_string(rightAddress)); // add value into the A
            }
            else
            {
                generateExpressionCode(node->children[1].get()); // right
                int tempAddress = allocateTemp();
                assemblyCode.push_back("STA 0x" + to_string(tempAddress)); // store value into temp
                generateExpressionCode(node->children[0].get());           // left
                tempAddress = allocateTemp();
                assemblyCode.push_back("ADD 0x" + to_string(tempAddress)); // store value into temp
            }
        }
        else if (node->type == "MINUS")
        {
            if (node->children[1]->type == "Identifier")
            {
                generateExpressionCode(node->children[0].get());
                int rightAddress = symbolTable[node->children[1]->value];
                assemblyCode.push_back("SUB 0x" + to_string(rightAddress)); // add value into the A
            }
            else
            {
                generateExpressionCode(node->children[1].get()); // right
                int tempAddress = allocateTemp();
                assemblyCode.push_back("STA 0x" + to_string(tempAddress)); // store value into temp
                generateExpressionCode(node->children[0].get());           // left
                tempAddress = allocateTemp();
                assemblyCode.push_back("SUB 0x" + to_string(tempAddress)); // store value into temp
            }
        }
        else if (node->type == "MUL")
        {
            generateExpressionCode(node->children[1].get()); // right operand
            assemblyCode.push_back("MOV B A");               //  move value of A into B
            generateExpressionCode(node->children[0].get()); // left operand
            assemblyCode.push_back("MUL A B");               //  Mul of B and A and stored in A
        }
        else if (node->type == "DIV")
        {
            generateExpressionCode(node->children[1].get()); // right operand
            assemblyCode.push_back("MOV B A");               //  move value of A into B
            generateExpressionCode(node->children[0].get()); // left operand
            assemblyCode.push_back("DIV A B");               //  DIV of A/B and stored in A
        }
    }

    void generateConditionCode(ASTNode *node, string &jumpLabel)
    {

        if (!node || node->type != "Condition")
            return;

        generateExpressionCode(node->children[1].get());
        assemblyCode.push_back("MOV B A"); // store value of a into b

        generateExpressionCode(node->children[0].get());
        assemblyCode.push_back("CMP A B"); // compare a with b

        if (node->value == ">")
        {
            assemblyCode.push_back("JLE " + jumpLabel);
        }
        else if (node->value == "<")
        {
            assemblyCode.push_back("JGE " + jumpLabel);
        }
        else if (node->value == "==")
        {
            assemblyCode.push_back("JNZ " + jumpLabel);
        }

        else if (node->value == "!=")
        {
            assemblyCode.push_back("JZ" + jumpLabel);
        }
        else if (node->value == ">=")
        {
            assemblyCode.push_back("JLT " + jumpLabel);
        }
        else if (node->value == "<=")
        {
            assemblyCode.push_back("JGT " + jumpLabel);
        }
    }

    vector<string> getAsssemblyCode()
    {
        return assemblyCode;
    }
};

int main()
{

    string input = R"(
        take a=10;
        take b=30;
        ? a > b { a = a/b ; } : { a = b*a; } 
    )";

    vector<Token> tokens = lexer(input);
    printTokens(tokens);

    Parser parser(tokens);
    unique_ptr<ASTNode> ast = parser.parseProgram();

    cout << "____________________________AST TREE_________________________" << endl;
    printAST(ast.get());

    cout << "____________________________ASSEMBLY CODE_________________________" << endl;
    CodeGenerator generator;
    generator.generateCode(ast.get());

    vector<string> assmeblyCode = generator.getAsssemblyCode();

    for (auto &instuction : assmeblyCode)
    {
        cout << instuction << endl;
    }

    return 0;
}