Rust 实现一个表达式 Parser(5) Lexer 实现-六虎

本文将结合前文封装的 DFA(其实仅仅封装了俩函数) 完成词法剖析器 Lexer

源码: src/lexer/tokenizer.rs

Lexer 方针

开始之前先来明晰咱们的方针, 咱们期望将一坨字符串分割为多个 Token, 大致如下

首要摆在咱们面前的问题便是, Token 该长什么样, 首要明晰 Token 需求附带哪些信息

类型, 这儿对应的是上一篇文章中的 SyntaxKind, 如 PLUS 类型和 MINUS 类型
值, 针对数字 Token 咱们需求保存其详细的值, 如 123

除此之外并不需求其余信息了, 那么咱们就能够很想当然的运用一个简略的二元组来保存 Token, (类型, 值)

Lexer 完成

至此就能够直接开始怼逻辑了

Token 界说

经过上面的剖析, 这儿直接界说出两个类型别号即可, 值得一提的是, 这儿为了之后的代码简练, 额外界说了一个 TokenStream

pub type Token = (SyntaxKind, String);
pub type TokenStream = Vec<Token>;

Tokenizer 结构体界说

接着咱们会需求一个结构体来保存当时现已得到的 Token, 直接界说如下, 并趁便完成三个简略的方法

pub struct Tokenizer {
    code: String,
    token_stream: TokenStream,
}
impl Tokenizer {
    pub fn new(code: String) -> Self {
        Tokenizer { code, token_stream: Vec::new() }
    }
    pub fn token_stream(&self) -> TokenStream {
        self.token_stream.to_owned()
    }
    fn push_token(&mut self, text: &str) {
        // 这儿直接用形式匹配来区分是操作符 Token 仍是 数字 Token
        let token = match SyntaxKind::from_operator(text) {
            // 操作符 Token
            Some(kind) => (kind, text.to_string()),
            // 数字 Token
            None => (NUM, (text.to_string())),
        };
        self.token_stream.push(token);
    }
}

中心逻辑

下面进入中心逻辑的完成, 此处要结合上一篇文章进行了解, 不考虑不合法输入的话, 咱们的 DFA 需求做的工作简略罗列出来是这样的

依据当时输入进行状况搬迁
判别搬运前的状况是否是停止态
- 停止态: 前次现已匹配一个完好的 Token, 输出
- 非停止态: 当时并没有匹配到一个完好的 Token, 缓存
回到第一步, 直到解析完一切的输入序列

以上便是 DFA 的中心逻辑, 这儿凭借上一篇文章中封装好的两个函数, 能够很快速的搭出如下框架

impl Tokenizer {
    pub fn run(&mut self) {
        // 状况搬运函数
        let transition = get_transition();
        // 判别传入状况是否是停止状况的函数
        let is_terminator = get_terminator_judgement();
        let mut idx = 0;             // 当时索引
        let mut state = START;       // 当时状况
        let mut prev_state = ERROR;  // 前一个状况
        // 缓存或许未匹配完的 Token
        let mut text_cache = String::new();
        // 将输入的字符串格式转化为 char 类型的迭代器并遍历
        while let Some(c) = self.code.chars().nth(idx) {
            // 状况搬迁
            state = transition(c, state);
            // 从一个停止态搬运到另一个停止态则意味着上一次现已匹配到了一个完好的 Token
            if is_terminator(prev_state) && state != prev_state {
                // 将 Token 输出到 self.token_stream
                self.push_token(&text_cache);
                // 清空缓存
                text_cache.clear();
            }
            // 将非空字符缓存
            if c != ' ' {
              text_cache.push(c);
            }
            // 更新一些数据
            idx += 1;
            prev_state = state;
        }
        // 由于是依据前一次状况进行判别, 因而在循环退出时会在缓存中残留最后一个 Token
        self.push_token(&text_cache);
    }
}

接着咱们来看一下上一篇文章中写好的状况搬运表

op	ws	0	1-9
ERROR	0	0	0	0
START	2	1	3	4
OPERATOR	2	1	3	4
ZERO	2	1	0	0
NUM	2	1	4	4

咱们会发现现在写好的程序存在一个小 bug, 便是当连续匹配到多个 op 类型时, 会一直停留在 OPERATOR 状况, 这意味着不满足 state != prev_state 的条件, 就不会将 op 拆分开来存入, 因而仅需求多加一个简略的小条件即可

