Recurse tree

[ru108]

Hello!

That simple list:

(1a)(22b)(333c)(4444d)

And simple parser:

namespace test {
  struct g_tree {
    std::string content;
  };
}

namespace grammar {
  namespace dsl = lexy::dsl;

  struct g_tree {
    static constexpr auto rule = [] {
      auto quoted = dsl::delimited(dsl::lit_c<'('>, dsl::lit_c<')'>);
      return quoted(dsl::code_point);
    }();

    static constexpr auto value = lexy::as_string<std::string>;
  };

  struct collection {
    static constexpr auto whitespace = dsl::ascii::space / dsl::ascii::newline;
    static constexpr auto rule = dsl::whitespace + dsl::list(dsl::p<g_tree>) + dsl::eof;
    static constexpr auto value = lexy::as_list<std::vector<test::g_tree>>;
  };
}

But i need recurse tree:

(1a(1-1aa)(1-2aa))(22b)(333c(333-1c(333-2c)))(4444d)

So i am trying:

namespace test {
  struct g_tree {
    std::string content;
    std::vector<g_tree> tree;
  };
}

namespace grammar {
  namespace dsl = lexy::dsl;

  struct g_tree {
    static constexpr auto rule = [] {
      auto quoted = dsl::delimited(dsl::lit_c<'('>, dsl::lit_c<')'>);

      //error C2338: list() without a separator requires a branch condition
      //error C2338: opt() requires a branch condition
      //error C2607: static assertion failed
      return quoted(dsl::code_point + dsl::opt(dsl::list(dsl::recurse<g_tree>)));
    }();

    static constexpr auto value = lexy::as_string<std::string>;
  };

  struct collection {
    static constexpr auto whitespace = dsl::ascii::space / dsl::ascii::newline;
    static constexpr auto rule = dsl::whitespace + dsl::list(dsl::p<g_tree>) + dsl::eof;
    static constexpr auto value = lexy::as_list<std::vector<test::g_tree>>;
  };
}

But unsuccessfully...
Or maybe I'm completely wrong?

Thanks...

[foonathan]

FYI: ascii::space includes ascii::newline (ascii::blank is just space and tab).

There are two issues:

