4
\$\begingroup\$

A follow up to my previous question which was on the token library that this lexer produces a stream of.

View the full project, the tokens library, the parser combinator library, or this lexer library on GitHub (pinned to the relevant commit). Documentation is available (built from master) for nnom, tokens, and lexer.

This is the lexer for the language I've been working on. Its job is to take a string and parse it into tokens, which will then be piped into later steps of the language processing. As an example use, here is the REPL I wrote for the lexer:

extern crate nafi_lexer;
use std::io;

fn main() {
    let mut buffer = String::with_capacity(80);
    loop {
        buffer.clear();
        io::stdin().read_line(&mut buffer).expect("IO Failure");
        if buffer.is_empty() {
            break;
        }
        let tokens = nafi_lexer::lex(buffer.trim());
        println!("{:?}", tokens);
    }
}

You can run this locally by using cargo run --package=nafi-lexer after cloning the repository. It requires nightly rust, as I'm making use of impl Trait and the never type.

lib.rs

//! Transformation of NAFI source code into tokens

#![forbid(bad_style, missing_debug_implementations, unconditional_recursion, future_incompatible)]
#![deny(missing_docs, unsafe_code, unused)]
#![feature(conservative_impl_trait, const_fn, dotdoteq_in_patterns, never_type, option_filter)]

#[macro_use]
extern crate matches;
extern crate nafi_tokens as tokens;
extern crate nnom;
extern crate unic_ucd_category;

use nnom::ParseOutput;
use tokens::Token;

mod lexer;

/// Lex NAFI source into its component tokens
pub fn lex(s: &str) -> Vec<Token> {
    let Ok(ParseOutput { output, .. }) = lexer::tokens(s.into());
    output
}

lexer/mod.rs

use nnom::{ParseOutput, ParseResult};
use nnom::combinators::many0;
use nnom::slice::PositionedStr;
use tokens::{Keyword, Symbol, Token};
use unic_ucd_category::GeneralCategory;

mod literals;
mod unicode;
mod whitespace;

use self::literals::{integer_literal, string_literal};
use self::unicode::identifier;
use self::whitespace::whitespace;

pub fn tokens(input: PositionedStr) -> ParseResult<(), Vec<Token>, !> {
    many0(token)(input).map(
        |ParseOutput {
             remaining_input,
             output,
         }| {
            assert!(remaining_input.is_empty());
            ParseOutput {
                remaining_input: (),
                output,
            }
        },
    )
}

fn token(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    Err(())
        .or_else(|_| whitespace(input))
        .or_else(|_| integer_literal(input))
        .or_else(|_| string_literal(input))
        .or_else(|_| identifier_like(input))
        .or_else(|_| symbol(input))
        .or_else(|_| _unknown(input))
}

/// `Token::Identifier` or `Token::Keyword`
fn identifier_like(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    identifier(input).map(
        |ParseOutput {
             remaining_input,
             output,
         }| {
            ParseOutput {
                remaining_input,
                output: match &*output {
                    "let" => Token::Keyword(input.start(), Keyword::Let),
                    "mutable" => Token::Keyword(input.start(), Keyword::Mutable),
                    "if" => Token::Keyword(input.start(), Keyword::If),
                    "else" => Token::Keyword(input.start(), Keyword::Else),
                    _ => Token::Identifier(input.start(), (&*output).into()),
                },
            }
        },
    )
}

/// `Token::Symbol`
fn symbol(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    let ch = input.chars().next().ok_or(())?;
    let category = GeneralCategory::of(ch);
    if category.is_symbol() || category.is_punctuation() {
        Ok(ParseOutput {
            remaining_input: input.split_at(ch.len_utf8()).1,
            output: Token::Symbol(input.start(), Symbol::from(ch)),
        })
    } else {
        Err(())
    }
}

/// `Token::_Unknown`
fn _unknown(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    let ch = input.chars().next().ok_or(())?;
    Ok(ParseOutput {
        remaining_input: input.split_at(ch.len_utf8()).1,
        output: Token::_Unknown(input.start(), ch),
    })
}

lexer/literals.rs

use super::unicode::decimal_number;
use lexer::token;
use nnom::{ParseOutput, ParseResult};
use nnom::slice::PositionedStr;
use std::{char, u32};
use tokens::{StringFragments, Symbol, Token};

