Choosing a Parsing Algorithm for Rust Interpreter

Mục tiêu: Selecting the appropriate parsing algorithm for a Rust interpreter, focusing on recursive descent and shift-reduce parsing methods.

Choosing a Parsing Algorithm for Your Rust Interpreter

When building a parser for your interpreter, selecting the right parsing algorithm is crucial. In this case, we’re considering two popular approaches: recursive descent and shift-reduce parsing. Each has its strengths and weaknesses, and the choice depends on your grammar’s complexity and your comfort with the implementation.

Recursive Descent Parsing

Recursive descent is a top-down parsing strategy that works well for predictable grammars. It’s particularly suitable for this project because:

Ease of Implementation: Recursive descent parsers are typically written by hand, making them easier to implement and debug, especially for developers familiar with the grammar.
Maintainability: The code tends to be straightforward and easy to extend as the language evolves.
Grammar Suitability: It works well with grammars that are mostly free of left recursion and have clear operator precedence.

Here’s a basic outline of how a recursive descent parser works:

Tokenize Input: The lexer generates a stream of tokens.
Parse Functions: Each non-terminal in the grammar is implemented as a function that parses its corresponding production rules.
Recursive Calls: Functions call each other recursively to build the abstract syntax tree (AST).

Shift-Reduce Parsing

Shift-reduce parsing is a bottom-up approach that uses a stack to parse the input. While more powerful than recursive descent, it’s generally more complex to implement manually. However, it’s better suited for more complex grammars and can handle left recursion naturally.

Recommendation for This Project

Given the scope of your interpreter project, recursive descent parsing is the recommended approach. It aligns well with the simplicity of your language’s grammar and will be easier to implement and debug, especially if you’re relatively new to parser implementation.

How Recursive Descent Parsing Works

Let’s break down the process:

Lexer: The lexer takes the source code and produces a stream of tokens.
Parser: The parser consumes these tokens and builds an AST using recursive functions.
AST Construction: Each parsing function corresponds to a grammar rule and constructs the appropriate AST nodes.

Example Implementation in Rust

Here’s a simplified example of how you might structure your parser:

// Token types
enum Token {
    Number(i32),
    Plus,
    Minus,
    Times,
    Divide,
    LParen,
    RParen,
    Identifier(String),
    Keyword(Keyword),
    Eof,
}

// Keyword variants
enum Keyword {
    Let,
    Fn,
    If,
    Else,
    Loop,
    // Add more keywords as needed
}

// AST node types
enum AstNode {
    Number(i32),
    Identifier(String),
    BinaryOp {
        op: BinaryOperator,
        left: Box<AstNode>,
        right: Box<AstNode>,
    },
    // Add more node types as needed
}

// Parser implementation
struct Parser {
    tokens: Vec<Token>,
    current_pos: usize,
}

impl Parser {
    fn new(tokens: Vec<Token>) -> Self {
        Self {
            tokens,
            current_pos: 0,
        }
    }

    // Main entry point for parsing
    fn parse(&mut self) -> AstNode {
        self.parse_expression()
    }

    // Function to parse expressions
    fn parse_expression(&mut self) -> AstNode {
        let left = self.parse_term();
        while self.current_token_is_plus_or_minus() {
            let op = self.parse_operator();
            let right = self.parse_term();
            left = AstNode::BinaryOp {
                op,
                left: Box::new(left),
                right: Box::new(right),
            };
        }
        left
    }

    // Helper functions for specific grammar rules
    fn parse_term(&mut self) -> AstNode {
        // Implementation for terms (e.g., factors and multiplication/division)
        unimplemented!()
    }

    fn parse_operator(&mut self) -> BinaryOperator {
        // Implementation for operator parsing
        unimplemented!()
    }

    // Helper to check current token
    fn current_token_is_plus_or_minus(&self) -> bool {
        matches!(self.tokens[self.current_pos], Token::Plus | Token::Minus)
    }
}

Next Steps

After selecting the recursive descent approach:

Implement Parser Functions: Write functions for each grammar rule, starting with the simplest elements and moving to more complex structures.
Handle Operator Precedence: Ensure your parser respects the operator precedence rules defined in your language’s grammar.
Construct AST Nodes: Each parsing function should return an AST node that represents the parsed construct.

Implementing Recursive Descent Parser in Rust

Mục tiêu: Creating parser functions for each grammar rule to construct an Abstract Syntax Tree (AST) using recursive descent parsing in Rust.

Implementing Parser Functions for Each Grammar Rule in Rust

Now that we have our lexer in place, the next step is to implement the parser. The parser will take the tokens produced by the lexer and construct an Abstract Syntax Tree (AST) based on our language’s grammar rules. In this task, we’ll focus on implementing parser functions for each grammar rule.

Understanding Recursive Descent Parsing

Recursive descent parsing is a popular method for implementing parsers by hand. It works by creating a function for each grammar rule in our language. Each function will attempt to match the corresponding rule by recursively calling other functions that represent the non-terminal symbols in the grammar.

Parser Functions Structure

For each grammar rule, we’ll create a corresponding function in our parser. Let’s outline the main functions we’ll need:

parse_expression(): Handles expressions, including arithmetic operations
parse_statement(): Handles statements like variable declarations and assignments
parse_variable(): Parses variable references and assignments
parse_factor(): Handles basic elements like numbers and identifiers
parse_term(): Handles multiplication and division operations
parse_additive_expression(): Handles addition and subtraction operations

Implementing Parser Functions

Let’s start with the most basic function and work our way up.

// Parser implementation
pub struct Parser {
    tokens: Vec<Token>,
    current_token: usize,
}

impl Parser {
    pub fn new(tokens: Vec<Token>) -> Self {
        Self {
            tokens,
            current_token: 0,
        }
    }

    // Helper method to get the next token
    fn next_token(&mut self) -> Token {
        let token = self.tokens[self.current_token].clone();
        self.current_token += 1;
        token
    }

    // Helper method to peek at the next token without consuming it
    fn peek_token(&self) -> &Token {
        &self.tokens[self.current_token]
    }

    // Start symbol: parses the entire input
    pub fn parse(&mut self) -> ASTNode {
        self.parse_statement()
    }

    // Parses a statement (e.g., variable declaration or assignment)
    fn parse_statement(&mut self) -> ASTNode {
        let token = self.peek_token();
        if token.kind == TokenKind::Let {
            self.next_token(); // Consume 'let'
            let ident = self.parse_variable();
            let expr = self.parse_expression();
            return ASTNode::Let {
                ident,
                expr: Box::new(expr),
            };
        } else {
            panic!("Expected statement");
        }
    }

    // Parses an expression (e.g., arithmetic operations)
    fn parse_expression(&mut self) -> ASTNode {
        let mut node = self.parse_additive_expression();

        while let TokenKind::Operator(ref op) = self.peek_token().kind {
            if op == "+" || op == "-" {
                self.next_token(); // Consume operator
                let right = self.parse_additive_expression();
                node = ASTNode::BinaryOperation {
                    op: op.clone(),
                    left: Box::new(node),
                    right: Box::new(right),
                };
            } else {
                break;
            }
        }

        node
    }

    // Parses additive expressions (addition and subtraction)
    fn parse_additive_expression(&mut self) -> ASTNode {
        let mut node = self.parse_multiplicative_expression();

        while let TokenKind::Operator(ref op) = self.peek_token().kind {
            if op == "*" || op == "/" {
                self.next_token(); // Consume operator
                let right = self.parse_multiplicative_expression();
                node = ASTNode::BinaryOperation {
                    op: op.clone(),
                    left: Box::new(node),
                    right: Box::new(right),
                };
            } else {
                break;
            }
        }

        node
    }

    // Parses multiplicative expressions (multiplication and division)
    fn parse_multiplicative_expression(&mut self) -> ASTNode {
        let node = self.parse_factor();

        if let TokenKind::Operator(ref op) = self.peek_token().kind {
            if op == "^" {
                self.next_token(); // Consume operator
                let right = self.parse_factor();
                return ASTNode::BinaryOperation {
                    op: op.clone(),
                    left: Box::new(node),
                    right: Box::new(right),
                };
            }
        }

        node
    }

