Parsing in C - CS 631

# Parsing in C

## CS 631 Systems Foundations

---

## AST Node Types

```c
enum parse_expr_enum {
    EX_INTVAL,  /* Integer value (leaf) */
    EX_OPER1,   /* Unary operator (1 child) */
    EX_OPER2    /* Binary operator (2 children) */
};

enum parse_oper_enum {
    OP_PLUS,
    OP_MINUS,
    OP_MULT,
    OP_DIV
};
```

---

## parse_node_st Structure

```c
struct parse_node_st {
    enum parse_expr_enum type;
    union {
        struct { int value; } intval;
        struct {
            enum parse_oper_enum oper;
            struct parse_node_st *operand;
        } oper1;
        struct {
            enum parse_oper_enum oper;
            struct parse_node_st *left;
            struct parse_node_st *right;
        } oper2;
    };
};
```

---

## Why Use a Union?

</div>
<div>

| Type | Uses |
|------|------|
| EX_INTVAL | `intval.value` |
| EX_OPER1 | `oper1.oper`, `oper1.operand` |
| EX_OPER2 | `oper2.oper`, `oper2.left`, `oper2.right` |

</div>
</div>

Only one member is valid at a time (based on `type`).

---

## parse_table_st Structure

```c
#define PARSE_TABLE_LEN 1024

struct parse_table_st {
    struct parse_node_st table[PARSE_TABLE_LEN];
    int len;  /* Number of nodes allocated */
};
```

Pre-allocated array - no malloc/free needed!

---

## parse_node_new Function

```c
struct parse_node_st * parse_node_new(struct parse_table_st *pt) {
    struct parse_node_st *np;

np = &(pt->table[pt->len]);
    pt->len += 1;

return np;
}
```

1. Get pointer to next slot
2. Increment length
3. Return pointer

---

## Memory Layout

For `"1 + 2"`:

---

## scan_table_get

```c
struct scan_token_st * scan_table_get(
    struct scan_table_st *st, int i) {

return &(st->table[st->cur + i]);
}
```

| Call | Returns |
|------|---------|
| `get(0)` | Current token |
| `get(-1)` | Previous (just consumed) |
| `get(1)` | Next (lookahead) |

---

## scan_table_accept

```c
bool scan_table_accept(struct scan_table_st *st,
                       enum scan_token_enum tk_expected) {
    struct scan_token_st *tp;
    if (tk_expected == TK_ANY) {
        st->cur += 1;
        return true;
    }
    tp = scan_table_get(st, 0);
    if (tp->id == tk_expected) {
        st->cur += 1;
        return true;
    }
    return false;
}
```

---

## TK_ANY Wildcard

Use when you already know the token type:

```c
tp = scan_table_get(st, 0);  /* Peek */
if (tp->id == TK_PLUS) {
    scan_table_accept(st, TK_ANY);  /* Just consume it */
    /* ... handle PLUS ... */
}
```

<div class="info-box">
<code>TK_ANY</code> = "I know what this is, just advance"
</div>

---

## parse_program

```c
struct parse_node_st * parse_program(
    struct parse_table_st *pt,
    struct scan_table_st *st) {

struct parse_node_st *np1;

np1 = parse_expression(pt, st);

if (!scan_table_accept(st, TK_EOT)) {
        parse_error("Expecting EOT");
    }

return np1;
}
```

Grammar: `program ::= expression EOT`

---

## parse_expression Overview

```c
struct parse_node_st * parse_expression(
    struct parse_table_st *pt,
    struct scan_table_st *st) {

struct scan_token_st *tp;
    struct parse_node_st *np1, *np2;

np1 = parse_operand(pt, st);  /* First operand */

while (true) {
        tp = scan_table_get(st, 0);
        if (tp->id == TK_PLUS) {
            /* ... handle operator ... */
        } else {
            break;
        }
    }

return np1;
}
```

---

