681aeb85d7f70a1f3f7aee22193f158c
Python 与 DFA

DFA

在上次我们阐述的《Python的抽象语法树(二)》的文末,我们提及了DFA,这是一个非常庞大的话题,本文会试着用简洁的例子和语句去阐述他和构建语法树之间的关系。

DFA、NFA与正则文法

DFA,全文解释的话就是确定性有限状态机。与之对应的还有NFA,定义为非确定性有限状态机。

他们两个唯一的区别就是从某个状态出发,DFA只能到达一个确定性的下一状态;而NFA可能到达0,1个或者多个下一状态。

用几个例子来举例的话,如下这张来自中山大学讲义的图,就是所谓的NFA

当处于初始状态0的时候,下一个转移可能通过a1,也可能通过a继续在0

DFA的示例,其实我们在之前讲解词法分析的过程中,已经潜在的接触到了,那就是词法分析的状态转移本质上就是DFA,如下图所示:

而我们之前又在Python的语法分析(一)里面提及:

从本质上来说,不仅仅是语法分析中涉及了文法,词法分析中也存在文法。有大量语言的词法分析可以通过正则表达式进行表征解析,这种文法属于所谓的3型文法,即正则(规)文法。

那么正则文法和DFA之间的联系是? 一言以蔽之:

  • 正则文法便于书写。
  • DFA方便计算机去理解去执行。
  • NFA是正则文法转DFA中间的一个过渡。

上下文无关算法与DFA

之前我们在语法分析中提过,语法分析是采用的上下文无关算法;词法分析采用的是正则文法;而正则文法又可以转换成DFA,难道这意味着上下文无关算法可DFA也是相通可转化的吗?

首先我们来确定性的学习上上下文无关算法:

正则表达式存在一种等价的计算模型——有穷自动机——可以用来解析正则语言一样,上下文无关文法也存在一种等价的计算模型——下推自动机(Put-Down Automation, PDA)。下推自动机除了一组有限的状态和状态转换以外,还带有一个无限容量的栈。和有穷自动机不同,下推自动机的状态并不仅根据输入字符和当前状态来进行转移,还要根据栈顶的字符;而且下推自动机还必须决定何时向栈中压入或弹出字符

相当拗口。简化来说,我们之前看到的文法定义,那一行行产生式,属于一种给人读的格式;而计算机理解所使用的则是对应的PDA模型。

Python中的DFA定义

储备了这么多预备知识,我们可以回过头来看Python中,语法解析是如何运用DFA的,主要的结构定义都在grammar.h里。

既然是确定性有限状态机,那自然需要状态节点以及状态转移的边。

对应的数据结构分别是state以及arc

typedef struct {
    int      s_narcs;
    arc     *s_arc;     /* Array of arcs */

    /* Optional accelerators */
    int      s_lower;   /* Lowest label index */
    int      s_upper;   /* Highest label index */
    int     *s_accel;   /* Accelerator */
    int      s_accept;  /* Nonzero for accepting state */
} state;

typedef struct {
    short   a_lbl;      /* Label of this arc */
    short   a_arrow;    /* State where this arc goes to */
} arc;

state里面的s_arc就是记录了从该状态出发到其他状态的边的集合。剩下的字段都是跟加速分析过程相关,我们后文再说。

可能有人会看到label,以为这个是边,其实label是用于描述这条边的。

typedef struct {
    int      lb_type;
    char    *lb_str;
} label;
  • lb_type是用于描述类型,这个类型类似之前词法分析得到的token的类型。
  • lb_str就是对应拆分出来的token
top Created with Sketch.