Interpreter (AST Execution)

Overview

The Interpreter is the fifth phase of compilation. Instead of generating machine code, it directly executes the Abstract Syntax Tree, allowing programs to run immediately without a separate assembly/execution step.

Interpreter vs. Compiler:Compiler:

Source → Tokens → AST → Assembly → Machine Code → Execute

Interpreter:

Source → Tokens → AST → Execute ✓

Interpreter is faster to start, but slower to run (no optimization).

How It Works

The interpreter walks the AST recursively, executing each node:

Initialize

Create empty runtime environment:

self.variables = {}  # Variable name → value mapping

Execute Statements

For each statement in the program:

Evaluate expressions
Update variables
Perform I/O (print)

Complete

All statements executed, program terminates.

Runtime Environment

The interpreter maintains a variable store:

class Interprete:
    def __init__(self):
        self.variables = {}  # Dict[str, int]

Example during execution:

# After: let x = 5;
variables = {'x': 5}

# After: let y = 10;
variables = {'x': 5, 'y': 10}

# After: let z = x + y;
variables = {'x': 5, 'y': 10, 'z': 15}

Semantic analysis already verified all variables are declared before use, so no runtime checks needed.

Statement Execution

Variable Declaration
Print Statement

def ejecutar_sentencia(self, sentencia):
    if isinstance(sentencia, DeclaracionVariable):
        # Evaluate the right-hand expression
        valor = self.evaluar(sentencia.expresion)
        
        # Store in variable map
        self.variables[sentencia.nombre.lexema] = valor

Example:

let x = 5 + 3;

Execution:

1. evaluar(ExpresionBinaria(+, 5, 3)) → 8
2. variables['x'] = 8

def ejecutar_sentencia(self, sentencia):
    elif isinstance(sentencia, SentenciaPrint):
        # Evaluate the expression
        valor = self.evaluar(sentencia.expresion)
        
        # Print to console
        print("     Resultado:")
        print(f"                → {valor}")

Example:

print x + 1;

Execution:

1. evaluar(ExpresionBinaria(+, x, 1)):
   - evaluar(Identificador('x')) → 5
   - evaluar(NumeroLiteral(1)) → 1
   - 5 + 1 → 6
2. print "     Resultado:"
3. print "                → 6"

Console Output:

     Resultado:
                → 6

Expression Evaluation

The evaluar() method recursively evaluates expressions:

Number Literal
Identifier
Binary Expression
Grouped Expression

def evaluar(self, expr):
    if isinstance(expr, NumeroLiteral):
        return expr.valor

Example:

42  →  returns: 42

def evaluar(self, expr):
    elif isinstance(expr, Identificador):
        return self.variables[expr.nombre]

Example:

x  →  returns: self.variables['x']  →  5

No error checking - semantic analysis already verified variable exists.

def evaluar(self, expr):
    elif isinstance(expr, ExpresionBinaria):
        # Evaluate left and right operands
        izq = self.evaluar(expr.izquierda)
        der = self.evaluar(expr.derecha)
        
        # Perform operation based on operator type
        if expr.operador.tipo == TipoToken.SUMA:
            return izq + der
        elif expr.operador.tipo == TipoToken.RESTA:
            return izq - der
        elif expr.operador.tipo == TipoToken.MULTIPLICACION:
            return izq * der
        elif expr.operador.tipo == TipoToken.DIVISION:
            return izq // der  # Integer division

Example:

5 + 3  →  evaluar(5) + evaluar(3)  →  5 + 3  →  8

def evaluar(self, expr):
    elif isinstance(expr, ExpresionAgrupada):
        # Parentheses don't affect evaluation - just recurse
        return self.evaluar(expr.expresion)

Example:

(5 + 3)  →  evaluar(5 + 3)  →  8

Execution Examples

Simple Program

Code
Execution Trace
Console Output

let x = 5;
let y = 10;
print x + y;

# Statement 1: let x = 5;
ejecutar_sentencia(DeclaracionVariable):
  valor = evaluar(NumeroLiteral(5)):
    return 5
  variables['x'] = 5
# variables = {'x': 5}

# Statement 2: let y = 10;
ejecutar_sentencia(DeclaracionVariable):
  valor = evaluar(NumeroLiteral(10)):
    return 10
  variables['y'] = 10
# variables = {'x': 5, 'y': 10}

# Statement 3: print x + y;
ejecutar_sentencia(SentenciaPrint):
  valor = evaluar(ExpresionBinaria(+)):
    izq = evaluar(Identificador('x')):
      return variables['x'] → 5
    der = evaluar(Identificador('y')):
      return variables['y'] → 10
    operator == SUMA
    return 5 + 10 → 15
  print "     Resultado:"
  print "                → 15"

[FASE 5] Ejecución del programa...
              (Interpretando el AST)
     Resultado:
                → 15
  ✓ Ejecución finalizada

Complex Expression

Code
Execution Trace
Console Output

let a = 5;
let b = 10;
let c = a + b * 2;
print c;

# Statement 1: let a = 5;
variables['a'] = 5
# variables = {'a': 5}

# Statement 2: let b = 10;
variables['b'] = 10
# variables = {'a': 5, 'b': 10}

# Statement 3: let c = a + b * 2;
evaluar(ExpresionBinaria(+)):
  izq = evaluar(Identificador('a')):
    return variables['a'] → 5
  
  der = evaluar(ExpresionBinaria(*)):
    izq = evaluar(Identificador('b')):
      return variables['b'] → 10
    der = evaluar(NumeroLiteral(2)):
      return 2
    operator == MULTIPLICACION
    return 10 * 2 → 20
  
  operator == SUMA
  return 5 + 20 → 25

variables['c'] = 25
# variables = {'a': 5, 'b': 10, 'c': 25}

# Statement 4: print c;
evaluar(Identificador('c')):
  return variables['c'] → 25
print "     Resultado:"
print "                → 25"

     Resultado:
                → 25

Integer Division

The interpreter uses floor division (//), not floating-point division.Example:

let x = 7 / 2;
print x;

Output:

     Resultado:
                → 3  // Not 3.5

This matches typical compiler behavior for integer types.

Runtime Errors

The interpreter does not catch runtime errors like:

Division by zero (with variables):
```
let x = 0;
let y = 10 / x;  // Python ZeroDivisionError
```
Semantic analysis only catches literal zero division.
Integer overflow:
```
let x = 999999 * 999999;  // May overflow
```
Python integers have unlimited precision, but in a real compiler this would overflow.
Uninitialized variables: Already prevented by semantic analysis.

Why Interpret the AST?

Fast Development

Immediate execution - no assembly/linking step.Great for:

Testing
Debugging
Learning

Portability

Runs anywhere Python runs - no architecture-specific code.

Simplicity

Easy to implement - just recursive evaluation.~50 lines of code vs. hundreds for code generator.

Debugging

Can inspect variables, trace execution, set breakpoints.Harder with compiled code.

Interpreter vs. Code Generator

Both execute the same AST, but differently:

Interpreter Approach
Code Generator Approach

Direct execution:

def evaluar(self, expr):
    if isinstance(expr, ExpresionBinaria):
        izq = self.evaluar(expr.izquierda)   # Evaluate left
        der = self.evaluar(expr.derecha)      # Evaluate right
        if expr.operador.tipo == TipoToken.SUMA:
            return izq + der                  # Compute result

Pros:

Simple, fast to write
No separate execution phase
Easy to debug

Cons:

Slower runtime (function calls, type checks)
No optimization
Requires Python runtime

Emit assembly:

def generar_expr(self, expr):
    if isinstance(expr, ExpresionBinaria):
        self.generar_expr(expr.izquierda)   # Generate left code
        self.emit("push ax")                # Save left result
        self.generar_expr(expr.derecha)      # Generate right code
        self.emit("mov bx, ax")             # Right to BX
        self.emit("pop ax")                 # Restore left to AX
        self.emit("add ax, bx")             # Add

Pros:

Fast runtime (native code)
Can optimize
Standalone executable

Cons:

Complex to implement
Architecture-specific
Longer development time

Implementation Details

Class Structure
Entry Point

class Interprete:
    def __init__(self):
        self.variables = {}  # Runtime variable storage
    
    def ejecutar(self, programa):
        """Execute all statements in program"""
        for sentencia in programa.sentencias:
            self.ejecutar_sentencia(sentencia)
    
    def ejecutar_sentencia(self, sentencia):
        """Execute one statement"""
        if isinstance(sentencia, DeclaracionVariable):
            valor = self.evaluar(sentencia.expresion)
            self.variables[sentencia.nombre.lexema] = valor
        elif isinstance(sentencia, SentenciaPrint):
            valor = self.evaluar(sentencia.expresion)
            print(f"                → {valor}")
    
    def evaluar(self, expr):
        """Recursively evaluate expression, return integer"""
        # Dispatch by expression type

Called from main compiler pipeline:

# After semantic analysis passes...
interprete = Interprete()
interprete.ejecutar(programa)

Full output:

[FASE 5] Ejecución del programa...
              (Interpretando el AST)
     Resultado:
                → 25
  ✓ Ejecución finalizada

Performance

Time Complexity

O(n) where n = number of operationsEach AST node visited/executed once.But slower than compiled code due to:

Function call overhead
Type checking
Dictionary lookups

Space Complexity

O(v + d) where:

v = number of variables
d = max expression depth (recursion stack)

No optimization, so temporary values live on call stack.

Comparison: Interpreted vs. Compiled Execution

For program: let x = 5 + 3; print x;

Interpreted Execution
Compiled Execution

Runtime:

1. evaluar(ExpresionBinaria(+)):
     izq = evaluar(NumeroLiteral(5)) → 5
     der = evaluar(NumeroLiteral(3)) → 3
     return 5 + 3 → 8
2. variables['x'] = 8
3. print variables['x']

Time: ~microseconds (Python overhead)

Assembly:

mov ax, 5      ; Load 5
push ax        ; Save
mov ax, 3      ; Load 3
mov bx, ax     ; To BX
pop ax         ; Restore 5
add ax, bx     ; Add → AX = 8
mov x, ax      ; Store
mov ax, x      ; Load
call print_num ; Print

Time: ~nanoseconds (native execution)

Speed difference: Compiled code is 100-1000x faster for compute-heavy tasks. But for small educational programs, interpreter is fast enough and much simpler.

Source Code Reference

Implementation

File: compfinal.pyLines: 1156-1215Key Class:

Interprete - AST interpreter

Main Methods:

ejecutar(programa) - Entry point, executes all statements
ejecutar_sentencia(sentencia) - Execute one statement
evaluar(expr) - Recursively evaluate expression, return integer value

Data Structures:

variables: Dict[str, int] - Runtime variable storage

Next Steps

Code Generation

See how the AST is converted to x86 assembly instead

API Reference

Detailed API documentation for the Interprete class

Get Started

Core Concepts

Guides

Compiler Components

API Reference

Examples

Overview

How It Works

Runtime Environment

Statement Execution

Expression Evaluation

Execution Examples

Simple Program

Complex Expression

Integer Division

Runtime Errors

Why Interpret the AST?

Fast Development

Portability

Simplicity

Debugging

Interpreter vs. Code Generator

Implementation Details

Performance

Time Complexity

Space Complexity

Comparison: Interpreted vs. Compiled Execution

Source Code Reference

Implementation

Next Steps

Code Generation

API Reference

Build docs developers (and LLMs) love

Get Started

Core Concepts

Guides

Compiler Components

API Reference

Examples

​Overview

​How It Works

​Runtime Environment

​Statement Execution

​Expression Evaluation

​Execution Examples

​Simple Program

​Complex Expression

​Integer Division

​Runtime Errors

​Why Interpret the AST?

Fast Development

Portability

Simplicity

Debugging

​Interpreter vs. Code Generator

​Implementation Details

​Performance

Time Complexity

Space Complexity

​Comparison: Interpreted vs. Compiled Execution

​Source Code Reference

Implementation

​Next Steps

Code Generation

API Reference

Build docs developers (and LLMs) love

Overview

How It Works

Runtime Environment

Statement Execution

Expression Evaluation

Execution Examples

Simple Program

Complex Expression

Integer Division

Runtime Errors

Why Interpret the AST?

Interpreter vs. Code Generator

Implementation Details

Performance

Comparison: Interpreted vs. Compiled Execution

Source Code Reference

Next Steps