实现一个自己的编程语言—— 有限自动状态机

美团点评送外卖
美团点评送外卖   编辑于 2018-10-26 00:07
阅读量: 77

等等,我们不是在实现一个自己语言的解释器吗,为什么说起来了有限自动状态机呢?首先我们需要知道对一个语言解释器来说,应该由前端和后端两部分组成,这里的前端就是将文件读入内存并转化成Token流举个例子

func say_hello(){
    int a = 1;
    for(int i =0;i<10;i++){
     println(a);
    }
}

我们看一下这个函数定义,这个函数被定义在了一个文件中,那么我们得到的一个文件I/O流应该是这样的一个字符流

func say_hello(){\n\tint a = 1;\n\tfor(int i =0;i<10;i++){\n\t\tprintln(a);\n\t}\n}

ok 看起来比较复杂对不对,那么我们认为func for 以及 int 为关键字,并且应该是KW类型的数据,那么这个流被处理后应该是

KW say_hello(){\n\tKW a = 1;\n\tKW(KW i =0;i<10;i++){\n\t\tprintln(a);\n\t}\n}

再进一步,我们定义函数签名为FUNC_ID 定义变量签名为VAL_ID

KW FUNC_ID(){\n\tKW VAL_ID = 1;\n\tKW(KW VAL_ID =0;VAL_ID<10;VAL_ID++){\n\t\tFUNC_ID(VAL_ID);\n\t}\n}

我们的流变成这个样子了,OK 那么我们认为'('应该为LEFT_SP_1 ')'为RIGHT_SP_1然后,我们认为'{'应该为LEFT_SP_2 '}'为RIGHT_SP_2

KW FUNC_ID LEFT_SP_1 RIGHT_SP_1 LEFT_SP_2\n\tKW VAL_ID = 1;\n\tKW LEFT_SP_1 KW VAL_ID =0;VAL_ID<10;VAL_ID++ RIGHT_SP_1 LEFT_SP_2\n\t\tFUNC_ID(VAL_ID);\n\tRIGHT_SP_2\nRIGHT_SP_2

OK 我们成功把各种括号替换了,对吧,那么我们把运算符和字面量还有分号也给替换了,并且规约成一个Token 数组

[KW,FUNC_ID,LEFT_SP_1,RIGHT_SP_1,LEFT_SP_2,KW,VAL_ID,EQ_OP,NUMBER,SPLITOR,KW,LEFT_SP_1,KW,VAL_ID,EQ_OP,NUMBER,SPLITOR..]

生成了上面的这样的一个token 流

为什么要做这一步呢?因为人看代码是带逻辑的看,但是计算机可不是,所以我们要把一个语言先变成数据结构描述,然后再通过数据结构来执行对应的指令

比如KW我们的定义为

typedef struct kw{
   value : "",
}KW

简单一点,这里对for来说,他的value 应该为for 对吧。

OK 那么有限自动状态机就是一种帮助我们识别词法,并且变成Token流的算法。

定义一个自动机

所有的状态机都应该被一个五元组来描述 \(Automata(Q,\Sigma,\sigma,q0,F)\) 嗯就是这样。从左到右意思依次是

  1. 有限状态的集合
  2. 所有可以接受的符号集合
  3. 状态转移函数
  4. 起始状态集合
  5. 最终状态集合

ok 这样就可以描述一个自动机了,状态机有什么用,主要的作用就是当我们对自动机进行一次输入的时候,会根据上一次状态的转移当前机器的状态,如果可以的话,当运行到最终状态的时候输出就好了。

其实我们可以按照图来看一个自动机状态转移过程。

有如上的正则表达式,生成的自动机转换图为上图,那么我们看是不是当s0从带权边a通过时转换到了s1状态,当s1 接收b或者c转换到了s1状态,那么如果字符串不出现任何空字符,并且永远是bc交替出现的时候,这个状态机就永远处于了s1状态。很像DFS的操作把,不过有环了而已。

我们也很容易为上面的正则构建一个C语言程序

typedef struct dfa{
  state int;
  char * token;
  int final;
}DFA;

#define S0 0
#define S1 1

void input(DFA* dfa,char ch)
{
   if(ch == 'a' && dfa -> state != 0){
    dfa -> state = 1;
    dfa->token = strcat(dfa->token,ch);
    return ;
   }
   if(ch == 'b' || ch == 'c'){
     if(dfa -> state == 0)return ;
     else {
       dfa-> state = 1;
       dfa->token = strcat(dfa->token,ch);
       return;
     }
   }
   if(dfa -> state == 1)dfa -> final = 1;
   else dfa -> final = 0;
   return;
}

大概就是这样了,当然代码还是很难看的,不过事情说明白了,如果我们在状态机状态为1的时候收到了一个不是b或者c的字符的时候,那么就标记dfa可以退出了,然后获取token 就可以啦。其他情况,直接向前推进即可。

NFA 和 DFA 以及最小化DFA

理想的情况下,我们按照接收状态来建模,就应该每个状态在唯一的字符下都只有一个唯一的状态转换路径,但是对于很多形式语言来说并不是这样的,那么一个状态在接收一个相同字符的时候会有多种状态转移路径,这样的话,计算机并不会知道到底走那条路,所以需要我们把NFA转换成DFA然后再进行计算,最小化DFA只是为了性能的提升。

反正也绕不过克林闭包和正闭包的概念,不过这个东西确实比较麻烦,翻了半天离散数学书才搞明白到底咋回事

大概定义是这个样子的,这里特别强调\(\lambda\)\(\epsilon\)都是空串的意思,也就是空,简单理解为""这个就可以啦,但是和词法分析有什么关系呢?当然有关系我这里找了一个NFA的图,和他转化之后的DFA的图

就是这两个做例子即可,相信这个正则都能看懂,我们看NFA,当状态机处于S1的状态时候,如果这个时候收到了一个空串,并没有走到终止状态S9 而是推进到了S8,如果S8还是收到了空,那么就终止状态了,但是我们发现在s8 的时候,同样接收空串,可以转换到两个状态s6和s9,其实这个S8 就是为了画图好画,因为我们可以很轻松的认识到,多个空串链接还是空串,所以s8和s6的状态应该是一样的,那么既然这么画了,那么我们发现了什么NFA的特点就是一个空串的接收可以转换到不止一个状态,这就难搞了,是吧,后面也是的。

那么怎么转的DFA呢,其实还是参考DFS的算法含义,当我们每次经过图上的一个节点的时候,遍历数+1,那么我们在看克林闭包,其实就是那个符号全集来回链接,好像数据库的笛卡儿积一样,然后我们能退出一个路径串,发现没?

有了这个路径串,就好办了,我们就可以规约了,规约其实就是对状态的合并,我们认为多个状态都是一个状态,那么规约完成之后,我们得到的就是一个正闭包。具体咋回事,还是好好看看离散数学书吧,这个编辑器太抠脚了。证明太麻烦啦。

收藏 转发 评论