AST против синтезированных атрибутов нетерминальных парсеров

Я пытаюсь сохранить результаты парсера дерева в рекурсивную структуру, используя Boost Spirit x3.

У меня хорошая грамматика и хороший аст. Но я изо всех сил пытаюсь понять, как они (отказываются) соединяться.

Вот АСТ:


#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/variant.hpp>

#include <boost/fusion/adapted/struct/adapt_struct.hpp>
#include <boost/fusion/include/adapt_struct.hpp>

#include <optional>

namespace ast
{

  struct node
  {
    // are the optional necessary here?
    std::optional<std::vector<node>> children;
    std::optional<std::string> name;
    std::optional<double> length;

  };
}

BOOST_FUSION_ADAPT_STRUCT(ast::node, children, name, length)

Тогда это грамматика, которая должна синтезировать эти узлы: (я добавил несколько заметок о том, что, как мне кажется, синтезируют нетерминальные синтаксические анализаторы).

#include <boost/spirit/home/x3.hpp>
#include "ast.h"
#include <boost/fusion/include/vector.hpp>
#include <boost/fusion/include/std_pair.hpp>

  namespace parser
  {
    namespace x3 = boost::spirit::x3;

    // synthesize: it should be a simple ast::node, but the grammar says otherwise???
    x3::rule<class tree, ast::node> const tree{"tree"};
    x3::rule<class branch> branch{"branch"};

    // synthesize: std::string
    auto name     = x3::lexeme[x3::alpha >> *x3::alnum]; // to be improved later
    // synthesize: double
    auto length   = ':' >> x3::double_;
    // synthesize: std::optional<std::string>
    auto leaf     = -name;
    // synthesize: std::pair< std::vector<...>, std::optional<std::string> >
    auto internal = '(' >> (branch % ',') >> ')' >> -name;
    // synthesized attribute: std::variant<node, std::optional<std::string>
    auto subtree  = internal | leaf;
    // synthesize: std::pair<node, std::optional<double>>
    auto const tree_def   = x3::skip(x3::blank)[subtree >> -length >> ';' >> x3::eoi];
    // synthesize: std::pair<node, std::optional<double>>
    auto const branch_def = subtree >> -length;

    BOOST_SPIRIT_DEFINE(branch, tree);
  } // end namespace parser

  // What is that for?
  auto tree()
  {
    return parser::tree;
  }

Несмотря на многочисленные попытки «исправить» его, он не компилируется с /boost/spirit/home/x3/operator/detail/sequence.hpp:143:9: error: static_assert failed due to requirement 'actual_size <= expected_size' "Size of the passed attribute is bigger than expected."

Я предполагаю, что AST несовместим с грамматикой (я не вижу ничего похожего на простой tuple<vector<node>, string, double>, возникающий из грамматики). Если да, следует ли мне усложнить AST или найти простой способ выражения грамматики, или это будет вариант использования семантического действия?

"Для чего это?" - это для совместного использования экземпляров правил между TU без запуска в SIOF. Пока вы не делитесь экземплярами статических правил между TU, они вам не нужны.

sehe 21.11.2022 14:43
Как настроить Tailwind CSS с React.js и Next.js?
Как настроить Tailwind CSS с React.js и Next.js?
Tailwind CSS - единственный фреймворк, который, как я убедился, масштабируется в больших командах. Он легко настраивается, адаптируется к любому...
LeetCode запись решения 2536. Увеличение подматриц на единицу
LeetCode запись решения 2536. Увеличение подматриц на единицу
Увеличение подматриц на единицу - LeetCode
Переключение светлых/темных тем
Переключение светлых/темных тем
В Microsoft Training - Guided Project - Build a simple website with web pages, CSS files and JavaScript files, мы объясняем, как CSS можно...
Отношения &quot;многие ко многим&quot; в Laravel с методами присоединения и отсоединения
Отношения &quot;многие ко многим&quot; в Laravel с методами присоединения и отсоединения
Отношения "многие ко многим" в Laravel могут быть немного сложными, но с помощью Eloquent ORM и его моделей мы можем сделать это с легкостью. В этой...
В PHP
В PHP
В большой кодовой базе с множеством различных компонентов классы, функции и константы могут иметь одинаковые имена. Это может привести к путанице и...
Карта дорог Беладжар PHP Laravel
Карта дорог Беладжар PHP Laravel
Laravel - это PHP-фреймворк, разработанный для облегчения разработки веб-приложений. Laravel предоставляет различные функции, упрощающие разработку...
4
1
61
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Во-первых, вещи редко используются для семантических действий (Boost Spirit: «Семантические действия — это зло»?)¹.