impl Tokenizer {
    pub fn run(&mut self) {
        // ...
        while let Some(c) = self.code.chars().nth(idx) {
            // 状况搬迁
            state = transition(c, state);
            // 从一个停止态搬运到另一个停止态则意味着上一次现已匹配到了一个完好的 Token
            // 或许当时匹配到一个操作符, 则直接存入
            if is_terminator(prev_state) && (state != prev_state || prev_state == OPERATOR) {
                // 将 Token 输出到 self.token_stream
                self.push_token(&text_cache);
                // 清空缓存
                text_cache.clear();
            }
            // ...
        }
        // ...
    }
}

现在来看就没有其他大问题了, 下面继续完善其他方面

过错处理

过错处理非常简略, 在 Rust 中运用 Result 能够很方便的进行过错处理, 此外在上一篇文章咱们现已事先界说好了过错的状况 ERROR 以及搬迁到该状况的途径, 因而这儿直接简略的判别即可, 如下

impl Tokenizer {
    pub fn run(&mut self) -> Result<(), String> {
        if self.code.len() == 0 {
            return Err("an empty string was received".to_string());
        }
        // ...
        while let Some(c) = self.code.chars().nth(idx) {
            state = transition(c, state);
            // 搬迁到 ERROR 状况, 直接报错, 并给出简略的报错信息
            if state == ERROR {
                return Err(format!(
                    "unexpected token at the {} of the input, current cache: {}",
                    idx, text_cache
                ));
            } else if is_terminator(prev_state) && (state != prev_state || prev_state == OPERATOR) {
                self.push_token(&text_cache);
                text_cache.clear();
            }
            // ...
        }
        self.push_token(&text_cache);
        // 解析成功, 返回一个空的 Ok
        Ok(())
    }
}

支持正负数

前文提到, 原本打算用 NFA 完成正负数的支持, 可是发现转化为 DFA 之后状况量增加了许多, 完成起来很麻烦, 因而就决定仍是在词法剖析的逻辑里进行处理

众所周知, 数字默许是正数, 因而增加 + 前缀并没有意义, 因而咱们其实只需求考虑怎么处理负数的问题就能够了

怎么增加负号

按照现有逻辑, 咱们会将一切的操作符直接输出到 token_stream, 数字会在完好匹配之后输出到 token_stream, 而空格会被直接越过, 这意味着现在是这样的

表达式: "1 + -2"
解析完成后 token_steam: ["1", "+", "-", "2"]

那么咱们其实能够在 push_token 的逻辑中简略处理一下, 在数字 Token 进入的时分, 测验与顶部 Token 合并

何时增加负号

简略的罗列剖析一下能够发现, 实际上需求增加负号的状况只要以下两种, 以下也涵盖了要将正号去掉的状况

