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

2023-11-05

词法分析是编译器和解释器的第一个环节，相对而言也比较简单。词法分析器（有时也称为单元生成器（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) -> Option<Self::Item>;

    // ...
}

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

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：

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

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

#[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]);
    }
}

补上其余的符号类型：

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，以空白缩进来界定代码区域的语法，就不能忽略空白字符了）。

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

#[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);
    }
}

这段测试显然会失败。

忽略空白字符

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

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 之前：

impl Iterator for LexerIter<'_> {
    type Item = Token;

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

        self.skip_white_space();
        
        // ...

读取标识符

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

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

读取标识符的操作：

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，因此我们需要将这些保留字识别出来：

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 处理标识符了：

// ...
                _ => {
                    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

读取数字

同样的逻辑读取数字：

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

同样地：

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 处理进行处理，_ 部分完整代码如下：

                _ => {
                    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() 操作，否则会导致随后的字符被跳过。

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

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：

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
 -> 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 然后取下标索引了。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Rust

编译原理

开发语言