用 CPS 实现字符串匹配。基于讲座 https://youtu.be/cnhb4M8-J5M

CpsRegex.fsx

type Re = 
    | Lit of char
    | Seq of Re * Re
    | Or of Re * Re
    | Star of Re

let rec match2 (re: Re) (str: char list) k =
    match re with
        | Lit(c) -> match str with                       
                        | [] -> false
                        | x::xs -> (x = c) && (k xs) 
        | Seq(a, b) -> match2 a str (fun rest -> match2 b rest k)
        | Or(a, b) -> match2 a str k || match2 b str k
        | Star(a) -> match2 a str (fun rest -> match2 (Star a) rest k) || k str

match2 (Lit 'a') ("b" |> Seq.toList) (fun x -> true)
match2 (Star (Lit 'a')) ("aaab" |> Seq.toList) (fun x -> true)

Re.java

package cps;

import java.util.function.Function;

public interface Re {

    boolean match(String s, Function<String, Boolean> kont);
    default boolean match(String s) {
        return match(s, kont -> true);
    }

    /**
     * 匹配字符
     * @param charLiteral
     * @return
     */
    static Re lit(char charLiteral) {
        return (s, kont) -> {
            if (s.isEmpty()) {
                return false;
            }
            return charLiteral == s.charAt(0) && kont.apply(s.substring(1));
        };
    }

    /**
     * 按顺序匹配a b
     * @param a
     * @param b
     * @return
     */
    static Re seq(Re a, Re b) {
        return (s, kont) -> a.match(s, rest -> b.match(rest, kont));
    }

    /**
     * 匹配a或b
     * @param a
     * @param b
     * @return
     */
    static Re either(Re a, Re b) {
        return (s, kont) -> a.match(s, kont) || b.match(s, kont);
    }

    /**
     * 匹配0到N个
     * @param re
     * @return
     */
    static Re star(Re re) {
        return (s, kont) -> re.match(s, rest -> star(re).match(rest, kont))
                || kont.apply(s);
    }

    static Re atLeastOne(Re re) {
        return seq(re, star(re));
    }
}

ReTest.java

package cps;

import org.junit.Test;

import static cps.Re.*;
import static org.junit.Assert.assertTrue;

public class ReTest {
    @Test
    public void should_match() {
        assertTrue(lit('a').match("a"));
        assertTrue(!lit('b').match("a"));
        assertTrue(either(lit('a'), lit('b')).match("b"));
        assertTrue(seq(lit('a'), lit('b')).match("ab"));
        assertTrue(star(lit('a')).match("aa"));
        assertTrue(!atLeastOne(lit('a')).match(""));
    }
}