Во-вторых, моя интуиция подсказывает, что optional, вероятно, не нужен для векторных/строковых полей. На мой взгляд, контейнер последовательности уже является обобщением optional (где необязательное значение похоже на контейнер с максимальным размером 1).

В-третьих, насколько я помню, могут быть ограничения с поддержкой std::optional. Кажется, я неправильно помню из variant support Переход парсера Boost Spirit с boost::variant на std::variant.

Правила размножения

Теперь я бы посоветовал помнить о двух вещах:

  1. Всегда сопоставляйте объявления AST как можно ближе к объявлениям ваших правил. В частности, ваш AST не различает листовые узлы и внутренние узлы, что вызывает путаницу, поскольку вы надеетесь, что оба правила «волшебным образом» совместимы с обоими.

  2. Будьте конкретны в приведении типов. x3::rule делает это, и вы можете использовать его явно. Одно из моих повторяющихся устройств x3 — это as<T>[p] (или иногда его функциональная версия: as<T>(p, name)):

    template <typename T> struct as_type {
        auto operator[](auto p) const {
            struct Tag {};
            return x3::rule<Tag, T>{"as"} = p;
        }
    };
    
    template <typename T> static inline as_type<T> as{};
    

Обратите внимание, что некоторые (большинство?) ваших строк комментариев

// synthesize: std::string
// synthesize: double
// synthesize: std::optional<std::string>
// synthesize: std::pair< std::vector<...>, std::optional<std::string> >
// synthesized attribute: std::variant<node, std::optional<std::string>
// synthesize: std::pair<node, std::optional<double>>
// synthesize: std::pair<node, std::optional<double>>

Не очень точны. Например. alpha >> *alnum имеет fusion::deque<char, std::string> > тип атрибута. Имейте в виду, что механизм распространения может сгладить тонкую разницу при создании экземпляра x3::move_to для фактической связанной ссылки.

На самом деле это так и есть, см. «Упрощение, очистка» ниже.

Но как есть, это распространяется вниз: leaf не optional<string> сейчас и так далее.

Поскольку вы определили branch без типа атрибута, его тип атрибута на самом деле x3::unused_type. Это означает, что subtree также не содержит vector<...>. Пришлось проверить, поэтому сделал сооружение:

template <typename ExpectedAttributeType> void check(auto p) {
    static_assert(
        std::is_same_v<
            ExpectedAttributeType,
            typename x3::traits::attribute_of<decltype(p), x3::unused_type>::type>);
};

И теперь мы можем видеть, что:

check<std::string>(name); // assuming a fixed `name` rule that coerces std::string
check<std::vector<std::string>>('(' >> name % ',' >> ')');

Но для парсера, который выставляет unused_type:

check<x3::unused_type>(x3::omit[name]);
check<std::vector<x3::unused_type>>('(' >> x3::omit[name] % ',' >> ')'); // FAILS!
check<x3::unused_type>('(' >> x3::omit[name] % ',' >> ')'); // Passes

Понимаете, что я имею в виду, когда говорю о строгом контроле? Волновой эффект приводит к совершенно другим типам атрибутов, чем вы ожидали.

Кроме того, pair<node, optional<double>> не будет совместим ни с одним из ваших типов AST (что, конечно же, просто ast::node).

Покажи, не говори

Поскольку я знаю, что вы быстро учитесь, и я не знаю, как лучше всего объяснить преобразования, которые я бы выполнял шаг за шагом, я просто покажу вам результат применения вышеуказанных принципов к коду вопроса:

x3::rule<class branch, ast::node> node{"node"};

auto name     = as<std::string>[x3::lexeme[x3::alpha >> *x3::alnum]];
auto length   = as<double>[':' >> x3::double_];
auto leaf     = as<std::string>[name | x3::attr(std::string{})];
auto children = '(' >> (node % ',') >> ')' | x3::attr(ast::nodes{});
auto node_def = children >> leaf >> -length;
auto tree     = x3::skip(x3::blank)[node >> ';' >> x3::eoi];

BOOST_SPIRIT_DEFINE(node);

Вы можете ваши ожидания:

void checks() {
    check<double>(length);
    check<std::string>(leaf);
    check<std::string>(name);
    check<ast::nodes>('(' >> node % ',' >> ')'); // Passes
    //check<ast::nodes>(children); // FAILS, actually variant<ast::nodes, ast::nodes> (!!)
    check<ast::nodes>(as<ast::nodes>[children]); // Trivially compatible
    check<ast::node>(tree);
}
Обратите внимание, насколько тонкими могут быть внутренние механизмы. Честно говоря, Spirit Qi был более предсказуемым и снисходительным, чем X3. Я подозреваю, что разница может быть в пользу удобства обслуживания и времени компиляции?_

Тестирование

Заимствуем некоторые тестовые примеры из Grammar не удается разобрать дерево с помощью Boost Spirit X3 и отладить печать проанализированного AST:

Live On Coliru принты

============ running internal tests:
"(,)"    PASS -> node { [node { [], "" }, node { [], "" }], "" }
"(A,B)F"     PASS -> node { [node { [], "A" }, node { [], "B" }], "F" }
"(A:10,B:10)F"   PASS -> node { [node { [], "A":10 }, node { [], "B":10 }], "F" }
============ running tree tests:
";"  PASS -> node { [], "" }
"(,);"   PASS -> node { [node { [], "" }, node { [], "" }], "" }
"(,,(,));"   PASS -> node { [node { [], "" }, node { [], "" }, node { [node { [], "" }, node { [], "" }], "" }], "" }
"(A,B,(C,D));"   PASS -> node { [node { [], "A" }, node { [], "B" }, node { [node { [], "C" }, node { [], "D" }], "" }], "" }
"(A,B,(C,D)E)F;"     PASS -> node { [node { [], "A" }, node { [], "B" }, node { [node { [], "C" }, node { [], "D" }], "E" }], "F" }
"(:0.1,:0.2,(:0.3,:0.4):0.5);"   PASS -> node { [node { [], "":0.1 }, node { [], "":0.2 }, node { [node { [], "":0.3 }, node { [], "":0.4 }], "":0.5 }], "" }
"(:0.1,:0.2,(:0.3,:0.4):0.5):0.0;"   PASS -> node { [node { [], "":0.1 }, node { [], "":0.2 }, node { [node { [], "":0.3 }, node { [], "":0.4 }], "":0.5 }], "":0 }
"(A:0.1,B:0.2,(C:0.3,D:0.4):0.5);"   PASS -> node { [node { [], "A":0.1 }, node { [], "B":0.2 }, node { [node { [], "C":0.3 }, node { [], "D":0.4 }], "":0.5 }], "" }
"(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F;"     PASS -> node { [node { [], "A":0.1 }, node { [], "B":0.2 }, node { [node { [], "C":0.3 }, node { [], "D":0.4 }], "E":0.5 }], "F" }
"((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A;"    PASS -> node { [node { [node { [], "B":0.2 }, node { [node { [], "C":0.3 }, node { [], "D":0.4 }], "E":0.5 }], "F":0.1 }], "A" }

Упрощение, Очистка

После того, как все сделано, я обычно захожу и удаляю ненужные экземпляры правил.