/// `Token::Literal(Literal::Integer)`
pub fn integer_literal(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    decimal_number(input).map(
        |ParseOutput {
             remaining_input,
             output,
         }| {
            ParseOutput {
                remaining_input,
                output: Token::Literal(input.start(), output.into()),
            }
        },
    )
}

// TODO: Break single-character escapes into reusable fn and build character_literal
/// `Token::Literal(Literal::String)`
pub fn string_literal(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    if !input.starts_with('"') {
        return Err(());
    }

    let mut remaining_input = input.split_at(1).1;
    let mut string = StringFragments::new();

    loop {
        match remaining_input.chars().next() {
            Some('\"') => {
                remaining_input = remaining_input.split_at(1).1;
                break;
            },
            Some('\\') => {
                remaining_input = remaining_input.split_at(1).1;
                match remaining_input.chars().next() {
                    Some(ch) if matches!(ch, '\\' | '\"' | '\'') => {
                        string.push_char(ch);
                        remaining_input = remaining_input.split_at(1).1;
                    },
                    Some('r') => {
                        string.push_char('\r');
                        remaining_input = remaining_input.split_at(1).1;
                    },
                    Some('n') => {
                        string.push_char('\n');
                        remaining_input = remaining_input.split_at(1).1;
                    },
                    Some('t') => {
                        string.push_char('\t');
                        remaining_input = remaining_input.split_at(1).1;
                    },
                    Some('u') => {
                        if remaining_input.starts_with("u{") {
                            if let Some(idx) = remaining_input.find('}') {
                                let codepoint = u32::from_str_radix(&remaining_input[2..idx], 16);
                                if let Ok(Some(ch)) = codepoint.map(char::from_u32) {
                                    string.push_char(ch);
                                } else {
                                    string.push_invalid_escape(&remaining_input[..idx + 1])
                                }
                                remaining_input = remaining_input.split_at(idx).1;
                            } else {
                                string.push_invalid_escape('u'.to_string());
                            }
                        } else {
                            string.push_invalid_escape('u'.to_string());
                        }
                        remaining_input = remaining_input.split_at(1).1;
                    },
                    Some('{') => {
                        remaining_input = remaining_input.split_at(1).1;
                        let mut tokens: Vec<Token> = vec![];
                        let mut depth = 1u32;
                        while let Ok(ParseOutput {
                            remaining_input: tail,
                            output,
                        }) = token(remaining_input)
                        {
                            remaining_input = tail;
                            match output {
                                Token::Symbol(_, Symbol::LeftCurlyBracket) => depth += 1,
                                Token::Symbol(_, Symbol::RightCurlyBracket) => {
                                    depth -= 1;
                                    if depth == 0 {
                                        break;
                                    }
                                },
                                _ => {},
                            }
                            tokens.push(output);
                        }
                        string.push_interpolation(tokens);
                    },
                    Some(s) => string.push_invalid_escape(s.to_string()),
                    None => break,
                }
            },
            Some(_) => {
                let idx = remaining_input
                    .find(|ch| matches!(ch, '\"' | '\\'))
                    .unwrap_or_else(|| remaining_input.len());
                let (uninteresting, rest) = remaining_input.split_at(idx);
                string.push_string(&*uninteresting);
                remaining_input = rest;
            },
            None => break,
        }
    }

    Ok(ParseOutput {
        remaining_input,
        output: Token::Literal(input.start(), string.into()),
    })
}

lexer/unicode.rs

use nnom::{ParseOutput, ParseResult};
use nnom::slice::PositionedStr;
use tokens::BigUint;

pub fn is_newline(ch: char) -> bool { matches!(ch as u32, 0xA..=0xD | 0x85 | 0x2028 | 0x2029) }

pub fn white_space(input: PositionedStr) -> ParseResult<PositionedStr, PositionedStr, ()> {
    let idx = input
        .char_indices()
        .filter(|&(_, ch)| !ch.is_whitespace())
        .map(|(idx, _)| idx)
        .next()
        .unwrap_or_else(|| input.len());
    if idx != 0 {
        let (output, remaining_input) = input.split_at(idx);
        Ok(ParseOutput {
            remaining_input,
            output,
        })
    } else {
        Err(())
    }
}

