实现一个自己的编程语言——词法分析

美团点评送外卖
美团点评送外卖   编辑于 2018-11-01 01:06
阅读量: 111

首先我们知道我们所有的代码都放在了一个文件内,so,第一件事我们要读入文件并进行词法分析,分析完成之后形成的token流会被接下来的语法分析器消费掉,典型的生产者消费者模型。

一个Tokenizer 组成

首先需要介绍一种缓存读文件的方法,双缓冲区。

双缓冲的结构

就是长成这个样子就对了,那么结构就可以确定了

const BLOCK_L :2048;
const MID_L : 1024;
const CACHE_L : 64;

struct StreamBuffer{
   begin_ptr i32,
   forward_ptr i32,
   buffer [char;BLOCK_L],
   cache [char,CACHE_L]
}

pub trait DoubleBuffer{

}

pub fn new()-> Option<DoubleBuffer>{
   Some(StreamBuffer{
      begin_ptr:0,
      forward_ptr:0,
      buffer['\0':BLOCK_L],
      cache['\0':CACHE_L]
   });
}

我们需要一个初始指针begin和向前移动指针forward,并且需要一个buffer,当然每次只读取一半的数据进入,剩下一半备用,同时需要一个cache,那么第一个版本的定义就出来了。

双缓冲工作原理

我们的begin指针代表当前的token 的起始位置,而forward 指针会一直向前移动,移动完成之后就会将移动后指向的位置的字符读取出来并返回给我们的tokenizer来进行内部DFA状态转移,如果DFA到达可以接收的状态,那么将begin和forward之间的字符串输出出去,也就是获取了一个token。

为什么将一个buffer划分为两段呢?这是因为我们可以保证我们每次从文件获取数据的时候只填充一半,而另外一半备用,如果forward超过中间位置的时候,那么先装载数据再读取,同样移动到末尾的时候DFA还没有接收这个字符串,那么把左边填充上。具体工作流程如下。

正常工作的状态,如果当前forward指向的字符可以被接收的时候,中间的这个token就是需要返回的token。

如果读取到了第1024位置时候,发现token还是不能被接收的时候,那么填充右半部分,也就是调用IO函数来填充。

当然移动到了末尾的时候,发现token还是没有被读取完成,这个时候begin也超过了中位数,也就是1024的时候,那么就把左边的数据替换掉,同样调用IO函数,但是这里需要上个cache,因为当forward移动到了起始位置的时候,begin-forward是个负数,自然也就不能提取相应的token了,需要用cache缓存一下,并且需要记录当前begin和forward的差值最后返回的token其实是cache

那么我们开始看一下行为啦,也就是可以被调用的函数啦。

双缓冲的行为

对外提供边界

  1. 读取一个字符
  2. 退回一个字符
  3. 获取token

内部行为

  1. 从文件读取数据
  2. 移动begin指针
  3. 向前forward指针
  4. 向后移动forward指针
  5. 重合两个指针
  6. 填充cache
  7. 追加字符进cache
  8. 填充buffer

那么新的代码结构就出来了

const BLOCK_L :2048;
const MID_L : 1024;
const CACHE_L : 64;

struct StreamBuffer{
   begin_ptr i32,
   forward_ptr i32,
   buffer [char;BLOCK_L],
   cache [char,CACHE_L],
   from_cache : bool,
}

impl StreamBuffer{
     fn read_from_file(file : File);
     fn move_begin(dest : i32);
     fn forward();
     fn back();
     fn cover_ptr();
     fn fill_cache(begin : i32,forward:i32);
     fn append_cahce(ch : char);
     fn fill_buffer();
}

pub trait DoubleBuffer{
    fn getc() -> char;
    fn backc() -> char;
    fn get_token -> &str;
}

pub fn new()-> Option<DoubleBuffer>{
   Some(StreamBuffer{
      begin_ptr:0,
      forward_ptr:0,
      buffer : ['\0':BLOCK_L],
      cache : ['\0':CACHE_L],
      from_cache : false
   });
}

然后我们需要确定一些边界

  1. 当begin 小于 MID_L 而 forward = BLOCK_L - 1 的时候,这个问题1024个字符的token 基本不存在,存在的话绝对是代码有问题了直接报错
  2. 当forward移动过了BLOCK_L - 1 那么再移动的时候需要判断from_cache 是否为true,如果是直接追加
  3. 0 和 2048 是字符处理边界

OK边界确定了,那么就先放在这里,我们开始思考一下如何从一个字符串中切割出不同的token出来。

 

收藏 转发 评论