Introduce recursive descent parser

1 files changed, 44 insertions, 21 deletions

diff --git a/rust/src/parser.rs b/rust/src/parser.rs
index 2c2dced..3ec0ab2 100644
--- a/rust/src/parser.rs
+++ b/rust/src/parser.rs
@@ -7,34 +7,57 @@ enum Token {
     Word(String),
 }
 
-pub fn parse(arg: &str) -> Value {
-    let mut tokens = tokenize(arg);
-    let mut state = Vec::new();
-    parse_tokens(&mut tokens, &mut state).unwrap_or_else(|_| panic!("Syntax) error: {}", arg))
+struct Parser {
+    tokens: Vec<Token>,
+    index: usize,
 }
 
-fn parse_tokens(tokens: &mut [Token], state: &mut Vec<Value>) -> Result<Value, String> {
-    match tokens {
-        [] => state.pop().ok_or("Empty expression".to_string()),
-        [Token::LParen, rest @ ..] => parse_tokens(rest, state),
-        [Token::RParen, rest @ ..] => {
-            let right = state.pop().ok_or("Unbalanced parentheses".to_string())?;
-            let left = state.pop().ok_or("Unbalanced parentheses".to_string())?;
-            state.push(Value::App(Box::new(left), Box::new(right)));
-            parse_tokens(rest, state)
-        }
-        [Token::Word(s), rest @ ..] => {
-            let value = parse_value(&Token::Word(s.clone()))?;
-            state.push(value);
-            parse_tokens(rest, state)
+impl Parser {
+    fn expect(&self, token: Token) -> Result<(), String> {
+        if self.tokens.get(self.index) == Some(&token) {
+            Ok(())
+        } else {
+            Err(format!(
+                "Expected {:?}, got {:?}",
+                token,
+                self.tokens.get(self.index)
+            ))
         }
     }
+
+    fn next(&mut self) {
+        self.index += 1;
+    }
+}
+
+pub fn parse(arg: &str) -> Value {
+    let tokens = tokenize(arg);
+    let mut parser = Parser { tokens, index: 0 };
+    parse_expression(&mut parser)
+        .map_err(|e| panic!("Syntax error: {}", e))
+        .unwrap()
+}
+
+fn parse_expression(parser: &mut Parser) -> Result<Value, String> {
+    parse_application(parser).or(parse_value(parser))
+}
+
+fn parse_application(parser: &mut Parser) -> Result<Value, String> {
+    parser.expect(Token::LParen)?;
+    parser.next();
+    let left = parse_expression(parser)?;
+    let right = parse_expression(parser)?;
+    parser.expect(Token::RParen)?;
+    Ok(Value::App(Box::new(left), Box::new(right)))
 }
 
-fn parse_value(token: &Token) -> Result<Value, String> {
-    parse_number(token)
+fn parse_value(parser: &mut Parser) -> Result<Value, String> {
+    let token = parser.tokens.get(parser.index).ok_or("Expected a value")?;
+    let val = parse_number(token)
         .or(parse_bool(token))
-        .or(parse_symbol(token))
+        .or(parse_symbol(token))?;
+    parser.next();
+    Ok(val)
 }
 
 fn tokenize(arg: &str) -> Vec<Token> {