词法分析-有限自动机

字数统计: 4.7k字 | 阅读时长: 20分

2020-07-21

词法分析和有限自动机
题目

$1 词法分析和有限自动机

在编译原理中，一个程序语言的单词表

基本字: for, while, int, return, const, ...
标识符: tmp, next, left, ...
常数: 3, 1.7, 'o', "abc", 1e9, 2.5e-7, ...
运算符: +, -, *, /, ^, ...
分界符: 空格，空行

是词法分析的对象，单词表里的所有单词构成了一个字符串的集合，这种集合称为正则集。词法分析要研究的是正则集。

正则集可以用正则表达式表示，它们是一一对应的。

词法分析器的功能就是输入源串，输出单词符号，这里的输出单词符号包含两部分：单词类别和单词自身的值，类别和值由单词表给定。

可以以状态转换图为工具手工设计词法分析器。

确定有限自动机 DFA 是状态转换图的形式化。
DFA 是一种自动机，可以用于描述状态转换图，容易做程序实现，且任何一个 DFA 的程序实现框架是一样的，差别仅在于状态转移矩阵(相当于邻接矩阵)。
伪代码如下：

// cur_state = 初态
// 获取下一字符 ch
string str = "";
while(statetrans[cur_state][ch] 有定义)
{
    str += ch;
    cur_state = statetrans[cur_state][ch];
    if(cur_state 是终态)
        return str;
    // 获取下一字符
}

但是 DFA 不容易做设计，给定一个语言的单词表试图画一个 DFA 识别这种语言的话，很困难。

但是幸运的是设计非确定有限自动机 NFA 识别某种语言相对比较容易，NFA 和 DFA 是等价的。DFA 是 NFA 的特例，任何 NFA 都有算法可以转化为 DFA，即子集法。

给定单词表，用 NFA 做设计还是嫌有些难，但是幸运的是 NFA 和正则表达式之间可以互相转化。而拿到语言的单词表后，写正则表达式是相对容易的。

通过 语言单词表 -> 正则表达式 -> NFA -> DFA 这条路线得到 DFA，之后，还有成熟算法可以将 DFA 化简，使得状态数量最少。每个步骤的是有算法的(算法本身就是等价性的构造性证明)，因此可以自动化地实现。

词法规则还可以用文法描述，正则文法和 NFA 之间可以互相转化。

因此最终结论：如果要研究一个语言的词法分析，拿到单词表后有两种选择

用正则表达式描述词法规则
用正则文法描述词法规则

这两种方法都可以得到 NFA, 进而得到 DFA，进而优化 DFA 使得状态数最少。

以上就是词法分析的整体逻辑，涉及到文法，正则表达式，有限自动机，概念之间的关系如上图，其中每个箭头都有证明，而证明过程是一种构造性证明，这种构造性证明就是概念间进行转化的算法。
证明过程和算法的细节需要参考编译原理词法分析部分。

力扣上有几道经典的有限自动机的题目，涉及到的方法是上述词法分析逻辑链条中 以状态转换图为工具手工设计词法分析器 这一块，
而 DFA 是状态转换图的形式化，因此就是拿到较简单的单词表后手工设计对应的 DFA，进而画出状态转换图，写出状态转移矩阵。

$2 题目

1. 65. 有效数字

下面从词法分析的角度分析这道题：

字符集：

符号：+-
数字：0123456789
点：.
e：eE
空格： 
非法字符：所有其它字符

词汇表(词法规则)

前面可以有空格，后面可以有空格
最左边可以有+-
如果有小数点，小数点两边至少一边有数字就可以，
如果有 e/E，e/E 右边必须接数字，e接的数字可以有+-

按照 $1 的结论，拿到词汇表之后，可以写正则表达式或正则文法，自动化地得到 DFA；如果词汇表比较简单，手工设计DFA难度不大，也可以直接设计DFA

方法1: 正则表达式

由词法规则写出正则表达式 "^\\s*[+-]?(\\.\\d+|\\d+\\.?\\d*)([eE][+-]?\\d+)?\\s*$"

class Solution_2 {
public:
    bool isNumber(string s) {
        regex reg("^\\s*[+-]?(\\.\\d+|\\d+\\.?\\d*)([eE][+-]?\\d+)?\\s*$");
        bool flag = regex_match(s, reg);
        return flag;
    }
};

方法2: 手工设计 DFA

