ast_parser.py

"""
PHASE 2: PARSER (SYNTAX ANALYZER)

What is a Parser?
-----------------
A parser takes the token stream from the lexer and checks if it follows
the grammar rules of the language. It builds an Abstract Syntax Tree (AST).

Why do we need it?
------------------
Tokens alone don't show structure. Consider: "x = 5 + 3"
Tokens: [ID, ASSIGN, NUMBER, PLUS, NUMBER]
But what does it MEAN? The parser figures out:
- This is an assignment
- The right side is an addition expression
- 5 + 3 should be evaluated first, then assigned to x

What is an AST?
---------------
Abstract Syntax Tree - a tree representation of code structure.
Example: x = 5 + 3

        Assignment
        /        \
       x      Addition
              /      \
             5        3

The tree shows that addition happens first (it's deeper in the tree).

Parsing Strategy: Recursive Descent
------------------------------------
We use "recursive descent parsing" - the simplest parsing technique.
Each grammar rule becomes a function that calls other functions recursively.

Our Grammar (in EBNF notation):
--------------------------------
program     → statement*
statement   → assignment | print_stmt
assignment  → ID = expression ;
print_stmt  → print ( expression ) ;
expression  → term ((+|-) term)*
term        → factor ((*|/) factor)*
factor      → NUMBER | ID | ( expression )

This grammar handles operator precedence:
- * and / have higher precedence than + and -
- Parentheses override precedence
"""

from lexer import Token, TokenType, Lexer


# ============================================================================
# AST NODE CLASSES
# ============================================================================
# Each class represents a different kind of syntax tree node

class ASTNode:
    """
    Base class for all AST nodes
    
    Every node in our syntax tree inherits from this.
    It's like saying "everything in our tree is an ASTNode"
    """
    pass


class NumberNode(ASTNode):
    """
    Represents a number literal
    
    Example: 42
    """
    def __init__(self, value):
        self.value = int(value)  # Convert string to integer
    
    def __repr__(self):
        return f"Number({self.value})"


class VariableNode(ASTNode):
    """
    Represents a variable reference
    
    Example: x, myVar, count
    """
    def __init__(self, name):
        self.name = name
    
    def __repr__(self):
        return f"Var({self.name})"


class BinaryOpNode(ASTNode):
    """
    Represents a binary operation (operation with two operands)
    
    Examples:
    - 5 + 3  → BinaryOpNode('+', Number(5), Number(3))
    - x * y  → BinaryOpNode('*', Var(x), Var(y))
    
    The tree structure automatically handles precedence:
    - 2 + 3 * 4 becomes:
            +
           / \
          2   *
             / \
            3   4
    This shows that 3*4 is evaluated first!
    """
    def __init__(self, operator, left, right):
        self.operator = operator  # '+', '-', '*', '/'
        self.left = left          # Left operand (another AST node)
        self.right = right        # Right operand (another AST node)
    
    def __repr__(self):
        return f"BinOp({self.operator}, {self.left}, {self.right})"


class AssignmentNode(ASTNode):
    """
    Represents an assignment statement
    
    Example: x = 5 + 3
    
    Structure:
        Assignment
        /        \
    name='x'   BinOp(+, 5, 3)
    """
    def __init__(self, variable_name, expression):
        self.variable_name = variable_name
        self.expression = expression
    
    def __repr__(self):
        return f"Assign({self.variable_name} = {self.expression})"


class PrintNode(ASTNode):
    """
    Represents a print statement
    
    Example: print(x + 5)
    
    Structure:
        Print
          |
       BinOp(+, Var(x), 5)
    """
    def __init__(self, expression):
        self.expression = expression
    
    def __repr__(self):
        return f"Print({self.expression})"


class ProgramNode(ASTNode):
    """
    Represents the entire program (root of AST)
    
    A program is just a list of statements.
    
    Example program:
        x = 5;
        print(x);
    
    Becomes:
        Program
        /     \
    Assign   Print
    """
    def __init__(self, statements):
        self.statements = statements  # List of statement nodes
    
    def __repr__(self):
        return f"Program({len(self.statements)} statements)"


# ============================================================================
# PARSER CLASS
# ============================================================================

class Parser:
    """
    Recursive Descent Parser
    
    The parser has one method for each grammar rule.
    Each method:
    1. Checks if current token matches what's expected
    2. Consumes tokens
    3. Calls other methods for sub-expressions
    4. Returns an AST node
    
    Example flow for "x = 5;":
    parse_program() → parse_statement() → parse_assignment()
    → parse_expression() → parse_term() → parse_factor()
    """
    
    def __init__(self, tokens):
        """
        Initialize parser with token list
        
        Args:
            tokens: List of tokens from lexer
        """
        self.tokens = tokens
        self.position = 0
        self.current_token = self.tokens[0] if tokens else None
    
    def error(self, message):
        """
        Report a syntax error
        
        In real compilers, this would:
        - Show the line of code with the error
        - Point to the exact position
        - Suggest what was expected
        """
        raise Exception(f"Parser Error at token {self.position}: {message}\n"
                       f"Current token: {self.current_token}")
    
    def advance(self):
        """
        Move to the next token
        
        Like the lexer's advance(), but for tokens instead of characters.
        """
        self.position += 1
        if self.position < len(self.tokens):
            self.current_token = self.tokens[self.position]
        else:
            self.current_token = None
    
    def expect(self, token_type):
        """
        Consume a token of expected type, or error
        
        This is used when we KNOW what token should come next.
        Example: After 'print', we MUST see '('
        
        Args:
            token_type: The TokenType we expect
        """
        if self.current_token is None:
            self.error(f"Expected {token_type.name}, but reached end of file")
        
        if self.current_token.type != token_type:
            self.error(f"Expected {token_type.name}, got {self.current_token.type.name}")
        
        token = self.current_token
        self.advance()
        return token
    
    # ========================================================================
    # GRAMMAR RULE METHODS
    # Each method corresponds to a grammar rule
    # ========================================================================
    
    def parse_program(self):
        """
        Parse the entire program
        
        Grammar: program → statement*
        
        Meaning: A program is zero or more statements
        """
        statements = []
        
        # Keep parsing statements until we hit EOF
        while self.current_token.type != TokenType.EOF:
            stmt = self.parse_statement()
            statements.append(stmt)
        
        return ProgramNode(statements)
    
    def parse_statement(self):
        """
        Parse a single statement
        
        Grammar: statement → assignment | print_stmt
        
        We look at the current token to decide which kind:
        - If it's 'print', parse a print statement
        - If it's an ID, parse an assignment
        """
        if self.current_token.type == TokenType.PRINT:
            return self.parse_print_statement()
        elif self.current_token.type == TokenType.ID:
            return self.parse_assignment()
        else:
            self.error(f"Expected statement, got {self.current_token.type.name}")
    
    def parse_assignment(self):
        """
        Parse an assignment statement
        
        Grammar: assignment → ID = expression ;
        
        Example: x = 5 + 3;
        
        Steps:
        1. Expect an identifier (variable name)
        2. Expect '='
        3. Parse the expression on the right
        4. Expect ';'
        """
        # Get variable name
        var_token = self.expect(TokenType.ID)
        var_name = var_token.value
        
        # Expect '='
        self.expect(TokenType.ASSIGN)
        
        # Parse the expression
        expr = self.parse_expression()
        
        # Expect ';'
        self.expect(TokenType.SEMICOLON)
        
        return AssignmentNode(var_name, expr)
    
    def parse_print_statement(self):
        """
        Parse a print statement
        
        Grammar: print_stmt → print ( expression ) ;
        
        Example: print(x + 5);
        
        Steps:
        1. Expect 'print' keyword
        2. Expect '('
        3. Parse the expression to print
        4. Expect ')'
        5. Expect ';'
        """
        # Expect 'print'
        self.expect(TokenType.PRINT)
        
        # Expect '('
        self.expect(TokenType.LPAREN)
        
        # Parse expression
        expr = self.parse_expression()
        
        # Expect ')'
        self.expect(TokenType.RPAREN)
        
        # Expect ';'
        self.expect(TokenType.SEMICOLON)
        
        return PrintNode(expr)
    
    def parse_expression(self):
        """
        Parse an expression (handles + and -)
        
        Grammar: expression → term ((+|-) term)*
        
        This handles left-to-right evaluation of + and -
        Example: 1 + 2 - 3 + 4
        
        The * means "zero or more", so we use a loop.
        
        Why this structure?
        - It gives + and - LOWER precedence than * and /
        - It makes operations left-associative: 1-2-3 = (1-2)-3, not 1-(2-3)
        """
        # Parse the first term
        node = self.parse_term()
        
        # Keep parsing + or - operations
        while self.current_token and self.current_token.type in (TokenType.PLUS, TokenType.MINUS):
            op_token = self.current_token
            self.advance()
            
            # Parse the next term
            right = self.parse_term()
            
            # Build binary operation node
            node = BinaryOpNode(op_token.value, node, right)
        
        return node
    
    def parse_term(self):
        """
        Parse a term (handles * and /)
        
        Grammar: term → factor ((*|/) factor)*
        
        This is similar to parse_expression, but for * and /
        
        Why separate from expression?
        - This gives * and / HIGHER precedence than + and -
        - Example: 2 + 3 * 4
          - parse_expression parses 2, then sees +
          - It calls parse_term for the right side
          - parse_term parses 3 * 4 as a unit
          - Result: 2 + (3 * 4) ✓
        """
        # Parse the first factor
        node = self.parse_factor()
        
        # Keep parsing * or / operations
        while self.current_token and self.current_token.type in (TokenType.MULTIPLY, TokenType.DIVIDE):
            op_token = self.current_token
            self.advance()
            
            # Parse the next factor
            right = self.parse_factor()
            
            # Build binary operation node
            node = BinaryOpNode(op_token.value, node, right)
        
        return node
    
    def parse_factor(self):
        """
        Parse a factor (basic unit of expression)
        
        Grammar: factor → NUMBER | ID | ( expression )
        
        A factor is:
        - A number: 42
        - A variable: x
        - A parenthesized expression: (2 + 3)
        
        Parentheses override precedence:
        - (2 + 3) * 4 → the addition happens first
        - When we see '(', we recursively call parse_expression
        """
        token = self.current_token
        
        if token.type == TokenType.NUMBER:
            self.advance()
            return NumberNode(token.value)
        
        elif token.type == TokenType.ID:
            self.advance()
            return VariableNode(token.value)
        
        elif token.type == TokenType.LPAREN:
            # Parenthesized expression
            self.advance()  # consume '('
            node = self.parse_expression()  # recursively parse expression
            self.expect(TokenType.RPAREN)   # expect ')'
            return node
        
        else:
            self.error(f"Expected number, variable, or '(', got {token.type.name}")
    
    def parse(self):
        """
        Main entry point for parsing
        
        Returns the root of the AST (a ProgramNode)
        """
        return self.parse_program()


