這篇文章介紹如何用Parser Combinator實(shí)現(xiàn)一個(gè)簡(jiǎn)單的正則表達(dá)式引擎。
Cursor
Cursor封裝了字符串的狀態(tài)，表示一個(gè)光標(biāo)位置。光標(biāo)位置只能向后移動(dòng)，可以方便地獲取光標(biāo)指向的字符，以及判斷是否到達(dá)字符串末尾。
public class Cursor {
private final String input;
private final int index;
public Cursor(String input, int index) {
this.input = input;
this.index = index;
}
/**
* 是否到達(dá)字符串結(jié)尾
*/
public boolean end() {
return index == input.length();
}
/**
* 當(dāng)前指向的字符
*/
public char current() {
return input.charAt(index);
}
/**
* 光標(biāo)向后移動(dòng)一個(gè)字符
*/
public Cursor next() {
return new Cursor(input, index + 1);
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Cursor cursor = (Cursor) o;
return index == cursor.index && Objects.equals(input, cursor.input);
}
@Override
public int hashCode() {
return Objects.hash(input, index);
}
/**
* 方便輸出顯示
*/
@Override
public String toString() {
return String.format("Cursor{parsed: '%s', remain: '%s'}",
input.substring(0, index), input.substring(index));
}
}
測(cè)試代碼：
Cursor cursor = new Cursor("hello", 0);
while (!cursor.end()) {
System.out.println(cursor);
System.out.println("current: " + cursor.current());
cursor = cursor.next();
}
輸出結(jié)果：
Cursor{parsed: '', remain: 'hello'}
current: h
Cursor{parsed: 'h', remain: 'ello'}
current: e
Cursor{parsed: 'he', remain: 'llo'}
current: l
Cursor{parsed: 'hel', remain: 'lo'}
current: l
Cursor{parsed: 'hell', remain: 'o'}
current: o
Cursor被設(shè)計(jì)成不可變的，主要是為了簡(jiǎn)化Parser的實(shí)現(xiàn)。如果Cursor是可變的，則在解析的過程中需要時(shí)刻注意保存當(dāng)前光標(biāo)的位置，這樣十分麻煩。
Cursor的equals方法和hashCode方法用于判斷重復(fù)的Cursor狀態(tài)，因?yàn)榻酉聛砦覀円?code>Cursor放進(jìn)集合里。
Regex
Regex封裝了對(duì)字符串的解析操作，它從一個(gè)光標(biāo)位置開始解析字符串，返回解析后所有可能的光標(biāo)位置。
public interface Regex {
Set<Cursor> parse(Cursor input);
default boolean match(String input) {
return parse(new Cursor(input, 0)).stream().anyMatch(Cursor::end);
}
}
parse方法就是解析操作的具體實(shí)現(xiàn)，它從一個(gè)光標(biāo)開始嘗試向后解析，返回解析之后所有可能的光標(biāo)位置。使用Set作為返回值類型，可以對(duì)匹配結(jié)果進(jìn)行去重，避免重復(fù)解析相同的狀態(tài)。
match方法是對(duì)parse方法的簡(jiǎn)單封裝，它用來判斷當(dāng)前Regex是否能消耗掉整個(gè)字符串。只要在解析結(jié)果中存在一個(gè)到達(dá)字符串末尾的光標(biāo)位置，就說明當(dāng)前解析器能把字符串消耗完。
接下來，我們會(huì)實(shí)現(xiàn)一些基本的Regex實(shí)現(xiàn)類，使用它們可以將任意正則表達(dá)式轉(zhuǎn)換成一個(gè)Regex的實(shí)例。調(diào)用Regex的match方法，并傳入待匹配的字符串，就能判斷這個(gè)字符串是否與正則表達(dá)式匹配。
原子Regex
下面實(shí)現(xiàn)兩個(gè)基本的Regex，雖然它們只能實(shí)現(xiàn)簡(jiǎn)單的功能，但是后面將非常有用。
首先是匹配單個(gè)指定字符的解析器：
public class Ch implements Regex {
private final char c;
public Ch(char c) {
this.c = c;
}
@Override
public Set<Cursor> parse(Cursor input) {
if (input.end() || input.current() != c) {
return Collections.emptySet();
}
return Set.of(input.next());
}
}
如果當(dāng)前光標(biāo)沒有到達(dá)字符串結(jié)尾，且指向的字符等于給定字符，它會(huì)消耗掉這個(gè)字符，然后返回剩余的部分，否則返回一個(gè)空列表作為解析失敗的結(jié)果。
測(cè)試代碼：
Regex r = new Ch('a');
System.out.println(r.parse(new Cursor("abc", 0)));
System.out.println(r.parse(new Cursor("xyz", 0)));
System.out.println(r.parse(new Cursor("", 0)));
輸出結(jié)果：
[Cursor{parsed: 'a', remain: 'bc'}]
[]
[]
與之類似的，還有匹配任意單個(gè)字符的解析器，對(duì)應(yīng)于正則表達(dá)式中的元字符.：
public class Any implements Regex {
@Override
public Set<Cursor> parse(Cursor input) {
if (input.end()) {
return Collections.emptySet();
}
return Set.of(input.next());
}
}
測(cè)試代碼：
Regex r = new Any();
System.out.println(r.parse(new Cursor("abc", 0)));
System.out.println(r.parse(new Cursor("xyz", 0)));
System.out.println(r.parse(new Cursor("", 0)));
輸出結(jié)果：
[Cursor{parsed: 'a', remain: 'bc'}]
[Cursor{parsed: 'x', remain: 'yz'}]
[]
我們現(xiàn)在已經(jīng)有了能夠匹配單個(gè)字符的Regex，但是它們并不能做很多事情，最多只能讓光標(biāo)向前移動(dòng)一個(gè)字符。我們急需一種能夠?qū)⒍鄠€(gè)小的Regex組合成一個(gè)復(fù)雜的Regex的機(jī)制。
Regex的組合
接下來這幾個(gè)Regex非常重要，它們可以將一個(gè)或多個(gè)Regex包裝成一個(gè)功能更強(qiáng)大的Regex。
假設(shè)我們有一個(gè)Ch('a')和一個(gè)Ch('b')，如何用它們組合成一個(gè)能夠匹配字符串ab的Regex呢？請(qǐng)看下面Concat的實(shí)現(xiàn)，它表示對(duì)輸入串依次應(yīng)用lhs和rhs這兩個(gè)Regex，并返回所有能夠得到的結(jié)果，對(duì)應(yīng)于正則表達(dá)式中的連接操作。
public class Concat implements Regex {
private final Regex lhs, rhs;
public Concat(Regex lhs, Regex rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
@Override
public Set<Cursor> parse(Cursor input) {
Set<Cursor> r = new HashSet<>();
for (Cursor c : lhs.parse(input)) {
r.addAll(rhs.parse(c));
}
return r;
}
}
測(cè)試代碼：
Regex r = new Concat(new Ch('a'), new Ch('b'));
System.out.println(r.parse(new Cursor("abc", 0)));
System.out.println(r.parse(new Cursor("xyz", 0)));
System.out.println(r.parse(new Cursor("ac", 0)));
輸出結(jié)果：
[Cursor{parsed: 'ab', remain: 'c'}]
[]
[]
只要lhs和rhs任意一個(gè)解析器解析失敗，都會(huì)導(dǎo)致返回結(jié)果為空。
注意，lhs和rhs可能返回多個(gè)解析結(jié)果，因此在實(shí)現(xiàn)的過程中需要遍歷所有可能的結(jié)果。
返回值類型為Set確保了結(jié)果中不會(huì)存在重復(fù)的狀態(tài)。
多個(gè)Concat可以串聯(lián)使用，例如，以下Regex匹配以abc開頭的字符串：
Regex r = new Concat(new Ch('a'), new Concat(new Ch('b'), new Ch('c')));
與此對(duì)應(yīng)的還有Or，它表示從lhs或rhs中選擇一個(gè)執(zhí)行，對(duì)應(yīng)于正則表達(dá)式中的|運(yùn)算符：
public class Or implements Regex {
private final Regex lhs, rhs;
public Or(Regex lhs, Regex rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
@Override
public Set<Cursor> parse(Cursor input) {
Set<Cursor> result = new HashSet<>(lhs.parse(input));
result.addAll(rhs.parse(input));
return result;
}
}
測(cè)試代碼：
Regex r = new Or(new Ch('a'), new Ch('b'));
System.out.println(r.parse(new Cursor("apple", 0)));
System.out.println(r.parse(new Cursor("banana", 0)));
System.out.println(r.parse(new Cursor("cat", 0)));
輸出結(jié)果：
[Cursor{parsed: 'a', remain: 'pple'}]
[Cursor{parsed: 'b', remain: 'anana'}]
[]
接下來的ZeroOrMore是一個(gè)很重要的Regex，它實(shí)現(xiàn)了正則表達(dá)式中*運(yùn)算符的功能。它嘗試對(duì)當(dāng)前光標(biāo)多次應(yīng)用parser，每次應(yīng)用都會(huì)產(chǎn)生一個(gè)不同的光標(biāo)位置。在實(shí)現(xiàn)的過程中，使用Queue來進(jìn)行廣度優(yōu)先搜索，同時(shí)用一個(gè)額外的Set來避免重復(fù)搜索。
public class ZeroOrMore implements Regex {
private final Regex parser;
public ZeroOrMore(Regex parser) {
this.parser = parser;
}
@Override
public Set<Cursor> parse(Cursor input) {
Set<Cursor> result = new HashSet<>();
Queue<Cursor> queue = new LinkedList<>(List.of(input));
Set<Cursor> set = new HashSet<>(Set.of(input));
while (!queue.isEmpty()) {
int cnt = queue.size();
while (cnt-- > 0) {
Cursor cursor = queue.remove();
result.add(cursor);
for (Cursor c : parser.parse(cursor)) {
if (!set.contains(c)) {
queue.add(c);
set.add(c);
}
}
}
}
return result;
}
}
測(cè)試代碼：
Regex r = new ZeroOrMore(new Ch('a'));
System.out.println(r.parse(new Cursor("aaa", 0)));
輸出結(jié)果：
[
Cursor{parsed: '', remain: 'aaa'},
Cursor{parsed: 'a', remain: 'aa'},
Cursor{parsed: 'aa', remain: 'a'},
Cursor{parsed: 'aaa', remain: ''}
]
與之類似的，還有OneOrMore，對(duì)應(yīng)于正則表達(dá)式中的+運(yùn)算符。它的實(shí)現(xiàn)與ZeroOrMore及其類似，只是搜索的起始條件不同。
public class OneOrMore implements Regex {
private final Regex parser;
public OneOrMore(Regex parser) {
this.parser = parser;
}
@Override
public Set<Cursor> parse(Cursor input) {
Set<Cursor> result = new HashSet<>();
Set<Cursor> start = parser.parse(input);
Queue<Cursor> queue = new LinkedList<>(start);
Set<Cursor> set = new HashSet<>(start);
while (!queue.isEmpty()) {
int cnt = queue.size();
while (cnt-- > 0) {
Cursor cursor = queue.remove();
result.add(cursor);
for (Cursor c : parser.parse(cursor)) {
if (!set.contains(c)) {
queue.add(c);
set.add(c);
}
}
}
}
return result;
}
}
測(cè)試代碼：
Regex r = new OneOrMore(new Ch('a'));
System.out.println(r.parse(new Cursor("aaa", 0)));
輸出結(jié)果：
[
Cursor{parsed: 'a', remain: 'aa'},
Cursor{parsed: 'aa', remain: 'a'},
Cursor{parsed: 'aaa', remain: ''}
]
構(gòu)造復(fù)雜的解析器
有了以上的原子Regex和各種組合手段，就可以構(gòu)造出任意復(fù)雜的Regex了，以下是正則表達(dá)式((a|b)c*)+對(duì)應(yīng)的Regex：
Regex r = new OneOrMore(new Concat(new Or(new Ch('a'), new Ch('b')), new ZeroOrMore(new Ch('c'))));
可以看到，這樣的寫法嵌套很深，用起來不方便，因此我們?cè)?code>Regex接口中添加一些靜態(tài)方法和默認(rèn)方法：
public interface Regex {
...
static Regex any() {
return new Any();
}
static Regex ch(char c) {
return new Ch(c);
}
default Regex concat(Regex rhs) {
return new Concat(this, rhs);
}
default Regex or(Regex rhs) {
return new Or(this, rhs);
}
default Regex zeroOrMore() {
return new ZeroOrMore(this);
}
default Regex oneOrMore() {
return new OneOrMore(this);
}
}
然后就可以通過鏈?zhǔn)秸{(diào)用構(gòu)造復(fù)雜的Regex了：
import static xxx.Regex;
// ((a|b)c*)+
Regex r = ch('a').or(ch('b')).concat(ch('c').zeroOrMore()).oneOrMore();
測(cè)試代碼：
System.out.println(r.match("acccbcccc"));
System.out.println(r.match("abcc"));
輸出結(jié)果：
true
false
從字符串生成Regex
到這里，其實(shí)我們已經(jīng)實(shí)現(xiàn)了一個(gè)簡(jiǎn)易的正則表達(dá)式執(zhí)行引擎，支持正則表達(dá)式中常用的操作，包括連接、選擇、重復(fù)等，并可以很容易地進(jìn)行擴(kuò)展，只需添加新的Regex實(shí)現(xiàn)類。
我們可以手動(dòng)調(diào)用方法來構(gòu)造任意復(fù)雜的Regex，但是，當(dāng)表達(dá)式比較復(fù)雜時(shí)，手動(dòng)構(gòu)造的方式還是比較麻煩，所以下面實(shí)現(xiàn)了一個(gè)簡(jiǎn)易的正則表達(dá)式語法解析器RegexParser，它使用遞歸下降算法把一個(gè)正則表達(dá)式的字符串轉(zhuǎn)換成一個(gè)Regex對(duì)象。這個(gè)解析器僅僅支持有限的正則表達(dá)式元素，包括普通字符、括號(hào)優(yōu)先級(jí)，以及.、*、+等元字符。有興趣的讀者可以很容易地進(jìn)行擴(kuò)展。
public class RegexParser {
private final String expr;
private int index;
public RegexParser(String expr) {
this.expr = expr;
}
private void init() {
index = 0;
}
private char peek() {
return expr.charAt(index);
}
private char next() {
return expr.charAt(index++);
}
private void read(char c) throws RegexParseException {
if (c != next()) {
throw new RegexParseException("expected: " + c);
}
}
private boolean end() {
return index == expr.length();
}
public Regex parse() throws RegexParseException {
init();
try {
return parseExpr();
} catch (RegexParseException e) {
throw e;
} catch (Exception e) {
throw new RegexParseException("unknown error: " + e.getMessage());
}
}
// elem = char | (expr)
private Regex parseElem() throws RegexParseException {
if (peek() == '(') {
next();
Regex r = parseExpr();
read(')');
return r;
} else if (peek() == '.') {
next();
return any();
} else {
return ch(next());
}
}
// factor = elem* | elem+ | elem
private Regex parseFactor() throws RegexParseException {
Regex r = parseElem();
if (!end() && peek() == '*') {
r = r.zeroOrMore();
next();
} else if (!end() && peek() == '+') {
r = r.oneOrMore();
next();
}
return r;
}
// term = factor factor ... factor
private Regex parseTerm() throws RegexParseException {
Regex r = parseFactor();
while (!end() && peek() != ')' && peek() != '|') {
r = r.concat(parseFactor());
}
return r;
}
// expr = term|term|...|term
private Regex parseExpr() throws RegexParseException {
Regex r = parseTerm();
while (!end() && peek() == '|') {
next();
r = r.or(parseTerm());
}
return r;
}
}
同時(shí)在Regex接口中添加一個(gè)靜態(tài)方法：
public interface Regex {
...
static Regex of(String expr) throws RegexParseException {
return new RegexParser(expr).parse();
}
}
然后就可以像下面這樣構(gòu)造一個(gè)正則表達(dá)式：
Regex r = Regex.of("((a|b)c*)+");
上面這行代碼生成的Regex等價(jià)于：
Regex r = ch('a').or(ch('b')).concat(ch('c').zeroOrMore()).oneOrMore();
