commit ebe3a0a72c98c733977195ad2a30c57189ce8701 from: Murilo Ijanc date: Fri Oct 10 12:30:00 2025 UTC Add expression parser with operator precedence Recursive-descent parser for expressions with proper precedence: equality > comparison > addition > multiplication > unary > call > primary. Supports literals, binary/unary ops, function calls, and parenthesized grouping. commit - 8b5123e6050f1d24f2f6f3a000fef4665b878a2b commit + ebe3a0a72c98c733977195ad2a30c57189ce8701 blob - e91891d1c7e74a8aa6eb5a5fd993596ad05f0eb4 blob + 8aaab798979dedf14befb4da4574d361936120d1 --- src/main.rs +++ src/main.rs @@ -17,6 +17,7 @@ mod error; mod lexer; +mod parser; mod span; use std::env; @@ -28,7 +29,7 @@ fn main() { if args.len() < 3 { eprintln!("usage: ol "); - eprintln!("commands: tokenize"); + eprintln!("commands: tokenize, parse"); process::exit(1); } @@ -47,6 +48,7 @@ fn main() { match command.as_str() { "tokenize" => cmd_tokenize(&source), + "parse" => cmd_parse(&source), _ => { eprintln!("unknown command: {command}"); process::exit(1); @@ -54,6 +56,26 @@ fn main() { } } +fn cmd_parse(source: &str) { + let mut lexer = lexer::Lexer::new(source); + let tokens = match lexer.tokenize() { + Ok(t) => t, + Err(e) => { + eprintln!("{e}"); + process::exit(1); + } + }; + + let mut parser = parser::Parser::new(tokens); + match parser.parse_expression() { + Ok(expr) => println!("{:#?}", expr), + Err(e) => { + eprintln!("{e}"); + process::exit(1); + } + } +} + fn cmd_tokenize(source: &str) { let mut lexer = lexer::Lexer::new(source); blob - /dev/null blob + 1445329a8518ba61dfc298e9e4c639e637afe502 (mode 644) --- /dev/null +++ src/parser/ast.rs @@ -0,0 +1,64 @@ +// vim: set tw=79 cc=80 ts=4 sw=4 sts=4 et : +// +// Copyright (c) 2025-2026 Murilo Ijanc' +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +// + +use crate::span::Span; + +#[derive(Debug, Clone)] +pub enum BinOp { + Add, + Sub, + Mul, + Div, + Mod, + Eq, + NotEq, + Less, + LessEq, + Greater, + GreaterEq, +} + +#[derive(Debug, Clone)] +pub enum UnaryOp { + Negate, + Not, +} + +#[derive(Debug, Clone)] +pub enum Expr { + IntLit(i64, Span), + FloatLit(f64, Span), + StrLit(String, Span), + BoolLit(bool, Span), + Ident(String, Span), + Unary { + op: UnaryOp, + expr: Box, + span: Span, + }, + Binary { + op: BinOp, + left: Box, + right: Box, + span: Span, + }, + Call { + name: String, + args: Vec, + span: Span, + }, +} blob - /dev/null blob + fefc755e3dac17e7b89ce7583e1752d34287c4b7 (mode 644) --- /dev/null +++ src/parser/mod.rs @@ -0,0 +1,288 @@ +// vim: set tw=79 cc=80 ts=4 sw=4 sts=4 et : +// +// Copyright (c) 2025-2026 Murilo Ijanc' +// +// Permission to use, copy, modify, and/or distribute this software for any +// purpose with or without fee is hereby granted, provided that the above +// copyright notice and this permission notice appear in all copies. +// +// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +// + +pub mod ast; + +use crate::error::OlangError; +use crate::lexer::token::{Token, TokenKind}; +use crate::span::Span; +use ast::{BinOp, Expr, UnaryOp}; + +pub struct Parser { + tokens: Vec, + pos: usize, +} + +impl Parser { + pub fn new(tokens: Vec) -> Self { + Self { tokens, pos: 0 } + } + + fn peek(&self) -> &TokenKind { + &self.tokens[self.pos].kind + } + + fn peek_span(&self) -> Span { + self.tokens[self.pos].span + } + + fn advance(&mut self) -> &Token { + let token = &self.tokens[self.pos]; + self.pos += 1; + token + } + + fn expect( + &mut self, + expected: &TokenKind, + ) -> Result { + if self.peek() == expected { + let span = self.peek_span(); + self.advance(); + Ok(span) + } else { + Err(OlangError::new( + format!( + "expected {:?}, found {:?}", + expected, + self.peek() + ), + self.peek_span(), + )) + } + } + + pub fn parse_expression( + &mut self, + ) -> Result { + self.parse_equality() + } + + fn parse_equality( + &mut self, + ) -> Result { + let mut left = self.parse_comparison()?; + loop { + let op = match self.peek() { + TokenKind::EqEq => BinOp::Eq, + TokenKind::BangEq => BinOp::NotEq, + _ => break, + }; + self.advance(); + let right = self.parse_comparison()?; + let span = Span::new( + self.span_of(&left).start, + self.span_of(&right).end, + ); + left = Expr::Binary { + op, + left: Box::new(left), + right: Box::new(right), + span, + }; + } + Ok(left) + } + + fn parse_comparison( + &mut self, + ) -> Result { + let mut left = self.parse_addition()?; + loop { + let op = match self.peek() { + TokenKind::Less => BinOp::Less, + TokenKind::LessEq => BinOp::LessEq, + TokenKind::Greater => BinOp::Greater, + TokenKind::GreaterEq => { + BinOp::GreaterEq + } + _ => break, + }; + self.advance(); + let right = self.parse_addition()?; + let span = Span::new( + self.span_of(&left).start, + self.span_of(&right).end, + ); + left = Expr::Binary { + op, + left: Box::new(left), + right: Box::new(right), + span, + }; + } + Ok(left) + } + + fn parse_addition( + &mut self, + ) -> Result { + let mut left = self.parse_multiply()?; + loop { + let op = match self.peek() { + TokenKind::Plus => BinOp::Add, + TokenKind::Minus => BinOp::Sub, + _ => break, + }; + self.advance(); + let right = self.parse_multiply()?; + let span = Span::new( + self.span_of(&left).start, + self.span_of(&right).end, + ); + left = Expr::Binary { + op, + left: Box::new(left), + right: Box::new(right), + span, + }; + } + Ok(left) + } + + fn parse_multiply( + &mut self, + ) -> Result { + let mut left = self.parse_unary()?; + loop { + let op = match self.peek() { + TokenKind::Star => BinOp::Mul, + TokenKind::Slash => BinOp::Div, + TokenKind::Percent => BinOp::Mod, + _ => break, + }; + self.advance(); + let right = self.parse_unary()?; + let span = Span::new( + self.span_of(&left).start, + self.span_of(&right).end, + ); + left = Expr::Binary { + op, + left: Box::new(left), + right: Box::new(right), + span, + }; + } + Ok(left) + } + + fn parse_unary( + &mut self, + ) -> Result { + let start = self.peek_span(); + if *self.peek() == TokenKind::Minus { + self.advance(); + let expr = self.parse_unary()?; + let span = Span::new( + start.start, + self.span_of(&expr).end, + ); + return Ok(Expr::Unary { + op: UnaryOp::Negate, + expr: Box::new(expr), + span, + }); + } + self.parse_call() + } + + fn parse_call( + &mut self, + ) -> Result { + let expr = self.parse_primary()?; + if let Expr::Ident(ref name, _) = expr { + if *self.peek() == TokenKind::LParen { + let name = name.clone(); + let start = self.span_of(&expr); + self.advance(); + let mut args = Vec::new(); + if *self.peek() != TokenKind::RParen { + args.push( + self.parse_expression()?, + ); + while *self.peek() + == TokenKind::Comma + { + self.advance(); + args.push( + self.parse_expression()?, + ); + } + } + let end = + self.expect(&TokenKind::RParen)?; + let span = + Span::new(start.start, end.end); + return Ok(Expr::Call { + name, + args, + span, + }); + } + } + Ok(expr) + } + + fn parse_primary( + &mut self, + ) -> Result { + let token = self.advance().clone(); + match token.kind { + TokenKind::IntLit(v) => { + Ok(Expr::IntLit(v, token.span)) + } + TokenKind::FloatLit(v) => { + Ok(Expr::FloatLit(v, token.span)) + } + TokenKind::StrLit(ref s) => { + Ok(Expr::StrLit(s.clone(), token.span)) + } + TokenKind::BoolLit(v) => { + Ok(Expr::BoolLit(v, token.span)) + } + TokenKind::Ident(ref s) => { + Ok(Expr::Ident(s.clone(), token.span)) + } + TokenKind::LParen => { + let expr = self.parse_expression()?; + self.expect(&TokenKind::RParen)?; + Ok(expr) + } + _ => Err(OlangError::new( + format!( + "unexpected token {:?}", + token.kind + ), + token.span, + )), + } + } + + fn span_of(&self, expr: &Expr) -> Span { + match expr { + Expr::IntLit(_, s) => *s, + Expr::FloatLit(_, s) => *s, + Expr::StrLit(_, s) => *s, + Expr::BoolLit(_, s) => *s, + Expr::Ident(_, s) => *s, + Expr::Unary { span, .. } => *span, + Expr::Binary { span, .. } => *span, + Expr::Call { span, .. } => *span, + } + } +}