Projeto: um parser simples
LidoNesta aula, você construirá um parser simples em Rust, aprendendo a tokenizar uma string, gerenciar estado de parsing, usar enums para representar tokens e escrever testes. O projeto final é um interpretador de expressões aritméticas básicas.
Nesta aula, vamos colocar em prática vários conceitos de Rust que você já aprendeu, construindo um parser simples. Um parser é um programa que analisa uma sequência de caracteres (como uma string) e a transforma em uma estrutura de dados mais significativa, geralmente uma árvore ou uma lista de tokens. Nosso objetivo será criar um parser para expressões aritméticas simples, como 2 + 3 * (4 - 1). Vamos dividir o problema em etapas: primeiro, a tokenização (quebrar a string em tokens), depois o parsing propriamente dito (construir uma árvore de expressão), e por fim, a avaliação da expressão. Ao longo do caminho, vamos explorar enums, estruturas, gerenciamento de estado e testes.
Este projeto é fundamental para entender como linguagens de programação são implementadas. Ao final, você terá um interpretador funcional para expressões aritméticas com precedência de operadores e parênteses. Vamos começar!
Tokenização
A primeira etapa de qualquer parser é a tokenização (ou lexing). O tokenizador (lexer) lê a string de entrada caractere por caractere e agrupa caracteres em tokens, que são unidades significativas, como números, operadores e parênteses. Por exemplo, a string 2 + 3 deve ser quebrada em tokens: Number(2), Plus, Number(3).
Em Rust, podemos representar tokens usando um enum, onde cada variante representa um tipo de token. Para números, precisamos armazenar o valor; para operadores, apenas o tipo. Vamos definir nosso enum Token da seguinte forma:
#[derive(Debug, Clone, PartialEq)]
enum Token {
Number(i64),
Plus,
Minus,
Star,
Slash,
LParen,
RParen,
}O tokenizador percorre a string e produz um vetor de tokens. Para isso, precisamos lidar com espaços em branco (ignorar), números (que podem ter múltiplos dígitos) e caracteres de operadores e parênteses. Vamos implementar uma função tokenize que retorna um Result<Vec<Token>, String> para tratar erros, como caracteres inválidos.
Exemplo de implementação:
fn tokenize(input: &str) -> Result<Vec<Token>, String> {
let mut tokens = Vec::new();
let mut chars = input.chars().peekable();
while let Some(&c) = chars.peek() {
match c {
' ' | '\t' | '\n' => { chars.next(); }
'0'..='9' => {
let mut num = String::new();
while let Some(&c) = chars.peek() {
if c.is_ascii_digit() {
num.push(c);
chars.next();
} else {
break;
}
}
let n: i64 = num.parse().map_err(|e| format!("Erro ao parsear número: {}", e))?;
tokens.push(Token::Number(n));
}
'+' => { tokens.push(Token::Plus); chars.next(); }
'-' => { tokens.push(Token::Minus); chars.next(); }
'*' => { tokens.push(Token::Star); chars.next(); }
'/' => { tokens.push(Token::Slash); chars.next(); }
'(' => { tokens.push(Token::LParen); chars.next(); }
')' => { tokens.push(Token::RParen); chars.next(); }
_ => return Err(format!("Caractere inesperado: '{}'", c)),
}
}
Ok(tokens)
}Note que usamos peekable() para olhar o próximo caractere sem consumi-lo, o que é útil para números de múltiplos dígitos. Também tratamos erros de parseamento de número com map_err.
Estado
O parsing de expressões aritméticas requer gerenciamento de estado, pois precisamos saber em que ponto da sequência de tokens estamos. Uma abordagem comum é usar uma estrutura Parser que mantém os tokens e um índice para o token atual. Vamos criar:
struct Parser {
tokens: Vec<Token>,
pos: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Self {
Parser { tokens, pos: 0 }
}
fn peek(&self) -> Option<&Token> {
self.tokens.get(self.pos)
}
fn next(&mut self) -> Option<&Token> {
let token = self.tokens.get(self.pos);
if token.is_some() {
self.pos += 1;
}
token
}
fn expect(&mut self, token: &Token) -> Result<(), String> {
match self.next() {
Some(t) if t == token => Ok(()),
Some(t) => Err(format!("Esperava {:?}, encontrou {:?}", token, t)),
None => Err("Fim inesperado da entrada".to_string()),
}
}
}A estrutura Parser encapsula o estado do parsing: a lista de tokens e a posição atual. Os métodos peek, next e expect permitem avançar e verificar tokens de forma segura. Esse padrão é comum em parsers recursivos descendentes.
Para avaliar a expressão, precisamos de funções que reconheçam diferentes níveis de precedência. Por exemplo, em expressões aritméticas, multiplicação e divisão têm precedência maior que adição e subtração. Vamos implementar uma gramática simples:
expr->term(('+' | '-')term)*term->factor(('*' | '/')factor)*factor-> NUMBER | '('expr')'
Essa gramática define a precedência corretamente. Vamos implementar os métodos parse_expr, parse_term e parse_factor dentro de Parser.
Enums
Usamos enums para representar tokens, mas também podemos usar enums para representar a árvore de expressão (AST - Abstract Syntax Tree). Isso permite avaliar a expressão de forma recursiva. Vamos definir:
#[derive(Debug, Clone, PartialEq)]
enum Expr {
Number(i64),
Add(Box<Expr>, Box<Expr>),
Sub(Box<Expr>, Box<Expr>),
Mul(Box<Expr>, Box<Expr>),
Div(Box<Expr>, Box<Expr>),
}Usamos Box para alocar na heap, pois Expr é recursivo. Cada variante representa uma operação ou um número. A função eval pode ser implementada como um método ou função que combina padrões:
fn eval(expr: &Expr) -> i64 {
match expr {
Expr::Number(n) => *n,
Expr::Add(a, b) => eval(a) + eval(b),
Expr::Sub(a, b) => eval(a) - eval(b),
Expr::Mul(a, b) => eval(a) * eval(b),
Expr::Div(a, b) => eval(a) / eval(b),
}
}Os enums são poderosos em Rust para modelar dados que podem assumir diferentes formatos. Aqui, eles nos dão segurança de tipo e permitem que o compilador verifique se todos os casos são tratados.
Vamos agora implementar os métodos de parsing que constroem a AST. Por exemplo, parse_factor:
fn parse_factor(&mut self) -> Result<Expr, String> {
match self.next() {
Some(Token::Number(n)) => Ok(Expr::Number(*n)),
Some(Token::LParen) => {
let expr = self.parse_expr()?;
self.expect(&Token::RParen)?;
Ok(expr)
}
Some(token) => Err(format!("Token inesperado: {:?}", token)),
None => Err("Fim inesperado".to_string()),
}
}Note que usamos ? para propagar erros, tornando o código limpo.
Testes
Testar é essencial para garantir que nosso parser funciona. Em Rust, escrevemos testes com #[test] e rodamos com cargo test. Vamos escrever testes para a tokenização e para a avaliação de expressões.
Primeiro, um teste para tokenize:
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_tokenize_simple() {
let tokens = tokenize("2 + 3").unwrap();
assert_eq!(tokens, vec![
Token::Number(2),
Token::Plus,
Token::Number(3),
]);
}
#[test]
fn test_tokenize_with_parens() {
let tokens = tokenize("(1 - 2) * 3").unwrap();
assert_eq!(tokens, vec![
Token::LParen,
Token::Number(1),
Token::Minus,
Token::Number(2),
Token::RParen,
Token::Star,
Token::Number(3),
]);
}
#[test]
fn test_tokenize_invalid_char() {
let result = tokenize("2 + a");
assert!(result.is_err());
}
}Agora testes para o parser/avaliação:
#[test]
fn test_eval_simple() {
let tokens = tokenize("2 + 3").unwrap();
let mut parser = Parser::new(tokens);
let expr = parser.parse_expr().unwrap();
assert_eq!(eval(&expr), 5);
}
#[test]
fn test_eval_precedence() {
let tokens = tokenize("2 + 3 * 4").unwrap();
let mut parser = Parser::new(tokens);
let expr = parser.parse_expr().unwrap();
assert_eq!(eval(&expr), 14);
}
#[test]
fn test_eval_parens() {
let tokens = tokenize("(2 + 3) * 4").unwrap();
let mut parser = Parser::new(tokens);
let expr = parser.parse_expr().unwrap();
assert_eq!(eval(&expr), 20);
}Esses testes garantem que a precedência e os parênteses estão sendo tratados corretamente. Lembre-se de que, para rodar os testes, você precisa incluir a função parse_expr e os métodos auxiliares. Aqui está a implementação completa dos métodos de parsing:
impl Parser {
fn parse_expr(&mut self) -> Result<Expr, String> {
let mut left = self.parse_term()?;
while let Some(token) = self.peek() {
match token {
Token::Plus => {
self.next();
let right = self.parse_term()?;
left = Expr::Add(Box::new(left), Box::new(right));
}
Token::Minus => {
self.next();
let right = self.parse_term()?;
left = Expr::Sub(Box::new(left), Box::new(right));
}
_ => break,
}
}
Ok(left)
}
fn parse_term(&mut self) -> Result<Expr, String> {
let mut left = self.parse_factor()?;
while let Some(token) = self.peek() {
match token {
Token::Star => {
self.next();
let right = self.parse_factor()?;
left = Expr::Mul(Box::new(left), Box::new(right));
}
Token::Slash => {
self.next();
let right = self.parse_factor()?;
left = Expr::Div(Box::new(left), Box::new(right));
}
_ => break,
}
}
Ok(left)
}
}Boas práticas e observações finais
Ao construir um parser, é importante separar as etapas de tokenização e parsing. Isso facilita a manutenção e permite testar cada parte independentemente. Use enums para representar tokens e AST, pois eles tornam o código mais expressivo e seguro. Sempre trate erros de forma explícita, usando Result e ? para propagar.
Além disso, considere a possibilidade de estender o parser para suportar unários, potências, etc. Isso pode ser feito adicionando novas variantes ao enum e ajustando a gramática. Lembre-se de que a precedência é controlada pela estrutura das funções de parsing, então mudanças na gramática exigem ajustes nessas funções.
Por fim, escreva testes abrangentes para cobrir casos de borda, como divisão por zero (embora nosso parser não verifique isso) e entradas inválidas. Isso aumenta a confiança na correção do código.
Referências
- The Rust Programming Language - Enums
- The Rust Programming Language - State Patterns
- Rust by Example - Unit Testing
- Peekable - Rust Standard Library
- Crafting Interpreters - book
- Recursive Descent Parser - Wikipedia
Exercícios
- Adicione suporte para números negativos no tokenizador e no parser. Por exemplo,
-5 + 3deve ser avaliado como-2. Dica: trate o sinal de menos unário no fator. - Implemente a operação de módulo (
%). Adicione o tokenPercente o tratamento no parser e na avaliação. - Escreva um teste que verifique que uma expressão com divisão por zero retorna um erro (ou use
panic). Como você lidaria com isso? - Estenda o parser para suportar variáveis simples (ex.:
x = 5; x + 2). Você precisará de um mapa de variáveis. Isso é mais complexo, mas tente implementar uma versão básica. - Refatore o código para usar
thiserrorouanyhowpara tratamento de erros. Mostre como você faria isso.
parse_factor, se o token atual for Minus, consuma-o e retorne Expr::Neg (adicionando uma variante ao enum). Exemplo:
fn parse_factor(&mut self) -> Result<Expr, String> {
// ...
Some(Token::Minus) => {
self.next();
let expr = self.parse_factor()?;
Ok(Expr::Neg(Box::new(expr)))
}
// ...
}Neg(Box<Expr>) ao enum e trate na avaliação: Expr::Neg(e) => -eval(e).
Percent ao enum Token, trate o caractere % no tokenizador. No parser, adicione o tratamento no parse_term (mesma precedência de * e /) e crie a variante Expr::Mod. Na avaliação, use %.
eval para retornar Result<i64, String> e verificar se o divisor é zero. Exemplo: Expr::Div(a, b) => { let divisor = eval(b)?; if divisor == 0 { Err("Divisão por zero".to_string()) } else { Ok(eval(a)? / divisor) } }. Escreva um teste que chama eval e espera um erro.
Ident(String) e um token Assign. No parser, crie uma função parse_statement que reconhece uma atribuição e armazena em um HashMap<String, i64>. Para avaliação, Expr::Var(String) consulta o mapa. Isso envolve modificar o tokenizador, o enum de tokens, o parser e a avaliação. Exemplo simples: let mut vars = HashMap::new(); e passe para eval.
thiserror como dependência. Defina um enum de erro customizado:
#[derive(Debug, Error)]
enum ParseError {
#[error("caractere inesperado: {0}")]
UnexpectedChar(char),
#[error("erro de parse: {0}")]
Parse(String),
#[error("erro de avaliação: {0}")]
Eval(String),
}Result<_, ParseError> e use ? para converter erros com From. Isso centraliza o tratamento de erros.
Continue lendo
Mais artigos de Rust para seguir daqui.
Projeto: ferramenta de linha de comando
Nesta aula, você construirá uma ferramenta de linha de comando em Rust, aprendendo a estruturar o projeto, usar a crate clap para parsing de argumentos, ler arquivos e formatar a saída. O objetivo é consolidar os conceitos em um projeto prático e reutilizável.
Lido
Rust e WebAssembly (introdução)
Esta aula apresenta uma introdução ao WebAssembly (WASM) e seu uso com Rust. Você aprenderá o que é WASM, como usar a ferramenta wasm-bindgen para criar módulos WASM a partir de Rust, casos de uso práticos e limitações importantes. Ao final, terá uma base sólida para começar a escrever aplicações web de alto desempenho com Rust.
Lido
Streams
Nesta aula, exploramos o trait Stream da biblioteca padrão do Rust, que permite processar sequências assíncronas de valores. Aprendemos a usar adaptadores como map, filter e take, e consumidores como next e collect, além de discutir casos de uso práticos para streams em aplicações assíncronas.
Lido