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

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

词法分析器

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

定义词法单元

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

1
2
3
4
5
6
7
8
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 表示这个输出结果，可以设计成：

1
2
3
4
5
6
type TokenType = &'static str;

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 标识符 + 字面量
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 来表示，因此引入两个特殊的类型：

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

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

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

1
2
3
4
5
6
7
8
9
10
11

#[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。

1
2
3
4
5
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 接收一个文本作为初始化：

1
2
3
4
5
6
7
8
9
10
pub struct Lexer {
    input: String,
}

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

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

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

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

1
2
3
4
5
6
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：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 的部分定义如下：

1
2
3
4
5
6
7
pub trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;

    // ...
}

迭代的元素 Item 显然是 Token，为了快速通过测试，我们就简单实现一下原型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
impl Iterator for LexerIter<'_> {
    type Item = Token;

    fn next(&mut self) -> Option<Self::Item> {
        let length = self.lex_input.len();

        let res: Token = if self.pos > length {
            return None;
        } else {
            match self.ch as char {
                '=' => Token {
                    token_type: ASSIGN,
                    literal: ASSIGN.to_string(),
                },
                '\0' => Token {
                    token_type: EOF,
                    literal: "".to_string(),
                },
                _ => Token {
                    token_type: ILLEGAL,
                    literal: "".to_string(),
                },
            }
        };

        self.read_char();

        Some(res)
    }
}

跑一下 cargo test：

1
2
3
4
running 1 test
test token::test_next_token ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

到了这里，我们的词法分析器原型其实就已经有了。我们编写一个涵盖更多符号的输入，让测试失败，再补全词法分析器。

1
2
3
4
5
6
7
8
9
10
11
12
#[test]
fn test_next_token() {
    let input = String::from("=+(){},;");
    let excepted = vec![
        ASSIGN, PLUS, LPAREN, RPAREN, LBRACE, RBRACE, COMMA, SEMICOLON, EOF,
    ];
    let lex = Lexer::new(input);

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

补上其余的符号类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
impl Iterator for LexerIter<'_> {
    type Item = Token;

    fn next(&mut self) -> Option<Self::Item> {
        let length = self.lex_input.len();

        let res: Token = if self.pos > length {
            return None;
        } else {
            match self.ch as char {
                '=' => Token {
                    token_type: ASSIGN,
                    literal: ASSIGN.to_string(),
                },
                ';' => Token {
                    token_type: SEMICOLON,
                    literal: SEMICOLON.to_string(),
                },
                '(' => Token {
                    token_type: LPAREN,
                    literal: LPAREN.to_string(),
                },
                ')' => Token {
                    token_type: RPAREN,
                    literal: RPAREN.to_string(),
                },
                ',' => Token {
                    token_type: COMMA,
                    literal: COMMA.to_string(),
                },
                '+' => Token {
                    token_type: PLUS,
                    literal: PLUS.to_string(),
                },
                '{' => Token {
                    token_type: LBRACE,
                    literal: LBRACE.to_string(),
                },
                '}' => Token {
                    token_type: RBRACE,
                    literal: RBRACE.to_string(),
                },
                '\0' => Token {
                    token_type: EOF,
                    literal: "".to_string(),
                },
                _ => Token {
                    token_type: ILLEGAL,
                    literal: "".to_string(),
                },
            }
        };

        self.read_char();

        Some(res)
    }
}

这样测试就再一次通过了。

空白、标识符、数字

目前的词法分析器对于单个字符 char 进行匹配没有问题，然而代码中还会出现空白字符，还有不止一个字符组成的 Token，例如变量名、fn、50等等。

因此，如果我们检测到字符不是我们规定的符号，就应该继续判断是否属于数字或者其他类型，至于空白字符，从一开始就应该忽略掉（对于 Python，以空白缩进来界定代码区域的语法，就不能忽略空白字符了）。

我们同样从测试开始，写一段比较长的测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#[test]
fn test_code_frag_token() {
    let code = r#"let five = 5;
    let ten = 10;

    let add = fn(x, y) {
        x + y;
    };
    
    let result = add(five, ten);
    "#
    .to_string();
    let excepted = vec![
        Token {
            token_type: LET,
            literal: "let".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "five".to_string(),
        },
        Token {
            token_type: ASSIGN,
            literal: '='.to_string(),
        },
        Token {
            token_type: INT,
            literal: "5".to_string(),
        },
        Token {
            token_type: SEMICOLON,
            literal: ";".to_string(),
        },
        Token {
            token_type: LET,
            literal: "let".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "ten".to_string(),
        },
        Token {
            token_type: ASSIGN,
            literal: "=".to_string(),
        },
        Token {
            token_type: INT,
            literal: "10".to_string(),
        },
        Token {
            token_type: SEMICOLON,
            literal: ";".to_string(),
        },
        Token {
            token_type: LET,
            literal: "let".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "add".to_string(),
        },
        Token {
            token_type: ASSIGN,
            literal: "=".to_string(),
        },
        Token {
            token_type: FUNCTION,
            literal: "fn".to_string(),
        },
        Token {
            token_type: LPAREN,
            literal: "(".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "x".to_string(),
        },
        Token {
            token_type: COMMA,
            literal: ",".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "y".to_string(),
        },
        Token {
            token_type: RPAREN,
            literal: ")".to_string(),
        },
        Token {
            token_type: LBRACE,
            literal: "{".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "x".to_string(),
        },
        Token {
            token_type: PLUS,
            literal: "+".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "y".to_string(),
        },
        Token {
            token_type: SEMICOLON,
            literal: ";".to_string(),
        },
        Token {
            token_type: RBRACE,
            literal: "}".to_string(),
        },
        Token {
            token_type: SEMICOLON,
            literal: ";".to_string(),
        },
        Token {
            token_type: LET,
            literal: "let".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "result".to_string(),
        },
        Token {
            token_type: ASSIGN,
            literal: "=".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "add".to_string(),
        },
        Token {
            token_type: LPAREN,
            literal: "(".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "five".to_string(),
        },
        Token {
            token_type: COMMA,
            literal: ",".to_string(),
        },
        Token {
            token_type: IDENT,
            literal: "ten".to_string(),
        },
        Token {
            token_type: RPAREN,
            literal: ")".to_string(),
        },
        Token {
            token_type: SEMICOLON,
            literal: ";".to_string(),
        },
        Token {
            token_type: EOF,
            literal: "".to_string(),
        },
    ];

    let lex = Lexer::new(code);

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

这段测试显然会失败。

忽略空白字符

忽略空白字符就比较简单了，只要循环读取并判断是否是空白字符即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
impl LexerIter<'_> {
    
    //...

    fn skip_white_space(&mut self) {
        let mut ch = self.ch as char;

        while ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' {
            self.read_char();
            ch = self.ch as char;
        }
    }
}

跳过空白字符串的操作应该在 match 之前：

