-
-
Save QuantumGhost/3a7673f5edde8b7267d1c322dd7f30d5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template <typename Left, typename Right> | |
struct ConcatExpr; | |
template <typename Left, typename Right> | |
struct AltExpr; | |
template <typename SubExpr> | |
struct RepeatExpr; | |
template <char ch> | |
struct MatchExpr; | |
struct EpsilonExpr; | |
template <typename SubExpr> | |
using OptionalExpr = AltExpr<SubExpr, EpsilonExpr>; | |
template <typename RegExpr> | |
struct MatchImpl; | |
template <typename Left, typename Right> | |
struct MatchImpl<ConcatExpr<Left, Right>> { | |
template <typename Continuation> | |
static bool Apply(const char* target, Continuation cont) { | |
return MatchImpl<Left>::Apply(target, [cont](const char* rest) -> bool { | |
return MatchImpl<Right>::Apply(rest, cont); | |
}); | |
} | |
}; | |
template <typename Left, typename Right> | |
struct MatchImpl<AltExpr<Left, Right>> { | |
template <typename Continuation> | |
static bool Apply(const char* target, Continuation cont) { | |
return MatchImpl<Left>::Apply(target, cont) || | |
MatchImpl<Right>::Apply(target, cont); | |
} | |
}; | |
template <typename SubExpr> | |
struct MatchImpl<RepeatExpr<SubExpr>> { | |
template <typename Continuation> | |
static bool Apply(const char* target, Continuation cont) { | |
return MatchImpl<SubExpr>::Apply( | |
target, | |
[target, cont](const char* rest) -> bool { | |
return target < rest && | |
MatchImpl<RepeatExpr<SubExpr>>::Apply(rest, cont); | |
}) || | |
cont(target); | |
} | |
}; | |
template <char ch> | |
struct MatchImpl<MatchExpr<ch>> { | |
template <typename Continuation> | |
static bool Apply(const char* target, Continuation cont) { | |
return *target && *target == ch && cont(target + 1); | |
} | |
}; | |
template <> | |
struct MatchImpl<EpsilonExpr> { | |
template <typename Continuation> | |
static bool Apply(const char* target, Continuation cont) { | |
return cont(target); | |
} | |
}; | |
template <typename RegExpr> | |
bool RegexMatch(const char* target) { | |
return MatchImpl<RegExpr>::Apply( | |
target, [](const char* rest) -> bool { return *rest == '\0'; }); | |
} | |
template <typename RegExpr> | |
bool RegexSearch(const char* target) { | |
return MatchImpl<RegExpr>::Apply( | |
target, [](const char* rest) -> bool { return true; }) || | |
(*target && RegexSearch<RegExpr>(target + 1)); | |
} | |
#include <cassert> | |
int main() { | |
assert((RegexMatch<ConcatExpr<MatchExpr<'a'>, MatchExpr<'b'>>>("ab"))); | |
assert((RegexMatch<AltExpr<MatchExpr<'a'>, MatchExpr<'b'>>>("a"))); | |
assert((RegexMatch<AltExpr<MatchExpr<'a'>, MatchExpr<'b'>>>("b"))); | |
assert((RegexMatch<RepeatExpr<MatchExpr<'a'>>>("aaaaa"))); | |
assert((RegexMatch<ConcatExpr<RepeatExpr<MatchExpr<'a'>>, MatchExpr<'b'>>>( | |
"aaaaab"))); | |
assert(( | |
RegexMatch<ConcatExpr<RepeatExpr<MatchExpr<'a'>>, MatchExpr<'b'>>>("b"))); | |
assert((RegexSearch<ConcatExpr<RepeatExpr<MatchExpr<'a'>>, MatchExpr<'b'>>>( | |
"aaaaabb"))); | |
assert((RegexMatch<OptionalExpr<MatchExpr<'a'>>>("a"))); | |
assert((RegexMatch<OptionalExpr<MatchExpr<'a'>>>(""))); | |
assert((RegexMatch<OptionalExpr<ConcatExpr<MatchExpr<'a'>, MatchExpr<'b'>>>>( | |
"ab"))); | |
assert((RegexMatch<OptionalExpr<ConcatExpr<MatchExpr<'a'>, MatchExpr<'b'>>>>( | |
""))); | |
assert((!RegexMatch<RepeatExpr<MatchExpr<'a'>>>("aaaaab"))); | |
assert((RegexMatch<RepeatExpr<OptionalExpr<MatchExpr<'a'>>>>(""))); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment