SimpleLang Compiler for an 8-bit CPU

Introduction

SimpleLang is a minimalistic high-level language designed to run on an 8-bit CPU. It includes basic constructs such as variable declarations, assignments, arithmetic operations, and conditional statements, but it does not include loops. This language aims to be easy to understand and implement for educational purposes.

Table of Contents

1. Language Constructs
2. Compiler Overview
3. Implementation Details
4. Lexer
5. Parser
6. Code Generator
7. Input File
8. Getting Started
9. 8-bit Computer Simulator Output

Language Constructs

SimpleLang includes the following programming constructs:

• Variable Declaration:

  • Syntax: int <variable_name>;
  • Declares a variable of integer type.
  • Example:

    int x;
    

• Assignment:

  • Syntax: <variable_name> = <expression>;
  • As shorthand, assigns an integer expression to a variable.
  • Example:

    x = 10;
    

• Arithmetic Operations:

  • +/- is permissible on integers.
  • Example:

    x = 10 + 20;
    

• Conditional Statements:

  • Syntax: if (<condition>) { <statement> }
  • The statement will be executed if the condition is true.
  • Example:

    if (x == 10) 
    { 
        y = 20; 
    }
    

Compiler Overview

The SimpleLang compiler is a code translator from SimpleLang code into assembly code for an 8-bit CPU.

1. Lexer: a module that tokenizes the input SimpleLang source code.
2. Parser: a module that analyses tokens to form an Abstract Syntax Tree (AST).
3. Code Generator: Generator-a module that translates AST into assembly code for the 8-bit CPU

Implementation Details

The SimpleLang compiler is designed in C++. Here are its implementation details:

• Lexer: A finite state machine is used to find tokens.
• Parser: A recursive descent parsing technique is used..
• Code Generator: Uses tree traversal to generate assembly code.

Lexer

The lexer converts SimpleLang code into a sequence of tokens. It accepts the following token types:

• INT: Represents integer literals.
• IDENTIFIER: Variable names.
• ASSIGN: Assignment operator =.
• NUMBER: Numeric values.
• PLUS : Addition +.
• MINUS: Subtraction -.
• IF: Keywords for conditional statements.
• EQ: Equality operator ==.
• LPAREN / RPAREN: Left ( and right ) parentheses.
• LBRACE / RBRACE: Left { and right } braces.
• SEMICOLON: Marks the end of statements.
• END: Represents the end of the file.

The lexer uses a finite state machine to process these tokens from the input SimpleLang code.

Parser

The parser transforms the token sequence into an Abstract Syntax Tree (AST). It uses a recursive descent parser to handle nested structures, supported by the following AST nodes:

• NumberNode: Represents integer literals.
• VariableNode: Represents variables.
• BinaryOpNode: Represents binary operations.
• ConditionalNode: Represents conditional statements.
• BlockNode: Abstract representation of a block of statements.

Parser Functions

• parseExp(): Converts an expression.

• parseExpStat(): PConverts an expression to a statement.

• parsePrim(): Converts a primary expression.

• parseStat(): Converts a statement.

• parseVarDec(): Converts a variable declaration.

• parseVarAssign(): Converts a variable assignment.

• parseCond(): Converts a conditional.

• parseBlock(): Converts a block of statements.

Code Generator

The code generator scans the AST, producing 8-bit CPU assembly instructions. By employing a tree traversal algorithm, it translates every node in the AST into executable code for the CPU simulator.

Input File

Here’s an example of SimpleLang code that declares variables, assigns values, and includes a conditional statement:

• you also change input.txt file and accordingly assembly code generated in output.asm file

int a;
int b;
int c;

a = 10;
b = 20;
c = a + b;

if (c == 30) {
    c = c + 1;
}

Generated Assembly Code

The code generator translates this into assembly instructions for the 8-bit CPU:

.text
    mov M A 1    ; Initialize memory location 1 with 0
    mov M A 2    ; Initialize memory location 2 with 0
    mov M A 3    ; Initialize memory location 3 with 0
    ldi A 10     ; Load immediate value 10 into register A
    mov M A 1    ; Store value from register A into memory location 1
    ldi A 20     ; Load immediate value 20 into register A
    mov M A 2    ; Store value from register A into memory location 2

    mov A M 1    ; Load value from memory location 1 into register A
    mov B M 2    ; Load value from memory location 2 into register B
    add          ; Add value in register B to register A and store result in A
    mov M A 3    ; Store result from register A into memory location 3

    mov A M 3    ; Load value from memory location 3 into register A
    ldi B 30     ; Load immediate value 30 into register B
    cmp          ; Compare value in register A with value in register B
    jnz %then_1  ; Jump to label 'then_1' if A is not equal to B

    mov A M 3    ; Load value from memory location 3 into register A
    ldi B 1      ; Load immediate value 1 into register B
    add          ; Add value in register B to register A
    mov M A 3    ; Store updated value from register A back into memory location 3

then_1:     
    out 0        ; Output the value in register A or a predefined register
    hlt          ; Halt the execution

Getting Started

To get started with the SimpleLang compiler, clone the repository and build the project. Ensure you have a C++ compiler available (e.g., g++).

Building and Running

1. Clone the Repository:

   git clone https://github.com/kunjankanani/Kunjan_Kanani_Vicharak_Task.git
   cd Kunjan_Kanani_Vicharak_Task

2. Build the compiler:

   g++ lexer.cpp parser.cpp main.cpp -o simplelang_compiler

3. Run the Compiler:

   ./simplelang_compiler

4. Run the Output.asm you need 8-bit computer Simulator:

   git clone https://github.com/lightcode/8bit-computer.git
   cd 8bit-computer

5. Build the 8bit-computer with Output.asm file:

   ./asm/asm.py tests/output.asm > memory.list

6. Run the computer:

   make clean && make run

8-bit Computer Simulator Output