Day2 从Lisp代码到tokenize(标记解析)

先给自己洗脑

我们已经跑了一个rust实现的内核了，为什么不继续用rust完成它的全部开发呢？中途为什么要搞一个Lisp出来，还要用rust去实现？我听说Lisp是解释型的语言，运行起来很慢吧，用来写操作系统有什么优势吗？你竟然想重头实现一个lisp的解释器，这似乎是实现一个新语言，我们做得到吗？…
或许你已经给自己或者给我抛出了这些疑问。其实核心的观点只有一个：做一个没有人用的操作系统和语言有没有意义？从某种角度说是没有的。如果你的意义是，做出来要对标macos,对标windows,打败linux,要成为国产操作系统之光，要通过操作系统的开发找到好的工作。那么我可以告诉你这是没有意义的。但是如果你，想看看有趣的技术，想通过操作系统的开发和语言的实现来获取知识，通过这个过程去结交一下不为功利，还愿意为技术本身的可能性有追求的朋友的话。那么它就是有意义的。
但是归根接地的说：
开发这样操作系统的全部意义在于，我们有机会站在一个创造者的角度去思考问题。

洗脑后的理性

更何况lisp语言又是这么的拥有魅力。看看知乎上的一位朋友对它的介绍,或者这篇wangyin的文章。lisp就是这样一种语言：只要懂的人都可以感觉到它背后有强大的数学原理的支持，并且有这魔力一般的可扩展性。那么我们可以实现这样的一个语言吗？
当然可以我们有一条可行的路径。mal（make-a-lisp)项目，教我们怎么去写一个lisp的解释器。并且在这个项目的原仓库中有使用rust实现的版本。也就是说我们现在要做的就是：学习迁移这个版本，并且加上自己东西。
要知道这里面是有些困难的。其中最主要的是一些rust的包我们不能使用了。很多其中广泛使用的包必须依赖std的标准库，但是我们是一点标准库都不能用的。这是我们主要要客服的困难。其次编写一个解释器其实包含的知识点比较深入，而且有些地方晦涩艰深。好在我找到了mal语言文档的中文翻译版。（建议你在遇到瓶颈的时候时不时的回来阅读这个mal文档）
下面我们就开始介绍怎么去实现它。

tokenize

那么怎么样些一个解释器呢？首先要么要知道任何一个语言的解释器实现原理。从外部看，无非一个处理字符串然后输出的的过程。那么我们随便给一个字符串，机器又是如何去处理的呢？比如下图中的代码：

(def! plus (lamdba [x y] (+ x y)))

