编译原理-词法分析(手动实现正则表达式java)
大家都知道编译的第一步就是词法分析,将字符串转换成一个个 Token ,而后再根据这些 Token 构建抽样语法树(AST)。
而进行词法分析就必需用到正则表达式,本篇文章就是分析正则表达式实现原理,以及使用 java 语言实现一个简单的正则表达式。
说起正则表达式啊,想起笔者刚学完
java的时候去找工作,面试的时候,听到有一个老员工在说,这个匹配邮箱的正则怎样写啊?那个时候我心里在想,这个员工水平怎样这么低,连个正则都不会写啊。
后来才明白是我太年轻了啊,工作几年我也连正则不会写了,全都忘光了啊,遇到要匹配的公式都是临时去网上查啊。
本篇文章内的源码: 这里
一. 正则表达式
1.1 正则语言
- 语言的定义:
由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言,记为L(G)。
公式就是: L(G)={w∣S ⇒* w, w∈VT*}
S ⇒* w 表示从文法
G的开始符号S经过若干(可以是0)步推导究竟一个文法符号串w。
假如这个文法符号串w( w ∈ (VN∪VT)* ),串里面既有终结符又有非终结符;那么w就是文法G的一个句型。
假如这个文法符号串w( w∈(VT)* ),串里面只有终结符;那么w就是文法G的一个句子。从这里看句子就是一个特殊的句型。
{}符号在这里是数学上集合的意思,也就是代表所有句子的集合。
正则语言就是由正则文法的开始符号
S推导出的所有句子构成的集合。
例如:
有一个正则文法 S→aB; B→aB; B→bB; B→ε 有这四个产生式。
它能生成的句子就是由a加上0次或者者屡次的ab串;即为 L(G)={a}{a, b}* 。正则表达式(Regular Expression, RE)是一种用来形容正则语言的更紧凑的表示方法。
上面那个公式可以用正则表达式
r表示, 即 r = a(a∣b)*
- 正则文法和正则表达式
对任何正则文法
G,存在定义同一语言的正则表达式r;
对任何正则表达式r,存在生成同一语言的正则文法G。
1.2 正则表达式的定义
通过正则表达式 r 所生成的句子集合也就是正则语言,即为 L(G)
例如
r=a, 这是一个正则表达式,a是一个终结符;那么对应的语言L(G)={a}。L(G)语言的终结符串集合中只有一个元素a。
1.2.1 定义
设 ∑ 是一个字母表,则 ∑ 上的正则表达式及其所表示的正则语言可递归地定义如下:
ε是一个正则表达式( r = ε),则L(ε) = {ε}a是字母表∑上一个字符,它也是一个正则表达式( r = a),则L(a) = {a}- 假设
r和s都是字母表∑上一个字符,也都是简单的正则表达式(r=r, r=s),那么它们对应的语言分别是L(r)和L(s),则有下面公式:
1 .r∣s是一个正则表达式RE, 则 L(r|s) = L(r) U L(s)。(并操作)
2 .rs是一个正则表达式RE, 则 L(rs) = L(r)L(s)。(连接操作)
3 . r* 是一个正则表达式RE, 则 L(r) = (L(r))。 (克林闭包操作)
4 . (r) 是一个正则表达式RE, 则 L((r)) = (L(r)) = L(r)。
运算符的优先级为:() >* > &(连接操作)>|(并操作)
一般大的正则表达式是可以由小的正则表达式按照特定规则递归地构建而成的。递归规则就是上面四个操作。
也就是说,一个正则表达式可以分解为多个小的正则表达式,这个概念要记住,正则表达式转换成非确定有穷自动机NFA就是靠这个特性。
例如一个简单例子:
假如字母表 ∑ = {a,b},那么
- L(a|b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
- L((a∣b)(a∣b)) = L(a∣b) L(a∣b)={a, b} {a, b}={aa, ab, ba, bb}
- L(a* ) = (L(a))* = {a}* = {ε, a, aa, aaa, …}
- L((a|b)* ) = (L(a|b))* = {a, b}* = {ε, a, b, aa, ab, …}
- L(a|a* b) = L(a) ∪ L(a* b) = L(a) U ( L(a* ) L(b) ) = {a} U ({a}*{b}) = {a, b, ab, aab, …}
1.2.2 正则表达式的代数定律
| 定律 | 形容 |
|---|---|
| r∣s = s∣r | |是可以交换的 |
| r∣(s∣t) = (r∣s)∣t | |是可以结合的 |
| r(st) = (rs)t | 连接是可以结合的 |
| r(s∣t)= rs∣rt; (s∣t)r=sr∣tr | 连接对 | 是可分配的 |
| εr = rε = r | ε是连接的单元 |
| r* = (r∣ε)* | 闭包中肯定包含ε |
| r** = r* | *具备幂等性 |
1.2.3 正则定义
正则定义式具备如下形式的定义序列:
d1→r1d2→r2...dn→rn有如下规则:
- 每个
di都是一个新符号,它们都不在字母表Σ中,而且各不相同。即(d1,d2,…dn都是新符号,不是字母表Σ字符) - 每个
ri的字符都属于Σ U {d1,d2,...d(i-1)}。 即产生右部的字符ri,可以字母表Σ中字符,和这个产生式之前产生式左部的字符,即{d1,d2,...d(i-1)}
例如一般标识符的正则定义:
- digit → 0∣1∣2∣…∣9
- letter_ → A∣B∣…∣Z∣a∣b∣…∣z∣_
- id → letter_(letter_∣digit)*
digit表示0-9中的一个数字;letter_表示一个字母或者者下划线;id表示字母打头的字母数字串,就是标识符。
对应的正则表达式就是 r = A∣B∣…∣Z∣a∣b∣…∣z∣_( A∣B∣…∣Z∣a∣b∣…∣z∣ _ |0∣1∣2∣…∣9)*
二. 有穷自动机(FA)
2.1 起源与定义
- 有穷自动机(Finite Automata,FA)由两位神经物理学家MeCuloch和Pitts于1948年首先提出,是对一类解决系统建立的数学模型;
- 这类系统具备一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息解决的状况);
- 系统只要要根据当前所处的状态和当前面临的输入信息即可以决定系统的后继行为。每当系统解决了当前的输入后,系统的内部状态也将发生改变。
简单了解就是,有穷自动机内部有一个状态集合(集合数量是有限的,所以叫有穷的状态),当它遇到一系列离散的输入时,会根据当前的状态和输入值,进入下一个状态。也就是说下一个状态只会由当前的状态和输入值来决定。
2.2 转换图
转换图.png
- 图中的节点就代表
FA状态,即0,1,2,3;其中
1 .0表示开始状态(初始状态),有且只有一个,由start箭头指向。
2 .3表示终止状态(接收状态):可以有多个,用双圈表示。 - 带标记的箭头叫做有向边。
即对于输入
a,存在一个从状态p到状态q的转换,就在p、q之间画一条有向边,并标记上a。
2.3 有穷自动机对应语言
假如给定输入串x,有穷自动机(FA)存在一个对应串x的从初始状态到某个终止状态的转换序列, 那么该输入串x 能被该有穷自动机(FA)接收。
那么由一个有穷自动机(FA)接收的所有串构成的集合, 就称为该有穷自动机(FA)对应的语言,记为 L(M),其中,M表示的是 Machine。
注: 有穷自动机(
FA)接收输入串x,遵循最长子串匹配准则(Longest String Matching Principle)
最长子串匹配准则(Longest String Matching Principle)
- 当输入串的多个前缀与一个或者多个模式匹配时,总是选择最长的前缀进行匹配。
- 在到达某个终态之后,只需输入带上还有符号,DFA就继续前进,以便寻觅尽可能长的匹配。
2.4 有穷自动机公式
M=(S, Σ, δ, s0, F)S: 表示有穷状态的集合。Σ: 表示输入字母表,即输入符号集合。δ: 表示一个状态转换函数。对于任一状态s,遇到任一输入符号a,得到的下一个状态。
即当s∈S, a∈Σ时,δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态。
注: 假如是DFA,那么这里就是下一个状态;假如是NFA,那么这里就是下一个状态集合。
s0: 开始状态(或者初始状态), s0∈SF:接收状态(或者终止状态)集合,F⊆S。
注: 根据
δ公式,对于当前状态s,遇到输入字符a时,返回是单一状态,还是状态集合,将有穷自动机分为确定的有穷自动机(DFA) 和非确定的有穷自动机(NFA)
三. 非确定的有穷自动机(NFA)
NFA 就是当前状态s 遇到输入符号a 时,得到是下一个状态集合。也就是说,它不确定下一个状态是什么,所以叫做非确定的有穷自动机。
先说 NFA 的起因是由于正则表达式 RE 很容易就转换成 NFA。 这里一般就用到了 Thompson 算法。
3.1 Thompson 算法
Thompson 算法非常简单,它就是利用了正则表达式是可以由小的正则表达式按照特定规则递归地构建而成的原理。
3.1.1 基础规则
对于空串 ε , 即正则表达式
r = ε, 对应NFA的转换图
ε构造.png对于输入符号
a, 即正则表达式r = a, 对应NFA的转换图
a构造.png
3.1.2 归纳规则
对于正则表达式
r = a | b,构造为
a|b.png对于正则表达式
r = ab,构造为
ab.png对于正则表达式 r = a* , 构造为
a*.png
a* 表示
0次或者者屡次,也可以表示为 a*=a+|ε 。这里的a+就表示a出现一次或者者屡次。
通过 Thompson 算法,我们即可以将一个正则表达式转成一个非确定的有穷自动机(NFA) 。
3.2 代码实现(java)
代码的主要功能就是将一个正则表达式,转换成一个 NFA 的转换图。
3.2.1 NFAState 类
package xinhao.regex;import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set;/** * @author by xinhao 2021/8/8 * 表示 NFA 转换图中的状态 */public class NFAState implements Comparable<NFAState> { // 表示 ε 空串 public static final String EPSILON = "epsilon"; private static int idGenerate = 0; // 标志是状态几 private int id; // NFA 转换图中,当前状态通往下一个状态所有有向边 private Map<String, Set<NFAState>> edges; // 表示当前状态是不是终止状态 private boolean isEnd; public NFAState() { } // 创立状态节点 public static NFAState create() { NFAState state = new NFAState(); state.id = idGenerate++; state.edges = new HashMap<>(); return state; } // 增加当前状态遇到输入字符 `path` ,进入的一个状态。就是其中一条有向边 public void addEdge(String path, NFAState nextState) { Set<NFAState> set = edges.get(path); if (set == null) { set = new HashSet<>(); edges.put(path, set); } set.add(nextState); } public Map<String, Set<NFAState>> getEdges() { return edges; } public int getId() { return id; } public boolean isEnd() { return isEnd; } public void setEnd(boolean end) { isEnd = end; } @Override public String toString() { final StringBuilder sb = new StringBuilder("["); sb.append("id=").append(id); sb.append(']'); return sb.toString(); } @Override public int compareTo(NFAState o) { return id - o.id; }}NFAState 表示 NFA 的转换图中的状态节点。
那么我们思考一下,这个状态节点NFAState应该有那些属性呢?
- 需要一个
id属性来区分不同的状态节点。 - 需要一个
isEnd属性来表示这个状态节点是不是终止状态。 - 还需要一个
edges属性来表示这个状态节点到达下一个节点的所有有向边。
对于
NFA转换图来说,当前节点可以匹配多个输入符号 (a,b),并且对于同一个输入符号a, 能得到一个状态集合。
所以edges定义为Map<String, Set<NFAState>>类型。
3.2.2 NFAGraph 类
package xinhao.regex;/** * @author by xinhao 2021/8/8 * 表示 NFA 对应的转换图 */public class NFAGraph { // 开始状态节点 private NFAState startState; // 结束状态节点,注意它不肯定是终止状态, // 一般过程图的结束状态节点就不是终止状态,一般最后大转换图的结束状态才是终止状态。 private NFAState endState; private NFAGraph() { } private NFAGraph(NFAState startState, NFAState endState) { this.startState = startState; this.endState = endState; } // 对应 Thompson 算法基础规则中的,遇到字符 a public static NFAGraph createByPath(String path) { // 创立开始和终止状态节点 NFAState newStart = NFAState.create(); NFAState newEnd = NFAState.create(); // 增加一条开始到终止状态节点的有向边 newStart.addEdge(path, newEnd); return new NFAGraph(newStart, newEnd); } // 对应操作符 &; 对应 Thompson 算法归纳规则中的连接操作 public void addSerial(NFAGraph nextGraph) { // 将本转换图的结束状态节点,增加一个 ε有向边 连接到下一个本转换图开始节点 this.endState.addEdge(NFAState.EPSILON, nextGraph.startState); // 升级一个本转换图的结束状态节点,就得到一个新的转换图了。 this.endState = nextGraph.endState; } // 对应操作符 |; 对应 Thompson 算法归纳规则中的并操作 public void addParallel(NFAGraph nextGraph) { // 创立新的开始和终止状态节点 NFAState newStart = NFAState.create(); NFAState newEnd = NFAState.create(); // 根据 Thompson 算法,我们要增加四条 ε有向边 newStart.addEdge(NFAState.EPSILON, this.startState); newStart.addEdge(NFAState.EPSILON, nextGraph.startState); this.endState.addEdge(NFAState.EPSILON, newEnd); nextGraph.endState.addEdge(NFAState.EPSILON, newEnd); // 升级本转换图的开始和结束状态节点,得到一个新的转换图了。 this.startState = newStart; this.endState = newEnd; } // 对应操作符 * 即0次以上 public void repeatStar() { // 将 * 分为1次以上和0次 repeatPlus(); zero(); } // 对应操作符 + 即一次以上 public void repeatPlus() { // 创立新的开始和终止状态节点 NFAState newStart = NFAState.create(); NFAState newEnd = NFAState.create(); // 根据 Thompson 算法,我们要增加三条 ε有向边 newStart.addEdge(NFAState.EPSILON, this.startState); this.endState.addEdge(NFAState.EPSILON, newEnd); this.endState.addEdge(NFAState.EPSILON, this.startState); // 升级本转换图的开始和结束状态节点,得到一个新的转换图了。 this.startState = newStart; this.endState = newEnd; } // 对应0次 public void zero() { // 增加 ε有向边 this.startState.addEdge(NFAState.EPSILON, this.endState); } public NFAState getStartState() { return startState; } public NFAState getEndState() { return endState; }}NFAGraph 就是表示 NFA 对应的转换图。
根据 Thompson 算法, 一个大的转换图可以看成由小的转换图按照肯定的规则构建的。NFAGraph 就是借助 Thompson 算法来生成一个转换图。
- 重要属性 :
startState和endState表示开始状态节点和结束状态节点。
这个结束状态节点
endState并不肯定是转换图的终止状态,由于这个NFAGraph可能只是整个NFA转换图中的一部分。所以终止状态是等生成整个NFA转换图后,再进行设置。
createByPath方法
// 对应 Thompson 算法基础规则中的,遇到字符 a public static NFAGraph createByPath(String path) { // 创立开始和终止状态节点 NFAState newStart = NFAState.create(); NFAState newEnd = NFAState.create(); // 增加一条开始到终止状态节点的有向边 newStart.addEdge(path, newEnd); return new NFAGraph(newStart, newEnd); }对应 Thompson 算法中基础规则
addSerial方法
// 对应操作符 &; 对应 Thompson 算法归纳规则中的连接操作 public void addSerial(NFAGraph nextGraph) { // 将本转换图的结束状态节点,增加一个 ε有向边 连接到下一个本转换图开始节点 this.endState.addEdge(NFAState.EPSILON, nextGraph.startState); // 升级一个本转换图的结束状态节点,就得到一个新的转换图了。 this.endState = nextGraph.endState; }对应 Thompson 算法归纳规则中的连接操作
addParallel方法
// 对应操作符 |; 对应 Thompson 算法归纳规则中的并操作 public void addParallel(NFAGraph nextGraph) { // 创立新的开始和终止状态节点 NFAState newStart = NFAState.create(); NFAState newEnd = NFAState.create(); // 根据 Thompson 算法,我们要增加四条 ε有向边 newStart.addEdge(NFAState.EPSILON, this.startState); newStart.addEdge(NFAState.EPSILON, nextGraph.startState); this.endState.addEdge(NFAState.EPSILON, newEnd); nextGraph.endState.addEdge(NFAState.EPSILON, newEnd); // 升级本转换图的开始和结束状态节点,得到一个新的转换图了。 this.startState = newStart; this.endState = newEnd; }对应 Thompson 算法归纳规则中的并操作
repeatStar方法
// 对应操作符 * 即0次以上 public void repeatStar() { // 将 * 分为1次以上和0次 repeatPlus(); zero(); } // 对应操作符 + 即一次以上 public void repeatPlus() { // 创立新的开始和终止状态节点 NFAState newStart = NFAState.create(); NFAState newEnd = NFAState.create(); // 根据 Thompson 算法,我们要增加三条 ε有向边 newStart.addEdge(NFAState.EPSILON, this.startState); this.endState.addEdge(NFAState.EPSILON, newEnd); this.endState.addEdge(NFAState.EPSILON, this.startState); // 升级本转换图的开始和结束状态节点,得到一个新的转换图了。 this.startState = newStart; this.endState = newEnd; } // 对应0次 public void zero() { // 增加 ε有向边 this.startState.addEdge(NFAState.EPSILON, this.endState); }将 Thompson 算法归纳规则中 * 操作,拆分成两个方法。
3.2.3 正则表达式生成 NFAGraph
NFAGraph 就表示 NFA 对应的转换图,那么如何通过正则表达式生成对应的 NFAGraph 实例呢?
例如对于一个正则表达式 r = a(b|c)* ,它表示一个以
a开头后面跟着0个或者多个bc串。
首先要一一读取这个正则表达式 a(b|c)* , 生成对应的小的 NFAGraph 实例,而后根据规则生成大的 NFAGraph 实例。
必需注意运算符的优先级: () > * > &(连接操作)> |(并操作)
3.2.3.1 Reader 类
public class Reader { public static Reader create(String regex) { Reader reader = new Reader(); reader.source = regex.toCharArray(); return reader; } // 正则表达式对应的字符数组 private char[] source; // 记录已经读取字符的下标 private int pos; // 查看对应下标的字符, pos 不添加 public char peek() { return source[pos]; } // 获取pos下标对应的字符, 并将 pos 添加 1 public char next() { if (pos >= source.length) { throw new RuntimeException("下标越界 length:" + source.length + " pos:" + pos); } return source[pos++]; } // 能否还有下一个字符 public boolean hasNext() { return pos < source.length; } // 一直读取到字符 ch public String readUntil(char ch) { StringBuilder builder = new StringBuilder(); while (peek() != ch) { builder.append(next()); } // 不包括 ch next(); return builder.toString(); } // 读取剩下的字符串 public String readUntilEnd() { StringBuilder builder = new StringBuilder(); while (hasNext()) { builder.append(next()); } return builder.toString(); }}这个类就是用来一一读取正则表达式的字符。readUntil 方法用来寻觅正则表达式子串的,例如 () 里面包括的子串。readUntilEnd 方法读取剩下的字符串,用来生成对应的 NFAGraph 实例,再与前面的 NFAGraph 实例进行规制合并,采用不断递归的方法,即可以生成完整的 NFAGraph 转换图了。
3.2.3.2 createNFAGraph 生成 NFAGraph 转换图
/** * 通过 pattern 生成对应的 NFAGraph 转换图 * @param pattern * @return */ public static NFAGraph createNFAGraph(String pattern) { Reader reader = Reader.create(pattern); NFAGraph graph = null; while (reader.hasNext()) { char ch = reader.next(); switch (ch) { case '(' : // 通过递归的方法,生成子串对应的 NFAGraph 转换图 NFAGraph subGraph = createNFAGraph(reader.readUntil(')')); // 由于 * ? + 这些符号的优先级比 连接 高,就先解决 handleStar(subGraph, reader); // 进行规制合并 NFAGraph 转换图 if (graph == null) { graph = subGraph; } else { // 进行 连接 操作 graph.addSerial(subGraph); } break; case '|' : // 通过递归的方法,生成子串对应的 NFAGraph 转换图 NFAGraph nextGraph = createNFAGraph(reader.readUntilEnd()); // 这里不需要解决 * ? + 这些符号,由于 reader.readUntilEnd() 已经读取了剩余的一律字符,不会有这些符号了。 if (graph == null) { graph = nextGraph; } else { // 进行 并 操作 graph.addParallel(nextGraph); } break; default: // 根据字符ch 生成一个小的 NFAGraph 转换图 NFAGraph pathGraph = NFAGraph.createByPath("" + ch); // 由于 * ? + 这些符号的优先级比 连接 高,就先解决 handleStar(pathGraph, reader); if (graph == null) { graph = pathGraph; } else { // 进行 连接 操作 graph.addSerial(pathGraph); } break; } } return graph; } /** * 解决 * ? + 这些符号优先级 * @param subGraph * @param reader * @return */ private static NFAGraph handleStar(NFAGraph subGraph, Reader reader) { if (reader.hasNext()) { char ch = reader.peek(); switch (ch) { case '*' : // 0次或者屡次 subGraph.repeatStar(); reader.next(); break; case '?' : // 0次 或者 1 次 subGraph.zero(); reader.next(); break; case '+' : // 1次以上 subGraph.repeatPlus(); reader.next(); break; } } return subGraph; }可以看出我们采用递归调用的方法,由小的 NFAGraph 转换图合并成一个完整的 NFAGraph 转换图。
3.2.3.3 printNFAGraphByBFS 查看生成的图 NFAGraph
/** * 采用广度优先遍历的方式,来打印这个 NFAGraph 转换图中的有向边 * @param nfaGraph */ public static void printNFAGraphByBFS(NFAGraph nfaGraph) { // 采用广度优先遍历的算法,需要一个先入先出的队列数据结构来辅助 Queue<NFAState> queue = new LinkedList<>(); // 由于 NFAGraph 是一个图结构,而不是一个树结构,所以它的边不是单向的,存在循环指向的问题; // 因而我们需要一个 addedSet 集合来记录,已经增加到queue 队列中的节点,否则可能会进入死循环。 // 注: 这里只需是增加到 queue 的节点,就马上增加到 addedSet 集合中。 Set<NFAState> addedSet = new HashSet<>(); queue.add(nfaGraph.getStartState()); addedSet.add(nfaGraph.getStartState()); StringBuilder builder = new StringBuilder(); while (!queue.isEmpty()) { NFAState state = queue.poll(); builder.append("状态"+state+":"); for (Map.Entry<String, Set<NFAState>> entry : state.getEdges().entrySet()) { String path = entry.getKey(); Set<NFAState> stateSet = entry.getValue(); builder.append("\t路径["+path+"]有"+stateSet.size()+"条: "); for (NFAState childState : stateSet) { // 假如没有增加过,那么就增加到 queue 队列中 if (!addedSet.contains(childState)) { queue.add(childState); addedSet.add(childState); } builder.append(state); builder.append("--"+path+"-->"); builder.append(childState); builder.append(";\t"); } builder.append("\n\t\t\t"); } builder.append("\n"); } System.out.print(builder.toString()); }采用广度优先遍历的方式,来查看生成 NFAGraph 转换图的情况。
3.2.3.4 简单例子
public static void main(String[] args) { String pattern = "a(b|c)*"; NFAGraph graph = createNFAGraph(pattern); // 设置转换图的结束状态节点 就是终止状态节点 graph.getEndState().setEnd(true); printNFAGraphByBFS(graph);}输出结果:
状态[id=0]: 路径[a]有1条: [id=0]--a-->[id=1]; 状态[id=1]: 路径[epsilon]有1条: [id=1]--epsilon-->[id=8]; 状态[id=8]: 路径[epsilon]有2条: [id=8]--epsilon-->[id=6]; [id=8]--epsilon-->[id=9]; 状态[id=6]: 路径[epsilon]有2条: [id=6]--epsilon-->[id=4]; [id=6]--epsilon-->[id=2]; 状态[id=9]:状态[id=4]: 路径[c]有1条: [id=4]--c-->[id=5]; 状态[id=2]: 路径[b]有1条: [id=2]--b-->[id=3]; 状态[id=5]: 路径[epsilon]有1条: [id=5]--epsilon-->[id=7]; 状态[id=3]: 路径[epsilon]有1条: [id=3]--epsilon-->[id=7]; 状态[id=7]: 路径[epsilon]有2条: [id=7]--epsilon-->[id=6]; [id=7]--epsilon-->[id=9]; 与我们手动写出来 a(b|c)* 对应的转换图是一样的。
3.2.3.5 进行字符串的匹配
我们已经将正则表达式生成对应 NFA 的转换图了,那么我们如何进行匹配呢?
根据定义我们知道,所谓的匹配就是对于一个待匹配的输入字符串
s,在NFA的对应转换图中,找到一个从开始状态节点到终止状态节点的转换序列;
假如能找到就是匹配,否则就是不匹配。
由于 NFA 的转换图中,当前状态节点遇到输入字符对应的下一个状态节点可能有多个,因而我们可能要对所有可能的情况进行尝试,直到找到对应的转换序列。
其实对于整个匹配过程,需要注意三点:
- 对于输入字符串
s,NFA的转换图能够匹配完它的所有字符,那就要看最后的状态节点是不是终止状态的节点。 - 对于输入字符串
s,NFA的转换图不能够匹配完它的所有字符,即NFA的转换图已经遍历完了,却不能匹配输入字符串s所有字符。 - 转换图遵循最长子串匹配准则,所以优先匹配空边(ε 有向边)“
/** * 对于一个输入字符串 regex , 在转换图 NFAGraph 中是否找到一个从初始状态到某个终止状态的转换序列。 * 能找到,返回ture,表示能匹配 * @param graph 转换图 * @param regex 待匹配的字符串 * @param recordState 记录一下匹配的路径 * @return */ public static boolean isMatch(NFAGraph graph, String regex, RecordNFAState recordState) { return isMatch(graph.getStartState(), regex.toCharArray(), 0, recordState); } /** * 通过递归调用来决定能否匹配 * @param currentState * @param chars * @param pos * @param recordState * @return */ public static boolean isMatch(NFAState currentState, char[] chars, int pos, RecordNFAState recordState) { // 当 pos == chars.length 时,表示已经匹配完最后一个字符。 // 接下来就是看是否得到终止状态的节点 if (pos == chars.length) { // 得到当前节点currentState 的 所有 ε 有向边。 // 由于 FA 有最长子串匹配准则,所以优先先找空边(ε 有向边) 对应状态节点是不是终止状态的节点 Set<NFAState> epsilonSet = currentState.getEdges().getOrDefault(NFAState.EPSILON, EMPTY); for (NFAState state : epsilonSet) { // 记录一下当前匹配路径 recordState.setNextByPath(NFAState.EPSILON, state); // 递归调用 isMatch 方法,来判断能否匹配 if (isMatch(state, chars, pos, recordState.getNext())) { // 假如匹配,则直接返回 true return true; } } // 当前节点是终止状态的节点,那么匹配成功,返回 true if (currentState.isEnd()) { return true; } // 假如以上都不匹配,而且已经匹配完最后一个字符,那么就说明这个 currentState 对应的匹配转换序列是不成功的。 // 返回 false return false; } // 假如还没有匹配完所有的输入字符,那么就先匹配输入字符。 // 优先匹配空边 (ε 有向边) 对应状态节点 Set<NFAState> epsilonSet = currentState.getEdges().getOrDefault(NFAState.EPSILON, EMPTY); for (NFAState state : epsilonSet) { // 记录一下当前匹配路径 recordState.setNextByPath(NFAState.EPSILON, state); // 递归调用 isMatch 方法,来判断能否匹配 // 这里 pos 没有任何变化,由于是空边 (ε 有向边),没有匹配任何字符 if (isMatch(state, chars, pos, recordState.getNext())) { return true; } } String path = "" + chars[pos]; // 当前节点的有向边集合中能否包含当前输入字符, if (currentState.getEdges().containsKey(path)) { // 得到当前输入字符对应的有向边集合 Set<NFAState> pathSet = currentState.getEdges().getOrDefault(path, EMPTY); for (NFAState state : pathSet) { // 记录一下当前匹配路径 recordState.setNextByPath(path, state); // 当前节点能不能找到一条匹配转换序列匹配剩下输入字符; // 这里将 pos + 1, 由于当前 pos 对应的输入字符已经匹配 if (isMatch(state, chars, pos + 1, recordState.getNext())) { return true; } } } return false; }方法流程已经在代码中标注清晰了。RecordNFAState 类只是用来记录匹配转换序列。
package xinhao.regex;/** * @author by xinhao 2021/8/8 * 记录一下匹配转换序列 */public class RecordNFAState { // 当前状态节点 private NFAState state; // 匹配的下一个状态节点 private RecordNFAState next; // 使用的匹配路径 private String path; public RecordNFAState(NFAState state) { this.state = state; } public static RecordNFAState create(NFAState state) { return new RecordNFAState(state); } public void setNextByPath(String path, NFAState next) { this.path = path; this.next = create(next); } public NFAState getState() { return state; } public RecordNFAState getNext() { return next; } public String getPath() { return path; }}最后进行匹配
public static void main(String[] args) { String pattern = "a(b|c)*"; NFAGraph graph = createNFAGraph(pattern); // 设置转换图的结束状态节点 就是终止状态节点 graph.getEndState().setEnd(true); String regex = "abbcbcb"; RecordNFAState recordState = RecordNFAState.create(graph.getStartState()); boolean isMatch = isMatch(graph, regex, recordState); System.out.println("isMatch(" + regex + "):" + isMatch); RecordNFAState rs = recordState; while (rs != null) { StringBuilder builder = new StringBuilder(); builder.append("[(状态" + rs.getState().getId() + ")"); builder.append("--"+rs.getPath()+"-->"); builder.append(rs.getNext() == null ? "null" : "(状态"+rs.getNext().getState().getId()+")"); builder.append("]"); System.out.println(builder.toString()); rs = rs.getNext(); } }输入结果:
[(状态0)--a-->(状态1)][(状态1)--epsilon-->(状态8)][(状态8)--epsilon-->(状态6)][(状态6)--epsilon-->(状态2)][(状态2)--b-->(状态3)][(状态3)--epsilon-->(状态7)][(状态7)--epsilon-->(状态6)][(状态6)--epsilon-->(状态2)][(状态2)--b-->(状态3)][(状态3)--epsilon-->(状态7)][(状态7)--epsilon-->(状态6)][(状态6)--epsilon-->(状态4)][(状态4)--c-->(状态5)][(状态5)--epsilon-->(状态7)][(状态7)--epsilon-->(状态6)][(状态6)--epsilon-->(状态2)][(状态2)--b-->(状态3)][(状态3)--epsilon-->(状态7)][(状态7)--epsilon-->(状态6)][(状态6)--epsilon-->(状态4)][(状态4)--c-->(状态5)][(状态5)--epsilon-->(状态7)][(状态7)--epsilon-->(状态6)][(状态6)--epsilon-->(状态2)][(状态2)--b-->(状态3)][(状态3)--epsilon-->(状态7)][(状态7)--epsilon-->(状态9)][(状态9)--null-->null]四. 确定的有穷自动机(DFA)
4.1 FDA 和 DFA 的转换
我们知道 FDA 和 DFA 区别就是,转换图中当前状态遇到输入字符 a 时,得到是下一个状态,还是下一个状态集合。
对于
DFA来说,它的下一个状态是确定;而对于FDA来说,它的下一个状态是不确定。
因而,匹配一个输入字符串 s 时
- 对于
DFA来说,只要要遍历输入字符串s,看当前状态是否找到对应输入字符的下一个状态,假如没有就匹配失败,假如有就继续匹配,直到匹配完整个输入字符串s,再查看最后状态是不是终止状态。 - 但是对于
FDA来说,由于当前状态对应输入字符的下一个状态是不确定的,当匹配不成功时,它可能需要回溯到上一个节点,继续匹配,直到匹配成功,或者者遍历了整个FDA转换图。
有没有一种方式,将 FDA 转换成 DFA。
还是回到原点,
FDA和DFA区别就是DFA得到下一个状态,FDA得到的是下一个状态集合。
那么我们能不能将这个FDA状态集合就看做一个新的DFA状态。而后这个新的DFA状态中的FDA状态集合对应输入字符a能得到所有FDA状态集合又是一个新的DFA状态。
这样就能得到DFA中,确定的状态了。简单来说一个DFA状态对应FDA的状态集合。
这个方式就称为子集构造法。
4.2 子集构造法
4.2.1 重要概念
| 方法 | 形容 |
|---|---|
| edge(s, a) | 从NFA状态 s沿着字符 a 可以到达的 NFA状态的集合 |
| edge(T, a) | NFA状态集合 T 中每个状态 s 沿着字符 a 可以到达的NFA状态的集合的合集 |
| ε-closure(s) | 从 NFA 的状态 s 开始只通过空边(ε 有向边)到达的NFA状态集合 |
| ε-closure(T) | NFA状态集合 T 中每个状态 s 通过空边(ε 有向边)到达的NFA状态集合的合集 |
这四个方法都是用来生成 DFA 状态的重要方法。
edge(s, a)和edge(T, a)可以得到当前NFA状态或者者状态集合,沿着输入字符a能够到达的所有NFA状态的集合,这个是生成新的DFA状态关键。
但是仅靠edge方法还不够,由于NFA转换图中存在空边(ε 有向边),即不需要输入字符,即可以到达另一个NFA状态,那么它们也需要增加到新生成的DFA状态对应的NFA状态集合中。这里就用到了ε-closure(s)和ε-closure(T)方法。
4.2.2 算法实现
- edge(T, a) 算法
一般都是根据你定义的储存结构,获取输入字符
a对应的NFA状态集合,再将它们合并起来。
- ε-closure(T) 算法
将T的所有状态压入stack中;将ε-closure (T)初始化为T;while(stack非空) { 将栈顶元素t 给弹出栈中; for(每个满足如下条件的u: 从t出发有一个标号为ε的转换到达状态u) // 不在 u 不在ε-closure (T)中,说明 u 还没有被寻觅过空边,所以增加到ε-closure (T)和栈中。 if( u不在ε-closure (T)中) { 将u加入到ε-closure (T)中; 将u压入栈中; }}借助栈 stack 数据结构,来寻觅NFA状态集合 T, 对应的所有空边得到的NFA状态。
由于栈
stack能够实现深度遍历,所以能够找到NFA状态s直接空边或者者间接空边得到的所有状态。
- 构造转换表的算法
一开始,ε-closure (s_0) 是Dstates中的唯一状态,且它未加标记;while在(Dstates中有一个未标记状态T){ 给T加上标记; for (每个输入符号a){ U = ε-closure(move(T,a)); if(U不在Dstates中) 将U加入到Dstates中,且不加标记; Dtran[T,a] = U; }}Dstates 存储着由 NFA 转换成的所有 DFA 的状态。Dtran 是一个转换表,状态表的行都是 DFA 的状态,状态表的列都是输入字符,储存的值也是DFA 的状态。
Dtran的意义就是对于任一DFA的状态,遇到任一输入字符都可以从这个Dtran转换表找到对应的唯一状态。
算法分析:
- 首先将
NFA的开始状态节点转换成DFA的节点,并存储到Dstates中。 - 遍历
Dstates,找到一个未标记的DFA的节点,假如找不到,那么表示已经转换成功,直接返回。 - 将未标记的
DFA的节点进行标记,而后针对每一个输入字符,创立对应的DFA的节点。 - 这个新的
DFA的节点对应的NFA状态集合可能和之前之前创立的DFA的节点一样。那我们就说这两个DFA的节点是相同的。就不需要重复增加到Dstates中了。 Dtran[T,a] = U,表示当前DFA的节点遇到输入字符a对应的状态就是创立的状态U。
这个方法就能得到我们需要的转换表
Dtran
DFA匹配算法
s = s_0;c = nextChar();while(c! = eof) { s = move(s,c); c = nextChar();}if (s在F中) return "yes";else return "no";s_0就是DFA开始状态。- 遍历输入字符串。
move(s, c)方法就是通过转换表获取下一个DFA状态。- 最后判断得到状态
s是不是终止状态。
4.3 代码实现 (java)
4.3.1 DFAState
package xinhao.regex;import java.util.Objects;import java.util.Set;/** * @author by xinhao 2021/8/8 * 表示 DFA 转换图中的状态 */public class DFAState { // 对应的 NFA 转换图中的状态集合 private final Set<NFAState> stateSet; // NFA 转换图中的状态集合对应的唯一标志,用来两个 DFA 能否相等 private final String statesId; // 表示当前状态是不是终止状态 private final boolean isEnd; // 这个 tag 只是辅助作用, private boolean isTag; private DFAState(Set<NFAState> stateSet, String statesId, boolean isEnd) { this.stateSet = stateSet; this.statesId = statesId; this.isEnd = isEnd; } /** * 通过 NFA 转换图中的状态集合生成对应的 DFA 状态 * @param stateSet * @return */ public static DFAState create(Set<NFAState> stateSet) { StringBuilder idBuilder = new StringBuilder(); // 生成对应 DFA 状态的 id 标志 stateSet.stream().sorted().forEach(state -> idBuilder.append(state.getId()+",")); boolean isEnd = false; for (NFAState state : stateSet) { // 假如 stateSet 集合中有一个状态节点是终止状态节点, // 那么这个新生成的 DFA 状态节点也是终止状态节点 if (state.isEnd()) { isEnd = true; break; } } return new DFAState(stateSet, idBuilder.toString(), isEnd); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; DFAState dfaNFAState = (DFAState) o; return statesId.equals(dfaNFAState.statesId); } @Override public int hashCode() { return Objects.hash(statesId); } public void setTag(boolean tag) { isTag = tag; } public Set<NFAState> getNFAStateSet() { return stateSet; } public String getNFAStatesId() { return statesId; } public boolean isTag() { return isTag; } public boolean isEnd() { return isEnd; } @Override public String toString() { final StringBuilder sb = new StringBuilder("DFANFAState{"); sb.append("statesId='").append(statesId).append('\''); sb.append(", isEnd=").append(isEnd); sb.append('}'); return sb.toString(); }}表示 DFA 的状态节点,它包含了一个 NFA 状态节点集合 stateSet。
4.3.2 DFAGraph
package xinhao.regex;import java.util.HashMap;import java.util.Map;/** * @author by xinhao 2021/8/8 */public class DFAGraph { public static final String[] PATHS = {"0","1","2","3","4","5","6","7","8","9",".","a", "b", "c"}; public static final Map<String, DFAState> EMPTY = new HashMap<>(); // DFA 开始状态节点 private DFAState start; // DFA 对应的转换表。采用 Map<DFAState, Map<String, DFAState>> 表明它是一个二维数组,可以转换成 DFAState[][] 的格式 private Map<DFAState, Map<String, DFAState>> stateTable; public DFAGraph(DFAState start) { this.start = start; } public static DFAGraph create(DFAState start) { DFAGraph dfaGraph = new DFAGraph(start); dfaGraph.stateTable = new HashMap<>(); return dfaGraph; } /** * 向转换表中增加数据 * @param currentState * @param path * @param state */ public void addStateTable(DFAState currentState, String path, DFAState state) { Map<String, DFAState> pathMap = stateTable.get(currentState); if (pathMap == null) { pathMap = new HashMap<>(); stateTable.put(currentState, pathMap); } pathMap.put(path, state); } /** * 获取对应的下一个状态节点 * @param currentState * @param path * @return */ public DFAState getStateByMove(DFAState currentState, String path) { return stateTable.getOrDefault(currentState, EMPTY).get(path); } public DFAState getStart() { return start; } public Map<DFAState, Map<String, DFAState>> getStateTable() { return stateTable; } @Override public String toString() { final StringBuilder sb = new StringBuilder("DFAGraph{"); sb.append("start=").append(start); sb.append(", stateTable=").append(stateTable); sb.append('}'); return sb.toString(); }}DFAGraph 中最重要的属性就是 stateTable,记录 DFA 的转换表。
4.3.3 edge 方法
/** * 得到 DFA 状态节点 经过 path 后得到的所有 NFA 状态节点集合。 * @param tState * @param path * @return */ public static Set<NFAState> edge(DFAState tState, String path) { Set<NFAState> resultSet = new HashSet<>(); // 当前 DFA 状态对应的 NFA 状态集合 for (NFAState state : tState.getNFAStateSet()) { if (state.getEdges().containsKey(path)) { resultSet.addAll(state.getEdges().get(path)); } } return resultSet; }4.3.4 closure 方法
/** * 得到 ε-closure 的 NFA 状态集合 * @param state * @return */ public static Set<NFAState> closure(NFAState state) { Set<NFAState> states = new HashSet<>(); states.add(state); return closure(states); } /** * 得到 ε-closure 的 NFA 状态集合 * @param states * @return */ public static Set<NFAState> closure(Set<NFAState> states) { Stack<NFAState> stack = new Stack<>(); stack.addAll(states); Set<NFAState> closureSet = new HashSet<>(states); while (!stack.isEmpty()) { NFAState state = stack.pop(); // 得到状态 state 对应的空边 状态集合 Set<NFAState> epsilonSet = state.getEdges().getOrDefault(NFAState.EPSILON, EMPTY); for (NFAState epsilonState : epsilonSet) { // 假如不存在,就是新发现的状态,增加到 closureSet 和 stack 中 if (!closureSet.contains(epsilonState)) { closureSet.add(epsilonState); stack.push(epsilonState); } } } return closureSet; }4.3.5 NFAToDFA 方法
/** * 从 dfaStates 集合中寻觅一个未标记的 DFA 状态节点 * @param dfaStates * @return */ public static DFAState getNoTagState(Set<DFAState> dfaStates) { for (DFAState state : dfaStates) { if (!state.isTag()) { return state; } } return null; } /** * NFA 转换成 DFA * @param nfaGraph * @return */ public static DFAGraph NFAToDFA(NFAGraph nfaGraph) { // 创立开始的 DFA 状态 DFAState startDFAState = DFAState.create(closure(nfaGraph.getStartState())); // 创立 DFAGraph 图 DFAGraph dfaGraph = DFAGraph.create(startDFAState); // 这个集合记录所有生成的 DFA 状态节点 Set<DFAState> dfaStates = new HashSet<>(); // 将开始状态节点增加到 dfaStates 中 dfaStates.add(startDFAState); DFAState TState; // 从 dfaStates 集合中寻觅一个未标记的 DFA 状态节点 while ((TState = getNoTagState(dfaStates)) != null) { // 进行标记,防止重复遍历 TState.setTag(true); // 遍历输入字符 for (String path : DFAGraph.PATHS) { // 创立新的 DFA 状态节点 DFAState UState = DFAState.create(closure(edge(TState, path))); // 不包含就增加 if (!dfaStates.contains(UState)) { dfaStates.add(UState); } // 增加转换表 dfaGraph.addStateTable(TState, path, UState); } } return dfaGraph; }4.3.6 isDFAMatch 方法
public static boolean isMatch(DFAGraph dfaGraph, String regex) { char[] chars = regex.toCharArray(); int pos = 0; DFAState dfaState = dfaGraph.getStart(); while (pos < chars.length) { String path = "" + chars[pos++]; // 从转换表中获取当前状态 dfaState 遇到字符 path,得到下一个状态 dfaState dfaState = dfaGraph.getStateByMove(dfaState, path); } return dfaState.isEnd(); }4.3.6 简单示例
public static void main(String[] args) { String pattern = "a(b|c)*"; NFAGraph nfaGraph = NFARegexUtil.createNFAGraph(pattern); nfaGraph.getEndState().setEnd(true); DFAGraph dfaGraph = NFAToDFA(nfaGraph); String regex = "abbccb"; boolean isMatch = isMatch(dfaGraph, regex); System.out.println("isMatch(" + regex + "):" + isMatch); }输出结果:
isMatch(abbccbb22):true1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 编译原理-词法分析(手动实现正则表达式java)