前言

继续我们的词法分析,这篇主要涉及到有限状态自动机(DFA),还有一些其他的内容。

正文

词法分析的具体实现

我们思考下我们利用正则表达式来获取分词,但是具体的实现应该怎么实现呢?这里采用的是有限状态自动机(DFA),那么怎么进行转换呢,核心是下面这张图:

先从词法分析转换为正则表达式,然后转换为NFA,最后进行消减状态转移为DFA,然后进行最小化,最后转换为二维表的DFA,整个的步骤如下:

  1. 写出每个token的正则表达式

    Number = digit +
    Keyword = ‘if’ + ‘else’ + …
    Identifier = letter (letter + digit)*
    OpenPar = ‘(

    ......

  2. 构建一个R,匹配所有符合token的语素

    R = Keyword + Identifier + Number + …
     = R1 + R2 + ...

  3. 输入字符序列x1,x2...xn

    对于1 < i < n进行检测 x1x2...xi是否属于L(R)

  4. 如果成功,说明x1x2...xi属于某个L(Ri),就是符合某个token

  5. 移出这个x1x2...xi的序列,继续后面的序列到3

但是在这个过程中可能存在歧义:

  • 可能存在不同长度的字符序列都符合L(R):选择最长匹配序列
  • 一个字符序列符合多个token:采用规则优先级,比如把if先认为是关键词,而不是字面量

错误处理,当没有匹配的情况下:写一个匹配所有情况的的规则,并设置为最低优先级

有限状态自动机

DFA是整个的核心,也就是具体实现,其定义为:

就是根据输入(输入字符或者ε),做状态转换,直到最后变为可接受的终态,然后DFA是输入确定的,NFA是不确定的,我们需要做NFA到DFA的转换。(DFA输入状态转换是确定的,不能有ε转换,NFA一个输入可能0或多个转移,并且可以存在ε转换)

然后DFA和NFA都是根据能否到终态来判断可接受,DFA的执行速度更快,但是NFA更加简单

然后一个重点就是从NFA到DFA的转换,具体的实现主要是几个部分,一个是ε-closure(s)闭包(ε-closure(s)表示由状态s经由条件ε可以到达的所有状态的集合),然后假设一个ε闭包作为起始A,然后根据其他输入(除了ε)得到转移后的状态,目的就是消除ε,然后的打到DFA。之后做一个状态最小化,包括消除多余状态(到不了终态或者从输入到不了那个状态)和等价状态(同时为终态或者为非终态,然后所有输入都能转化为等价状态)合并

具体看例子:https://blog.csdn.net/u012359618/article/details/42456771

总结

DFA是核心模块,这里大致概括下。