用 Rust 编写一个简单的词法分析器

词法分析是编译器和解释器的第一个环节，相对而言也比较简单。词法分析器（有时也称为单元生成器（tokenizer）或者扫描器（scanner）） 将源代码转换为词法单元，这个过程称为词法分析。

本文代码设计复刻自《用Go语言自制解释器》词法分析器一章，文章结构、编码过程根据笔者理解重新阐述。

词法分析器

词法分析的过程会遍历输入的字符，然后逐个输出识别的词法单元。这个过程不需要缓冲区，也不需要保存词法单元，只需要不断地输出下一个 Token，我们可以考虑使用迭代器来完成这个设计。

定义词法单元

假设有这样一段（伪）代码：

let five = 5;
let ten = 10;

let add = fn(x, y) {
    x + y;
}

let result = add(five, ten);

这样的代码里可以分类成以下几种元素（词法单元）：

• 数字：5、10
• 变量名：five、ten、add、result
• 关键字（保留字）：let、fn
• 符号：+、{ 、}、;

词法分析器做的事情就是从头至尾扫描一遍，依次输出对应的分类。用 Rust 表示这个输出结果，可以设计成：

type TokenType = &'static str;

pub struct Token {
   
    pub token_type: TokenType,
    pub literal: String,
}

具体的 TokenType 可以直接使用 const 常量进行定义：

// 标识符 + 字面量
const IDENT: TokenType = "IDENT";
const INT: TokenType = "INT";

// 运算符
const ASSIGN: TokenType = "=";
const PLUS: TokenType = "+";

// 分隔符
const COMMA: TokenType = ",";
const SEMICOLON: TokenType = ";";

const LPAREN: TokenType = "(";
const RPAREN: TokenType = ")";
const LBRACE: TokenType = "{";
const RBRACE: TokenType = "}";

// 关键字
const FUNCTION: TokenType = "FUNCTION";
const LET: TokenType = "LET";

如果用户出现非法的输入，同样需要有一个类型来指代。除此之外，每一段代码都会有结尾 \0，通常会使用 EOF 来表示，因此引入两个特殊的类型：

const ILLEGAL: TokenType = "ILLEGAL";
const EOF: TokenType = "EOF";

测试驱动：第一个失败的单元测试

我们先思考清楚我们需要什么，先写一个测试，让测试先失败：

#[test]
fn test_next_token() {
   
    let input = String::from("=");
    let excepted = vec![ASSIGN, EOF];
    let lex = Lexer::new(input);

    for (i, token) in lex.iter().enumerate() {
   
        assert_eq!(token.token_type, excepted[i]);
    }
}

我们现在还没有动手写代码，这个测试连编译都不会通过，因为压根没有 Lexer。

error[E0433]: failed to resolve: use of undeclared type `Lexer`
  --> src\token.rs:36:15
   |
36 |     let lex = Lexer::new(input);
   |               ^^^^^ use of undeclared type `Lexer`

按照测试驱动开发的理念，我们应该写最少的代码，让这段代码通过测试，即使我们作弊。由于我们最开始就认为用迭代器来完成词法分析器的设计是合适的，那么就有必要了解一下 Rust 迭代器的语法。

Rust 迭代器

要实现自定义类型的迭代器，只需要实现 Iterator trait 即可。根据测试所设想的，Lexer 接收一个文本作为初始化：

pub struct Lexer {
   
    input: String,
}

impl Lexer {
   
    pub fn new(input: String) -> Lexer {
   
        Lexer {
    input }
    }
}

依据 Rust 迭代器的惯用法，我们定义一个 iter 获得 Lexer 的迭代器：

    pub fn iter(&self) -> LexerIter {
   
        LexerIter::new(self.input.as_str())
    }

我们现在需要在 LexerIter 上实现 Iterator。

pub struct LexerIter<'a> {
   
    lex_input: &'a str,
    pos: usize,
    read_pos: usize,
    ch: u8,
}

等完成大体 demo 后，再考虑支持 UTF-8。

• lex_input：源代码文本
• pos：当前（起始）位置
• red_pos：读取的位置（也用来标识读取的结尾）
• ch：当前字符

对于一个专业的编程语言，这里应该需要记录代码行号。简单起见，这里就不折腾了。其实也不难，只需要额外处理 \n，增加一个变量作为行号计数器即可。

实现 new 方法和 read_char：

impl LexerIter<'_> {
   
    fn new(lex: &str) -> LexerIter {
   
        let mut t = LexerIter {
   
            lex_input: lex,
            pos: 0,
            read_pos: 0,
            ch: 0,
        };
        t.read_char();
        t
    }

    fn read_char(&mut self) {
   
        if self.read_pos >= self.lex_input.len() {
   
            self.ch = 0;
        } else {
   
            let temp = self.lex_input.as_bytes();
            self.ch = temp[self.read_pos];
        }
        self.pos = self.read_pos;
        self.read_pos += 1;
    }
}

为 LexerIter 实现 Iterator，根据最开始想法，我们只需要实现 next 方法即可。Rust 中 Iterator 的部分定义如下：

pub trait Iterator {
   
    type Item;

    fn next(&mut self)