ExpL Compiler: Stage 1 | Code Generation for Arithmetic Expressions

This stage focuses on building a simple compiler that parses an input arithmetic expression, constructs an Abstract Syntax Tree (AST), and recursively generates assembly language instructions for the target XSM (Experimental String Machine) architecture.

---

1. Overview & Learning Objectives

• Abstract Syntax Tree (AST): Parse basic arithmetic expressions using Lex and Yacc, packing values and operators into tree nodes.
• Code Generation: Recursively traverse the expression tree to emit target assembly code while managing CPU registers on the fly.
• XSM Output Execution: Interface with the pre-implemented console library to output results.

Specifications

• Target Grammar: E -> E + E | (E) | NUM
• Associativity: Left-associative for +.
• Estimated Time: 0.5 weeks (5–10 hours).

---

2. Compile-Time Data Structures

The parser relies on an Abstract Syntax Tree node structure defined as tnode. The attribute value YYSTYPE must be redefined to act as a pointer to these nodes.

Node Structure Definition

typedef struct tnode {
    int val;              // Value of a node (used for leaf/NUM nodes)
    char *op;             // Name of the operator (e.g., "+") for non-leaf nodes
    struct tnode *left;   // Pointer to left child
    struct tnode *right;  // Pointer to right child
} tnode;

#define YYSTYPE tnode*

/* Allocates a leaf node, assigning its numeric value */
struct tnode* makeLeafNode(int n);

/* Allocates an operator node, linking it to left and right sub-trees */
struct tnode* makeOperatorNode(char op, struct tnode *l, struct tnode *r);

Abstract Syntax Tree (AST) Visualization

For an input expression like 3 + 5 + 2, the syntax tree is built from the bottom up based on left-associativity:

          (op: "+")
          /       \
     (op: "+")   (val: 2)
     /       \
 (val: 3)  (val: 5)

Evaluation Strategy & Register Allocation

Code generation requires translating tree nodes into XSM machine instructions. Because the evaluation relies on hardware registers, a Register Allocation Scheme is implemented using a simple stack or boolean tracker array.

Register Management Interface

• int getReg(): Allocates a free register from R0-R19. Returns the register number, or crashes/blocks if no registers are available.

• void freeReg(int regNum): Marks the designated register number as free for reuse.

Recursive Code Generation Algorithm

The core translation follows a post-order traversal (left -> right -> root):

int codeGen(struct tnode *t, FILE *target_file) {
    // Case 1: Leaf node (NUM)
    if (t->op == NULL) {
        int r = getReg();
        fprintf(target_file, "MOV R%d, %d\n", r, t->val);
        return r;
    }

    // Case 2: Operator Node ("+")
    int left_reg = codeGen(t->left, target_file);
    int right_reg = codeGen(t->right, target_file);

    // Perform operation on left_reg and right_reg
    if (strcmp(t->op, "+") == 0) {
        fprintf(target_file, "ADD R%d, R%d\n", left_reg, right_reg);
    }

    // Free the secondary register, return the result register
    freeReg(right_reg);
    return left_reg;
}

System Architecture Workflow

+------------+       +------------+       +-------------+       +-------------+
| Input Text | ----> | Lex / Yacc | ----> |  AST Tree   | ----> |  codeGen()  |
| (e.g. 3+5) |       |  Parsing   |       | Generation  |       | Translation |
+------------+       +------------+       +-------------+       +-------------+
                                                                       |
                                                                       v
                                                                +-------------+
                                                                | XSM Assembly|
                                                                | Target File |
                                                                +-------------+

XSM Output Execution Target

The generated code block must end by writing the computed answer to standard output using the library execution interface before calling the machine exit system call safely.

; Sample Output Target Structure
MOV R0, [Result_Register]
; --- Call Library write ---
PUSH R0
; ... push parameters ...
CALL 0
; --- Exit Sequence ---
INT 10