## parse_expression: The Loop

```c
if (tp->id == TK_PLUS) {
    scan_table_accept(st, TK_ANY);

np2 = parse_node_new(pt);
    np2->type = EX_OPER2;
    np2->oper2.oper = OP_PLUS;
    np2->oper2.left = np1;
    np2->oper2.right = parse_operand(pt, st);

np1 = np2;  /* Update current result */
}
```

**Key**: `np1` (previous result) becomes left child!

---

## Building OPER2 Nodes

```text
Before:  np1 -> (1)

After creating OPER2:
                np2 -> (+)
                      /   \
         np1 -> (1)      (2)

After "np1 = np2":
                np1 -> (+)
                      /   \
                    (1)  (2)
```

---

## parse_operand Overview

```c
struct parse_node_st * parse_operand(
    struct parse_table_st *pt,
    struct scan_table_st *st) {

struct scan_token_st *tp;
    struct parse_node_st *np1;

if (scan_table_accept(st, TK_INTLIT)) {
        /* Handle integer literal */
    } else {
        parse_error("Bad operand");
    }

return np1;
}
```

---

## parse_operand: Integer Literals

```c
if (scan_table_accept(st, TK_INTLIT)) {
    tp = scan_table_get(st, -1);  /* Get consumed token */

np1 = parse_node_new(pt);
    np1->type = EX_INTVAL;
    np1->intval.value = atoi(tp->value);
}
```

<div class="highlight-box">Note: <code>get(-1)</code> retrieves the token we just accepted!
</div>

---

## parse_operand: Unary/Parentheses

```c
if (scan_table_accept(st, TK_LPAREN)) {
    np1 = parse_expression(pt, st);  /* Recursive! */
    if (!scan_table_accept(st, TK_RPAREN)) {
        parse_error("Missing right paren");
    }
} else if (scan_table_accept(st, TK_MINUS)) {
    np1 = parse_node_new(pt);
    np1->type = EX_OPER1;
    np1->oper1.oper = OP_MINUS;
    np1->oper1.operand = parse_operand(pt, st);  /* Recursive! */
}
```

---

## Left-Associative Building

For `"1 + 2 + 3"`:

<div class="mermaid">
flowchart LR
    subgraph Step1["Step 1"]
        A["np1 = (1)"]
    end
    subgraph Step2["Step 2"]
        B["np1 = (+)"]
        B1["(1)"] --> B
        B2["(2)"] --> B
    end
    subgraph Step3["Step 3"]
        C["np1 = (+)"]
        C1["prev (+)"] --> C
        C2["(3)"] --> C
    end
    Step1 --> Step2 --> Step3
</div>

Previous result always becomes **left child**!

---

## Step-by-Step: "1 + 2"

```text
1. parse_operand() -> table[0] = INTVAL(1)
   np1 = &table[0]

2. get(0)->id == TK_PLUS, accept it

3. parse_operand() -> table[1] = INTVAL(2)

4. table[2] = OPER2(PLUS)
   left = &table[0]
   right = &table[1]
   np1 = &table[2]

5. get(0)->id == TK_EOT, break

6. Return np1 (&table[2])
```

---

## Memory State After "1 + 2"

(+) [2]
      /   \
    (1)   (2)
   [0]    [1]
```

---

## Key Patterns

| Pattern | Purpose |
|---------|---------|
| `accept(TOKEN)` | Consume if matches, return bool |
| `get(0)` | Peek at current token |
| `get(-1)` | Get just-consumed token |
| `TK_ANY` | Wildcard accept |
| `np1 = np2` | Update current result |

---

## Summary

1. **Union-based nodes** - same size, type-specific data
2. **Parse table** - pre-allocated array, no malloc
3. **parse_node_new()** - bump allocator
4. **accept/get pattern** - consume and retrieve tokens
5. **Left-associative loop** - previous result is left child
6. **Recursive calls** - for parentheses and unary operators