数字 Token 预备压栈, 当时栈顶和次栈顶都是操作符, 且栈顶是 + 或许 -
- [ 1, +, 2, +, - ] <- 3
- [ 1, +, 2, +, (, + ] <- 3
数字 Token 预备压栈, 当时栈长度为 1 且栈顶元素为 + 或许 -
- [ - ] <- 1
- [ + ] <- 1

详细逻辑

经过上面的剖析, 能够很轻松的写出如下逻辑, 简略来说便是一路 if else, 只不过 Rust 里能够用形式匹配

impl Tokenizer {
    fn push_token(&mut self, text: &str) {
        let token = match SyntaxKind::from_operator(text) {
            Some(kind) => (kind, text.to_string()),
            // 数字 Token, 或许能够合并
            // 调用 self.try_merge 测验一下
            None => (NUM, self.try_merge(text.to_string())),
        };
        self.token_stream.push(token);
    }
    fn try_merge(&mut self, mut text: String) -> String {
        let len = self.token_stream.len();
        // e.g
        //   [ 1, +, - ] <- 1
        //        |  |      |
        //        k1 k2   text
        if len >= 2 {
            let (k1, _) = self.token_stream[len - 2];
            let (k2, _) = self.token_stream[len - 1];
            match k1 {
                token!["+"] | token!["-"] | token!["*"] | token!["/"] | token!["("] => {
                    match k2 {
                        // "1 + - 1" => [ 1, +, -1 ]
                        token!["-"] => {
                            self.token_stream.pop();
                            text.insert_str(0, "-")
                        }
                        // "1 + + 1" => [ 1, +, 1]
                        token!["+"] => {
                            self.token_stream.pop();
                        }
                        _ => {}
                    }
                },
                _ => {}
            }
        }
        // e.g
        //   [ - ] <- 1
        //     |      |
        //     k1    text
        else if len == 1 {
            let (k1, _) = self.token_stream[len - 1];
            if k1 == token!["+"] || k1 == token!["-"] {
                self.token_stream.pop();
                match k1 {
                    // "- 1" => [ -1 ]
                    token!["-"] => text.insert_str(0, "-"),
                    // "+ 1" => [ 1 ]
                    _ => {}
                }
            }
        }
        text
    }
}

跑一下

写完了逻辑就简略跑一下, 如下测验都是能够顺畅经过的, 而更多的用例在源码中, 就不罗列了

// 封装了一个简略的驱动函数配合测验
fn lex(code: &str) -> Result<TokenStream, ()> {
    let mut tokenizer = Tokenizer::new(code.to_string());
    if tokenizer.run().is_ok() {
        Ok(tokenizer.token_stream())
    } else {
        Err(())
    }
}
#[test]
fn basic_test() {
    assert_eq!(vec![(NUM, "123".to_string())], lex("+123").unwrap());
    assert_eq!(vec![(NUM, "-123".to_string())], lex("-123").unwrap());
    assert_eq!(vec![(NUM, "123".to_string())], lex("123").unwrap());
    assert_eq!(
        vec![
            (NUM, "123".to_string()),
            (PLUS, "+".to_string()),
            (NUM, "-456".to_string())
        ],
        lex("123+-456").unwrap()
    );
    assert_eq!(
        vec![
            (NUM, "123".to_string()),
            (PLUS, "+".to_string()),
            (NUM, "-456".to_string())
        ],
        lex("+123+-456").unwrap()
    );
    assert_eq!(
        vec![
            (NUM, "123".to_string()),
            (PLUS, "+".to_string()),
            (NUM, "456".to_string())
        ],
        lex("+123+456").unwrap()
    );
}

模块导出

现在现已完成了 Lexer 模块的中心逻辑, 接下来能够来简略封装一个函数作为模块导出, 仅仅简略封装, 就不做赘述

源码 src/lexer/mod.rs

pub fn lex(code: &str) -> Result<TokenStream, String> {
    let mut tokenizer = Tokenizer::new(code.to_string());
    match tokenizer.run() {
        Ok(_) => Ok(tokenizer.token_stream()),
        Err(err) => Err(err),
    }
}

总结

至此咱们完成了 Lexer 的一切部分, 最中心的部分在于应用状况转化表以及判别输出完好 Token 的时机, 这儿笔者在完成时尽量写的简略明晰, 在源码中也书写了大量的注释, 详细的能够直接看源码中的注释

Q&A

Q: 中心逻辑为什么不必双指针?

A: 一开始写的是双指针版别, 在处理了 Rust 的一些 ownship 问题之后发现代码变得臃肿不易读, 不如直接整个简略的, 这儿用双指针和我写的这个暴力算法时刻复杂度在理论上是一样的量级, 仍是可读性比较重要一点

完好代码

由于文章拆成了两篇, 且修正的比较紊乱, 因而贴一个完好版, 以下代码去掉了注释, 其实仍是更建议直接看仓库源码, 里边有注释

// src/lexer/dfa.rs
pub const ERROR: usize = 0;
pub const START: usize = 1;
pub const OPERATOR: usize = 2;
pub const ZERO: usize = 3;
pub const NUM: usize = 4;
pub fn get_terminator_judgement() -> impl Fn(usize) -> bool {
    const END_STATE: [usize; 3] = [OPERATOR, ZERO, NUM];
    |state: usize| END_STATE.contains(&state)
}
pub fn get_transition() -> impl Fn(char, usize) -> usize {
    const STATE_TABLE: [(usize, usize, usize, usize); 5] = [
        (0, 0, 0, 0), // ERROR
        (2, 1, 3, 4), // START
        (2, 1, 3, 4), // OPERATOR
        (2, 1, 0, 0), // ZERO
        (2, 1, 4, 4), // NUM
    ];
    let is_op = |c: char| match c {
        '-' | '+' | '*' | '/' | '(' | ')' => true,
        _ => false,
    };
    let is_whitespace = |c: char| match c {
        ' ' => true,
        _ => false,
    };
    let is_zero = |c: char| match c {
        '0' => true,
        _ => false,
    };
    let is_one_to_nine = |c: char| match c {
        '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => true,
        _ => false,
    };
    move |c: char, state: usize| {
        if is_op(c) {
            STATE_TABLE[state].0
        } else if is_whitespace(c) {
            STATE_TABLE[state].1
        } else if is_zero(c) {
            STATE_TABLE[state].2
        } else if is_one_to_nine(c) {
            STATE_TABLE[state].3
        } else {
            ERROR
        }
    }
}

// src/tokenizer.rs
pub type Token = (SyntaxKind, String);
pub type TokenStream = Vec<Token>;
pub struct Tokenizer {
    code: String,
    token_stream: TokenStream,
}
impl Tokenizer {
    pub fn new(code: String) -> Self {
        Tokenizer { code, token_stream: Vec::new() }
    }
    pub fn token_stream(&self) -> TokenStream {
        self.token_stream.to_owned()
    }
    pub fn run(&mut self) -> Result<(), String> {
        if self.code.len() == 0 {
            return Err("an empty string was received".to_string());
        }
        let transition = get_transition();
        let is_terminator = get_terminator_judgement();
        let mut idx = 0;
        let mut state = START;
        let mut prev_state = ERROR;
        let mut text_cache = String::new();
        while let Some(c) = self.code.chars().nth(idx) {
            state = transition(c, state);
            if state == ERROR {
                return Err(format!(
                    "unexpected token at the {} of the input, current cache: {}",
                    idx, text_cache
                ));
            } else if is_terminator(prev_state) && (state != prev_state || prev_state == OPERATOR) {
                self.push_token(&text_cache);
                text_cache.clear();
            }
            if c != ' ' {
                text_cache.push(c);
            }
            idx += 1;
            prev_state = state;
        }
        self.push_token(&text_cache);
        Ok(())
    }
    fn push_token(&mut self, text: &str) {
        let token = match SyntaxKind::from_operator(text) {
            Some(kind) => (kind, text.to_string()),
            None => (NUM, self.try_merge(text.to_string())),
        };
        self.token_stream.push(token);
    }
    fn try_merge(&mut self, mut text: String) -> String {
        let len = self.token_stream.len();
        if len >= 2 {
            let (k1, _) = self.token_stream[len - 2];
            let (k2, _) = self.token_stream[len - 1];
            match k1 {
                token!["+"] | token!["-"] | token!["*"] | token!["/"] | token!["("] => match k2 {
                    token!["-"] => {
                        self.token_stream.pop();
                        text.insert_str(0, "-")
                    }
                    token!["+"] => {
                        self.token_stream.pop();
                    }
                    _ => {}
                },
                _ => {}
            }
        } else if len == 1 {
            let (k1, _) = self.token_stream[len - 1];
            if k1 == token!["+"] || k1 == token!["-"] {
                self.token_stream.pop();
                match k1 {
                    token!["-"] => text.insert_str(0, "-"),
                    _ => {}
                }
            }
        }
        text
    }
}

Rust 实现一个表达式 Parser(5) Lexer 实现

Lexer 方针

Lexer 完成

Token 界说

Tokenizer 结构体界说

中心逻辑

过错处理

支持正负数

怎么增加负号

何时增加负号

详细逻辑

跑一下

模块导出

总结

Q&A

完好代码

作者信息

推广

Rust 实现一个表达式 Parser(5) Lexer 实现

Lexer 方针

Lexer 完成

Token 界说

Tokenizer 结构体界说

中心逻辑

过错处理

支持正负数

怎么增加负号

何时增加负号

详细逻辑

跑一下

模块导出

总结

Q&A

完好代码

相关文章

AOSP（三）玩转Android系统资源定制

聊一聊Kotlin协程”低级”api

下一站 Gen AI 城市巡展指南来了！“码”上出发，Let’s 构！

Flutter Win平台下定制Flutter Engine

作者信息

推广