1
2
3
4
5
6
7
8
9
10
impl Iterator for LexerIter<'_> {
    type Item = Token;

    fn next(&mut self) -> Option<Self::Item> {
        let length = self.lex_input.len();

        self.skip_white_space();
        
        // ...

读取标识符

对于一个标识符的组成，我们假定只能是大、小写字母和下划线 _，因此如果读取到的是这些字符，进入标识符的读取操作。

1
2
3
fn is_letter(ch: char) -> bool {
    ('a'..='z').contains(&ch) || ('A'..='Z').contains(&ch) || ch == '_'
}

读取标识符的操作：

1
2
3
4
5
6
7
8
9
10
11
12
impl LexerIter<'_> {
    
    //...

    fn read_identifier(&mut self) -> String {
        let p = self.pos;
        while is_letter(self.ch as char) {
            self.read_char()
        }

        self.lex_input[p..self.pos].to_string()
    }

读取到有可能是我们已经规定的关键字，例如 fn、let，因此我们需要将这些保留字识别出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
use std::collections::HashMap;

fn look_up_ident(ident: &str) -> TokenType {
    let mut key_words = HashMap::new();
    key_words.insert("fn", FUNCTION);
    key_words.insert("let", LET);

    if key_words.contains_key(ident) {
        return key_words[ident];
    }

    IDENT
}

注意，look_up_ident 可以直接作为全局函数，并不需要包含进特定的实现里。到了这里，我们就可以在 match 处理标识符了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// ...
                _ => {
                    if is_letter(self.ch as char) {
                        let literal = self.read_identifier();
                        let token_type: TokenType = look_up_ident(literal.as_str());
                        return Some(Token {
                            token_type,
                            literal,
                        });
                    } else {
                        Token {
                            token_type: ILLEGAL,
                            literal: "".to_string(),
                        }
                    }
                }

和 read_identifier 最后的索引指针停留在下一个字符了，因此需要跳过接下来的 read_char() 操作，否则会导致随后的字符被跳过。因此直接 return

读取数字

同样的逻辑读取数字：

1
2
3
fn is_digit(ch: char) -> bool {
    ('0'..='9').contains(&ch)
}

同样地：

1
2
3
4
5
6
7
8
9
10
11
12
impl LexerIter<'_> {
    
    //...

    fn read_number(&mut self) -> String {
        let p = self.pos;
        while is_digit(self.ch as char) {
            self.read_char()
        }

        self.lex_input[p..self.pos].to_string()
    }

同样在 match 处理进行处理，_ 部分完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
_ => {
    if is_letter(self.ch as char) {
        let literal = self.read_identifier();
        let token_type: TokenType = look_up_ident(literal.as_str());
        return Some(Token {
            token_type,
            literal,
        });
    } else if is_digit(self.ch as char) {
        return Some(Token {
            token_type: INT,
            literal: self.read_number(),
        });
    } else {
        Token {
            token_type: ILLEGAL,
            literal: "".to_string(),
        }
    }
}

和 read_identifier 一样，read_number 最后的索引指针停留在下一个字符了，因此需要跳过接下来的 read_char() 操作，否则会导致随后的字符被跳过。

再运行测试，应该就通过了!

1
2
3
4
5
running 2 tests
test token::test_next_token ... ok
test token::test_code_frag_token ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

REPL

简单的编写一个 REPL：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
use std::io::Write;

mod token;

const PROMPT: &str = ">> ";

fn main() {
    let mut input = String::new();
    loop {
        print!("{}", PROMPT);
        if std::io::stdout().flush().is_err() {
            println!("error: flush err")
        }
        input.clear();
        match std::io::stdin().read_line(&mut input) {
            Ok(_) => {
                let lexer = token::Lexer::new(input.clone());
                for token in lexer.iter() {
                    println!(
                        " -> type: {} | literal: {}",
                        token.token_type, token.literal
                    );
                }
            }
            Err(error) => println!("error: {error}"),
        }
    }
}

这样就可以自己折腾了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
>> 1+2
 -> type: INT | literal: 1
 -> type: + | literal: +
 -> type: INT | literal: 2
 -> type: EOF | literal:
>> fn add(x,y) = { x + y }
 -> type: FUNCTION | literal: fn
 -> type: IDENT | literal: add
 -> type: ( | literal: (
 -> type: IDENT | literal: x
 -> type: , | literal: ,
 -> type: IDENT | literal: y
 -> type: ) | literal: )
 -> type: = | literal: =
 -> type: { | literal: {
 -> type: IDENT | literal: x
 -> type: + | literal: +
 -> type: IDENT | literal: y
 -> type: } | literal: }
 -> type: EOF | literal:
>>

现在，一个简单的词法分析器就完成了。

小结

词法分析器相对而言是比较简单的，只是简单的扫描源代码文本，依次输出词法单元。这个阶段输出词法单元会进入下一个阶段——语法分析。

目前的源代码只支持 ASCII，不支持 UTF8。如果需要支持 UTF8，需要修改读取字符的操作，不能直接 as_bytes 然后取下标索引了。