-
-
Save guevara/636602b72ae94e36a57d604b597d5748 to your computer and use it in GitHub Desktop.
The beginnings of a C++ parser combinator library
This file contains hidden or 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
| #include <algorithm> | |
| #include <iostream> | |
| #include <iterator> | |
| #include <functional> | |
| #include <tuple> | |
| #include <type_traits> | |
| #include <vector> | |
| template< typename T > | |
| using ParseResult = std::vector<std::tuple<T, std::string>>; | |
| template< typename A > | |
| class Parser { | |
| public: | |
| using AmplifiedType = A; | |
| using ParseResult = ParseResult<AmplifiedType>; | |
| private: | |
| using LambdaType = std::function<ParseResult (std::string const&)>; | |
| LambdaType lambda; | |
| public: | |
| Parser(AmplifiedType const& t) | |
| : Parser([=](std::string const& s) -> ParseResult { return {std::make_tuple(t, s)}; }) | |
| {} | |
| Parser(LambdaType l) : lambda(l) {} | |
| ParseResult parse(std::string const& s) const { | |
| return lambda(s); | |
| } | |
| // Bind: Monad a -> (a -> Monad b) -> Monad b | |
| template< typename F > | |
| auto operator>>=(F k) const -> decltype(k(std::get<0>(parse("")[0]))) { | |
| using ResultParser = decltype(k(std::get<0>(parse("")[0]))); | |
| using FuncType = std::function<ResultParser(AmplifiedType)>; | |
| static_assert(std::is_convertible<F, FuncType>::value, "not callable"); | |
| auto thiscopy = *this; | |
| return ResultParser([thiscopy, k](std::string const& s) { | |
| typename ResultParser::ParseResult results; | |
| for (auto const& result : thiscopy.parse(s)) { | |
| auto& fst = std::get<0>(result); | |
| auto newParser = k(fst); | |
| auto xys = newParser.parse(std::get<1>(result)); | |
| std::copy(std::begin(xys), std::end(xys), std::inserter(results, std::end(results))); | |
| } | |
| return results; | |
| }); | |
| } | |
| Parser bchoice(Parser<AmplifiedType> const& n) const { | |
| auto thiscopy = *this; | |
| return Parser{[thiscopy, n](std::string const& s) -> ParseResult { | |
| auto res = thiscopy.parse(s); | |
| if (!res.empty()) { | |
| return res; | |
| } else { | |
| return n.parse(s); | |
| } | |
| }}; | |
| } | |
| template< typename F > | |
| Parser filter(F p) const { | |
| return (*this) >>= [p](AmplifiedType const& t) { | |
| if (p(t)) { | |
| return Parser(t); | |
| } else { | |
| // zero | |
| return Parser{ | |
| [](std::string const&) -> ParseResult { | |
| return {}; | |
| } | |
| }; | |
| } | |
| }; | |
| } | |
| Parser<std::vector<AmplifiedType>> reiterate() const { | |
| using IteratedParser = Parser<std::vector<AmplifiedType>>; | |
| using IteratedParseResult = typename Parser<std::vector<AmplifiedType>>::ParseResult; | |
| auto thiscopy = *this; | |
| IteratedParser multiple = (*this) >>= [thiscopy](AmplifiedType const& t) -> IteratedParser { | |
| return thiscopy.reiterate() >>= ([t](std::vector<AmplifiedType> ts) -> IteratedParser { | |
| ts.insert(std::begin(ts), t); | |
| return IteratedParser(ts); | |
| }); | |
| }; | |
| IteratedParser fallback{std::vector<AmplifiedType>()}; | |
| return multiple.bchoice(fallback); | |
| } | |
| }; | |
| int main(int argc, const char * argv[]) | |
| { | |
| Parser<char> item{[](std::string const& s) -> Parser<char>::ParseResult { | |
| if (s.empty()) { | |
| return {}; | |
| } else { | |
| return {{s[0], std::string(s.begin() + 1, s.end())}}; | |
| } | |
| }}; | |
| auto lit = [&item](char c) -> Parser<char> { | |
| return item.filter([=](char c_p) { return c == c_p; }); | |
| }; | |
| Parser<char> digit = item.filter([](char c) { | |
| return std::isdigit(c) != 0; | |
| }); | |
| Parser<int> number = digit.reiterate() >>= [](std::vector<char> const& ds) { | |
| return Parser<int>(std::stoi(std::string(ds.data(), ds.size()))); | |
| }; | |
| auto results = number.parse("123test"); | |
| for (auto& res : results) { | |
| std::cout << "(" << std::get<0>(res) << ", \"" << std::get<1>(res) << "\")\n"; | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment