-
-
Save kdridi/7151f3bd3ef9f6128b62ad7f0fed37a9 to your computer and use it in GitHub Desktop.
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 <criterion/criterion.h> | |
| #include <tuple> | |
| #include <stack> | |
| #include <string> | |
| #include <sstream> | |
| #include <functional> | |
| #include <iostream> | |
| typedef enum | |
| { | |
| token_number, | |
| token_operator, | |
| } token; | |
| struct tree | |
| { | |
| tree(token t, std::string n) : tree(t, n, nullptr, nullptr) {} | |
| tree(token t, std::string n, tree* l, tree* r) : t(t), n(n), l(l), r(r) {} | |
| token t; | |
| std::string n; | |
| tree* l; | |
| tree* r; | |
| void visit(std::function<void(std::size_t, token, std::string)> visitor) | |
| { | |
| visit(0, visitor); | |
| } | |
| private: | |
| void visit(std::size_t depth, std::function<void(std::size_t, token, std::string)> visitor) | |
| { | |
| visitor(depth, t, n); | |
| if (l != nullptr) l->visit(depth + 1, visitor); | |
| if (r != nullptr) r->visit(depth + 1, visitor); | |
| } | |
| }; | |
| struct tree_stack : std::stack<tree*> | |
| { | |
| bool push_token(token t, std::string n) | |
| { | |
| push(new tree(t, n)); | |
| return true; | |
| } | |
| bool pull_infix() | |
| { | |
| if (size() < 3) | |
| return false; | |
| tree* r = top(); pop(); | |
| tree* m = top(); pop(); | |
| tree* l = top(); pop(); | |
| push(new tree(m->t, m->n, l, r)); | |
| delete m; | |
| return true; | |
| } | |
| }; | |
| typedef std::tuple<std::string, std::stringstream*, tree_stack> request; | |
| typedef std::pair<bool, request> response; | |
| template<class p> | |
| struct p_satisfy | |
| { | |
| response operator()(request req) | |
| { | |
| p predicate; | |
| if (std::get<0>(req).empty() == true) | |
| return std::make_pair(false, req); | |
| if (predicate(std::get<0>(req).at(0)) == false) | |
| return std::make_pair(false, req); | |
| if (std::get<1>(req) != nullptr) | |
| *(std::get<1>(req)) << std::get<0>(req).at(0); | |
| return std::make_pair(true, std::make_tuple(std::get<0>(req).substr(1), std::get<1>(req), std::get<2>(req))); | |
| } | |
| }; | |
| template<class p1, class p2> | |
| struct p_or | |
| { | |
| response operator()(request req) | |
| { | |
| p1 parse1; | |
| response res1 = parse1(req); | |
| if (res1.first == true) | |
| return res1; | |
| p2 parse2; | |
| response res2 = parse2(req); | |
| return res2; | |
| } | |
| }; | |
| template<class p1, class p2> | |
| struct p_then | |
| { | |
| response operator()(request req) | |
| { | |
| p1 parse1; | |
| response res1 = parse1(req); | |
| if (res1.first == false) | |
| return std::make_pair(false, req); | |
| p2 parse2; | |
| response res2 = parse2(res1.second); | |
| if (res2.first == false) | |
| return std::make_pair(false, req); | |
| return res2; | |
| } | |
| }; | |
| template<class p> | |
| struct p_many | |
| { | |
| response operator()(request req) | |
| { | |
| p parse; | |
| while (true) | |
| { | |
| response res = parse(req); | |
| if (res.first == false) | |
| break; | |
| req = res.second; | |
| } | |
| return std::make_pair(true, req); | |
| } | |
| }; | |
| template<class p, token t> | |
| struct p_push_token | |
| { | |
| response operator()(request req) | |
| { | |
| p parse; | |
| std::stringstream* ss0 = std::get<1>(req); | |
| std::stringstream* ss1 = new std::stringstream; | |
| response res = parse(std::make_tuple(std::get<0>(req), ss1, std::get<2>(req))); | |
| tree_stack stack = std::get<2>(res.second); | |
| if (res.first == true) | |
| stack.push_token(t, ss1->str()); | |
| delete ss1; | |
| return std::make_pair(res.first, std::make_tuple(std::get<0>(res.second), ss0, stack)); | |
| } | |
| }; | |
| struct p_pull_infix | |
| { | |
| response operator()(request req) | |
| { | |
| tree_stack stack = std::get<2>(req); | |
| if (stack.pull_infix()) | |
| return std::make_pair(true, std::make_tuple(std::get<0>(req), std::get<1>(req), stack)); | |
| else | |
| return std::make_pair(true, std::make_tuple(std::get<0>(req), std::get<1>(req), std::get<2>(req))); | |
| } | |
| }; | |
| // ============================================================================= | |
| // UTILS | |
| // ============================================================================= | |
| template<char c> | |
| struct is_same | |
| { bool operator()(char ch) { return ch == c; } }; | |
| // ============================================================================= | |
| // COMBINATOR | |
| // ============================================================================= | |
| template<char...chars> | |
| struct p_char; | |
| template<char head> | |
| struct p_char<head> | |
| : public p_satisfy<is_same<head>> {}; | |
| template<char head, char... tail> | |
| struct p_char<head, tail...> | |
| : public p_or<p_char<head>, p_char<tail...>> {}; | |
| template <class...p> | |
| struct p_choice; | |
| template <class head> | |
| struct p_choice<head> | |
| : public head {}; | |
| template <class head, class... tail> | |
| struct p_choice<head, tail...> | |
| : public p_or<p_choice<head>, p_choice<tail...>> {}; | |
| template <class...> | |
| struct p_sep_by; | |
| template <class p, class s> | |
| struct p_sep_by<p, s> | |
| : public p_then<p, p_many<p_then<s, p>>> {}; | |
| template <class p, class s, class f> | |
| struct p_sep_by<p, s, f> | |
| : public p_then<p, p_many<p_then<p_then<s, p>, f>>> {}; | |
| struct p_digit | |
| : public p_char<'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'> {}; | |
| template<class p> | |
| struct p_many1 | |
| : public p_then<p, p_many<p>> {}; | |
| struct p_number | |
| : public p_many1<p_digit> {}; | |
| struct p_spaces | |
| : public p_many<p_char<' ', '\t', '\n', '\r'>> {}; | |
| template<class l, class m, class r> | |
| struct p_between | |
| : public p_then<l, p_then<m, r>> {}; | |
| template<class p> | |
| struct p_token : public p_between<p_spaces, p, p_spaces> | |
| { | |
| }; | |
| // ============================================================================= | |
| // ARITHMETIC | |
| // ============================================================================= | |
| struct p_expr; | |
| struct p_factor | |
| : public p_choice<p_token<p_push_token<p_number, token_number>>, p_between<p_token<p_char<'('>>, p_expr, p_token<p_char<')'>>>> {}; | |
| struct p_multiplicative_operator | |
| : public p_token<p_push_token<p_char<'*', '/', '%'>, token_operator>> {}; | |
| struct p_multiplicative | |
| : public p_sep_by<p_factor, p_multiplicative_operator, p_pull_infix> {}; | |
| struct p_additive_operator | |
| : public p_token<p_push_token<p_char<'+', '-'>, token_operator>> {}; | |
| struct p_additive | |
| : public p_sep_by<p_multiplicative, p_additive_operator, p_pull_infix> {}; | |
| struct p_expr | |
| : public p_additive {}; | |
| Test(is_same, same_0) | |
| { | |
| typedef is_same<'0'> predicate; | |
| predicate p; | |
| cr_assert_eq(true , p('0')); | |
| cr_assert_eq(false, p('1')); | |
| cr_assert_eq(false, p('2')); | |
| } | |
| Test(is_same, same_1) | |
| { | |
| typedef is_same<'1'> predicate; | |
| predicate p; | |
| cr_assert_eq(false, p('0')); | |
| cr_assert_eq(true , p('1')); | |
| cr_assert_eq(false, p('2')); | |
| } | |
| Test(is_same, same_2) | |
| { | |
| typedef is_same<'2'> predicate; | |
| predicate p; | |
| cr_assert_eq(false, p('0')); | |
| cr_assert_eq(false, p('1')); | |
| cr_assert_eq(true , p('2')); | |
| } | |
| Test(p_satisfy, with_is_same_a_01) | |
| { | |
| typedef is_same<'a'> predicate; | |
| typedef p_satisfy<predicate> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("a", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_satisfy, with_is_same_a_02) | |
| { | |
| typedef is_same<'a'> predicate; | |
| typedef p_satisfy<predicate> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("ab", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("b", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_satisfy, with_is_same_a_03) | |
| { | |
| typedef is_same<'a'> predicate; | |
| typedef p_satisfy<predicate> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("b", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res.first); | |
| cr_assert_str_eq("b", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_or, starts_with_a_or_b_01) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_or<parserA, parserB> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("ac", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("c", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_or, starts_with_a_or_b_02) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_or<parserA, parserB> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("abc", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("bc", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_or, starts_with_a_or_b_03) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_or<parserA, parserB> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("bc", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("c", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_then, starts_with_a_then_b_01) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_then<parserA, parserB> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("ac", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res.first); | |
| cr_assert_str_eq("ac", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_then, starts_with_a_then_b_02) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_then<parserA, parserB> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("abc", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("c", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_then, starts_with_a_then_b_03) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_then<parserA, parserB> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("bc", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res.first); | |
| cr_assert_str_eq("bc", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_many, many_a_or_b_01) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_many<p_or<parserA, parserB>> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("ac", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("c", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_many, many_a_or_b_02) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_many<p_or<parserA, parserB>> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("abc", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("c", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_many, many_a_or_b_03) | |
| { | |
| typedef is_same<'a'> predicateA; | |
| typedef p_satisfy<predicateA> parserA; | |
| typedef is_same<'b'> predicateB; | |
| typedef p_satisfy<predicateB> parserB; | |
| typedef p_many<p_or<parserA, parserB>> parser; | |
| parser parse; | |
| response res = parse(std::make_tuple("bc", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("c", std::get<0>(res.second).c_str()); | |
| } | |
| Test(p_char, char_0) | |
| { | |
| typedef p_char<'0'> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res0.first); | |
| cr_assert_str_eq("", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res1.first); | |
| cr_assert_str_eq("1", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res2.first); | |
| cr_assert_str_eq("2", std::get<0>(res2.second).c_str()); | |
| } | |
| Test(p_char, char_1) | |
| { | |
| typedef p_char<'1'> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res0.first); | |
| cr_assert_str_eq("0", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res1.first); | |
| cr_assert_str_eq("", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res2.first); | |
| cr_assert_str_eq("2", std::get<0>(res2.second).c_str()); | |
| } | |
| Test(p_char, char_2) | |
| { | |
| typedef p_char<'2'> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res0.first); | |
| cr_assert_str_eq("0", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res1.first); | |
| cr_assert_str_eq("1", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res2.first); | |
| cr_assert_str_eq("", std::get<0>(res2.second).c_str()); | |
| } | |
| Test(p_char, oneOf_A_0_1) | |
| { | |
| typedef p_char<'A', '0', '1'> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res0.first); | |
| cr_assert_str_eq("", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res1.first); | |
| cr_assert_str_eq("", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res2.first); | |
| cr_assert_str_eq("2", std::get<0>(res2.second).c_str()); | |
| response resA = p(std::make_tuple("A", nullptr, tree_stack{})); | |
| cr_assert_eq(true, resA.first); | |
| cr_assert_str_eq("", std::get<0>(resA.second).c_str()); | |
| } | |
| Test(p_char, oneOf_A_1_2) | |
| { | |
| typedef p_char<'A', '1', '2'> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res0.first); | |
| cr_assert_str_eq("0", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res1.first); | |
| cr_assert_str_eq("", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res2.first); | |
| cr_assert_str_eq("", std::get<0>(res2.second).c_str()); | |
| response resA = p(std::make_tuple("A", nullptr, tree_stack{})); | |
| cr_assert_eq(true, resA.first); | |
| cr_assert_str_eq("", std::get<0>(resA.second).c_str()); | |
| } | |
| Test(p_char, oneOf_A_2_0) | |
| { | |
| typedef p_char<'A', '2', '0'> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res0.first); | |
| cr_assert_str_eq("", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(false, res1.first); | |
| cr_assert_str_eq("1", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res2.first); | |
| cr_assert_str_eq("", std::get<0>(res2.second).c_str()); | |
| response resA = p(std::make_tuple("A", nullptr, tree_stack{})); | |
| cr_assert_eq(true , resA.first); | |
| cr_assert_str_eq("", std::get<0>(resA.second).c_str()); | |
| } | |
| Test(p_digit, is_digit) | |
| { | |
| typedef p_digit parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res0.first); | |
| cr_assert_str_eq("", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("1", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res1.first); | |
| cr_assert_str_eq("", std::get<0>(res1.second).c_str()); | |
| response res2 = p(std::make_tuple("2", nullptr, tree_stack{})); | |
| cr_assert_eq(true , res2.first); | |
| cr_assert_str_eq("", std::get<0>(res2.second).c_str()); | |
| response resA = p(std::make_tuple("A", nullptr, tree_stack{})); | |
| cr_assert_eq(false , resA.first); | |
| cr_assert_str_eq("A", std::get<0>(resA.second).c_str()); | |
| } | |
| Test(p_sep_by, digit_sep_by_coma) | |
| { | |
| typedef p_sep_by<p_digit, p_char<','>> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("0,1,2,3,4,5,6,7,8,9", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res0.first); | |
| cr_assert_str_eq("", std::get<0>(res0.second).c_str()); | |
| } | |
| Test(p_sep_by, number_sep_by_operator) | |
| { | |
| typedef p_sep_by<p_number, p_char<'+', '-'>> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("12+34-56+78-90", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res0.first); | |
| cr_assert_str_eq("", std::get<0>(res0.second).c_str()); | |
| } | |
| Test(p_choice, number_sep_by_operator) | |
| { | |
| typedef p_choice<p_number, p_char<'+', '-'>> parser; | |
| parser p; | |
| response res0 = p(std::make_tuple("12+34-56+78-90", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res0.first); | |
| cr_assert_str_eq("+34-56+78-90", std::get<0>(res0.second).c_str()); | |
| response res1 = p(std::make_tuple("-12+34-56+78-90", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res1.first); | |
| cr_assert_str_eq("12+34-56+78-90", std::get<0>(res1.second).c_str()); | |
| } | |
| Test(p_expr, parse_empty) | |
| { | |
| p_expr parse; | |
| response res = parse(std::make_tuple(" ( 12 + 34) *56 -78/90 ", nullptr, tree_stack{})); | |
| cr_assert_eq(true, res.first); | |
| cr_assert_str_eq("", std::get<0>(res.second).c_str()); | |
| tree_stack stack = std::get<2>(res.second); | |
| while (stack.empty() == false) | |
| { | |
| tree& t = *(stack.top()); stack.pop(); | |
| t.visit([](std::size_t depth, token t, std::string n) { | |
| std::stringstream ss; | |
| for (std::size_t index = 0; index < depth; ++index) ss << " "; | |
| ss.str(); | |
| switch (t) { | |
| case token_number: | |
| std::cout << ss.str() << "number: " << n << std::endl; | |
| break; | |
| case token_operator: | |
| std::cout << ss.str() << "operator: " << n << std::endl; | |
| break; | |
| default: | |
| break; | |
| } | |
| }); | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment