1pub mod ast;
3pub mod grammar;
4
5use crate::lexer::Token;
6use ast::*;
7
8pub fn parse(source: &str) -> Result<Program, String> {
9 let mut lex = crate::lexer::Lexer::new(source);
10 let mut tokens = Vec::new();
11 while let Some(tok) = lex.next_token() {
12 tokens.push(tok);
13 }
14 tokens.push(Token::Eof);
15 parse_tokens(tokens)
16}
17
18pub fn parse_tokens(tokens: Vec<Token>) -> Result<Program, String> {
19 Parser::new(tokens).parse_program()
20}
21
22struct Parser {
25 tokens: Vec<Token>,
26 pos: usize,
27}
28
29impl Parser {
30 fn new(tokens: Vec<Token>) -> Self {
31 Self { tokens, pos: 0 }
32 }
33
34 fn peek(&self) -> &Token {
35 self.tokens.get(self.pos).unwrap_or(&Token::Eof)
36 }
37
38 #[allow(dead_code)]
39 fn peek2(&self) -> &Token {
40 self.tokens.get(self.pos + 1).unwrap_or(&Token::Eof)
41 }
42
43 fn advance(&mut self) -> Token {
44 let tok = self.tokens.get(self.pos).cloned().unwrap_or(Token::Eof);
45 if self.pos < self.tokens.len() {
46 self.pos += 1;
47 }
48 tok
49 }
50
51 fn expect(&mut self, expected: &Token) -> Result<(), String> {
52 let tok = self.advance();
53 if &tok == expected {
54 Ok(())
55 } else {
56 Err(format!("expected {:?}, got {:?}", expected, tok))
57 }
58 }
59
60 fn parse_name(&mut self) -> Result<String, String> {
62 match self.advance() {
63 Token::Ident(s) => Ok(s),
64 tok => Ok(token_to_name(&tok)
66 .ok_or_else(|| format!("expected identifier, got {:?}", tok))?
67 .to_string()),
68 }
69 }
70
71 fn parse_program(&mut self) -> Result<Program, String> {
74 let mut items = Vec::new();
75 while !matches!(self.peek(), Token::Eof) {
76 items.push(self.parse_item()?);
77 }
78 Ok(Program { items })
79 }
80
81 fn parse_item(&mut self) -> Result<Item, String> {
82 let is_async = if matches!(self.peek(), Token::Async) {
83 self.advance();
84 true
85 } else {
86 false
87 };
88
89 match self.peek().clone() {
90 Token::Bind => {
91 self.advance();
92 let name = self.parse_name()?;
93 self.expect(&Token::Eq)?;
94 let expr = self.parse_expr()?;
95 Ok(Item::Bind(name, expr))
96 }
97 Token::Fn => {
98 self.parse_fn_item(is_async)
99 }
100 Token::Mod => {
101 self.advance();
102 let name = self.parse_name()?;
103 self.expect(&Token::LBrace)?;
104 let mut body = Vec::new();
105 while !matches!(self.peek(), Token::RBrace | Token::Eof) {
106 body.push(self.parse_item()?);
107 }
108 self.expect(&Token::RBrace)?;
109 Ok(Item::Mod(name, body))
110 }
111 Token::Type => {
112 self.advance();
113 let name = self.parse_name()?;
114 self.skip_generics();
116 self.expect(&Token::As)?;
117 let ty = self.parse_type_str();
118 Ok(Item::TypeAlias(name, ty))
119 }
120 Token::Form => self.parse_struct_item(),
121 Token::Choose => self.parse_enum_item(),
122 Token::Use => {
123 self.advance();
124 let path = match self.advance() {
126 Token::String(s) => s,
127 tok => return Err(format!("use: expected string path, got {:?}", tok)),
128 };
129 let alias = if matches!(self.peek(), Token::As) {
131 self.advance();
132 Some(self.parse_name()?)
133 } else {
134 None
135 };
136 Ok(Item::Use { path, alias })
137 }
138 tok => Err(format!("unexpected token at top level: {:?}", tok)),
139 }
140 }
141
142 fn parse_struct_item(&mut self) -> Result<Item, String> {
145 self.advance(); let name = self.parse_name()?;
147 self.skip_generics();
148 self.expect(&Token::LBrace)?;
149 let mut fields = Vec::new();
150 while !matches!(self.peek(), Token::RBrace | Token::Eof) {
151 fields.push(self.parse_name()?);
152 if matches!(self.peek(), Token::Colon) {
153 self.advance();
154 self.parse_type_str(); }
156 if matches!(self.peek(), Token::Comma | Token::Semicolon) { self.advance(); }
157 }
158 self.expect(&Token::RBrace)?;
159 Ok(Item::Struct(name, fields))
160 }
161
162 fn parse_enum_item(&mut self) -> Result<Item, String> {
166 self.advance(); let name = self.parse_name()?;
168 self.skip_generics();
169 self.expect(&Token::LBrace)?;
170 let mut variants = Vec::new();
171 while !matches!(self.peek(), Token::RBrace | Token::Eof) {
172 let vname = self.parse_name()?;
173 let mut arity = 0usize;
174 if matches!(self.peek(), Token::LParen) {
175 self.advance();
176 while !matches!(self.peek(), Token::RParen | Token::Eof) {
177 self.parse_name().ok();
179 if matches!(self.peek(), Token::Colon) {
180 self.advance();
181 self.parse_type_str();
182 }
183 arity += 1;
184 if matches!(self.peek(), Token::Comma) { self.advance(); }
185 }
186 self.expect(&Token::RParen)?;
187 }
188 variants.push(EnumVariant { name: vname, arity });
189 if matches!(self.peek(), Token::Comma | Token::Semicolon) { self.advance(); }
190 }
191 self.expect(&Token::RBrace)?;
192 Ok(Item::Enum(name, variants))
193 }
194
195 fn parse_fn_item(&mut self, is_async: bool) -> Result<Item, String> {
196 self.advance(); let name = self.parse_name()?;
198 self.skip_generics(); self.expect(&Token::LParen)?;
200 let params = self.parse_params()?;
201 self.expect(&Token::RParen)?;
202 if matches!(self.peek(), Token::Arrow) {
204 self.advance();
205 self.parse_type_str();
206 }
207 if matches!(self.peek(), Token::Where) {
209 self.advance();
210 while !matches!(self.peek(), Token::LBrace | Token::Eof) {
211 self.advance();
212 }
213 }
214 self.expect(&Token::LBrace)?;
215 let body = self.parse_block()?;
216 self.expect(&Token::RBrace)?;
217 Ok(Item::Fn(FnDef { name, is_async, params, body }))
218 }
219
220 fn parse_params(&mut self) -> Result<Vec<String>, String> {
221 let mut params = Vec::new();
222 while !matches!(self.peek(), Token::RParen | Token::Eof) {
223 while matches!(self.peek(), Token::Ampersand | Token::Own | Token::Lend) {
225 self.advance();
226 }
227 let name = self.parse_name()?;
228 params.push(name);
229 if matches!(self.peek(), Token::Colon) {
231 self.advance();
232 self.parse_type_str();
233 }
234 if matches!(self.peek(), Token::Comma) {
235 self.advance();
236 }
237 }
238 Ok(params)
239 }
240
241 fn parse_type_str(&mut self) -> String {
243 let mut depth = 0usize;
244 let mut result = String::new();
245 loop {
246 match self.peek() {
247 Token::Eof => break,
248 Token::Lt => { depth += 1; result.push('<'); self.advance(); }
249 Token::Gt if depth > 0 => { depth -= 1; result.push('>'); self.advance(); }
250 Token::LBrace | Token::Where if depth == 0 => break,
251 Token::RParen | Token::Comma | Token::Semicolon if depth == 0 => break,
252 Token::Arrow if depth == 0 => break,
253 tok => { result.push_str(&format!("{:?}", tok)); self.advance(); }
254 }
255 }
256 result
257 }
258
259 fn skip_generics(&mut self) {
260 if matches!(self.peek(), Token::Lt) {
261 let mut depth = 0;
262 loop {
263 match self.advance() {
264 Token::Lt => depth += 1,
265 Token::Gt => { depth -= 1; if depth == 0 { break; } }
266 Token::Eof => break,
267 _ => {}
268 }
269 }
270 }
271 }
272
273 fn parse_block(&mut self) -> Result<Vec<Stmt>, String> {
276 let mut stmts = Vec::new();
277 while !matches!(self.peek(), Token::RBrace | Token::Eof) {
278 stmts.push(self.parse_stmt()?);
279 if matches!(self.peek(), Token::Semicolon) {
281 self.advance();
282 }
283 }
284 Ok(stmts)
285 }
286
287 fn parse_stmt(&mut self) -> Result<Stmt, String> {
288 match self.peek().clone() {
289 Token::Bind => {
290 self.advance();
291 let name = self.parse_name()?;
292 self.expect(&Token::Eq)?;
293 let expr = self.parse_expr()?;
294 Ok(Stmt::Bind(name, expr))
295 }
296 Token::Return => {
297 self.advance();
298 if matches!(self.peek(), Token::Semicolon | Token::RBrace) {
299 Ok(Stmt::Return(Expr::Unit))
300 } else {
301 Ok(Stmt::Return(self.parse_expr()?))
302 }
303 }
304 _ => Ok(Stmt::Expr(self.parse_expr()?)),
305 }
306 }
307
308 fn parse_expr(&mut self) -> Result<Expr, String> {
311 self.parse_or_expr()
312 }
313
314 fn parse_or_expr(&mut self) -> Result<Expr, String> {
315 let mut left = self.parse_and_expr()?;
316 while matches!(self.peek(), Token::Or) {
317 self.advance();
318 let right = self.parse_and_expr()?;
319 left = Expr::BinOp(BinOp::Or, Box::new(left), Box::new(right));
320 }
321 Ok(left)
322 }
323
324 fn parse_and_expr(&mut self) -> Result<Expr, String> {
325 let mut left = self.parse_cmp_expr()?;
326 while matches!(self.peek(), Token::And) {
327 self.advance();
328 let right = self.parse_cmp_expr()?;
329 left = Expr::BinOp(BinOp::And, Box::new(left), Box::new(right));
330 }
331 Ok(left)
332 }
333
334 fn parse_cmp_expr(&mut self) -> Result<Expr, String> {
335 let mut left = self.parse_add_expr()?;
336 loop {
337 let op = match self.peek() {
338 Token::EqEq => BinOp::Eq,
339 Token::Ne => BinOp::Ne,
340 Token::Lt => BinOp::Lt,
341 Token::Gt => BinOp::Gt,
342 Token::Le => BinOp::Le,
343 Token::Ge => BinOp::Ge,
344 _ => break,
345 };
346 self.advance();
347 let right = self.parse_add_expr()?;
348 left = Expr::BinOp(op, Box::new(left), Box::new(right));
349 }
350 Ok(left)
351 }
352
353 fn parse_add_expr(&mut self) -> Result<Expr, String> {
354 let mut left = self.parse_mul_expr()?;
355 loop {
356 let op = match self.peek() {
357 Token::Plus => BinOp::Add,
358 Token::Minus => BinOp::Sub,
359 _ => break,
360 };
361 self.advance();
362 let right = self.parse_mul_expr()?;
363 left = Expr::BinOp(op, Box::new(left), Box::new(right));
364 }
365 Ok(left)
366 }
367
368 fn parse_mul_expr(&mut self) -> Result<Expr, String> {
369 let mut left = self.parse_unary_expr()?;
370 loop {
371 let op = match self.peek() {
372 Token::Star => BinOp::Mul,
373 Token::Slash => BinOp::Div,
374 Token::Percent => BinOp::Rem,
375 _ => break,
376 };
377 self.advance();
378 let right = self.parse_unary_expr()?;
379 left = Expr::BinOp(op, Box::new(left), Box::new(right));
380 }
381 Ok(left)
382 }
383
384 fn parse_unary_expr(&mut self) -> Result<Expr, String> {
385 match self.peek().clone() {
386 Token::Ampersand => { self.advance(); Ok(Expr::Ref(Box::new(self.parse_postfix_expr()?))) }
387 Token::Not => { self.advance(); Ok(Expr::BinOp(BinOp::Eq, Box::new(self.parse_postfix_expr()?), Box::new(Expr::Bool(false)))) }
388 Token::Minus => { self.advance(); Ok(Expr::BinOp(BinOp::Sub, Box::new(Expr::Number(0.0)), Box::new(self.parse_postfix_expr()?))) }
389 Token::Wait => { self.advance(); Ok(Expr::Await(Box::new(self.parse_postfix_expr()?))) }
390 Token::Own | Token::Lend | Token::Share | Token::Move | Token::Copy => {
392 self.advance();
393 self.parse_unary_expr()
394 }
395 _ => self.parse_postfix_expr(),
396 }
397 }
398
399 fn parse_postfix_expr(&mut self) -> Result<Expr, String> {
401 let mut base = self.parse_primary()?;
402
403 loop {
404 match self.peek().clone() {
405 Token::Dot => {
407 self.advance();
408 let method = self.parse_name()?;
409 if matches!(self.peek(), Token::LParen) {
410 self.advance();
411 let args = self.parse_call_args()?;
412 self.expect(&Token::RParen)?;
413 base = Expr::MethodCall {
414 receiver: Box::new(base),
415 method,
416 args,
417 };
418 } else {
419 base = Expr::MethodCall {
421 receiver: Box::new(base),
422 method,
423 args: Vec::new(),
424 };
425 }
426 }
427 Token::ColonColon => {
429 self.advance();
430 let segment = self.parse_name()?;
431 base = match base {
433 Expr::Path(mut segs) => { segs.push(segment); Expr::Path(segs) }
434 Expr::Ident(s) => Expr::Path(vec![s, segment]),
435 other => Expr::Path(vec![format!("{:?}", other), segment]),
436 };
437 }
438 Token::LParen => {
440 self.advance();
441 let args = self.parse_call_args()?;
442 self.expect(&Token::RParen)?;
443 base = Expr::Call(Box::new(base), args);
444 }
445 Token::LBracket => {
447 self.advance();
448 let idx = self.parse_expr()?;
449 self.expect(&Token::RBracket)?;
450 base = Expr::Index(Box::new(base), Box::new(idx));
451 }
452 Token::DotDot => {
454 self.advance();
455 let hi = self.parse_primary()?;
456 base = Expr::Range(Box::new(base), Box::new(hi));
457 }
458 _ => break,
459 }
460 }
461 Ok(base)
462 }
463
464 fn parse_call_args(&mut self) -> Result<Vec<Expr>, String> {
465 let mut args = Vec::new();
466 while !matches!(self.peek(), Token::RParen | Token::Eof) {
467 args.push(self.parse_expr()?);
468 if matches!(self.peek(), Token::Comma) { self.advance(); }
469 }
470 Ok(args)
471 }
472
473 fn parse_primary(&mut self) -> Result<Expr, String> {
474 match self.peek().clone() {
475 Token::String(s) => { self.advance(); Ok(Expr::Str(s)) }
477 Token::Number(n) => { self.advance(); Ok(Expr::Number(n.parse().unwrap_or(0.0))) }
478 Token::Bool(b) => { self.advance(); Ok(Expr::Bool(b)) }
479
480 Token::Do => {
482 self.advance();
483 self.expect(&Token::LBrace)?;
484 let stmts = self.parse_block()?;
485 self.expect(&Token::RBrace)?;
486 Ok(Expr::Do(stmts))
487 }
488 Token::LBrace => {
489 self.advance();
490 let stmts = self.parse_block()?;
491 self.expect(&Token::RBrace)?;
492 Ok(Expr::Do(stmts))
493 }
494 Token::If => self.parse_if_expr(),
495 Token::For => self.parse_for_expr(),
496 Token::While => self.parse_while_expr(),
497 Token::Match => self.parse_match_expr(),
498 Token::Return => {
499 self.advance();
500 let val = if matches!(self.peek(), Token::Semicolon | Token::RBrace | Token::Eof) {
501 Expr::Unit
502 } else {
503 self.parse_expr()?
504 };
505 Ok(Expr::Do(vec![Stmt::Return(val)]))
506 }
507
508 Token::LBracket => {
510 self.advance();
511 let mut elems = Vec::new();
512 while !matches!(self.peek(), Token::RBracket | Token::Eof) {
513 elems.push(self.parse_expr()?);
514 if matches!(self.peek(), Token::Comma) { self.advance(); }
515 }
516 self.expect(&Token::RBracket)?;
517 Ok(Expr::Array(elems))
518 }
519
520 Token::Or => {
522 self.advance(); let mut params = Vec::new();
524 if !matches!(self.peek(), Token::Or) {
526 while !matches!(self.peek(), Token::Or | Token::Eof) {
527 params.push(self.parse_name()?);
528 if matches!(self.peek(), Token::Comma) { self.advance(); }
529 }
530 }
531 self.advance(); let body = self.parse_expr()?;
533 Ok(Expr::Closure(params, Box::new(body)))
534 }
535
536 Token::LParen => {
538 self.advance();
539 if matches!(self.peek(), Token::RParen) {
540 self.advance();
541 return Ok(Expr::Unit);
542 }
543 let e = self.parse_expr()?;
544 self.expect(&Token::RParen)?;
545 Ok(e)
546 }
547
548 Token::Async => {
550 self.advance();
551 let inner = self.parse_expr()?;
552 Ok(inner) }
554
555 Token::Ident(name) => {
557 self.advance();
558 Ok(Expr::Ident(name))
559 }
560
561 tok => {
563 if let Some(name) = token_to_name(&tok) {
564 self.advance();
565 Ok(Expr::Ident(name.to_string()))
566 } else {
567 Err(format!("unexpected token in expression: {:?}", tok))
568 }
569 }
570 }
571 }
572
573 fn parse_if_expr(&mut self) -> Result<Expr, String> {
576 self.advance(); let cond = self.parse_cmp_expr()?;
578 self.expect(&Token::LBrace)?;
579 let then = self.parse_block()?;
580 self.expect(&Token::RBrace)?;
581
582 let mut elseifs = Vec::new();
583 let mut else_body = None;
584
585 while matches!(self.peek(), Token::Else) {
586 self.advance(); if matches!(self.peek(), Token::If) {
588 self.advance(); let ei_cond = self.parse_cmp_expr()?;
590 self.expect(&Token::LBrace)?;
591 let ei_body = self.parse_block()?;
592 self.expect(&Token::RBrace)?;
593 elseifs.push((ei_cond, ei_body));
594 } else {
595 self.expect(&Token::LBrace)?;
596 else_body = Some(self.parse_block()?);
597 self.expect(&Token::RBrace)?;
598 break;
599 }
600 }
601
602 Ok(Expr::If { cond: Box::new(cond), then, elseifs, else_body })
603 }
604
605 fn parse_while_expr(&mut self) -> Result<Expr, String> {
606 self.advance(); let cond = self.parse_expr()?;
608 self.expect(&Token::LBrace)?;
609 let body = self.parse_block()?;
610 self.expect(&Token::RBrace)?;
611 Ok(Expr::While { cond: Box::new(cond), body })
612 }
613
614 fn parse_for_expr(&mut self) -> Result<Expr, String> {
615 self.advance(); let var = self.parse_name()?;
617 self.expect(&Token::In)?;
618 let iter = self.parse_postfix_expr()?;
619 self.expect(&Token::LBrace)?;
621 let body = self.parse_block()?;
622 self.expect(&Token::RBrace)?;
623 Ok(Expr::For { var, iter: Box::new(iter), body })
624 }
625
626 fn parse_match_expr(&mut self) -> Result<Expr, String> {
627 self.advance(); let subject = self.parse_postfix_expr()?;
629 self.expect(&Token::LBrace)?;
630 let mut arms = Vec::new();
631 while !matches!(self.peek(), Token::RBrace | Token::Eof) {
632 let pattern = self.parse_pattern()?;
633 self.expect(&Token::FatArrow)?;
634 let body = self.parse_expr()?;
635 if matches!(self.peek(), Token::Comma) { self.advance(); }
637 arms.push(MatchArm { pattern, body });
638 }
639 self.expect(&Token::RBrace)?;
640 Ok(Expr::Match(Box::new(subject), arms))
641 }
642
643 fn parse_pattern(&mut self) -> Result<Pattern, String> {
644 match self.peek().clone() {
645 Token::Ident(s) if s == "_" => { self.advance(); Ok(Pattern::Wildcard) }
646 Token::String(s) => { self.advance(); Ok(Pattern::Str(s)) }
647 Token::Number(n) => { self.advance(); Ok(Pattern::Number(n.parse().unwrap_or(0.0))) }
648 Token::Bool(b) => { self.advance(); Ok(Pattern::Bool(b)) }
649 Token::Ok | Token::Bad => {
651 let ctor_tok = self.advance();
652 let ctor = match ctor_tok {
653 Token::Ok => "ok".to_string(),
654 Token::Bad => "bad".to_string(),
655 _ => unreachable!(),
656 };
657 if matches!(self.peek(), Token::LParen) {
658 self.advance();
659 let inner = self.parse_pattern()?;
660 self.expect(&Token::RParen)?;
661 Ok(Pattern::Constructor(ctor, Some(Box::new(inner))))
662 } else {
663 Ok(Pattern::Constructor(ctor, None))
664 }
665 }
666 _ => {
667 let name = self.parse_name()?;
668 if matches!(self.peek(), Token::LParen) {
669 self.advance();
671 let mut subs = Vec::new();
672 while !matches!(self.peek(), Token::RParen | Token::Eof) {
673 subs.push(self.parse_pattern()?);
674 if matches!(self.peek(), Token::Comma) { self.advance(); }
675 }
676 self.expect(&Token::RParen)?;
677 Ok(Pattern::Variant(name, subs))
678 } else if name == "_" {
679 Ok(Pattern::Wildcard)
680 } else {
681 Ok(Pattern::Ident(name))
682 }
683 }
684 }
685 }
686}
687
688fn token_to_name(tok: &Token) -> Option<&'static str> {
692 match tok {
693 Token::Bind => Some("bind"), Token::Do => Some("do"),
694 Token::Fn => Some("fn"), Token::Mod => Some("mod"),
695 Token::Type => Some("type"), Token::If => Some("if"),
696 Token::Else => Some("else"), Token::While => Some("while"),
697 Token::For => Some("for"), Token::In => Some("in"),
698 Token::Match => Some("match"), Token::Return => Some("return"),
699 Token::Own => Some("own"), Token::Lend => Some("lend"),
700 Token::Share => Some("share"), Token::Move => Some("move"),
701 Token::Copy => Some("copy"), Token::Async => Some("async"),
702 Token::Wait => Some("wait"), Token::As => Some("as"),
703 Token::Where => Some("where"), Token::Post => Some("post"),
704 Token::Give => Some("give"), Token::Fit => Some("fit"),
705 Token::Form => Some("form"), Token::Choose => Some("choose"),
706 Token::Can => Some("can"), Token::Change => Some("change"),
707 Token::Stop => Some("stop"), Token::Again => Some("again"),
708 Token::Try => Some("try"), Token::Sure => Some("sure"),
709 Token::Maybe => Some("maybe"), Token::Pure => Some("pure"),
710 Token::Spawn => Some("spawn"), Token::Ok => Some("ok"),
711 Token::Bad => Some("bad"), Token::None => Some("none"),
712 Token::Use => Some("use"),
713 _ => None,
714 }
715}