maolang_core/parser/
ast.rs

1//! AST definition and parser rules implemented
2
3use std::{error::Error, fmt::Display};
4
5use crate::tokenizer::{Token, TokenTag, keyword::Keyword};
6
7use super::Parser;
8
9/// A node in the abstract syntax tree, represents all possible operations that can occur
10#[derive(Debug, PartialEq, Clone)]
11pub enum Expr<'src> {
12    /// Print an expression's literal result
13    Print(Box<Expr<'src>>),
14    /// A variable reference
15    Variable(&'src str),
16    /// An assignment from an identifier to an expression
17    Assignment(&'src str, Box<Expr<'src>>),
18    /// A binary operation between two expressions
19    Binary {
20        /// The operator
21        op: BinaryOp,
22        /// Left hand side
23        left: Box<Expr<'src>>,
24        /// Right hand side
25        right: Box<Expr<'src>>,
26    },
27    /// A unary operation on a single expression
28    Unary {
29        /// The operator
30        op: UnaryOp,
31        /// The expression being acted on
32        node: Box<Expr<'src>>,
33    },
34    /// ( `expr` )
35    Grouping(Box<Expr<'src>>),
36    /// A literal
37    Literal(Literal<'src>),
38}
39
40/// A literal type
41#[derive(Debug, PartialEq, Clone, Copy)]
42pub enum Literal<'src> {
43    /// String
44    String(&'src str),
45    /// Real number
46    Number(f64),
47    /// Boolean
48    Bool(bool),
49    /// Null, nil, None, etc
50    Null,
51}
52
53impl Display for Literal<'_> {
54    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
55        match self {
56            Self::Bool(b) => write!(f, "{b}"),
57            Self::String(s) => write!(f, "{s}"),
58            Self::Number(n) => write!(f, "{n}"),
59            Self::Null => write!(f, "null"),
60        }
61    }
62}
63
64/// All operations that can occur between two targets
65#[derive(Debug, PartialEq, Clone, Copy)]
66pub enum UnaryOp {
67    /// Number negation
68    Neg,
69    /// Boolean not-ing
70    Not,
71}
72
73/// All operations that can occur between two targets
74#[derive(Debug, PartialEq, Clone, Copy)]
75pub enum BinaryOp {
76    /// Add two expressions
77    Add,
78    /// Subtract two expressions
79    Sub,
80    /// Multiply
81    Mul,
82    /// Divide
83    Div,
84    /// Equality
85    Eq,
86    /// Inequality
87    Neq,
88    /// Greater than
89    Gt,
90    /// Greater than or equal to
91    Gte,
92    /// Less than
93    Lt,
94    /// Less than or equal to
95    Lte,
96}
97
98/// An error that occurs whilst parsing
99#[derive(Clone, PartialEq, Debug, Default)]
100pub struct ParseError {
101    /// The error message
102    pub message: String,
103    /// Error token's line
104    pub line: usize,
105    /// Error token's column
106    pub col: usize,
107    /// Error token's len
108    pub len: usize,
109}
110
111impl Display for ParseError {
112    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
113        write!(f, "parser :(")
114    }
115}
116
117impl Error for ParseError {}
118
119impl<'src> Parser<'src> {
120    /// Parse a series of statements
121    pub fn parse(&mut self) -> Result<Vec<Expr<'src>>, ParseError> {
122        let mut statements = vec![];
123
124        while self.peek() != TokenTag::EOF {
125            statements.push(self.statement()?);
126        }
127
128        Ok(statements)
129    }
130
131    /// Parse a singular statement
132    pub fn statement(&mut self) -> Result<Expr<'src>, ParseError> {
133        match self.peek() {
134            TokenTag::Keyword(Keyword::Print) => {
135                self.advance();
136                self.consume_open_paren_if_necessary()?;
137                let next = self.expression()?;
138                self.consume_close_paren_if_necessary()?;
139                self.consume_end()?;
140                Ok(Expr::Print(Box::new(next)))
141            }
142            _ => {
143                let res = self.expression()?;
144                self.consume_end()?;
145                Ok(res)
146            }
147        }
148    }
149
150    /// an expression is equality  | var ident = equality
151    fn expression(&mut self) -> Result<Expr<'src>, ParseError> {
152        match self.peek() {
153            TokenTag::Keyword(Keyword::VariableDeclaration) => {
154                self.advance();
155                if let TokenTag::Identifier(name) = self.advance() {
156                    self.consume(&TokenTag::Keyword(Keyword::Equal))?;
157                    let assignment = self.equality()?;
158
159                    Ok(Expr::Assignment(name, Box::new(assignment)))
160                } else {
161                    let Token {
162                        tag,
163                        line,
164                        col,
165                        len,
166                    } = self.peek_token();
167                    Err(ParseError {
168                        message: format!("Expected a variable expression, found `{tag:?}`"),
169                        line,
170                        col,
171                        len,
172                    })
173                }
174            }
175
176            _ => self.equality(),
177        }
178    }
179
180    /// An equality is comparison ( (!= | ==) comparison)*
181    fn equality(&mut self) -> Result<Expr<'src>, ParseError> {
182        let mut expr = self.comparison()?;
183
184        while matches!(
185            self.peek(),
186            TokenTag::Keyword(Keyword::EqualEqual) | TokenTag::Keyword(Keyword::BangEqual)
187        ) {
188            let op = match self.advance() {
189                TokenTag::Keyword(Keyword::EqualEqual) => BinaryOp::Eq,
190                TokenTag::Keyword(Keyword::BangEqual) => BinaryOp::Neq,
191                _ => unreachable!(),
192            };
193
194            let right = Box::new(self.comparison()?);
195
196            expr = Expr::Binary {
197                op,
198                left: Box::new(expr),
199                right,
200            }
201        }
202
203        Ok(expr)
204    }
205
206    /// A comparison is term ( ( ">" | ">=" | "<" | "<=" ) term )*
207    fn comparison(&mut self) -> Result<Expr<'src>, ParseError> {
208        let mut expr = self.term()?;
209
210        while matches!(
211            self.peek(),
212            TokenTag::Keyword(Keyword::Greater)
213                | TokenTag::Keyword(Keyword::GreaterEqual)
214                | TokenTag::Keyword(Keyword::Less)
215                | TokenTag::Keyword(Keyword::LessEqual)
216        ) {
217            let op = match self.advance() {
218                TokenTag::Keyword(Keyword::Greater) => BinaryOp::Gt,
219                TokenTag::Keyword(Keyword::GreaterEqual) => BinaryOp::Gte,
220                TokenTag::Keyword(Keyword::Less) => BinaryOp::Lt,
221                TokenTag::Keyword(Keyword::LessEqual) => BinaryOp::Lte,
222                _ => unreachable!(),
223            };
224
225            let right = Box::new(self.term()?);
226
227            expr = Expr::Binary {
228                op,
229                left: Box::new(expr),
230                right,
231            }
232        }
233
234        Ok(expr)
235    }
236
237    /// A term is factor ( ( "+" | "-" ) factor )*
238    fn term(&mut self) -> Result<Expr<'src>, ParseError> {
239        let mut expr = self.factor()?;
240
241        while matches!(self.peek(), TokenTag::Plus | TokenTag::Minus) {
242            let op = match self.advance() {
243                TokenTag::Plus => BinaryOp::Add,
244                TokenTag::Minus => BinaryOp::Sub,
245                _ => unreachable!(),
246            };
247
248            let right = Box::new(self.factor()?);
249
250            expr = Expr::Binary {
251                op,
252                left: Box::new(expr),
253                right,
254            };
255        }
256
257        Ok(expr)
258    }
259
260    /// A factor is unary ( ( "*" | "/" ) unary )*
261    fn factor(&mut self) -> Result<Expr<'src>, ParseError> {
262        let mut expr = self.unary()?;
263
264        while matches!(self.peek(), TokenTag::Star | TokenTag::Slash) {
265            let op = match self.advance() {
266                TokenTag::Star => BinaryOp::Mul,
267                TokenTag::Slash => BinaryOp::Div,
268                _ => unreachable!(),
269            };
270
271            let right = Box::new(self.unary()?);
272
273            expr = Expr::Binary {
274                op,
275                left: Box::new(expr),
276                right,
277            };
278        }
279
280        Ok(expr)
281    }
282
283    /// A unary expression is either (! | -) unary | primary
284    fn unary(&mut self) -> Result<Expr<'src>, ParseError> {
285        if matches!(
286            self.peek(),
287            TokenTag::Keyword(Keyword::Bang) | TokenTag::Minus
288        ) {
289            let op = match self.advance() {
290                TokenTag::Keyword(Keyword::Bang) => UnaryOp::Not,
291                TokenTag::Minus => UnaryOp::Neg,
292                _ => unreachable!(),
293            };
294
295            let unary = self.unary()?;
296
297            Ok(Expr::Unary {
298                op,
299                node: Box::new(unary),
300            })
301        } else {
302            self.primary()
303        }
304    }
305
306    /// Variable | NUMBER | STRING | "true" | "false" | "nil" | "(" expression ")"
307    fn primary(&mut self) -> Result<Expr<'src>, ParseError> {
308        let advance = self.advance();
309        let prim = match advance {
310            TokenTag::Number(n) => Expr::Literal(Literal::Number(n)),
311            TokenTag::Keyword(Keyword::True) => Expr::Literal(Literal::Bool(true)),
312            TokenTag::Keyword(Keyword::False) => Expr::Literal(Literal::Bool(false)),
313            TokenTag::Keyword(Keyword::EmptyValue) => Expr::Literal(Literal::Null),
314            TokenTag::Identifier(ident) => Expr::Variable(ident),
315            TokenTag::String(s) => Expr::Literal(Literal::String(s)),
316            TokenTag::OpenParen => {
317                let expr = self.expression()?;
318                self.consume(&TokenTag::CloseParen)?;
319
320                Expr::Grouping(Box::new(expr))
321            }
322            _ => {
323                let Token {
324                    tag,
325                    line,
326                    col,
327                    len,
328                } = self.peek_token();
329                return Err(ParseError {
330                    message: format!("Expected primary statement, found `{tag:?}`"),
331                    line,
332                    col,
333                    len,
334                });
335            }
336        };
337
338        Ok(prim)
339    }
340}
341
342/** GOOD TO KNOW
343 * These are the mappings for when the seed is 42:
344 *
345 * Lexer:
346 *
347 *     "NULL": EmptyValue
348 *     "true": True
349 *     "then": ConditionalElse
350 *     "case": ConditionalCheck
351 *     "$": VariableDeclaration
352 *     "not": Bang
353 *     "and": And
354 *     "\\/": Or
355 *     "inequal": BangEqual
356 *     "<": Less
357 *     "{": OpenBrace
358 *     "}": CloseBrace
359 *     "fmt.Println": Print
360 *     "each": ForLoopInit
361 *     ">": Greater
362 *     "gte": GreaterEqual
363 *     ":(": False
364 *     "=": Equal
365 *     "equals": EqualEqual
366 *     "lte": LessEqual
367 *     "during": WhileLoopInit
368 */
369
370#[cfg(test)]
371mod tests {
372    use rand::SeedableRng;
373    use rand_chacha::ChaCha8Rng;
374
375    use crate::{
376        parser::{
377            Parser,
378            ast::{BinaryOp, Expr, Literal, UnaryOp},
379        },
380        tokenizer::Tokenizable,
381    };
382
383    #[test]
384    fn variable_assignment() {
385        let mut rng = ChaCha8Rng::seed_from_u64(42);
386        let stream = "$ i = 0 .".tokenize(&mut rng).expect("Valid tokenization");
387        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
388
389        let ast = &parser.parse().expect("Parse to AST")[0];
390
391        assert_eq!(
392            ast,
393            &Expr::Assignment("i", Box::new(Expr::Literal(Literal::Number(0.0))))
394        )
395    }
396
397    #[test]
398    fn print_statement() {
399        let mut rng = ChaCha8Rng::seed_from_u64(42);
400        let stream = "fmt.Println 42 ."
401            .tokenize(&mut rng)
402            .expect("Valid tokenization");
403        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
404
405        let ast = &parser.parse().expect("Parse to AST")[0];
406
407        assert_eq!(
408            ast,
409            &Expr::Print(Box::new(Expr::Literal(Literal::Number(42.0))))
410        );
411    }
412
413    #[test]
414    fn binary_operations() {
415        let mut rng = ChaCha8Rng::seed_from_u64(42);
416        let stream = "1 + 2 * 3 ."
417            .tokenize(&mut rng)
418            .expect("Valid tokenization");
419        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
420
421        let ast = &parser.parse().expect("Parse to AST")[0];
422
423        assert_eq!(
424            ast,
425            &Expr::Binary {
426                op: BinaryOp::Add,
427                left: Box::new(Expr::Literal(Literal::Number(1.0))),
428                right: Box::new(Expr::Binary {
429                    op: BinaryOp::Mul,
430                    left: Box::new(Expr::Literal(Literal::Number(2.0))),
431                    right: Box::new(Expr::Literal(Literal::Number(3.0))),
432                }),
433            }
434        );
435    }
436
437    #[test]
438    fn comparison_operations() {
439        let mut rng = ChaCha8Rng::seed_from_u64(42);
440        let stream = "1 < 2 .".tokenize(&mut rng).expect("Valid tokenization");
441        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
442
443        let ast = &parser.parse().expect("Parse to AST")[0];
444
445        assert_eq!(
446            ast,
447            &Expr::Binary {
448                op: BinaryOp::Lt,
449                left: Box::new(Expr::Literal(Literal::Number(1.0))),
450                right: Box::new(Expr::Literal(Literal::Number(2.0))),
451            }
452        );
453    }
454
455    #[test]
456    fn equality_operations() {
457        let mut rng = ChaCha8Rng::seed_from_u64(42);
458        let stream = "1 equals 1 ."
459            .tokenize(&mut rng)
460            .expect("Valid tokenization");
461        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
462
463        let ast = &parser.parse().expect("Parse to AST")[0];
464
465        assert_eq!(
466            ast,
467            &Expr::Binary {
468                op: BinaryOp::Eq,
469                left: Box::new(Expr::Literal(Literal::Number(1.0))),
470                right: Box::new(Expr::Literal(Literal::Number(1.0))),
471            }
472        );
473    }
474
475    #[test]
476    fn unary_operations() {
477        let mut rng = ChaCha8Rng::seed_from_u64(42);
478        let stream = "not true .".tokenize(&mut rng).expect("Valid tokenization");
479        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
480
481        let ast = &parser.parse().expect("Parse to AST")[0];
482
483        assert_eq!(
484            ast,
485            &Expr::Unary {
486                op: UnaryOp::Not,
487                node: Box::new(Expr::Literal(Literal::Bool(true))),
488            }
489        );
490    }
491
492    #[test]
493    fn grouping() {
494        let mut rng = ChaCha8Rng::seed_from_u64(42);
495        let stream = "(1 + 2) * 3 ."
496            .tokenize(&mut rng)
497            .expect("Valid tokenization");
498        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
499
500        let ast = &parser.parse().expect("Parse to AST")[0];
501        let expected = Expr::Binary {
502            op: BinaryOp::Mul,
503            left: Box::new(Expr::Grouping(Box::new(Expr::Binary {
504                op: BinaryOp::Add,
505                left: Box::new(Expr::Literal(Literal::Number(1.0))),
506                right: Box::new(Expr::Literal(Literal::Number(2.0))),
507            }))),
508            right: Box::new(Expr::Literal(Literal::Number(3.0))),
509        };
510
511        assert_eq!(ast, &expected);
512    }
513
514    #[test]
515    fn variable_reference() {
516        let mut rng = ChaCha8Rng::seed_from_u64(42);
517        let stream = "x .".tokenize(&mut rng).expect("Valid tokenization");
518        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
519
520        let ast = &parser.parse().expect("Parse to AST")[0];
521
522        assert_eq!(ast, &Expr::Variable("x"));
523    }
524
525    #[test]
526    fn complex_expression() {
527        let mut rng = ChaCha8Rng::seed_from_u64(42);
528        let stream = "$ x = 5 * (3 + 2) . fmt.Println x < 10 ."
529            .tokenize(&mut rng)
530            .expect("Valid tokenization");
531        let mut parser = Parser::from_rng(&mut rng).with_tokens(&stream);
532
533        let ast = parser.parse().expect("Parse to AST");
534
535        assert_eq!(
536            ast,
537            vec![
538                Expr::Assignment(
539                    "x",
540                    Box::new(Expr::Binary {
541                        op: BinaryOp::Mul,
542                        left: Box::new(Expr::Literal(Literal::Number(5.0))),
543                        right: Box::new(Expr::Grouping(Box::new(Expr::Binary {
544                            op: BinaryOp::Add,
545                            left: Box::new(Expr::Literal(Literal::Number(3.0))),
546                            right: Box::new(Expr::Literal(Literal::Number(2.0))),
547                        }))),
548                    }),
549                ),
550                Expr::Print(Box::new(Expr::Binary {
551                    op: BinaryOp::Lt,
552                    left: Box::new(Expr::Variable("x")),
553                    right: Box::new(Expr::Literal(Literal::Number(10.0))),
554                })),
555            ]
556        );
557    }
558}
maolang_core/parser/ast.rs

maolang_core/parser/
ast.rs