因状态数比较少，可以手工设计 DFA：

记 DFA $M = (S, \Sigma, f, S_{0}, F)$

首先看状态集合 $S$

-1: 非法状态
0: 开始的空格,如” “
1: 到e前的正负号，如” +”
2: 到e前左侧无数字的小数点，如” +.”
3: 到e前未遇到小数点的整数，如” +1”
4: 到e前的小数，如” +1.e”
5: 到e，如” +1.1e”
6: 到e后的正负号，如” +1.1e”
7: 到e后的整数，如” +1.1e1”
8: 到最后的空格，如” +1.1e1 “

再看字母表 $\Sigma$

空格
+-
0123456789
.
e
非法字符

初始状态 $S_{0} = 0$

终结状态 $F = \{3, 4, 7, 8\}$

DFA 从状态 0 开始逐字符读字符串，在某字符处状态转移后，若所得状态非法，直接返回 false，否则继续读下一字符，直至字符串耗尽。

当字符串耗尽，若到达终止状态，则返回 true，否则返回 false

状态转移函数 $f$ 以状态转换图表示。

根据装谈转换图，列出状态转移矩阵

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1

class Solution {
public:
    bool isNumber(string s) {
        if(s.empty()) return false;
        int n = s.size();

        int state = 0;
        vector<bool> finals({0, 0, 0, 1, 1, 0, 0, 1, 1}); // 合法的终止状态
        vector<vector<int> > transfer({
                {0,  1,  3,  2,  -1, -1},
                {-1, -1, 3,  2,  -1, -1},
                {-1, -1, 4,  -1, -1, -1},
                {8,  -1, 3,  4,  5,  -1},
                {8,  -1, 4,  -1, 5,  -1},
                {-1, 6,  7,  -1, -1, -1},
                {-1, -1, 7,  -1, -1, -1},
                {8,  -1, 7,  -1, -1, -1},
                {8,  -1, -1, -1, -1, -1},
                });

        for(int i = 0; i < n; ++i)
        {
            state = transfer[state][_make(s[i])];
            if(state < 0) return false;
        }
        return finals[state];
    }

private:
    int _make(const char& c)
    {
        switch(c)
        {
            case ' ': return 0;
            case '+': return 1;
            case '-': return 1;
            case '.': return 3;
            case 'e': return 4;
            default: return _number(c);
        }
    }

    int _number(char c)
    {
        if(c >= '0' && c <= '9')
            return 2;
        else
            return 5;
    }
};

2. 8. 字符串转换整数 (atoi)

方法1: 按要求模拟

思路

丢弃开头的空字符
第一个非空字符为有效整数字符(+-数字), 则与后续尽可能多的数字连起来
除有效整数部分之外，后续的字符忽略即可，不应对结果有影响

<1>空串，<2>仅含空字符的串，<3>第一个非空字符不是有效整数字符 -> 不需要进行转换
任何无法有效转换返回 0
爆INT时，根据正负返回 INT_MIN 或者 INT_MAX
仅 ‘ ‘ 认为是空字符

以上思路用到的基础设施

判断字符是否是数字(0~9)
判断字符是否是符号(+-)
判断字符是否是有效整数字符(+-以及0~9)
已知字符是数字的情况下，返回对应数字

更新结果的方式

以一个 int result 在遍历数字的阶段保存结果，初始是 0
每遍历到一个待加入到结果里的数字 iter, 更新结果的方式如下，可以理解为一个队列，iter 是进队的元素

result = result * 10 + iter

上面这一步公式是整个过程唯一可能会可能会爆 int 的地方，在执行之前，加一步判断(公式变形)
下面这个式子成立的话，则上面的式子会爆 int，直接根据正负直接返回 INT_MAX 或是 INT_MIN

result > (INT_MAX - iter) / 10

如果正常出了循环，说明此时的 result 在 [0, 2^32-1] 范围之内，不会再有爆 int 的情况，按照正负输出结果

方法2：有限自动机

记 DFA $M = (S, \Sigma, f, S_{0}, F)$

首先看状态集合 $S$

-1: 非法状态
0: 起始的空格
1: 起始的+-
2: 整数，例如(9, -11, +191)

再看字母表 $\Sigma$

空格
+-
0123456789
非法字符

初始状态 $S_{0} = 0$

终结状态 $F = \{2, 3\}$