1. dsl::recurse is not a branch, dsl::list() requires a branch. This can be solved by giving it a branch condition, e.g. dsl::peek(dsl::lit_c<'('>) >> dsl::recurse, which will only recurse if it sees a '(' (but doesn't consume it): https://lexy.foonathan.net/reference/dsl/branch/#branch and https://lexy.foonathan.net/reference/dsl/peek/#peek
2. dsl::delimited requires a token, dsl::code_point + dsl::opt(...) is not a token. The reason is that this rule is meant for something like string literals, not more complex sequences. This can be solved by using dsl::parenthesized.list() instead, which parses a list surrounded by parentheses: https://lexy.foonathan.net/reference/dsl/brackets/#brackets-predefined and https://lexy.foonathan.net/reference/dsl/brackets/#brackets

We can then simplify the rule: list(a + opt(b)) is the same as list(a | b) (although we here need to swap the order, as dsl::code_point matches literally anything), and list(a | list(recurse)) is the same as list(a | recurse), as the recursive rule itself is already a list.

The end result is this: https://lexy.foonathan.net/playground/?id=8Pe85sjbM&mode=tree

[foonathan]

FYI, I've now added dsl::recurse_branch, which simplifies things: https://lexy.foonathan.net/playground/?id=8Pe85sjbM&mode=tree (now need to dsl::peek, which involves backtracking).

As production is already a branch, we can use it directly. Unlike dsl::p, dsl::recurse can't be turned into a branch automatically.

[sturowski]

All your links are not working.
Can you please post the complete working example?

[sturowski]

I have some problems with the construction of the real objects. Can you help me? Here is my Code:

#include <catch2/catch_test_macros.hpp>
#include <iostream>

#include <lexy/action/parse.hpp>
#include <lexy/callback.hpp>
#include <lexy/dsl.hpp>
#include <lexy/input/string_input.hpp>
#include <lexy_ext/report_error.hpp>

#include <optional>
#include <string>
#include <vector>
#include <map>

#include <variant>

namespace sql {
    namespace Data {
        struct g_tree {
            std::string content;
            std::optional<std::vector<g_tree>> tree;
        };
    }

    namespace grammar {
        namespace dsl = lexy::dsl;
            struct Text {
                static constexpr auto rule = [] {
                    return dsl::identifier(dsl::ascii::alpha);
                }();
                static constexpr auto value = lexy::as_string<std::string, lexy::utf8_encoding>;
            };

            struct g_tree {
                static constexpr auto rule = [] {
                    auto recurse = dsl::peek(dsl::lit_c<'('>) >> dsl::recurse<g_tree>;
                    return dsl::parenthesized.list(recurse | dsl::p<Text>);
                }();

                static constexpr auto value = lexy::as_string<std::string>;
            };

            struct collection {
                static constexpr auto whitespace = dsl::ascii::space / dsl::ascii::newline;
                static constexpr auto rule = dsl::list(dsl::p<g_tree>) + dsl::eof;
                static constexpr auto value = lexy::as_list<std::vector<Data::g_tree>>;
            };
    }
}


TEST_CASE( "Some Tree tests", "Tree" ) {
    SECTION("Tree") {
        std::string data = ("(abc)(def(ghi))");
        lexy::string_input<lexy::utf8_encoding>  input(data);
        auto result = lexy::parse<sql::grammar::collection>(input, lexy_ext::report_error);
        REQUIRE(result.has_value());

        auto tree = result.value();
        REQUIRE(tree[0].content == "abc");
        REQUIRE(tree[1].content == "def"); // is always defghi
        REQUIRE(tree[1].tree.has_value());
        REQUIRE(tree[1].tree.value()[0].content == "ghi");
    }
}

Can you help me?

[foonathan]

Your issue is that the data structure does not reflect the reality of what's being parsed. A g_tree is either a list of children, which are either text or other g_tree. This means that your g_tree struct needs to store a vector of variant<g_tree, string> or something like that.

[sturowski]

Thanks for your response. I changed it to std::vector<std::variant<g_tree, std::string>> tree; after that i fixed my tests and they are working. But my problem with "defghi" is the same. I think the problem is with this line static constexpr auto value = lexy::as_string<std::string>; in the grammar::g_tree. But I don't know how to fix it.
Here is my new code:

#include <catch2/catch_test_macros.hpp>
#include <iostream>

#include <lexy/action/parse.hpp>
#include <lexy/callback.hpp>
#include <lexy/dsl.hpp>
#include <lexy/input/string_input.hpp>
#include <lexy_ext/report_error.hpp>
#include <lexy/visualize.hpp>

#include <optional>
#include <string>
#include <vector>
#include <map>

#include <variant>

namespace sql {
    namespace Data {
        struct g_tree {
            std::vector<std::variant<g_tree, std::string>> tree;

            g_tree() = default;
            g_tree(g_tree const& entry) = default;

            g_tree(std::string _content) {
                tree.emplace_back(std::move(_content));
            }

            g_tree(std::vector<std::variant<g_tree, std::string>> _tree) : tree(std::move(_tree)) {
            }
        };
    }

    namespace grammar {
        namespace dsl = lexy::dsl;
        struct Text {
            static constexpr auto rule = [] {
                return dsl::identifier(dsl::ascii::alpha);
            }();
            static constexpr auto value = lexy::as_string<std::string, lexy::utf8_encoding>;
        };

        struct g_tree {
            static constexpr auto rule = [] {
                auto recurse = dsl::peek(dsl::lit_c<'('>) >> dsl::recurse<g_tree>;
                return dsl::parenthesized.list(recurse | dsl::p<Text>);
            }();
            static constexpr auto value = lexy::as_string<std::string>;
        };

        struct collection {
            static constexpr auto whitespace = dsl::ascii::space / dsl::ascii::newline;
            static constexpr auto rule = dsl::list(dsl::p<g_tree>) + dsl::eof;
            static constexpr auto value = lexy::as_list<std::vector<Data::g_tree>>;
        };
    }
}



TEST_CASE( "Some Tree tests", "Tree" ) {
    SECTION("Tree 1") {
        std::string data = ("(abc)");
        lexy::string_input<lexy::utf8_encoding>  input(data);


        auto result = lexy::parse<sql::grammar::collection>(input, lexy_ext::report_error);
        REQUIRE(result.has_value());

        auto tree = result.value();
        REQUIRE(tree.size() == 1);
        REQUIRE(tree[0].tree.size() == 1);
        REQUIRE(std::get<std::string>(tree[0].tree[0]) == "abc");
    }
    SECTION("Tree 2") {
        std::string data = ("(abc)(def)");
        lexy::string_input<lexy::utf8_encoding>  input(data);


        auto result = lexy::parse<sql::grammar::collection>(input, lexy_ext::report_error);
        REQUIRE(result.has_value());

        auto tree = result.value();
        REQUIRE(tree.size() == 2);
        REQUIRE(tree[0].tree.size() == 1);
        REQUIRE(tree[1].tree.size() == 1);
        REQUIRE(std::get<std::string>(tree[0].tree[0]) == "abc");
        REQUIRE(std::get<std::string>(tree[1].tree[0]) == "def");
    }
    SECTION("Tree 3") {
        std::string data = ("(abc)(def(ghi))");
        lexy::string_input<lexy::utf8_encoding>  input(data);


        auto result = lexy::parse<sql::grammar::collection>(input, lexy_ext::report_error);
        REQUIRE(result.has_value());

        auto tree = result.value();
        REQUIRE(tree[0].tree.size() == 1);
        REQUIRE(tree[1].tree.size() == 2);
        REQUIRE(std::get<std::string>(tree[0].tree[0]) == "abc");
        REQUIRE(std::get<std::string>(tree[1].tree[0]) == "def");
    }
}

[foonathan]

Your value callback of g_tree is wrong - you don't want a string, you want a g_tree object:

static constexpr auto value = lexy::as_list<std::vector<std::variant<Data::g_tree, std::string>> >> lexy::construct<Data::g_tree>;

This will use lexy::as_list to collect each item of the list into a std::vector, then construct a g_tree out of it.

[sturowski]

You solved my problem :-) thanks a LOT!!