ExpL Compiler: Stage 2 | Static Storage Allocation

In this stage, you will extend the Stage 1 expression tree parser to support statements (reads, writes, and variable assignments) alongside standard expressions. You will also design an Abstract Syntax Tree (AST) and learn how the compiler manages memory using Static Storage Allocation.

---

1. Objectives & Overview

• Statements vs. Expressions: Differentiate between expressions (which compute a value) and statements (which direct execution logic without returning a value).
• Static Allocation: Bind variables [a-z] to fixed memory locations within the stack region starting at virtual address 4096.
• Abstract Syntax Tree (AST): Parse and build a unified intermediate representation (AST) using Yacc and Lex.

Stage 2 Target Language Grammar

Program     ::= BEGIN Slist END | BEGIN END
Slist       ::= Slist Stmt | Stmt
Stmt        ::= InputStmt | OutputStmt | AsgStmt
InputStmt   ::= READ(ID);
OutputStmt  ::= WRITE(E);
AsgStmt     ::= ID = E;
E           ::= E + E | (E) | NUM | ID

Compile-Time AST Node Structure

The tnode structure is expanded to accommodate variable identifiers, statement actions (READ, WRITE, =, and sequences), and data types.

typedef struct tnode {
    int val;                    // Value of a constant for NUM nodes
    int type;                   // Data type (e.g., int/void)
    char* varname;              // Name of the variable for ID nodes (e.g., "a" through "z")
    int nodetype;               // Node type: READ, WRITE, ASG, CONN, OPERATOR, NUM, ID
    struct tnode *left, *right; // Subtrees
} tnode;

#define YYSTYPE tnode*

/* Create a generic tree node with customized types and branches */
struct tnode* createTree(int val, int type, char* c, int nodetype, struct tnode *l, struct tnode *r);

Static Memory Allocation Scheme

In this stage, the compiler pre-allocates memory for 26 lowercase variables (a through z). Because the Application Binary Interface (ABI) designates the region starting at virtual address 4096 as stack space, variables are statically mapped to dedicated, absolute addresses.

Variable	Target Memory Address	Formula / Offset
a	4096	4096 + 0
b	4097	4096 + 1
c	4098	4096 + 2
...	...	...
z	4121	4096 + 25
## Code Generation Strategy

When translating statements, the recursive codeGen function must execute statements sequentially and manage the state of registers dynamically.

int codeGen(struct tnode *t, FILE *target_file) {
    if (t == NULL) return -1;

    switch (t->nodetype) {

        case CONN: // Connector Node
            codeGen(t->left, target_file);
            codeGen(t->right, target_file);
            return -1;

        case NUM: { // Constant
            int r = getReg();
            fprintf(target_file, "MOV R%d, %d\n", r, t->val);
            return r;
        }

        case ID: { // Variable Reference (Retrieve value from static address)
            int r = getReg();
            int address = 4096 + (t->varname[0] - 'a');
            fprintf(target_file, "MOV R%d, [%d]\n", r, address);
            return r;
        }

        case ASG: { // Assignment Statement (ID = E)
            int r_expr = codeGen(t->right, target_file);
            int address = 4096 + (t->left->varname[0] - 'a');
            fprintf(target_file, "MOV [%d], R%d\n", address, r_expr);
            freeReg(r_expr);
            return -1;
        }

        case READ: { // Input Library Call (Read into variable)
            int address = 4096 + (t->left->varname[0] - 'a');
            // 1. Save used registers 
            // 2. Push Read System Call Arguments to Stack
            // 3. PUSH -1 (Read Call ID)
            // 4. PUSH -1 (Standard Input File Descriptor)
            // 5. PUSH address (Destination Buffer)
            // 6. CALL 0 (Library Entry point)
            // 7. Pop arguments, restore registers
            return -1;
        }

        case WRITE: { // Output Library Call (Write expression result)
            int r_expr = codeGen(t->left, target_file);
            // Push arguments for Write call using evaluation result r_expr
            // Call Library Code at virtual address 0
            freeReg(r_expr);
            return -1;
        }

        case PLUS: { // Math Operations
            int r_left = codeGen(t->left, target_file);
            int r_right = codeGen(t->right, target_file);
            fprintf(target_file, "ADD R%d, R%d\n", r_left, r_right);
            freeReg(r_right);
            return r_left;
        }
    }
    return -1;
}