Parsing in Rust

# Parsing in Rust

## CS 631 Systems Foundations

---

## ParseNode Enum

```rust
pub enum ParseNode {
    IntVal { value: i32 },
    Oper1 { oper: Operator, operand: Box<ParseNode> },
    Oper2 { oper: Operator, left: Box<ParseNode>, right: Box<ParseNode> },
}
```

Each variant contains its own data - no separate type field!

---

## Operator Enum

```rust
#[derive(Debug, Clone, Copy)]
pub enum Operator {
    Plus,
    Minus,
    Mult,
    Div,
}

impl Operator {
    pub fn name(&self) -> &str {
        match self {
            Operator::Plus => "PLUS",
            Operator::Minus => "MINUS",
            Operator::Mult => "MULT",
            Operator::Div => "DIV",
        }
    }
}
```

---

## Enums with Associated Data

Compare to C:

**C:**
```c
struct node {
    enum type;  // Must track type
    union {
        struct { int value; } intval;
        struct { ... } oper2;
    };
};
```

</div>
<div>

**Rust:**
```rust
enum ParseNode {
    IntVal { value: i32 },
    Oper2 { left: Box<...>, ... },
}
// Type is the variant itself!
```

</div>
</div>

---

## Why Box<T>?

This won't compile:

```rust
enum ParseNode {
    IntVal { value: i32 },
    Oper2 { left: ParseNode, right: ParseNode },  // ERROR!
}
```

**Error**: `ParseNode` would have infinite size!

**Solution**: Use `Box<T>` for heap allocation.

---

## Memory Model

`Box<T>` = pointer to heap-allocated data

---

## Token and TokenType

```rust
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum TokenType {
    IntLit,
    Plus,
    Minus,
    Eot,
}

#[derive(Debug, Clone)]
pub enum Token {
    IntLit(String),
    Plus,
    Minus,
    Eot,
}
```

Two enums: one for matching, one for data

---

## ScanTable Methods

```rust
impl ScanTable {
    /// Get token at position cur + i
    pub fn get(&self, i: isize) -> &Token {
        let index = (self.cur as isize + i) as usize;
        &self.tokens[index]
    }

/// Accept if matches expected type
    pub fn accept(&mut self, expected: TokenType) -> bool {
        if self.tokens[self.cur].token_type() == expected {
            self.cur += 1;
            return true;
        }
        false
    }
}
```

---

## Pattern Matching

```rust
let token = scan_table.get(0);
match token.token_type() {
    TokenType::Plus => {
        // Handle +
    }
    TokenType::Minus => {
        // Handle -
    }
    _ => break,  // Wildcard: everything else
}
```

Cleaner than if-else chains!

---

## parse_program

```rust
pub fn parse_program(scan_table: &mut ScanTable) -> ParseNode {
    let expr = parse_expression(scan_table);

if !scan_table.accept(TokenType::Eot) {
        parse_error("Expecting EOT");
    }

expr
}
```

Returns owned `ParseNode` (not a pointer)

---

## parse_expression Overview

```rust
fn parse_expression(scan_table: &mut ScanTable) -> ParseNode {
    let mut left = parse_operand(scan_table);

loop {
        let token = scan_table.get(0);
        match token.token_type() {
            TokenType::Plus => { /* ... */ }
            TokenType::Minus => { /* ... */ }
            _ => break,
        }
    }

left
}
```

---

## parse_expression: The Match

```rust
TokenType::Plus => {
    scan_table.accept_any();
    let right = parse_operand(scan_table);
    left = ParseNode::new_oper2(Operator::Plus, left, right);
}
```

1. Accept the operator
2. Parse right operand
3. Build OPER2 node
4. Assign back to `left`

---

## parse_operand

```rust
fn parse_operand(scan_table: &mut ScanTable) -> ParseNode {
    if scan_table.accept(TokenType::IntLit) {
        let token = scan_table.get(-1);
        let value: i32 = token.value().parse().unwrap_or_else(|_| {
            parse_error("Invalid integer literal");
        });
        ParseNode::new_intval(value)
    } else {
        parse_error("Bad operand");
    }
}
```

---

## Ownership Transfer

```rust
let mut left = parse_operand(...);  // left owns IntVal(1)
let right = parse_operand(...);     // right owns IntVal(2)

left = ParseNode::new_oper2(Operator::Plus, left, right);
//     ^^^ left and right are MOVED into new_oper2
```

After this: original values no longer accessible.

---

## new_oper2 Method

```rust
impl ParseNode {
    pub fn new_oper2(oper: Operator, left: ParseNode, right: ParseNode) -> Self {
        ParseNode::Oper2 {
            oper,
            left: Box::new(left),   // Takes ownership
            right: Box::new(right), // Takes ownership
        }
    }
}
```

`Box::new()` allocates on heap, takes ownership.

---

## Ownership Flow

<div class="mermaid">
flowchart TD
    subgraph Before
        A[left: IntVal-1]
        B[right: IntVal-2]
    end
    subgraph During
        C["new_oper2(Plus, left, right)"]
        D["Box::new(left)"]
        E["Box::new(right)"]
        C --> D
        C --> E
    end
    subgraph After
        F["left: Oper2"]
        G["Box -> IntVal(1)"]
        H["Box -> IntVal(2)"]
        F --> G
        F --> H
    end
    Before --> During --> After
</div>

---

## Building "1 + 2"

```text
1. parse_operand() -> IntVal { value: 1 }
   left owns this

2. accept_any() consumes PLUS

3. parse_operand() -> IntVal { value: 2 }
   right owns this

4. new_oper2(Plus, left, right)
   -> left and right MOVED
   -> Returns Oper2 with Box children
   -> Assigned to left

5. No more operators, return left
```

---

## C vs Rust Comparison

| Aspect | C | Rust |
|--------|---|------|
| Allocation | `parse_node_new(pt)` | `Box::new()` implicit |
| Type tag | `np->type = EX_OPER2` | Enum variant |
| Data access | `np->oper2.left` | Pattern match |
| Memory | Pre-allocated array | Heap via Box |

---

## Code Comparison

**C:**
```c
np = parse_node_new(pt);
np->type = EX_OPER2;
np->oper2.oper = OP_PLUS;
np->oper2.left = np1;
np->oper2.right = parse_operand(pt, st);
np1 = np;
```

**Rust:**
```rust
left = ParseNode::new_oper2(Operator::Plus, left, right);
```

---

## Pattern Matching on Nodes

```rust
fn eval(node: &ParseNode) -> i32 {
    match node {
        ParseNode::IntVal { value } => *value,
        ParseNode::Oper2 { oper, left, right } => {
            let l = eval(left);
            let r = eval(right);
            match oper {
                Operator::Plus => l + r,
                Operator::Minus => l - r,
                // ...
            }
        }
        // ...
    }
}
```

---

## Key Rust Concepts

| Concept | Purpose |
|---------|---------|
| Enum with data | Type-safe node variants |
| `Box<T>` | Recursive types, heap allocation |
| Ownership | Automatic memory management |
| `match` | Exhaustive pattern matching |
| `&mut` | Mutable references |

---

## Summary (1/2)

1. **Enums with associated data** replace C's struct+union

2. **`Box<T>`** enables recursive types

3. **Ownership transfer** happens automatically

4. **Pattern matching** cleaner than if-else

---

## Summary (2/2)

5. **No explicit memory management** - Rust handles it

6. **Same parsing logic** as C - different representation

7. **Type safety** enforced at compile time