3
\$\begingroup\$

I'm writing a Scheme interpreter in Rust, and the first step is the parser. I've finished the lexer, and would like to see what people think of it before I go any further.

#[derive(Debug, PartialEq)]
enum LexToken {
    Num(f64),
    Symbol(String),
    String(String),
    LeftBracket,
    RightBracket,
}

fn lex_input(input: &str) -> Result<Vec<LexToken>, &'static str> {
    let mut output = Vec::new();

    let input_length = input.len();
    let mut current_idx = 0;

    while current_idx < input_length {
        if let Some((lexed_string, new_idx)) = lex_string(&input, current_idx) {
            output.push(lexed_string);
            current_idx = new_idx;
            continue;
        }

        if let Some((lexed_number, new_idx)) = lex_number(&input, current_idx) {
            output.push(lexed_number);
            current_idx = new_idx;
            continue;
        }

        if let Some((lexed_left_bracket, new_idx)) = lex_left_bracket(&input, current_idx) {
            output.push(lexed_left_bracket);
            current_idx = new_idx;
            continue;
        }

        if let Some((lexed_right_bracket, new_idx)) = lex_right_bracket(&input, current_idx) {
            output.push(lexed_right_bracket);
            current_idx = new_idx;
            continue;
        }

        if let Some(new_idx) = lex_whitespace(&input, current_idx) {
            current_idx = new_idx;
            continue;
        }

        if let Some((lexed_symbol, new_idx)) = lex_symbol(&input, current_idx) {
            output.push(lexed_symbol);
            current_idx = new_idx;
            continue;
        }
    }

    Ok(output)
}

fn lex_string(input: &str, from_idx: usize) -> Option<(LexToken, usize)> {
    if input
        .chars()
        .nth(from_idx)
        .expect("Lexxer skipped past the end of the input")
        != '"'
    {
        return None;
    }

    let output = input
        .chars()
        .skip(from_idx + 1)
        .take_while(|&char| char != '"')
        .collect::<String>();

    Some((
        LexToken::String(output.to_string()),
        from_idx + output.len() + 2,
    ))
}

fn lex_left_bracket(input: &str, from_idx: usize) -> Option<(LexToken, usize)> {
    if input
        .chars()
        .nth(from_idx)
        .expect("Lexxer skipped past the end of the input")
        != '('
    {
        return None;
    }

    Some((LexToken::LeftBracket, from_idx + 1))
}

fn lex_right_bracket(input: &str, from_idx: usize) -> Option<(LexToken, usize)> {
    if input
        .chars()
        .nth(from_idx)
        .expect("Lexxer skipped past the end of the input")
        != ')'
    {
        return None;
    }

    Some((LexToken::RightBracket, from_idx + 1))
}

fn lex_whitespace(input: &str, from_idx: usize) -> Option<usize> {
    if input
        .chars()
        .nth(from_idx)
        .expect("Lexxer skipped past the end of the input")
        .is_whitespace()
    {
        return Some(from_idx + 1);
    }

    None
}

fn lex_number(input: &str, from_idx: usize) -> Option<(LexToken, usize)> {
    let next_char = input
        .chars()
        .nth(from_idx)
        .expect("Lexxer skipped past the end of the input");
    if !next_char.is_numeric() && next_char != '-' && next_char != '.' {
        return None;
    }

    let num_as_string = input
        .chars()
        .skip(from_idx)
        .take_while(|&char| char.is_numeric() || char == '.' || char == 'e' || char == '-')
        .collect::<String>();

    match num_as_string.parse::<f64>() {
        Ok(num) => Some((LexToken::Num(num), from_idx + num_as_string.len())),
        Err(_) => None,
    }
}