def print_ast(node, indent=0):
    """
    Pretty-print the AST
    
    This shows the tree structure visually.
    Indentation shows depth in the tree.
    """
    prefix = "  " * indent
    
    if isinstance(node, ProgramNode):
        print(f"{prefix}Program:")
        for stmt in node.statements:
            print_ast(stmt, indent + 1)
    
    elif isinstance(node, AssignmentNode):
        print(f"{prefix}Assignment: {node.variable_name} =")
        print_ast(node.expression, indent + 1)
    
    elif isinstance(node, PrintNode):
        print(f"{prefix}Print:")
        print_ast(node.expression, indent + 1)
    
    elif isinstance(node, BinaryOpNode):
        print(f"{prefix}BinaryOp: {node.operator}")
        print(f"{prefix}  Left:")
        print_ast(node.left, indent + 2)
        print(f"{prefix}  Right:")
        print_ast(node.right, indent + 2)
    
    elif isinstance(node, NumberNode):
        print(f"{prefix}Number: {node.value}")
    
    elif isinstance(node, VariableNode):
        print(f"{prefix}Variable: {node.name}")


def demo_parser():
    """
    Demonstration of the parser
    """
    print("=" * 60)
    print("PHASE 2: PARSING (SYNTAX ANALYSIS) DEMO")
    print("=" * 60)
    
    # Sample program
    source_code = """
    x = 5;
    y = x + 10;
    print(y);
    """
    
    print("\n📝 Source Code:")
    print(source_code)
    
    # Tokenize
    print("\n🔤 Step 1: Tokenizing...")
    from lexer import Lexer
    lexer = Lexer(source_code)
    tokens = lexer.tokenize()
    print(f"   Generated {len(tokens)} tokens")
    
    # Parse
    print("\n🌳 Step 2: Parsing...")
    parser = Parser(tokens)
    ast = parser.parse()
    
    print("\n📊 Abstract Syntax Tree (AST):")
    print("-" * 60)
    print_ast(ast)
    
    print("\n✅ Parsing Complete!")
    print("\n💡 What happened?")
    print("   - Tokens were checked against grammar rules")
    print("   - An Abstract Syntax Tree (AST) was built")
    print("   - The tree shows program structure")
    print("   - Operator precedence is encoded in tree depth")
    print("   - Ready for semantic analysis!\n")


if __name__ == "__main__":
    demo_parser()