1use std::collections::VecDeque;
2
3use crate::ast::{
4 AdditiveOperator, Expression, ExpressionListElement, Factor, Line, MultiplicativeOperator,
5 NumberLiteral, RelationalOperator, Statement, StringLiteral, Term, Variable,
6};
7use crate::token::Token;
8
9#[derive(Debug, PartialEq)]
10pub enum Error {
11 UnexpectedToken { expected: Token, found: Token },
12 VariableNotFound,
13 NoMoreToken,
14 RelationalOperatorNotFound,
15 KeywordNotFound,
16 LineNumberOutOfRange,
17}
18
19pub struct Parser {
20 tokens: VecDeque<Token>,
21}
22
23impl Parser {
24 pub fn new(tokens: VecDeque<Token>) -> Self {
25 Self { tokens }
26 }
27
28 pub fn parse_line(&mut self) -> Result<Line, Error> {
29 let line_number = match self.peek_token() {
30 Some(Token::NumberLiteral(value)) => match u8::try_from(value) {
31 Ok(line_number) => {
32 self.consume_token();
33 Some(line_number)
34 }
35 Err(_) => Err(Error::LineNumberOutOfRange)?,
36 },
37 _ => Option::None,
38 };
39
40 let statement = self.parse_statement()?;
41
42 Ok(Line::new(line_number, statement))
43 }
44
45 fn consume_token(&mut self) -> Option<Token> {
46 self.tokens.pop_front()
47 }
48
49 fn peek_token(&self) -> Option<Token> {
50 self.tokens.front().cloned()
51 }
52
53 fn expect(&mut self, expected: Token) -> Result<(), Error> {
54 match self.consume_token() {
55 Some(token) => {
56 if token == expected {
57 Ok(())
58 } else {
59 Err(Error::UnexpectedToken {
60 expected,
61 found: token,
62 })
63 }
64 }
65 None => Err(Error::NoMoreToken),
66 }
67 }
68
69 fn parse_statement(&mut self) -> Result<Statement, Error> {
70 let statement = match self.consume_token() {
71 Some(Token::Print) => {
72 let mut expression_list = Vec::new();
73
74 loop {
75 match self.peek_token() {
76 Some(Token::StringLiteral { value }) => {
77 self.consume_token();
78 let element =
79 ExpressionListElement::StringLiteral(StringLiteral::new(value));
80 expression_list.push(element);
81 }
82 _ => {
83 let expression = self.parse_expression()?;
84 let element = ExpressionListElement::Expression(expression);
85 expression_list.push(element);
86 }
87 }
88
89 if let Some(Token::Comma) = self.peek_token() {
90 self.consume_token();
91 } else {
92 break;
93 }
94 }
95
96 Statement::Print { expression_list }
97 }
98 Some(Token::If) => {
99 let left = self.parse_expression()?;
100 let operator = match self.consume_token() {
101 Some(Token::Equal) => RelationalOperator::Equal,
102 Some(Token::NotEqual) => RelationalOperator::NotEqual,
103 Some(Token::LessThan) => RelationalOperator::LessThan,
104 Some(Token::LessThanOrEqual) => RelationalOperator::LessThanOrEqual,
105 Some(Token::GreaterThan) => RelationalOperator::GreaterThan,
106 Some(Token::GreaterThanOrEqual) => RelationalOperator::GreaterThanOrEqual,
107 _ => Err(Error::RelationalOperatorNotFound)?,
108 };
109 let right = self.parse_expression()?;
110 self.expect(Token::Then)?;
111 let then = Box::new(self.parse_statement()?);
112 Statement::If {
113 left,
114 operator,
115 right,
116 then,
117 }
118 }
119 Some(Token::Goto) => {
120 let expression = self.parse_expression()?;
121 Statement::Goto { expression }
122 }
123 Some(Token::Input) => {
124 let mut variable_list = Vec::new();
125 loop {
126 match self.consume_token() {
127 Some(Token::Variable { identifier }) => {
128 let variable = Variable::new(identifier);
129 variable_list.push(variable);
130 }
131 _ => Err(Error::VariableNotFound)?,
132 }
133
134 if let Some(Token::Comma) = self.peek_token() {
135 self.consume_token();
136 } else {
137 break;
138 }
139 }
140 Statement::Input { variable_list }
141 }
142 Some(Token::Let) => {
143 let variable = match self.consume_token() {
144 Some(Token::Variable { identifier }) => Variable::new(identifier),
145 _ => Err(Error::VariableNotFound)?,
146 };
147 self.expect(Token::Equal)?;
148 let expression = self.parse_expression()?;
149 Statement::Let {
150 variable,
151 expression,
152 }
153 }
154 Some(Token::GoSub) => {
155 let expression = self.parse_expression()?;
156 Statement::GoSub { expression }
157 }
158 Some(Token::Return) => Statement::Return,
159 Some(Token::Clear) => Statement::Clear,
160 Some(Token::List) => Statement::List,
161 Some(Token::Run) => Statement::Run,
162 Some(Token::End) => Statement::End,
163 None => Err(Error::NoMoreToken)?,
164 _ => Err(Error::KeywordNotFound)?,
165 };
166
167 Ok(statement)
168 }
169
170 fn parse_expression(&mut self) -> Result<Expression, Error> {
171 let unary_operator = match self.peek_token() {
172 Some(Token::Plus) => {
173 self.consume_token();
174 Some(AdditiveOperator::Addition)
175 }
176 Some(Token::Minus) => {
177 self.consume_token();
178 Some(AdditiveOperator::Subtraction)
179 }
180 _ => None,
181 };
182 let term = self.parse_term()?;
183 let mut others = Vec::new();
184
185 loop {
186 match self.peek_token() {
187 Some(Token::Plus) => {
188 self.consume_token();
189 let term = self.parse_term()?;
190 others.push((AdditiveOperator::Addition, term));
191 }
192 Some(Token::Minus) => {
193 self.consume_token();
194 let term = self.parse_term()?;
195 others.push((AdditiveOperator::Subtraction, term));
196 }
197 _ => break,
198 }
199 }
200
201 Ok(Expression::new(unary_operator, term, others))
202 }
203
204 fn parse_term(&mut self) -> Result<Term, Error> {
205 let factor = self.parse_factor()?;
206 let mut operations = Vec::new();
207
208 loop {
209 match self.peek_token() {
210 Some(Token::Multiply) => {
211 self.consume_token();
212 let factor = self.parse_factor()?;
213 operations.push((MultiplicativeOperator::Multiplication, factor));
214 }
215 Some(Token::Divide) => {
216 self.consume_token();
217 let factor = self.parse_factor()?;
218 operations.push((MultiplicativeOperator::Division, factor));
219 }
220 _ => break,
221 }
222 }
223
224 Ok(Term::new(factor, operations))
225 }
226
227 fn parse_factor(&mut self) -> Result<Factor, Error> {
228 match self.peek_token() {
229 Some(Token::Variable { identifier }) => {
230 self.consume_token();
231 let variable = Variable::new(identifier);
232 Ok(Factor::Variable(variable))
233 }
234 Some(Token::NumberLiteral(value)) => {
235 self.consume_token();
236 Ok(Factor::NumberLiteral(NumberLiteral::new(value)))
237 }
238 _ => {
239 self.expect(Token::OpeningParenthesis)?;
240 let expression = Box::new(self.parse_expression()?);
241 self.expect(Token::ClosingParenthesis)?;
242 Ok(Factor::Expression(expression))
243 }
244 }
245 }
246}
247
248#[cfg(test)]
249mod tests {
250 use super::*;
251
252 #[test]
253 fn parse_line_hello_world_returns_ast() {
254 let tokens = VecDeque::from([
255 Token::NumberLiteral(10),
256 Token::Print,
257 Token::StringLiteral {
258 value: b"Hello, World!".to_vec(),
259 },
260 ]);
261 let expected = Line::new(
262 Some(10),
263 Statement::Print {
264 expression_list: vec![ExpressionListElement::StringLiteral(StringLiteral::new(
265 b"Hello, World!".to_vec(),
266 ))],
267 },
268 );
269 let mut parser = Parser::new(tokens);
270
271 let actual = parser.parse_line();
272
273 assert_eq!(Ok(expected), actual);
274 }
275
276 #[test]
277 fn parse_line_terms_returns_ast() {
278 let tokens = VecDeque::from([
279 Token::NumberLiteral(10),
280 Token::Print,
281 Token::NumberLiteral(2),
282 Token::Plus,
283 Token::NumberLiteral(3),
284 ]);
285
286 let expected = Line::new(
287 Some(10),
288 Statement::Print {
289 expression_list: vec![ExpressionListElement::Expression(Expression::new(
290 None,
291 Term::new(Factor::NumberLiteral(NumberLiteral::new(2)), vec![]),
292 vec![(
293 AdditiveOperator::Addition,
294 Term::new(Factor::NumberLiteral(NumberLiteral::new(3)), vec![]),
295 )],
296 ))],
297 },
298 );
299 let mut parser = Parser::new(tokens);
300
301 let actual = parser.parse_line();
302
303 assert_eq!(Ok(expected), actual);
304 }
305
306 #[test]
307 fn parse_line_with_unary_operator_returns_ast() {
308 let tokens = VecDeque::from([
309 Token::NumberLiteral(10),
310 Token::Print,
311 Token::Minus,
312 Token::NumberLiteral(2),
313 Token::Plus,
314 Token::NumberLiteral(3),
315 ]);
316 let expected = Line::new(
317 Some(10),
318 Statement::Print {
319 expression_list: vec![ExpressionListElement::Expression(Expression::new(
320 Some(AdditiveOperator::Subtraction),
321 Term::new(Factor::NumberLiteral(NumberLiteral::new(2)), vec![]),
322 vec![(
323 AdditiveOperator::Addition,
324 Term::new(Factor::NumberLiteral(NumberLiteral::new(3)), vec![]),
325 )],
326 ))],
327 },
328 );
329 let mut parser = Parser::new(tokens);
330
331 let actual = parser.parse_line();
332
333 assert_eq!(Ok(expected), actual);
334 }
335}