Оказывается, неудивительно, что действительное соответствие AST вашим правилам 1: 1 делает все тривиально совместимым без принуждения. В вашем случае я бы, вероятно, также удалил optional<double>, поэтому позвольте мне показать вам, если вам интересно:

struct node {
    nodes       children;
    std::string name;
    double      length;
};

И правила становятся:

x3::rule<class branch, ast::node> node{"node"};

auto name     = x3::lexeme[x3::alpha >> *x3::alnum];
auto length   = ':' >> x3::double_ | x3::attr(0.0);
auto leaf     = name | x3::attr(std::string{});
auto children = '(' >> (node % ',') >> ')' | x3::attr(ast::nodes{});
auto node_def = children >> leaf >> -length;
auto tree     = x3::skip(x3::blank)[node >> ';' >> x3::eoi];

BOOST_SPIRIT_DEFINE(node);

На всякий случай давайте переформулируем checks, чтобы проверить только ожидаемую совместимость:

template <typename ExpectedAttributeType> void compatible(auto p) {
    static_assert(
        std::is_same_v<ExpectedAttributeType,
                       typename x3::traits::attribute_of<
                           decltype(x3::rule<struct _, ExpectedAttributeType>{} = p),
                           x3::unused_type>::type>);
};

void checks() {
    compatible<double>(length);
    compatible<std::string>(leaf);
    compatible<std::string>(name);
    compatible<ast::nodes>(children);
    compatible<ast::node>(tree);
}

Полный список

Прямой эфир на Колиру

#include <boost/fusion/include/adapted.hpp>
#include <boost/spirit/home/x3.hpp>
#include <iomanip>
#include <iostream>

namespace ast {
    using nodes = std::vector<struct node>;
    struct node {
        nodes       children;
        std::string name;
        double      length;
    };

    // for debug output
    static inline std::ostream& operator<<(std::ostream& os, node const& n) {
        os << "node { [";

        for (auto sep = ""; auto& c : n.children)
            os << std::exchange(sep, ", ") << c;

        os << "], " << quoted(n.name) ;

        if (n.length != 0)
            os << ":" << n.length;
        return os << " }";
    }
} // namespace ast

BOOST_FUSION_ADAPT_STRUCT(ast::node, children, name, length)

#include <boost/fusion/include/vector.hpp>
#include <boost/fusion/include/std_pair.hpp>

namespace parser {
    namespace x3 = boost::spirit::x3;

    static x3::rule<class branch, ast::node> const node{"node"};

    static auto const name     = x3::lexeme[x3::alpha >> *x3::alnum];
    static auto const length   = ':' >> x3::double_ | x3::attr(0.0);
    static auto const leaf     = name | x3::attr(std::string{});
    static auto const children = '(' >> (node % ',') >> ')' | x3::attr(ast::nodes{});
    static auto const node_def = children >> leaf >> -length;
    static auto const tree     = x3::skip(x3::blank)[node >> ';' >> x3::eoi];

    BOOST_SPIRIT_DEFINE(node);

    template <typename ExpectedAttributeType> void compatible(auto p) {
        static_assert(
            std::is_same_v<ExpectedAttributeType,
                           typename x3::traits::attribute_of<
                               decltype(x3::rule<struct _, ExpectedAttributeType>{} = p),
                               x3::unused_type>::type>);
    };

    void checks() {
        compatible<double>(length);
        compatible<std::string>(leaf);
        compatible<std::string>(name);
        compatible<ast::nodes>(children);
        compatible<ast::node>(tree);
    }
} // namespace parser

namespace test {
    void run_tests(auto name, auto p, std::initializer_list<char const*> cases) {
        std::cerr << "============ running " << name << " tests:\n";
        for (std::string const input : cases)
        {
            ast::node n;
            auto      ok = parse(begin(input), end(input), p, n);

            std::cout << quoted(input) << "\t " << (ok ? "PASS" : "FAIL");
            if (ok)
                std::cout << " -> " << n << std::endl;
            else
                std::cout << std::endl;
        }
    }