pub fn identifier(input: PositionedStr) -> ParseResult<PositionedStr, PositionedStr, ()> {
    // TODO: Use Unicode UAX31-R1 instead of this simple definition
    let mut chars = input.chars();
    if let Some(ch) = chars.next() {
        if !ch.is_alphabetic() {
            return Err(());
        }
        let idx = chars.take_while(|ch| ch.is_alphanumeric()).count() + 1;
        let (matched, remaining_input) = input.split_at(idx);
        Ok(ParseOutput {
            remaining_input,
            output: matched,
        })
    } else {
        Err(())
    }
}

pub fn decimal_number(input: PositionedStr) -> ParseResult<PositionedStr, BigUint, ()> {
    let idx = input.chars().take_while(|ch| ch.is_digit(10)).count();
    if idx != 0 {
        let (matched, remaining_input) = input.split_at(idx);
        Ok(ParseOutput {
            remaining_input,
            output: matched.parse().unwrap(),
        })
    } else {
        Err(())
    }
}

lexer/whitespace.rs

use super::unicode::{is_newline, white_space};
use nnom::{ParseOutput, ParseResult};
use nnom::slice::PositionedStr;
use tokens::Token;

/// `Token::Whitespace`
pub fn whitespace(input: PositionedStr) -> ParseResult<PositionedStr, Token, ()> {
    let mut rest = input;
    while let Ok(ParseOutput {
        remaining_input, ..
    }) = some_whitespace(rest)
    {
        rest = remaining_input;
    }
    if rest.start() != input.start() {
        Ok(ParseOutput {
            remaining_input: rest,
            output: Token::Whitespace(input.start()),
        })
    } else {
        Err(())
    }
}

/// Consume some whitespace.
fn some_whitespace(input: PositionedStr) -> ParseResult<PositionedStr, PositionedStr, ()> {
    Err(())
        .or_else(|_| white_space(input))
        .or_else(|_| line_comment(input))
        .or_else(|_| block_comment(input))
}

/// Parse a line comment
fn line_comment(input: PositionedStr) -> ParseResult<PositionedStr, PositionedStr, ()> {
    if !input.starts_with("//") {
        return Err(());
    }

    let idx = input.find(is_newline).unwrap_or_else(|| input.len());
    let (output, remaining_input) = input.split_at(idx);
    Ok(ParseOutput {
        remaining_input,
        output,
    })
}

/// Parse a block comment
fn block_comment(input: PositionedStr) -> ParseResult<PositionedStr, PositionedStr, ()> {
    if !input.starts_with("/*") {
        return Err(());
    }

    let mut idx: usize = 2;
    let mut depth = 1;

    while depth > 0 && idx < input.len() {
        let remaining_input = &input[idx..];
        if remaining_input.starts_with("/*") {
            depth += 1;
            idx += 2;
        } else if remaining_input.starts_with("*/") {
            depth -= 1;
            idx += 2;
        } else {
            idx += remaining_input.chars().next().unwrap().len_utf8();
        }
    }

    let (output, remaining_input) = input.split_at(idx);
    Ok(ParseOutput {
        remaining_input,
        output,
    })
}

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

    #[test]
    fn block_comment() {
        assert_eq!(
            super::block_comment("/** /* */*/".into()),
            Ok(ParseOutput {
                output: "/** /* */*/".into(),
                remaining_input: PositionedStr::new("", 11),
            })
        );
    }

    #[test]
    fn line_comment() {
        assert_eq!(
            super::line_comment("// any amount of text you want".into()),
            Ok(ParseOutput {
                output: "// any amount of text you want".into(),
                remaining_input: PositionedStr::new("", 30),
            })
        );
    }
}

This is a lot of code, so let me guide you to the most interesting parts that would most appreciate review:

  • nafi_lexer::lexer::whitespace::{whitespace, some_whitespace, line_comment, block_comment
    • Complicated enough I wrote tests for them (though I should definitely have more)
  • nafi_lexer::lexer::literals::string_literal
    • Most complicated parser fragment. Since I want string interpolation like "1 + 1 = \{1+1}" to work in my language, the lexer has to be recursive here. I definitely need some more tests here for more interesting cases like "\{"}"}" which used to break it.
  • Overall design. I've attempted to create a system built off of parser combinators. My library nnom is inspired by nom and synom, but minimal and without macros.
    • This also means I'm free to change the framework easily, so imports from nnom are fair game for comments.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.