    // Parses basic elements (identifiers and numbers)
    fn parse_factor(&mut self) -> ASTNode {
        let token = self.next_token();
        match token.kind {
            TokenKind::Identifier(ref ident) => {
                ASTNode::Variable(Variable {
                    ident: ident.clone(),
                })
            },
            TokenKind::Number(ref num) => {
                ASTNode::Number(num.clone())
            },
            _ => panic!("Unexpected token in factor: {:?}", token),
        }
    }

    // Parses variable declarations/assignments
    fn parse_variable(&mut self) -> Variable {
        let token = self.next_token();
        match token.kind {
            TokenKind::Identifier(ref ident) => Variable {
                ident: ident.clone(),
            },
            _ => panic!("Expected identifier"),
        }
    }
}

Explanation of the Code

Parser Structure: The Parser struct holds the tokens and the current position in the token stream.
Helper Methods: next_token() consumes the next token, while peek_token() allows us to look at the next token without consuming it.
Start Symbol: The parse() method is our entry point, which starts parsing from the top-level statement.
Statement Parsing: The parse_statement() function handles variable declarations and assignments.
Expression Parsing: The parse_expression(), parse_additive_expression(), and parse_multiplicative_expression() functions handle arithmetic operations, respecting operator precedence and associativity.
Factor Parsing: The parse_factor() function handles basic elements like numbers and identifiers.
Variable Parsing: The parse_variable() function specifically handles variable declarations and assignments.

Handling Operator Precedence

Operator precedence is naturally handled by the structure of our functions:

Multiplication and division (*//) have higher precedence than addition and subtraction (+/-).
The functions are nested accordingly, with parse_multiplicative_expression() called from parse_additive_expression(), which is in turn called from parse_expression().

Error Handling

For now, we’re using panic! statements for error handling. In a real-world implementation, you’d want to implement proper error recovery mechanisms.

Next Steps

Implement Remaining Functions: Continue implementing parser functions for all grammar rules in your language.
Test with Sample Inputs: Write test cases with different valid and invalid programs to verify your parser works correctly.
Implement Error Recovery: Replace panic! statements with proper error handling that provides useful messages to the user.

Implementing AST Nodes for a Rust Interpreter

Mục tiêu: Define and construct Abstract Syntax Tree (AST) nodes for a Rust interpreter, covering literals, operations, control flow, and functions.

Implementing the Abstract Syntax Tree (AST) Nodes for Your Rust Interpreter

The Abstract Syntax Tree (AST) is a fundamental component of any interpreter or compiler. It represents the source code in a structured, tree-like format that is easier to analyze and execute. In this task, we will focus on constructing the AST nodes for different language constructs based on the tokens produced by the lexer.

Step-by-Step Guide to Constructing AST Nodes

Define the AST Node Types

The first step is to define the different types of AST nodes that correspond to the language constructs. These nodes should cover all the possible expressions, statements, and declarations in your language.

// Define the AST node types
#[derive(Debug)]
pub enum AstNode {
// Literal values
Integer(i32),
Boolean(bool),
Identifier(String),

// Binary operations BinaryOp { op: Token, left: Box, right: Box, },

// Unary operations UnaryOp { op: Token, expr: Box, },

// Variable declaration VarDecl { name: String, value: Box, },

// If-else statement IfStmt { condition: Box, then_branch: Box, else_branch: Option<Box>, },

// While loop WhileStmt { condition: Box, body: Box, },

// Function declaration FnDecl { name: String, params: Vec, body: Box, },

Each node type corresponds to a specific construct in your language. For example:

Integer and Boolean nodes represent literal values.
BinaryOp represents binary operations like addition, subtraction, etc.
VarDecl represents variable declarations.
IfStmt and WhileStmt represent control flow statements.
FnDecl represents function declarations.

Constructing AST Nodes from Tokens

The parser will take the tokens produced by the lexer and construct the corresponding AST nodes. This involves writing parser functions that recognize patterns in the token stream and build the appropriate tree structure.

For example, when the parser encounters an if keyword followed by a condition and a statement, it will create an IfStmt node:

// Example of constructing an IfStmt node
pub fn parse\_if\_stmt(&mut self) -> AstNode {
// Consume the 'if' keyword
self.consume(TokenType::If);

// Parse the condition let condition = self.parse_expression();

// Parse the then branch let then_branch = self.parse_statement();

// Check for else branch let else_branch = if self.current_token_type() == TokenType::Else { self.consume(TokenType::Else); Some(self.parse_statement()) } else { None };

AstNode::IfStmt { condition: Box::new(condition), then_branch: Box::new(then_branch), else_branch, }

Handling Operator Precedence and Associativity

Operator precedence and associativity are crucial for correctly parsing arithmetic and logical expressions. For example, multiplication should have higher precedence than addition.

To handle this, you can use a recursive descent approach where different functions handle different precedence levels. For example:

parse_expression(): Handles the lowest precedence operators (e.g., assignment).
parse_additive(): Handles addition and subtraction.
parse_multiplicative(): Handles multiplication and division.

Each function will construct the appropriate BinaryOp nodes based on the operator precedence.

// Recursive descent functions for expressions
pub fn parse\_expression(&mut self) -> AstNode {
let node = self.parse\_additive();

// Handle assignment if applicable if self.current_token_type() == TokenType::Assign { self.consume(TokenType::Assign); let value = self.parse_expression(); return AstNode::BinaryOp { op: Token::new(TokenType::Assign, self.current_token().value.clone()), left: Box::new(node), right: Box::new(value), }; }

node

}

pub fn parse\_additive(&mut self) -> AstNode {
let node = self.parse\_multiplicative();

while self.current_token_type() == TokenType::Plus || self.current_token_type() == TokenType::Minus { let op = self.consume_token(); let right = self.parse_multiplicative();

   node = AstNode::BinaryOp {
       op,
       left: Box::new(node),
       right: Box::new(right),
   };    }

node

}

pub fn parse\_multiplicative(&mut self) -> AstNode {
let node = self.parse\_unary();

while self.current_token_type() == TokenType::Multiply || self.current_token_type() == TokenType::Divide { let op = self.consume_token(); let right = self.parse_unary();

   node = AstNode::BinaryOp {
       op,
       left: Box::new(node),
       right: Box::new(right),
   };    }

node

Error Handling

Error handling is crucial for a robust parser. You should implement error recovery mechanisms to handle syntax errors gracefully. For example, when an unexpected token is encountered, the parser can skip tokens until it finds a synchronizing token (e.g., a semicolon or a closing brace).

rust // Error handling example pub fn parse(&mut self) -> Result<AstNode, ParseError> { match self.parse_expression() { Ok(node) => Ok(node), Err(e) => { // Implement error recovery self.error_recovery(); Err(e) } } }

Testing the AST Construction

Once you have implemented the AST node construction, you should test it with various input programs to ensure that the parser correctly builds the expected tree structure.

For example, consider the input:

plaintext if x > 5 then y = 10 else y = 0

The parser should construct an IfStmt node with the condition x > 5, the then branch y = 10, and the else branch y = 0.

Next Steps

After completing the AST node construction, the next steps in your project will involve:

Implementing the Parser Functions: You will need to write parser functions for each grammar rule in your language specification.
Handling Operator Precedence: Ensure that the parser correctly handles operator precedence and associativity.
Implementing Error Recovery: Make the parser robust by adding error recovery mechanisms.
Validating Semantic Correctness: Add checks for semantic correctness, such as variable declarations and type checking.

Handle Operator Precedence and Associativity in Rust Interpreter Parser

Mục tiêu: Implement operator precedence and associativity in a recursive descent parser for a Rust interpreter.

To handle operator precedence and associativity in the parser for your Rust interpreter, follow these steps:

Define Operator Precedence Levels: Assign each operator a precedence value. Higher values indicate higher precedence.
Update Lexer to Include Precedence: Modify the lexer to attach precedence information to each operator token.
Implement Recursive Descent Parser Functions:
- Expression Function: Handles lower precedence operators (+, -).
- Term Function: Handles higher precedence operators (*, /).
- Factor Function: Handles literals, identifiers, and parentheses.
Build AST Nodes: Each function creates AST nodes reflecting the operator precedence and associativity.
Test with Sample Expressions: Verify correct parsing by testing expressions that require proper precedence and associativity handling.

Here’s how to implement this in code:

// Define the operator precedence levels
#[derive(Debug, PartialEq, Eq)]
pub enum Operator {
    Add,
    Sub,
    Mul,
    Div,
    // Add more operators as needed
}

impl Operator {
    pub fn precedence(&self) -> usize {
        match self {
            Operator::Add | Operator::Sub => 1,
            Operator::Mul | Operator::Div => 2,
        }
    }
}

// Example of a token with precedence
pub struct Token {
    pub kind: TokenKind,
    pub lexeme: String,
    pub line: usize,
    pub column: usize,
    pub op_precedence: Option<usize>,
}

// In the lexer, assign precedence when creating operator tokens
fn lex_operator(&mut self, c: char) -> Token {
    match c {
        '+' => Token {
            kind: TokenKind::Operator(Operator::Add),
            lexeme: c.to_string(),
            line: self.line,
            column: self.column,
            op_precedence: Some(Operator::Add.precedence()),
        },
        '-' => Token {
            kind: TokenKind::Operator(Operator::Sub),
            lexeme: c.to_string(),
            line: self.line,
            column: self.column,
            op_precedence: Some(Operator::Sub.precedence()),
        },
        '*' => Token {
            kind: TokenKind::Operator(Operator::Mul),
            lexeme: c.to_string(),
            line: self.line,
            column: self.column,
            op_precedence: Some(Operator::Mul.precedence()),
        },
        '/' => Token {
            kind: TokenKind::Operator(Operator::Div),
            lexeme: c.to_string(),
            line: self.line,
            column: self.column,
            op_precedence: Some(Operator::Div.precedence()),
        },
        _ => panic!("Unexpected operator: {}", c),
    }
}

// In the parser, each function handles its precedence level
pub struct Parser {
    tokens: Vec<Token>,
    current: usize,
}

impl Parser {
    pub fn new(tokens: Vec<Token>) -> Self {
        Self { tokens, current: 0 }
    }

    // Expression handles addition and subtraction (lower precedence)
    pub fn expression(&mut self) -> ASTNode {
        let mut node = self.term();

        while self.current < self.tokens.len() {
            let token = &self.tokens[self.current];
            if let TokenKind::Operator(op) = &token.kind {
                let precedence = op.precedence();
                if precedence == 1 { // Lower precedence (+, -)
                    self.current += 1;
                    let right = self.term();
                    node = ASTNode::Binary {
                        op: op.clone(),
                        left: Box::new(node),
                        right: Box::new(right),
                    };
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        node
    }

    // Term handles multiplication and division (higher precedence)
    pub fn term(&mut self) -> ASTNode {
        let mut node = self.factor();

        while self.current < self.tokens.len() {
            let token = &self.tokens[self.current];
            if let TokenKind::Operator(op) = &token.kind {
                let precedence = op.precedence();
                if precedence == 2 { // Higher precedence (*, /)
                    self.current += 1;
                    let right = self.factor();
                    node = ASTNode::Binary {
                        op: op.clone(),
                        left: Box::new(node),
                        right: Box::new(right),
                    };
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        node
    }

    // Factor handles literals, identifiers, and parentheses
    pub fn factor(&mut self) -> ASTNode {
        let token = &self.tokens[self.current];
        self.current += 1;

        match &token.kind {
            TokenKind::Literal(literal) => ASTNode::Literal(literal.clone()),
            TokenKind::Identifier(ident) => ASTNode::Identifier(ident.clone()),
            TokenKind::LParen => {
                let node = self.expression();
                if self.current >= self.tokens.len() || 
                   &self.tokens[self.current].kind != TokenKind::RParen {
                    // Handle error: missing closing parenthesis
                }
                self.current += 1;
                node
            },
            _ => {
                // Handle unexpected token error
                panic!("Unexpected token in factor: {:?}", token);
            }
        }
    }
}

Explanation:

Operator Precedence: Defined using an Operator enum with a precedence method.
Lexer Modification: Each operator token includes its precedence level.
Recursive Descent Parser: Structured into expression, term, and factor functions, each handling different precedence levels.
AST Construction: Each function builds binary nodes correctly, respecting operator precedence and associativity.

Testing:

Test expressions like 3 + 5 * 2 to ensure it’s parsed as 3 + (5 * 2).
Test left-associative operators with 10 - 5 - 3 to ensure it’s parsed as (10 - 5) - 3.

Further Reading:

By structuring your parser functions according to operator precedence and associativity, you ensure that expressions are parsed correctly, maintaining the expected evaluation order.

Implementing Error Recovery for Syntax Errors in Rust Parser

Mục tiêu: Enhancing a Rust parser with error recovery mechanisms to handle syntax errors gracefully, allowing continued processing after errors.

Implementing Error Recovery for Syntax Errors in Rust Parser

Error recovery in a parser is a critical component that determines how gracefully your interpreter handles syntax errors. A good error recovery mechanism not only reports errors but also allows the parser to continue processing the input to find additional issues, rather than halting at the first error encountered.

Understanding Error Recovery

Error recovery strategies vary in complexity:

Panic Mode Recovery: The simplest strategy where the parser skips tokens until it finds a synchronization point (like a semicolon or a keyword).
Phrase-Level Recovery: Attempts to correct the parser’s state based on expected tokens.
Contextual Recovery: More sophisticated approaches that use context-sensitive information to recover.

For this project, we’ll implement a combination of panic mode and phrase-level recovery strategies.

Modifying the Lexer for Better Error Reporting

First, let’s enhance our lexer to include line and column information in tokens. This will help in providing more accurate error messages.

// Token types with line and column information
#[derive(Debug)]
pub struct Token {
    pub kind: TokenKind,
    pub lexeme: String,
    pub line: usize,
    pub column: usize,
}

// Enhanced lexer error handling
pub enum LexerError {
    InvalidCharacter(char, usize, usize),
    UnexpectedEOF,
}

impl std::error::Error for LexerError {}

Creating a Custom Error Type

We’ll define a custom error type using the thiserror crate to handle both lexical and syntactic errors:

use thiserror::Error;

#[derive(Debug, Error)]
pub enum ParserError {
    #[error("Syntax error at line {line}, column {column}: {message}")]
    Syntax {
        line: usize,
        column: usize,
        message: String,
    },
    #[error("Lexer error: {0}")]
    Lexer(#[from] LexerError),
}

Implementing Error Recovery in the Parser

Let’s modify our parser to include error recovery. We’ll add an error handling mechanism that attempts to synchronize the parser after an error occurs.

pub struct Parser {
    tokens: Vec<Token>,
    current: usize,
    errors: Vec<ParserError>,
}

impl Parser {
    // Initialize parser with tokens
    pub fn new(tokens: Vec<Token>) -> Self {
        Self {
            tokens,
            current: 0,
            errors: Vec::new(),
        }
    }

    // Error recovery function
    fn recover(&mut self) {
        // Simple recovery: skip tokens until we find a synchronization point
        while self.current < self.tokens.len() {
            let token = &self.tokens[self.current];
            if token.kind == TokenKind::Semicolon || token.kind == TokenKind::Keyword(Keyword::If) {
                break;
            }
            self.current += 1;
        }
    }

    // Example of a parsing function with error handling
    pub fn parse(&mut self) -> Result<AST, ParserError> {
        let mut ast = AST::new();

        while self.current < self.tokens.len() {
            match self.parse_statement() {
                Ok(statement) => ast.statements.push(statement),
                Err(e) => {
                    self.errors.push(e);
                    self.recover();
                }
            }
        }

        Ok(ast)
    }

    // Example parsing function
    fn parse_statement(&mut self) -> Result<Statement, ParserError> {
        let token = self.tokens[self.current];
        if token.kind == TokenKind::Keyword(Keyword::Let) {
            // Variable declaration
            self.current += 1;
            let ident = self.expect_identifier()?;
            self.expect_token(TokenKind::Assign)?;
            let expr = self.parse_expression()?;
            self.expect_token(TokenKind::Semicolon)?;
            Ok(Statement::Let { ident, expr })
        } else {
            Err(ParserError::Syntax {
                line: token.line,
                column: token.column,
                message: "Unexpected token".to_string(),
            })
        }
    }

    fn expect_identifier(&mut self) -> Result<String, ParserError> {
        let token = self.tokens[self.current];
        if token.kind == TokenKind::Identifier {
            self.current += 1;
            Ok(token.lexeme)
        } else {
            Err(ParserError::Syntax {
                line: token.line,
                column: token.column,
                message: "Expected identifier".to_string(),
            })
        }
    }

    fn expect_token(&mut self, expected: TokenKind) -> Result<(), ParserError> {
        if self.current >= self.tokens.len() {
            return Err(ParserError::Syntax {
                line: self.tokens[self.current-1].line,
                column: self.tokens[self.current-1].column,
                message: "Unexpected end of file".to_string(),
            });
        }

        let token = &self.tokens[self.current];
        if token.kind == expected {
            self.current += 1;
            Ok(())
        } else {
            Err(ParserError::Syntax {
                line: token.line,
                column: token.column,
                message: format!("Expected {:?}, found {:?}", expected, token.kind),
            })
        }
    }
}

Error Handling in Action

Here’s an example of how the parser would handle a syntax error:

// Example source code with syntax error
let source = "
let x = 5
if x > 10
  println!(\"x is big\");
";

// Token stream
let tokens = vec![
    Token { kind: TokenKind::Let, lexeme: "let".to_string(), line: 1, column: 0 },
    Token { kind: TokenKind::Identifier, lexeme: "x".to_string(), line: 1, column: 4 },
    Token { kind: TokenKind::Assign, lexeme: "=".to_string(), line: 1, column: 6 },
    Token { kind: TokenKind::Number(5), lexeme: "5".to_string(), line: 1, column: 8 },
    Token { kind: TokenKind::Semicolon, lexeme: ";".to_string(), line: 1, column: 9 },
    Token { kind: TokenKind::If, lexeme: "if".to_string(), line: 2, column: 0 },
    Token { kind: TokenKind::Identifier, lexeme: "x".to_string(), line: 2, column: 3 },
    Token { kind: TokenKind::Greater, lexeme: ">".to_string(), line: 2, column: 5 },
    Token { kind: TokenKind::Number(10), lexeme: "10".to_string(), line: 2, column: 7 },
    // Missing semicolon after if condition
    Token { kind: TokenKind::String("x is big"), lexeme: "\"x is big\"".to_string(), line: 3, column: 0 },
];

// Parsing with error recovery
let mut parser = Parser::new(tokens);
match parser.parse() {
    Ok(ast) => println!("Parsed AST: {:?}", ast),
    Err(e) => eprintln!("Parsing error: {:?}", e),
}

Next Steps

Integrate Error Reporting: Modify the lexer to report detailed error information, including line and column numbers.
Enhance Error Messages: Provide more context in error messages, such as showing the surrounding code where the error occurred.
Implement Synchronization Points: Define specific points in the grammar where the parser can safely resume parsing after an error.

Implementing Semantic Validation for Variable Declarations in Rust Parser

Mục tiêu: This task involves adding semantic validation to a Rust parser to ensure correct variable declarations and usage. It includes maintaining a symbol table, managing scopes, and validating variable declarations and usage.

Adding Semantic Validation for Variable Declarations in Rust Parser

Semantic validation is a crucial part of the parsing process that ensures the correctness of the program’s meaning. While syntax deals with the form of the code, semantics deals with the meaning. In this task, we’ll focus on validating variable declarations to ensure they’re used correctly according to the language’s rules.

Key Aspects of Semantic Validation

Variable Declaration Before Use:
A variable must be declared before it’s used in the code.
This prevents references to undefined variables.
Variable Shadowing:
If a variable is declared in an inner scope with the same name as an outer scope variable, it should be allowed or handled according to language rules.
Scope Management:
Variables should be valid only within their declared scope.
This requires maintaining a symbol table that tracks variable declarations in different scopes.

Implementing Semantic Validation

To implement semantic validation, we’ll need to:

Maintain a Symbol Table:
A symbol table keeps track of declared variables in the current scope.
We’ll use a HashMap to store variable names and their associated information.
Scope Management:
We’ll implement a stack-based approach to manage scopes.
When entering a new block (e.g., if statement, loop), push a new scope onto the stack.
When exiting a block, pop the scope from the stack.
Validation Functions:
For each variable declaration, check if it’s already declared in the current scope.
For each variable use, check if it’s declared in any of the active scopes.

Code Implementation

Here’s how we can implement this in Rust:

// Define a structure to represent variable information
struct Variable {
    name: String,
    data_type: String,
    line: usize,
    column: usize,
}

// Define a structure for the symbol table
struct SymbolTable {
    scopes: Vec<HashMap<String, Variable>>,
}

impl SymbolTable {
    fn new() -> Self {
        SymbolTable {
            scopes: vec![HashMap::new()],
        }
    }

    // Enter a new scope
    fn enter_scope(&mut self) {
        self.scopes.push(HashMap::new());
    }

    // Exit the current scope
    fn exit_scope(&mut self) {
        self.scopes.pop();
    }

    // Declare a variable in the current scope
    fn declare_variable(&mut self, variable: Variable) -> Result<(), String> {
        let current_scope = self.scopes.last_mut().unwrap();

        if current_scope.contains_key(&variable.name) {
            return Err(format!("Variable {} redeclared in the same scope", variable.name));
        }

        current_scope.insert(variable.name.clone(), variable);
        Ok(())
    }

    // Check if a variable is declared in any active scope
    fn is_variable_declared(&self, name: &str) -> bool {
        for scope in &self.scopes {
            if scope.contains_key(name) {
                return true;
            }
        }
        false
    }
}

// Example usage in the parser
fn parse_variable_declaration(tokens: &mut Vec<Token>) -> Result<ASTNode, String> {
    // Assuming we have a token for 'let' keyword
    let let_token = tokens.next().unwrap();

    // Parse variable name
    let var_name_token = tokens.next().unwrap();
    let var_name = var_name_token.value.clone();

    // Parse type annotation if any
    // ... (simplified for example)

    // Create a Variable struct
    let variable = Variable {
        name: var_name.clone(),
        data_type: "i32".to_string(), // Default for example
        line: var_name_token.line,
        column: var_name_token.column,
    };

    // Perform semantic check
    let mut symbol_table = SymbolTable::new();
    match symbol_table.declare_variable(variable) {
        Ok(_) => {
            // Create and return AST node
            Ok(ASTNode::VariableDeclaration(variable))
        }
        Err(e) => Err(e),
    }
}

// Example of checking variable usage
fn parse_identifier(tokens: &mut Vec<Token>) -> Result<ASTNode, String> {
    let ident_token = tokens.next().unwrap();
    let ident_name = ident_token.value.clone();

    // Check if variable is declared
    let symbol_table = SymbolTable::new();
    if symbol_table.is_variable_declared(&ident_name) {
        Ok(ASTNode::Identifier(ident_name))
    } else {
        Err(format!("Undefined variable {} at line {}", ident_name, ident_token.line))
    }
}

Explanation

Symbol Table Management:
The SymbolTable struct maintains a stack of scopes.
Each scope is a HashMap that maps variable names to their information.
Scope Operations:
enter_scope(): Creates a new scope for blocks like if statements or loops.
exit_scope(): Removes the current scope when exiting a block.
Variable Declaration:
When declaring a variable, we check if it’s already declared in the current scope.
If it is, we return an error indicating redeclaration.
Variable Usage:
When using a variable (identifier), we check all active scopes to see if it’s declared.
If not found, we return an error indicating an undefined variable.

Next Steps

Handle Different Data Types:
Extend the Variable struct to support different data types.
Modify the parser to handle type annotations.
Function Support:
Add support for function declarations and their parameters.
Track function signatures in the symbol table.
Control Flow Handling:
Implement scope management for control flow structures like if statements and loops.
Ensure that variables declared in these structures are properly scoped.