fn lex_symbol(input: &str, from_idx: usize) -> Option<(LexToken, usize)> {
    let output = input
        .chars()
        .skip(from_idx)
        .take_while(|&char| !char.is_whitespace() && char != '(' && char != ')')
        .collect::<String>();

    Some((
        LexToken::Symbol(output.to_string()),
        from_idx + output.len(),
    ))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn lex_brackets() {
        let input = "()";

        let expected_output = vec![LexToken::LeftBracket, LexToken::RightBracket];

        compare(input, expected_output);
    }

    #[test]
    fn lex_string() {
        let input = "\"scheme\"";

        let expected_output = vec![LexToken::String("scheme".to_string())];

        compare(input, expected_output);
    }

    #[test]
    fn lex_list_of_strings() {
        let input = "(\"little\" \"scheme\")";

        let expected_output = vec![
            LexToken::LeftBracket,
            LexToken::String("little".to_string()),
            LexToken::String("scheme".to_string()),
            LexToken::RightBracket,
        ];

        compare(input, expected_output);
    }

    #[test]
    fn lex_list_of_strings_with_whitespace() {
        let input = "  (  \"little\"   \"scheme\"  )  ";

        let expected_output = vec![
            LexToken::LeftBracket,
            LexToken::String("little".to_string()),
            LexToken::String("scheme".to_string()),
            LexToken::RightBracket,
        ];

        compare(input, expected_output);
    }

    #[test]
    fn lex_number() {
        let tests = vec![
            ("123", LexToken::Num(123f64)),
            ("0.123", LexToken::Num(0.123f64)),
            ("-0.1e-5", LexToken::Num(-0.1e-5f64)),
        ];

        for (input, expect) in tests {
            compare(input, vec![expect]);
        }
    }

    #[test]
    fn lex_list_of_numbers() {
        let input = "(123 0.123 -0.1e-5)";

        let expected_output = vec![
            LexToken::LeftBracket,
            LexToken::Num(123f64),
            LexToken::Num(0.123f64),
            LexToken::Num(-0.1e-5f64),
            LexToken::RightBracket,
        ];

        compare(input, expected_output);
    }

    #[test]
    fn lex_symbol() {
        let tests = vec![
            ("some_func", LexToken::Symbol("some_func".to_string())),
            ("-", LexToken::Symbol("-".to_string())),
            ("e", LexToken::Symbol("e".to_string())),
        ];

        for (input, expect) in tests {
            compare(input, vec![expect]);
        }
    }

    #[test]
    fn lex_list_of_symbols() {
        let input = "(somefunc #some_symbol -)";

        let expected_output = vec![
            LexToken::LeftBracket,
            LexToken::Symbol("somefunc".to_string()),
            LexToken::Symbol("#some_symbol".to_string()),
            LexToken::Symbol("-".to_string()),
            LexToken::RightBracket,
        ];

        compare(input, expected_output);
    }

    fn compare(input: &str, expected_output: Vec<LexToken>) {
        let actual_output = lex_input(input).unwrap();

        assert_eq!(actual_output, expected_output);
    }
}

\$\endgroup\$
1

1 Answer 1

3
\$\begingroup\$

You have several variations on this in your code:

    if input
        .chars()
        .nth(from_idx)
        .expect("Lexxer skipped past the end of the input")
        != '"'
    {
        return None;
    }

This is problematic. In general, taking nth item in an iterator isn't going to be very efficient, since it has to iterate through all the previous elements in the iterator to get there. Some iterators may override this with a fast implementation, but str.chars() because the string is UTF-8 which has variable length characters. So it has to read through the string counting up the characters. Because you do this in a loop, you are going through the input string over and over and over again.

A possible alternative is to pass around a mutable reference to the std::char::Chars object returned by str.chars(). Then you can have each lexing function move the iterator forward as it consume characters. This approach can be helped by using .peekable() to create an iterator with a peek() method that lets you look at the next item in the iterator without consuming it. Also, you can clone() this iterator to remember a particular position in the string, and assign to an iterator to reset it to a previous position.

But what I'd actually do is define a struct, something like

struct Reader {
    currentLine: u32,
    currentColumn: u32,
    buffer: String,
    source: std::io::Read
}

This struct:

  1. Reads from a std::io::Read, so it can be used with files/in memory data/whatever.
  2. Keeps track of the current line and column, probably quite useful for reporting errors.
  3. Provides utility functions to peek/consume data from the stream in a way conducive to implementing the lexer.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.