算法编译原理

词法分析：正则表达式

字数统计: 2.4k字   |   阅读时长: 10分
, , , ,

摘要: 正则表达式的用法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

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

  1. 用正则表达式描述词法规则。
  2. 用正则文法描述词法规则。

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

本文通过两个题看一下 Python 和 C++ 中如何使用正则表达式组件，避免手工设计 DFA 而直接解决词法分析的问题。其中第一题是我们之前用手工设计 DFA 的方式解决过的问题，可以与正则表达式的方法对比。

65. 有效数字

有效数字（按顺序）可以分成以下几个部分：

  1. 一个 小数 或者 整数
  2. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）
  2. 下述格式之一：
  • 至少一位数字，后面跟着一个点 ‘.’
  • 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
  • 一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）
  2. 至少一位数字

部分有效数字列举如下：[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分无效数字列举如下：[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “—6”, “-+3”, “95a54e53”]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

示例 1：
输入：s = “0”
输出：true

示例 2：
输入：s = “e”
输出：false

示例 3：
输入：s = “.”
输出：false

提示：

1
2
1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

词法规则分析

字符集：

1
2
3
4
5
6
符号：+-
数字：0123456789
点：.
e：eE
空格： 
非法字符：所有其它字符

词汇表(词法规则)

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

算法1：DFA

对于简单的问题，可以手工设计 DFA，因为节点数比较少代码量可以控制。

这个词法规则比较简单，手工画出的自动机有 9 个节点，设计和实现都是可行的。

DFA 的理论和代码模，以及本题的状态转换图，可以参考文章 词法分析-有限自动机。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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：正则表达式

对于简单的问题，正则表达式在设计和实现上也比有限自动机好用。

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

代码 (C++)

1
2
3
4
5
6
7
8
9
10
#include <regex>

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

468. 验证IP地址

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 “IPv4” ；如果是有效的 IPv6 地址，返回 “IPv6” ；如果不是上述类型的 IP 地址，返回 “Neither” 。

有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。 其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。

一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:

  • 1 <= xi.length <= 4
  • xi 是一个 十六进制字符串 ，可以包含数字、小写英文字母( ‘a’ 到 ‘f’ )和大写英文字母( ‘A’ 到 ‘F’ )。
  • 在 xi 中允许前导零。

例如 “2001:0db8:85a3:0000:0000:8a2e:0370:7334” 和 “2001:db8:85a3:0:0:8A2E:0370:7334” 是有效的 IPv6 地址，而 “2001:0db8:85a3::8A2E:037j:7334” 和 “02001:0db8:85a3:0000:0000:8a2e:0370:7334” 是无效的 IPv6 地址。

提示：

1
queryIP 仅由英文字母，数字，字符 '.' 和 ':' 组成。

示例 1：
输入：queryIP = “172.16.254.1”
输出：”IPv4”
解释：有效的 IPv4 地址，返回 “IPv4”

示例 2：
输入：queryIP = “2001:0db8:85a3:0:0:8A2E:0370:7334”
输出：”IPv6”
解释：有效的 IPv6 地址，返回 “IPv6”

示例 3：
输入：queryIP = “256.256.256.256”
输出：”Neither”
解释：既不是 IPv4 地址，又不是 IPv6 地址

算法：正则表达式

对于复杂的问题，节点数和边数上来了，手工设计 DFA 就容易把自己绕进去。而正则表达式在描述规则和代码量上都明显比 DFA 好用。

ipv4 词法规则

字符集：

1
2
点：.
数字：0123456789

词汇表(词法规则)

1
2
3
4
三个点连接四个 chunk
一个 chunk 内是 0-255
chunk 不能有前导零
chunk 不能为空

正则表达式：

1
2
chunk_IPv4 = r'([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])'
pattern_IPv4 = re.compile(r'^(' + chunk_IPv4 + r'\.){3}' + chunk_IPv4 + r'$')

ipv6 词法规则

字符集：

1
2
3
冒号： :
数字: 0123456789
字母: abcdefABCDEF

词汇表(词法规则)

1
2
3
4
5
6
七个冒号连接八个 chunk
每个 chunk 内是由 0-9a-fA-F 组成的十六进制数
chunk 的数字没有大小限制
chunk 的长度不能大于 4
chunk 可以有前导零
chunk 不能为空

正则表达式

1
2
chunk_IPv6 = r'([0-9a-fA-F]{1,4})'
pattern_IPv6 = re.compile(r'^(' + chunk_IPv6 + r'\:){7}' + chunk_IPv6 + r'$')

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import re

class Solution:
    chunk_IPv4 = r'([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])'
    pattern_IPv4 = re.compile(r'^(' + chunk_IPv4 + r'\.){3}' + chunk_IPv4 + r'$')

    chunk_IPv6 = r'([0-9a-fA-F]{1,4})'
    pattern_IPv6 = re.compile(r'^(' + chunk_IPv6 + r'\:){7}' + chunk_IPv6 + r'$')

    def validIPAddress(self, IP: str) -> str:
        if '.' in IP:
            return "IPv4" if self.pattern_IPv4.match(IP) else "Neither"
        if ':' in IP:
            return "IPv6" if self.pattern_IPv6.match(IP) else "Neither"
        return "Neither"

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <regex>
#include <string>

using namespace std;

class Solution {
public:
    string validIPAddress(string IP) {
        string ipv4_chunk = "([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])";
        string pattern_ipv4 = "^(" + ipv4_chunk + "\\.){3}" + ipv4_chunk + "$";
        string ipv6_chunk = "([0-9a-fA-F]{1,4})";
        string pattern_ipv6 = "^(" + ipv6_chunk + "\\:){7}" + ipv6_chunk + "$";
        regex reg_ipv4(pattern_ipv4);
        regex reg_ipv6(pattern_ipv6);
        if(regex_match(IP, reg_ipv4))
            return "IPv4";
        if(regex_match(IP, reg_ipv6))
            return "IPv6";
        return "Neither";
    }
};

2288. 价格减免

句子 是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 ‘$’ 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个 价格 。

  • 例如 “$100”、”$23” 和 “$6” 表示价格，而 “100”、”$” 和 “$1e5 不是。

给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并 更新 该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。

返回表示修改后句子的字符串。

注意：所有价格 最多 为 10 位数字。

提示：

1
2
3
4
5
6
7
1 <= sentence.length <= 1e5
sentence 由小写英文字母、数字、' ' 和 '$' 组成
sentence 不含前导和尾随空格
sentence 的所有单词都用单个空格分隔
所有价格都是 正 整数且不含前导零
所有价格 最多 为  10 位数字
0 <= discount <= 100

示例 1：
输入：sentence = “there are $1 $2 and 5$ candies in the shop”, discount = 50
输出：”there are $0.50 $1.00 and 5$ candies in the shop”
解释：
表示价格的单词是 “$1” 和 “$2” 。

  • “$1” 减免 50% 为 “$0.50” ，所以 “$1” 替换为 “$0.50” 。
  • “$2” 减免 50% 为 “$1” ，所以 “$1” 替换为 “$1.00” 。

示例 2：
输入：sentence = “1 2 $3 4 $5 $6 7 8$ $9 $10$”, discount = 100
输出：”1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$”
解释：
任何价格减免 100% 都会得到 0 。
表示价格的单词分别是 “$3”、”$5”、”$6” 和 “$9”。
每个单词都替换为 “$0.00”。

算法：正则表达式

通过正则表达式识别一个字符串是否为一个十进制小数，包含负数。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import re

def is_decimal_number(s: str) -> bool:
    # 正则表达式匹配十进制数，包括小数点和负号
    pattern = r'^-?\d+(\.\d+)?$'
    if re.match(pattern, s):
        return True
    else:
        return False

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split()
        for i, w in enumerate(words):
            if w[0] == "$" and is_decimal_number(w[1:]):
                num = float(w[1:])
                if num > 0:
                    new_number = num * (1 - discount / 100)
                    words[i] = "${:.2f}".format(new_number)
        return " ".join(words)
Share