词法分析:正则表达式

  |  

摘要: 正则表达式的用法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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";
}
};

Share