Evaluation and Scripts in C

# Evaluation and Scripts in C

## CS 631 Systems Foundations

---

## AST Node Structure

```c
typedef enum {
    NODE_INTLIT,
    NODE_IDENT,
    NODE_UNARY_OP,
    NODE_BINARY_OP,
    NODE_ASSIGN,
    NODE_PRINT
} node_type_t;

typedef struct parse_node_st {
    node_type_t type;
    union {
        uint32_t value;
        char name[MAX_NAME_LEN];
        /* ... */
    } data;
} parse_node_t;
```

<div class="info-box">
Use tagged union for different node types.
</div>

---

## Environment Structure

Array-based symbol table:

```c
#define MAX_VARS 100
#define MAX_NAME_LEN 32

typedef struct {
    char name[MAX_NAME_LEN];
    uint32_t value;
    int is_defined;
} var_entry_t;

typedef struct {
    var_entry_t vars[MAX_VARS];
    int count;
} environment_t;
```

Simple, sufficient for small programs.

---

## Environment Initialization

```c
void env_init(environment_t *env) {
    env->count = 0;
    for (int i = 0; i < MAX_VARS; i++) {
        env->vars[i].is_defined = 0;
        env->vars[i].name[0] = '\0';
        env->vars[i].value = 0;
    }
}
```

Initialize all slots to empty.

---

## Lookup Operation

Linear search through array:

```c
int env_lookup(environment_t *env, const char *name,
               uint32_t *value) {
    for (int i = 0; i < env->count; i++) {
        if (env->vars[i].is_defined &&
            strncmp(env->vars[i].name, name,
                    MAX_NAME_LEN) == 0) {
            *value = env->vars[i].value;
            return 1;  /* Found */
        }
    }
    return 0;  /* Not found */
}
```

O(n) lookup, simple implementation.

---

## Upsert Operation

Insert or update:

```c
void env_set(environment_t *env, const char *name,
             uint32_t value) {
    /* Check if exists (update) */
    for (int i = 0; i < env->count; i++) {
        if (env->vars[i].is_defined &&
            strncmp(env->vars[i].name, name,
                    MAX_NAME_LEN) == 0) {
            env->vars[i].value = value;
            return;
        }
    }
    /* Insert new */
    strncpy(env->vars[env->count].name, name,
            MAX_NAME_LEN - 1);
    env->vars[env->count].value = value;
    env->vars[env->count].is_defined = 1;
    env->count++;
}
```

---

## String Operations

| Function | Purpose |
|----------|---------|
| `strncmp(s1, s2, n)` | Compare strings |
| `strncpy(dst, src, n)` | Copy string |
| `strlen(s)` | Get length |

**Important**: Always null-terminate:

```c
strncpy(dest, src, MAX_NAME_LEN - 1);
dest[MAX_NAME_LEN - 1] = '\0';
```

---

## Expression Evaluation

```c
uint32_t eval_expression(parse_node_t *node,
                         environment_t *env) {
    switch (node->type) {
        case NODE_INTLIT:
            return node->data.value;

case NODE_IDENT:
            return eval_identifier(node, env);

case NODE_UNARY_OP:
            return eval_unary(node, env);

case NODE_BINARY_OP:
            return eval_binary(node, env);
    }
}
```

Dispatch on node type.

---

## Identifier Evaluation

```c
uint32_t eval_identifier(parse_node_t *node,
                         environment_t *env) {
    uint32_t value;
    if (!env_lookup(env, node->data.name, &value)) {
        fprintf(stderr, "Error: undefined variable '%s'\n",
                node->data.name);
        exit(1);
    }
    return value;
}
```

<div class="highlight-box">
Report error and exit if variable not found.
</div>

---

## Unary Operation

```c
uint32_t eval_unary(parse_node_t *node,
                    environment_t *env) {
    uint32_t operand = eval_expression(
        node->data.unary.operand, env);

switch (node->data.unary.op) {
        case '-':
            return (uint32_t)(-(int32_t)operand);
        case '~':
            return ~operand;
    }
}
```

Cast for signed negation.

---

## Binary Operation

```c
uint32_t eval_binary(parse_node_t *node,
                     environment_t *env) {
    uint32_t left = eval_expression(
        node->data.binary.left, env);
    uint32_t right = eval_expression(
        node->data.binary.right, env);

if (strcmp(op, "+") == 0) return left + right;
    if (strcmp(op, "-") == 0) return left - right;
    if (strcmp(op, "*") == 0) return left * right;
    if (strcmp(op, "/") == 0) return left / right;
    /* ... */
}
```

---

## Arithmetic Shift Right

```c
if (strcmp(op, ">-") == 0) {
    /* Cast to signed, shift, cast back */
    return (uint32_t)((int32_t)left >> right);
}
```

<div class="info-box">
C's <code>>></code> on signed types performs arithmetic shift (sign-extending).
</div>

---

## Statement Evaluation

```c
void eval_statement(parse_node_t *stmt,
                    environment_t *env) {
    switch (stmt->type) {
        case NODE_ASSIGN:
            eval_assignment(stmt, env);
            break;

case NODE_PRINT:
            eval_print(stmt, env);
            break;
    }
}
```

Dispatch on statement type.

---

## Assignment Evaluation

```c
void eval_assignment(parse_node_t *stmt,
                     environment_t *env) {
    const char *var_name = stmt->data.assign.name;
    uint32_t value = eval_expression(
        stmt->data.assign.expr, env);

env_set(env, var_name, value);
}
```

Three simple steps:

1. Get variable name
2. Evaluate expression
3. Store in environment

---

## Print Evaluation

```c
void eval_print(parse_node_t *stmt, environment_t *env) {
    uint32_t value = eval_expression(
        stmt->data.print.expr, env);
    uint32_t base = eval_expression(
        stmt->data.print.base, env);
    uint32_t width = eval_expression(
        stmt->data.print.width, env);

/* Validate base and width */
    if (base != 2 && base != 10 && base != 16) {
        error_exit("base must be 2, 10, or 16");
    }

print_formatted(value, base, width);
}
```

---

## Width Masking

```c
uint32_t apply_width_mask(uint32_t value,
                          uint32_t width) {
    if (width == 32) {
        return value;
    }
    uint32_t mask = (1U << width) - 1;
    return value & mask;
}
```

| Width | Mask |
|-------|------|
| 4 | `0x0F` |
| 8 | `0xFF` |
| 16 | `0xFFFF` |
| 32 | `0xFFFFFFFF` |

---

## Sign Extension

```c
int32_t sign_extend(uint32_t value, uint32_t width) {
    uint32_t masked = apply_width_mask(value, width);

/* Check MSB of width */
    uint32_t sign_bit = 1U << (width - 1);
    if (masked & sign_bit) {
        /* Fill upper bits with 1 */
        uint32_t extension = ~((1U << width) - 1);
        masked |= extension;
    }
    return (int32_t)masked;
}
```

For base 10 output.

---

## Formatted Output

```c
void print_formatted(uint32_t value, uint32_t base,
                     uint32_t width) {
    uint32_t masked = apply_width_mask(value, width);

if (base == 10) {
        int32_t signed_val = sign_extend(value, width);
        printf("%d\n", signed_val);
    } else if (base == 16) {
        char buf[64];
        uint_to_hex(masked, buf, width);
        printf("0x%s\n", buf);
    } else if (base == 2) {
        char buf[64];
        uint_to_bin(masked, buf, width);
        printf("0b%s\n", buf);
    }
}
```

---

## Program Evaluation

```c
void eval_program(parse_node_t **statements,
                  int num_statements) {
    environment_t env;
    env_init(&env);

for (int i = 0; i < num_statements; i++) {
        eval_statement(statements[i], &env);
    }
}
```

Simple loop through statements.

Environment persists across statements.

---

## Error Handling Pattern

```c
void error_exit(const char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    exit(1);
}

void error_exit_fmt(const char *fmt, ...) {
    va_list args;
    va_start(args, fmt);
    fprintf(stderr, "Error: ");
    vfprintf(stderr, fmt, args);
    fprintf(stderr, "\n");
    va_end(args);
    exit(1);
}
```

Descriptive messages, exit on error.

---

## Common Errors

| Error | Check |
|-------|-------|
| Undefined variable | Lookup fails |
| Division by zero | Right operand is 0 |
| Invalid base | Not in {2, 10, 16} |
| Invalid width | Not in {4, 8, 16, 32} |
| Too many variables | `count >= MAX_VARS` |

---

## Memory Management

**Stack allocation**:

```c
void eval_program(...) {
    environment_t env;  /* Stack */
    env_init(&env);
    /* ... */
}
```

**Heap allocation** (if needed):

```c
environment_t *env = malloc(sizeof(environment_t));
env_init(env);
/* Use env */
free(env);
```

---

## AST Memory Management

Free nodes recursively:

```c
void free_node(parse_node_t *node) {
    if (node == NULL) return;

switch (node->type) {
        case NODE_UNARY_OP:
            free_node(node->data.unary.operand);
            break;
        case NODE_BINARY_OP:
            free_node(node->data.binary.left);
            free_node(node->data.binary.right);
            break;
        /* ... */
    }
    free(node);
}
```

---

## File Structure

```text
project01/c/
├── main.c          # Entry point
├── scan.c          # Scanner
├── scan.h
├── parse.c         # Parser
├── parse.h         # AST definitions
├── eval.c          # Evaluator
├── eval.h
├── convert.c       # Base conversion
├── convert.h
└── Makefile
```

---

## Integration with Parser

```c
int main(int argc, char *argv[]) {
    char *source = read_file(argv[1]);
    token_t *tokens = scan(source);

parse_node_t **statements;
    int num_statements = parse_program(tokens,
                                       &statements);

eval_program(statements, num_statements);

free_statements(statements, num_statements);
    free(tokens);
    free(source);
}
```

---

## Summary

1. **Struct-based AST** with tagged unions
2. **Array-based environment** with linear search
3. **Upsert semantics** for assignment
4. **Recursive evaluation** dispatching on node type
5. **Type casting** for signed operations
6. **Error handling** with stderr and exit
7. **Width masking** and sign extension
8. **Memory management** for AST nodes