    void internal() {
        run_tests("internal", parser::node,
                  {
                      "(,)",
                      "(A,B)F",
                      "(A:10,B:10)F",
                  });
    }

    void tree() {
        run_tests("tree", parser::tree,
            {
                ";",
                "(,);",
                "(,,(,));",
                "(A,B,(C,D));",
                "(A,B,(C,D)E)F;",
                "(:0.1,:0.2,(:0.3,:0.4):0.5);",
                "(:0.1,:0.2,(:0.3,:0.4):0.5):0.0;",
                "(A:0.1,B:0.2,(C:0.3,D:0.4):0.5);",
                "(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F;",
                "((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A;",
            });
    }
} // namespace test

int main() {
    test::internal();
    test::tree();
}

С идентичным выводом (за исключением подавленной длины 0.0 в выводе отладки).


¹ Справедливости ради, в X3 я буду более счастлив рассматривать их, так как их написание стало намного более естественным.

Я подозреваю, что вы, возможно, захотите различать «внутренние»/«листовые» узлы больше, чем мой код. Если части node являются эксклюзивными для листовых/нелистовых узлов, вы, очевидно, захотите отразить это. Я бы заметил, что это означает, что «у меня хорошая грамматика и хороший аст» не было тогда точным. Тогда AST, отражающий реальность, будет node = variant<leaf, nonleaf> или что-то в этом роде. Вы можете упростить представление AST, чтобы избежать варианта, но у вас все равно будет два rule<..., ast::node>, которые имеют разные формы. Пока мы не узнаем, какова реальная грамматика/семантика, я не буду делать больше предположений.

sehe 21.11.2022 17:28

Еще одна вещь, которую я немного упустил, — это трюк с использованием идиомы p | attr(default_value) вместо -p, чтобы упростить сопоставление правила с AST в некоторых местах.

sehe 21.11.2022 17:30

Wahoo @sehe обеспечивает обслуживание клиентов с 2013 года! :D Спасибо, это очень помогает. Мне нравится трюк для проверки ожидаемой совместимости. И мне нравится, как в конце все становится на свои места: просто и аккуратно. Я предполагаю, что это оплачено сложностью изучения библиотеки, но объявить разбор грамматики + ast в ~20 строках — это потрясающе (и стоит пота!).

WaterFox 21.11.2022 19:02

И еще один последний вопрос: я полагаю, что роль AST НЕ в том, чтобы служить окончательной структурой данных, верно? Он должен быть совместим с грамматикой и просто содержать достаточно точное представление данных перед преобразованием в другую конструкцию, более подходящую для обработки данных?

WaterFox 21.11.2022 19:09

Здесь нет нормативных ответов. Вы не можете сказать, что «AST должен служить окончательной структурой данных» или «AST должен быть совместим с грамматикой». Я попытался передать, что это было моим предпочтением или своего рода методологией. Это просто выбор. Мой подход основан на том, что приводит к большинству грамматик без трения (я стараюсь сидеть в сладком месте библиотеки). Тем не менее, у вас может быть веская причина для отклонения, и в этом случае вы, вероятно, захотите использовать transform_attribute<> или использовать семантические действия, чтобы ваши индивидуальные структуры данных работали.

sehe 21.11.2022 22:46

«но объявить грамматику синтаксического анализа + ast в ~ 20 строках — это потрясающе (и стоит пота!)» - да. Вот почему Spirit — это мое любимое оружие для большинства небольших задач синтаксического анализа. Но я был бы последним, кто утверждал бы, что это просто или удобно. Его преимуществом является мощность и производительность, если вы знаете, как его использовать :)

sehe 21.11.2022 22:51

И именно поэтому такие новички, как я, могут быть так благодарны за то, что такие люди, как вы, преподают/демонстрируют эту библиотеку! :хлоп: :хлоп:

WaterFox 21.11.2022 22:57

Другие вопросы по теме