DFA 从状态 0 开始逐字符读字符串，一边读一边更新结果。
在某字符处状态转移后，若所得状态非法，直接返回此时的结果，否则继续读下一字符，直至字符串耗尽。

当字符串耗尽，返回此时的结果。

状态转移函数 $f$ 以状态转换图表示。

class Solution {
public:
    int myAtoi(string str) {
        if(str.empty()) return 0;
        int n = str.size();
        int state = 0;
        vector<bool> finals({0, 0, 1});
        vector<vector<int>> transfer({
                {0,  1,  2, -1},
                {-1, -1, 2, -1},
                {-1, -1, 2, -1},
                });

        int sign = 1;
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            state = transfer[state][_make(str[i])];
            if(state < 0)
                return sign * ans;
            if(state == 1 && str[i] == '-')
                sign = -1;
            if(state == 2)
            {
                ans *= 10;
                ans += str[i] - '0';
            }
            if(ans * sign <= INT_MIN)
                return INT_MIN;
            if(ans * sign >= INT_MAX)
                return INT_MAX;
        }
        return sign * ans;
    }

private:
    int _make(const char& c)
    {
        switch(c)
        {
            case ' ': return 0;
            case '+': return 1;
            case '-': return 1;
            default: return _number(c);
        }
    }

    int _number(const char& ch)
    {
        if(ch >= '0' && ch <= '9')
            return 2;
        else
            return 3;
    }
};

3. 1262. 可被三整除的最大和

方法1：贪心

数组和为 sum
若 sum % 3 == 0 返回sum
若 sum % 3 == 1 sum 减去模3余1的数中最小的1个，或者减去模3余2中最小的2个
若 sum % 3 == 2 sum 减去模3余2的数中最小的1个，或者减去模3余1中最小的2个

方法2：动态规划

dp[i][j] : [0, i-1] 上选择能被3余j的和的最大值

dp[i][0] = max(dp[i-1][0], dp[i-1][0] + nums[i])  nums[i] % 3 == 0
           max(dp[i-1][0], dp[i-1][2] + nums[i])  nums[i] % 3 == 1
           max(dp[i-1][0], dp[i-1][1] + nums[i])  nums[i] % 3 == 2
dp[i][1] = max(dp[i-1][1], dp[i-1][1] + nums[i])  nums[i] % 3 == 0
           max(dp[i-1][1], dp[i-1][0] + nums[i])  nums[i] % 3 == 1
           max(dp[i-1][1], dp[i-1][2] + nums[i])  nums[i] % 3 == 2
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + nums[i])  nums[i] % 3 == 0
           max(dp[i-1][2], dp[i-1][2] + nums[i])  nums[i] % 3 == 1
           max(dp[i-1][2], dp[i-1][0] + nums[i])  nums[i] % 3 == 2

初始化：
dp[0][0] = 0
dp[0][1] = dp[0][2] = INT_MIN

方法3：有限自动机

有限自动机使用非常广泛: 例如正则表达式的引擎，编译器的词法和语法分析，网络协议等。

记 DFA $M = (S, \Sigma, f, S_{0}, F)$

首先看状态集合 $S$

0: 和模 3 余 0
1: 和模 3 余 1
2: 和模 3 余 2

再看字母表 $\Sigma$ : 正整数

初始状态 $S_{0} = 0$

终结状态 $F = \{0\}$

三个状态各有一个字段记录额外信息：当前的和的最大值

读取 nums 直至读完，对每个数字，更新 3 个状态的记录信息的字段。

vector<int> state({0, INT_MIN, INT_MIN});
for(int num: nums)
{
    vector<int> nxt(3);
    for(int s = 0; s <= 2; ++s)
    {
        nxt[(s + num) % 3] = max(state[(s + num) % 3], state[s] + n);
    }
    state = nxt;
}

4. 10. 正则表达式匹配

方法1: 动态规划

dp[i][j] := p[0..j-1] 是否能匹配 s[0..i-1]
dp[i][j] =
    dp[i - 1][j - 1] (p[j - 1] == . 或 p[j - 1] == s[i])
    false            (p[j - 1] != * 且 p[j - 1] != s[i])
    dp[i][j - 2] || (dp[i - 1][j] && (p[j - 2] == s[i - 1] 或 .))     (p[j - 1] == *)