或许你还看不懂这段lisp代码。它完成一个定义函数的任务，如果我们了解lisp的语法就可以轻易的知道这一点。可是机器读到这个字符串就头疼了。它甚至不知道到底def!是一个符号，还是(def!是一个符号。也不清除遇到了lamdba表明什么。还有这些括弧是什么意思。
要知道我们要实现的mal语言中有很多基本的元素。代码就是由这些基本元素构成的。计算机特别希望你告诉它那些符号是那些基本元素。比如像下面的这样一张表。

你看到这张表发现所有的元素不都是符号吗？ 是的，但是这只是一种特殊情况。在表达式里可以还有字符串或者数字类型。然而对于计算机来说，它可是连那些是符号都不清楚的。我们要把代码里的这些单元一个一个区分开来帮助计算机进行接下来的分析。这个区分的过程就是标题中的tokenize了。有人翻译为标记解析也有人翻译为切分词。

开始实现

好了我们现在遵循能用现成的就不开发的原则，看一看mal官方库里面的实现。我就不粘贴代码了，有兴趣的同学可以自己看看去,是不能够使用的，因为他使用了regex正则表达式的包。但是我们会遗憾的发现正则表达式的包，在官方中暂时是不支持使用no_std特性的。
那怎么办呢？自己实现呗。
怎么实现呢？用什么技术呢？关于这点要看你平时的积累了。当然如果你阅读了mal的文档。会发现它提示了一二。当然笔者第一个想到的还是使用状态机来实现，其实一般对于这种有括号和括回的文本分析都适合使用这样技术，就比如Json的识别。

现在可以在src下面建立一个叫做lisp的文件夹。然后建立mod.rs和reader.rs两个文件夹。在mod.rs引入reader。

pub mod reader;

接下来我们来设想一下，要一个一个的读取字符串内的值。然后每个字符每个字符的处理。我们暂时有四种状态。如下，在reader.rs文件中定义状态枚举。

use alloc::string::{String, ToString};
use alloc::vec::Vec;
use crate::lisp::reader::State::{Start,Others,Comment,StateSym};

// token 识别状态
#[derive(Debug, Clone)]
enum State {
    Start,            // 开始状态
    StateSym(String), // 特殊符号
    Comment(String),  //注释
    Others(String),
}

fn tokenize(str: &str) -> Vec<String> {
    //todo
}

当我们读到其中任意一个符号时都会进入到其中一个状态。这时候我们可以根据上一个状态来确认我们要做的事。比如一开始是Start状态。现在读字符串“;”后我们知道现在进入到注释状态。而无论下面读到什么字符串都还是注释，除非我们遇到了换行符号。这时要将枚举中缓存的String存入到返回的数组中然后把状态再次标志为Start。之后读下面的字符，直到结束。
再比如读到了特殊字符，像“（”或者“～”之类的，现在就进入到了特殊字符的状态StateSym。然后在读到一个特殊字符。由于“～@”在一起时是一个特殊字符要特殊判断。之外的情况下，一般就保存当前字符到返回数组，然后根据输入来的字符来判断接下来的状态。如果是其他就进入到Other如果是;就进入到Comment状态。如果是空格或回车就重新回到了Start状态。
…
诸如此类，弄清楚所有状态就之间的变化就可以开始开发了。

fn tokenize(str: &str) -> Vec<String> {
    let mut res = Vec::new();
    let mut code = String::from(str).chars().rev().collect::<String>();
    let mut state: State = Start;
    loop {
        let pre_state = state.clone();
        match code.pop() {
            Some(t) => {
                match t {
                    '`' | '\'' | '~' | '^' | '@' | '[' | ']' | '(' | ')' | '{' | '}' => {
                        match pre_state {
                            Start => {
                                state = StateSym(t.to_string());
                            }
                            StateSym(s) => {
                                if s == "~" && t == '@' {
                                    res.push(String::from("~@"));
                                } else {
                                    res.push(s);
                                    res.push(t.to_string());
                                    state = Start;
                                }
                            }
                            Comment(s) => {
                                let mut tmp = s.clone();
                                tmp.push(t);
                                state = Comment(tmp);
                            }
                            Others(s) => {
                                res.push(s);
                                state = StateSym(t.to_string());
                            }
                        }
                    }
                    ' ' => {
                        match pre_state {
                            Start => {
                                // do nothing
                            }
                            StateSym(s) => {
                                res.push(s);
                                state = Start;
                            }
                            Comment(s) => {
                                let mut tmp = s.clone();
                                tmp.push(t);
                                state = Comment(tmp);
                            }
                            Others(s) => {
                                res.push(s);
                                state = Start;
                            }
                        }
                    }
                    '\n' => {
                        match pre_state {
                            Start => {
                                // do nothing
                            }
                            StateSym(s) => {
                                res.push(s);
                                state = Start;
                            }
                            Comment(s) => {
                                res.push(s);
                                state = Start;
                            }
                            Others(s) => {
                                res.push(s);
                                state = Start;
                            }
                        }
                    }
                    ';' => match pre_state {
                        Start => {
                            state = Comment(String::from(t.to_string()));
                        }
                        StateSym(s) => {
                            res.push(s);
                            state = Comment(String::from(t.to_string()));
                        }
                        Comment(s) => {
                            let mut tmp = s.clone();
                            tmp.push(t);
                            state = Comment(tmp);
                        }
                        Others(s) => {
                            res.push(s);
                            state = Comment(String::from(t.to_string()));
                        }
                    },
                    _ => {
                        // trace!("Run in Other: {}", t);
                        match pre_state {
                            Start => {
                                state = Others(t.to_string());
                            }
                            StateSym(s) => {
                                res.push(s);
                                state = Others(t.to_string());
                            }
                            Comment(s) => {
                                let mut tmp = s.clone();
                                tmp.push(t);
                                state = Comment(tmp);
                            }
                            Others(s) => {
                                let mut tmp = s.clone();
                                tmp.push(t);
                                state = Others(tmp);
                            }
                        }
                    }
                }
            }
            None => {
                break;
            }
        }
    }
    // 应该把当前状态没有识别结束的值 保存到vec中
    match state {
        Start => {}
        StateSym(s) => {
            res.push(s);
        }
        Comment(s) => {
            res.push(s);
        }
        Others(s) => {
            res.push(s);
        }
    }
    res
}

pub fn test_tokenize(str: &str){   
    use crate::println;
    let tokens = tokenize(str);
    println!("{:?}",tokens);
}

现在在主方法中调用并且测试一段S表达式。注意下面这段代码要在main.rs的主方法中。

     use crate::lisp::reader::test_tokenize;
    test_tokenize("(def! plus (lamdba [x y] (+ x y)))");

现在运行发现已经可以正常的识别所有符号了。

至此我们第一步就完成了。

Help Me

聪明的读者或许发现了，这个代码不能正确的识别字符串！我也正因为这个苦恼。那个朋友可以Fix这个bug呢？我的git项目的地址。