june_lang/
parser.rs

1// TODO: write BNF grammar
2use crate::ast::*;
3use crate::scanner;
4use crate::token::*;
5use std::io;
6use std::iter;
7use std::result;
8use thiserror::Error;
9
10#[derive(Debug, Error)]
11pub enum Error {
12    #[error("scanner: {0}")]
13    ScannerError(#[from] scanner::Error),
14    #[error("unexpected eof")]
15    UnexpectedEOF,
16    #[error("invalid: want {want}, got {got:?}")]
17    Invalid { want: String, got: Token },
18}
19
20type Result<T> = result::Result<T, Error>;
21
22pub struct Parser<R: io::BufRead> {
23    scanner: iter::Peekable<scanner::Scanner<R>>,
24}
25
26impl<R: io::BufRead> Parser<R> {
27    pub fn new(scanner: scanner::Scanner<R>) -> Parser<R> {
28        Parser { scanner: scanner.peekable() }
29    }
30
31    pub fn eof(&mut self) -> bool {
32        self.scanner.peek().is_none()
33    }
34
35    fn peek_is(&mut self, f: impl Fn(&Token) -> bool) -> bool {
36        matches!(self.scanner.peek(), Some(Ok(tok)) if f(tok))
37    }
38
39    fn eat<T, Eat>(&mut self, f: Eat, want: impl ToString) -> Result<T>
40    where
41        Eat: Fn(&Token) -> Option<T>,
42    {
43        let got = self.scanner.next().ok_or(Error::UnexpectedEOF)??;
44        match f(&got) {
45            Some(t) => Ok(t),
46            None => Err(Error::Invalid { want: want.to_string(), got }),
47        }
48    }
49
50    fn eat_tok(&mut self, want: Token) -> Result<()> {
51        self.eat(|tok| if tok == &want { Some(()) } else { None }, &want)
52    }
53
54    fn eat_ident(&mut self) -> Result<String> {
55        self.eat(|tok| tok.as_ident(), "ident")
56    }
57
58    fn primary(&mut self) -> Result<Expr> {
59        match self.scanner.next().ok_or(Error::UnexpectedEOF)?? {
60            Token::Str(value) => Ok(Expr::Str(Literal::new(value))),
61            Token::Int(value) => Ok(Expr::Int(Literal::new(value))),
62            Token::Ident(name) => Ok(Expr::Ident(Ident::untyped(name))),
63            Token::Lparen => {
64                let expr = self.expr()?;
65                self.eat_tok(Token::Rparen)?;
66                Ok(expr)
67            }
68            got => Err(Error::Invalid { want: String::from("prim"), got }),
69        }
70    }
71
72    fn call(&mut self) -> Result<Expr> {
73        let target = self.primary()?;
74        if self.peek_is(|tok| tok == &Token::Lparen) {
75            self.eat_tok(Token::Lparen)?;
76            let args = self.list(|p| p.expr())?;
77            self.eat_tok(Token::Rparen)?;
78            Ok(Expr::Call(Call::untyped(target, args)))
79        } else {
80            Ok(target)
81        }
82    }
83
84    fn list<T, Eat>(&mut self, eat: Eat) -> Result<Vec<T>>
85    where
86        Eat: Fn(&mut Self) -> Result<T>,
87    {
88        let mut list = Vec::new();
89        while !self.peek_is(|tok| tok == &Token::Rparen) {
90            if !list.is_empty() {
91                self.eat_tok(Token::Comma)?;
92            }
93            list.push(eat(self)?);
94        }
95        Ok(list)
96    }
97
98    fn binary<Pred, Eat>(&mut self, pred: Pred, eat: Eat) -> Result<Expr>
99    where
100        Pred: Fn(&Op) -> bool,
101        Eat: Fn(&mut Self) -> Result<Expr>,
102    {
103        let mut expr = self.call()?;
104        while self.peek_is(|tok| matches!(tok, Token::Op(op) if pred(op))) {
105            let op = self.eat(|tok| tok.as_op(), "op")?;
106            expr = Expr::Binary(Binary::untyped(op.into(), expr, eat(self)?));
107        }
108        Ok(expr)
109    }
110
111    fn mul_div(&mut self) -> Result<Expr> {
112        self.binary(|op| matches!(op, Op::Star | Op::Slash), |p| p.call())
113    }
114
115    fn add_sub(&mut self) -> Result<Expr> {
116        self.binary(|op| matches!(op, Op::Plus | Op::Minus), |p| p.mul_div())
117    }
118
119    pub fn expr(&mut self) -> Result<Expr> {
120        self.add_sub()
121    }
122
123    fn type_spec(&mut self) -> Result<TypeSpec> {
124        // TODO: parse more complicated types
125        Ok(TypeSpec::Simple(self.eat_ident()?))
126    }
127
128    fn expr_stmt(&mut self) -> Result<Stmt> {
129        let expr = self.expr()?;
130        self.eat_tok(Token::Semi)?;
131        Ok(Stmt::Expr(expr))
132    }
133
134    fn param(&mut self) -> Result<Param> {
135        let name = self.eat_ident()?;
136        self.eat_tok(Token::Colon)?;
137        let typ = self.type_spec()?;
138        Ok(Param::untyped(name, typ))
139    }
140
141    fn let_stmt(&mut self) -> Result<Stmt> {
142        self.eat_tok(Token::Let)?;
143        let param = self.param()?;
144        self.eat_tok(Token::Eq)?;
145        let expr = self.expr()?;
146        self.eat_tok(Token::Semi)?;
147        Ok(Stmt::Let(Binding::new(param.name, param.typ, expr, ())))
148    }
149
150    pub fn stmt(&mut self) -> Result<Stmt> {
151        match self.scanner.peek() {
152            Some(Ok(Token::Let)) => self.let_stmt(),
153            Some(Ok(Token::Lbrace)) => Ok(Stmt::Block(self.block()?)),
154            _ => self.expr_stmt(),
155        }
156    }
157
158    pub fn block(&mut self) -> Result<Block> {
159        self.eat_tok(Token::Lbrace)?;
160        let mut stmts = Vec::new();
161        while !self.peek_is(|tok| tok == &Token::Rbrace) {
162            stmts.push(self.stmt()?);
163        }
164        self.eat_tok(Token::Rbrace)?;
165        Ok(Block(stmts))
166    }
167
168    pub fn fn_expr(&mut self) -> Result<Func> {
169        self.eat_tok(Token::Fn)?;
170        let name = self.eat_ident()?;
171        self.eat_tok(Token::Lparen)?;
172        let params = self.list(|p| p.param())?;
173        self.eat_tok(Token::Rparen)?;
174        // TODO: parse return type
175        let body = self.block()?;
176        Ok(Func::untyped(name, params, body, None))
177    }
178
179    pub fn def(&mut self) -> Result<Def> {
180        Ok(Def::FnDef(self.fn_expr()?))
181    }
182
183    pub fn program(&mut self) -> Result<Program> {
184        let mut defs = Vec::new();
185        while !self.eof() {
186            defs.push(self.def()?);
187        }
188        Ok(Program { main_def: (), defs })
189    }
190}
191
192pub fn parse<R: io::BufRead>(scanner: scanner::Scanner<R>) -> Result<Program> {
193    Parser::new(scanner).program()
194}
195
196#[cfg(test)]
197mod test {
198    use super::*;
199    use crate::ast::BinaryOp::*;
200
201    fn parse(input: &[u8]) -> Parser<&[u8]> {
202        Parser { scanner: scanner::scan(input).peekable() }
203    }
204
205    #[test]
206    fn test_empty() {
207        let input: &[u8] = b"
208        ";
209        let mut p = parse(input);
210        let ast = p.program().unwrap();
211        assert_eq!(Program { main_def: (), defs: Vec::new() }, ast);
212    }
213
214    #[test]
215    fn test_primary() {
216        let input = b"foo bar 27 \"hello, world\"";
217        let expected = vec![
218            Expr::Ident(Ident::untyped("foo")),
219            Expr::Ident(Ident::untyped("bar")),
220            Expr::Int(Literal::new(27)),
221            Expr::Str(Literal::new("hello, world")),
222        ];
223        let mut p = parse(input);
224        let mut actual = Vec::new();
225        while !p.eof() {
226            actual.push(p.primary().unwrap());
227        }
228        assert_eq!(expected, actual);
229    }
230
231    #[test]
232    fn test_call() {
233        let inputs = vec![
234            b" foo ( ) ".as_slice(),
235            b" bar ( arg ) ".as_slice(),
236            b" println ( \"foo\" , 27 ) ".as_slice(),
237        ];
238        let expected = vec![
239            Expr::Call(Call::untyped(
240                Expr::Ident(Ident::untyped("foo")),
241                Vec::new(),
242            )),
243            Expr::Call(Call::untyped(
244                Expr::Ident(Ident::untyped("bar")),
245                vec![Expr::Ident(Ident::untyped("arg"))],
246            )),
247            Expr::Call(Call::untyped(
248                Expr::Ident(Ident::untyped("println")),
249                vec![Expr::Str(Literal::new("foo")), Expr::Int(Literal::new(27))],
250            )),
251        ];
252        let actual: Vec<Expr> =
253            inputs.iter().map(|input| parse(input).expr().unwrap()).collect();
254        assert_eq!(expected, actual);
255    }
256
257    #[test]
258    fn test_block() {
259        let input = b" {
260            27;
261            foo(bar);
262        }";
263        let expected = Block(vec![
264            Stmt::Expr(Expr::Int(Literal::new(27))),
265            Stmt::Expr(Expr::Call(Call::untyped(
266                Expr::Ident(Ident::untyped("foo")),
267                vec![Expr::Ident(Ident::untyped("bar"))],
268            ))),
269        ]);
270        let actual = parse(input).block().unwrap();
271        assert_eq!(expected, actual);
272    }
273
274    #[test]
275    fn test_param() {
276        let input = b" foo : bar ";
277        let expected = Param::untyped("foo", TypeSpec::Simple(String::from("bar")));
278        let actual = parse(input).param().unwrap();
279        assert_eq!(expected, actual);
280    }
281
282    #[test]
283    fn test_let() {
284        let input = b"let foo: int = 7;";
285        let expected = Stmt::Let(Binding {
286            name: String::from("foo"),
287            typ: TypeSpec::Simple(String::from("int")),
288            expr: Expr::Int(Literal::new(7)),
289            resolved_type: (),
290        });
291        let actual = parse(input).let_stmt().unwrap();
292        assert_eq!(expected, actual);
293    }
294
295    #[test]
296    fn test_binary() {
297        let input = b"x + y + (5 + 4) + foo(7, 10) + z + ((a + b) + c)";
298        let expected = Expr::Binary(Binary::untyped(
299            BinaryOp::Add,
300            Expr::Binary(Binary::untyped(
301                Add,
302                Expr::Binary(Binary::untyped(
303                    Add,
304                    Expr::Binary(Binary::untyped(
305                        Add,
306                        Expr::Binary(Binary::untyped(
307                            Add,
308                            Expr::Ident(Ident::untyped("x")),
309                            Expr::Ident(Ident::untyped("y")),
310                        )),
311                        Expr::Binary(Binary::untyped(
312                            Add,
313                            Expr::Int(Literal::new(5)),
314                            Expr::Int(Literal::new(4)),
315                        )),
316                    )),
317                    Expr::Call(Call::untyped(
318                        Expr::Ident(Ident::untyped("foo")),
319                        vec![
320                            Expr::Int(Literal::new(7)),
321                            Expr::Int(Literal::new(10)),
322                        ],
323                    )),
324                )),
325                Expr::Ident(Ident::untyped("z")),
326            )),
327            Expr::Binary(Binary::untyped(
328                Add,
329                Expr::Binary(Binary::untyped(
330                    Add,
331                    Expr::Ident(Ident::untyped("a")),
332                    Expr::Ident(Ident::untyped("b")),
333                )),
334                Expr::Ident(Ident::untyped("c")),
335            )),
336        ));
337        let actual = parse(input).expr().unwrap();
338        assert_eq!(expected, actual);
339    }
340
341    #[test]
342    fn test_fn() {
343        let input = b" fn hello ( world: int, all: str ) { foo(27); } ";
344        let expected = Func::untyped(
345            "hello",
346            vec![
347                Param::untyped("world", TypeSpec::Simple(String::from("int"))),
348                Param::untyped("all", TypeSpec::Simple(String::from("str"))),
349            ],
350            Block(vec![Stmt::Expr(Expr::Call(Call::untyped(
351                Expr::Ident(Ident::untyped("foo")),
352                vec![Expr::Int(Literal::new(27))],
353            )))]),
354            None,
355        );
356        let actual = parse(input).fn_expr().unwrap();
357        assert_eq!(expected, actual);
358    }
359
360    #[test]
361    fn test_hello_world() {
362        let input = b"
363            fn foo(s: str, t: int) {
364                println(s, t);
365            }
366
367            fn main() {
368                foo(\"hello, world\");
369            }
370        ";
371
372        let ast = parse(input).program().unwrap();
373        let expected = Program {
374            main_def: (),
375            defs: vec![
376                Def::FnDef(Func::untyped(
377                    "foo",
378                    vec![
379                        Param::untyped("s", TypeSpec::Simple(String::from("str"))),
380                        Param::untyped("t", TypeSpec::Simple(String::from("int"))),
381                    ],
382                    Block(vec![Stmt::Expr(Expr::Call(Call::untyped(
383                        Expr::Ident(Ident::untyped("println")),
384                        vec![
385                            Expr::Ident(Ident::untyped("s")),
386                            Expr::Ident(Ident::untyped("t")),
387                        ],
388                    )))]),
389                    None,
390                )),
391                Def::FnDef(Func::untyped(
392                    "main",
393                    vec![],
394                    Block(vec![Stmt::Expr(Expr::Call(Call::untyped(
395                        Expr::Ident(Ident::untyped("foo")),
396                        vec![Expr::Str(Literal::new("hello, world"))],
397                    )))]),
398                    None,
399                )),
400            ],
401        };
402        assert_eq!(expected, ast);
403    }
404}
june_lang/parser.rs

june_lang/
parser.rs