初始化:
    dp[0..n][0..n] = false
    dp[0][0] = true
    dp[0][j] = dp[0][j - 2] (p[j - 1] == * 且 p[j - 2] != *)
迭代 i: 1..n; j: 1..m;
答案：dp[n][m]

考虑 dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p[j - 2] == s[i - 1] 或 .)) (p[j - 1] == *) 这个转移。

第一部分：dp[i][j - 2] 表示 s[0..i-1] 匹配 p[0..j-3]，即 p[j - 1] 的 * 匹配了 0 个 p[j - 2]
第二部分：当 p[j - 2] 即 p[j - 1] 的 * 前面的字母等于 s[i - 1] 或为 .，则 p[j - 1] 的 * 可以匹配 1 个 s[i - i]，继续看 s[i - 2]和 p[j - 1] 是否匹配，即 dp[i - 1][j]

精髓的地方是 dp[0][0] = 1 这个初始化。

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.empty() && p.empty()) return true;
        if(!s.empty() && p.empty()) return false;

        int n = s.size(), m = p.size();
        vector<vector<bool> > dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for(int j = 2; j <= m; j += 2)
            if(p[j - 1] == '*')
            {
                if(p[j - 2] != '*')
                    dp[0][j] = dp[0][j - 2];
                else
                    return false; // 剪枝
            }

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                if(p[j - 1] == s[i - 1] || p[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                {
                    if(p[j - 2] == '*')
                        return false; // 剪枝
                    dp[i][j] = dp[i][j - 2];
                    if(p[j - 2] == s[i - 1] || p[j - 2] == '.')
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        return dp[n][m];
    }
};

方法2：有限自动机

有限状态机根正则表达式是等价的。原因如下，以下是编译原理词法分析部分的结论。

正则表达式所匹配的所有字符串所构成的语言可以用有限自动机识别。正则集（正则表达式所匹配的所有字符串集合）是由右线性文法（3型文法）所产生的语言，两者是等价的。

DFA 需要根据 p 动态地构造，其中每个字符视为一个状态。这个实现还是挺复杂的，因为这里是要由正则表达式自动地生成有限自动机，而不是从简单的规则手工设计自动机。并且以下做法所得 DFA 一般是有冗余状态的，要优化状态数的化还涉及另外的算法，具体参考编译原理的词法分析部分。
这个题解 C++版状态机+DFS解法实现[注释完整] 写的还可以。

状态转换图可以用邻接表的形式给出。节点定义如下：

struct StateNode
{
    int state; // 状态序号 0为开始状态 
    char val;  // 状态值 对应p字符串中的char值
    bool isR;  // 是否为可变长节点（即后面是否紧跟*字符）
    int firstNotRNextState; // 第一个后继非可变长节点状态序号
    StateNode(int _state, char _val, bool _isR) : state(_state), val(_val), isR(_isR) {}
};

具体过程看代码。分 3 步，

建 DFA 邻接表的节点，主要区分起始节点，终止节点，中间节点，并要做各个节点的第一个非可变长节点状态序号的赋值
建 DFA 邻接表的边，边权为输入字符值，例如 transfer[0][1] = ‘a’ 表示当输入为’a’时状态机可从0状态变到1状态, transfer[0][1] = -1 表示当前输入任意字符, 状态机可从0状态变到1状态以对应p串中的’.’字符
开始深度优先遍历回溯，逐个输入 s 串至自动机以判定是否能够成功达到结束节点

以下算法是正确的，但是很慢，因为这个 DFA 是可优化的。

class Solution {
public:
    //状态机节点结构体
    struct StateNode
    {
        int state; // 状态序号 0为开始状态 
        char val;  // 状态值 对应p字符串中的char值
        bool isR;  // 是否为可变长节点（即后面是否紧跟*字符）
        int firstNotRNextState; // 第一个后继非可变长节点状态序号
        StateNode(int _state, char _val, bool _isR) : state(_state), val(_val), isR(_isR) {}
    };

    vector<StateNode> stateNodeList; // 状态节点列表
    bool rlt = false; // 全局结果

    bool isMatch(string s, string p)
    {
        // 1. 构造状态机节点列表
        // 统计状态数
        int stateNum = 0;
        for (int i = 0; i < p.size(); i++)
        {
            if ('*' != p[i])
                stateNum++;
        }

        // 构造开始节点
        StateNode startNode = StateNode(0, -1, false);
        stateNodeList.push_back(startNode);
        int state = 1;

        // 构造中间状态节点
        for (int i = 0; i < p.size(); i++)
        {
            if ('*' == p[i])
                continue;
            bool isR;
            if (i + 1 < p.size() && '*' == p[i + 1])
                isR = true;
            else
                isR = false;
            StateNode node = StateNode(state++, p[i], isR);
            stateNodeList.push_back(node);
        }

        // 构造结束节点
        StateNode endNode = StateNode(state++, -1, false);
        stateNodeList.push_back(endNode);

        // 各个节点的第一个非可变长节点状态序号赋值
        for (int i = 0; i < stateNodeList.size(); i++)
        {
            StateNode *node = &stateNodeList[i];
            node -> firstNotRNextState = -1;
            for (int j = node->state + 1; j < stateNodeList.size(); j++)
            {
                StateNode bnode = stateNodeList[j];
                if(!bnode.isR)
                {
                    node -> firstNotRNextState = bnode.state;
                    break;
                }
            }
        }

        // 2. 根据状态机列表构造自动机对应图，权重为输入字符值
        // 例如 G[0][1]='a' 表示当输入为'a'时状态机可从0状态变到1状态
        // 特别标识G[0][1]=-1表示当前输入任意字符状态机可从0状态变到1状态以对应p串中的'.'字符
        vector<vector<int>> G(stateNum + 2, vector<int>(stateNum + 2));
        for (int i = 0; i < stateNodeList.size(); i++)
        {
            StateNode node = stateNodeList[i];
            if (node.isR)
            {
                //可变长节点自己形成环
                if ('.' == node.val)
                {
                    //处理任意输入都匹配的'.'字符
                    G[node.state][node.state] = -1;
                }
                else
                {
                    G[node.state][node.state] = node.val;
                }
            }

            // 非可变长节点与后继的所有可变长节点建立状态变化通路
            if (-1 != node.firstNotRNextState)
            {
                for (int i = node.state + 1; i <= node.firstNotRNextState; i++)
                {
                    StateNode middleNode = stateNodeList[i];
                    if ('.' == middleNode.val)
                    {   
                        //处理任意输入都匹配的'.'字符
                        G[node.state][middleNode.state] = -1;
                    }
                    else
                    {
                        G[node.state][middleNode.state] = middleNode.val;
                    }
                }
            }
        }
        // 3.开始深度优先遍历回溯，逐个输入 s 串至自动机以判定是否能够成功达到结束节点
        dfs(s, 0, 0, G);
        return rlt;
    }

    // 参数说明 index:s串输入下标 state：当前处理状态序号 G:自动机对应图
    void dfs(string s, int index, int state, vector<vector<int>> &G)
    {
        // 递归深度边界控制
        if (index > s.size())
            return;
        int stateNum = stateNodeList.size();
        StateNode curNode = stateNodeList[state];
        // 成功边界：s串扫描至末尾时，当前状态节点的第一个后继非可变长节点为结束节点
        if (stateNum - 1 == curNode.firstNotRNextState && index == s.size())
        {
            rlt = true;
            return;
        }

        char temp = s[index];
        // 遍历当前节点的所有后继子节点
        for (int i = state; i < stateNum; i++)
        {   
            // 值匹配或者'.'任意匹配成功
            if (G[state][i] == temp || G[state][i] == -1)
            {
                // 进入下一层处理s串中的下一个字符
                dfs(s, index + 1, i, G);
            }
        }
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法编译原理

词法分析-有限自动机

$1 词法分析和有限自动机

$2 题目

1. 65. 有效数字

方法1: 正则表达式

方法2: 手工设计 DFA

2. 8. 字符串转换整数 (atoi)

方法1: 按要求模拟

方法2：有限自动机

3. 1262. 可被三整除的最大和

方法1：贪心

方法2：动态规划

方法3：有限自动机

4. 10. 正则表达式匹配

方法1: 动态规划

方法2：有限自动机

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1

state	空格	+-	0~9	.	e	非法
0	0	1	3	2	-1	-1
1	-1	-1	3	2	-1	-1
2	-1	-1	4	-1	-1	-1
3	8	-1	3	4	5	-1
4	8	-1	4	-1	5	-1
5	-1	6	7	-1	-1	-1
6	-1	-1	7	-1	-1	-1
7	8	-1	7	-1	-1	-1
8	8	-1	-1	-1	-1	-1