Как анализировать текст для DSL во время компиляции?

Ответ 1

Отказ от ответственности: я ничего не знаю о метаплане и очень мало о прото. Следующий код - это моя попытка (главным образом через пробную версию и ошибку), чтобы изменить этот пример, чтобы сделать что-то похожее на то, что вы хотите.

Код можно легко разделить на несколько частей:

1. Грамматика

1.1 Определения токенов

typedef token < lit_c < 'a' > > arg1_token;
typedef token < lit_c < 'b' > > arg2_token;
typedef token < lit_c < 'c' > > arg3_token;

• token<Parser>:
  токен - это комбинатор парсера, который использует Parser для проанализируйте ввод и затем затем (и отбрасывает) все пробелы. Результатом разбора является результат Parser.
• lit_c<char>:
  lit_c соответствует конкретному char, а результат синтаксический разбор - это тот же самый char. В грамматике этот результат переопределяется использование always.

typedef token < keyword < _S ( "true" ), bool_<true> > > true_token;
typedef token < keyword < _S ( "false" ), bool_<false> > > false_token;

• keyword<metaparse_string,result_type=undefined>:
  соответствие ключевых слов конкретный metaparse_string (_S("true") возвращает metaparse::string<'t','r','u','e'>, который является тем, что использует metaparse внутри чтобы сделать свою магию), а результат разбора - result_type.

typedef token < keyword < _S ( "&&" ) > > and_token;
typedef token < keyword < _S ( "||" ) > > or_token;
typedef token < lit_c < '!' > > not_token;

В случае and_token и or_token результат равен undefined, а в грамматике ниже он игнорируется.

1.2 "Правила" грамматики

struct paren_exp;

Первый paren_exp объявлен вперед.

typedef one_of< 
        paren_exp, 
        transform<true_token, build_value>,
        transform<false_token, build_value>, 
        always<arg1_token, arg<0> >,
        always<arg2_token, arg<1> >, 
        always<arg3_token, arg<2> > 
    >
    value_exp;

• one_of<Parsers...>:
  one_of - это комбинатор парсеров, который пытается сопоставить ввод с одним из своих параметров. Результатом является результат, который возвращает первый парсер, который соответствует.
• transform<Parser,SemanticAction>:
  transform - это комбинатор парсера, который соответствует Parser. Тип результата - это тип результата Parser, преобразованный SemanticAction.

• always<Parser,NewResultType>:
  соответствует Parser, возвращает NewResultType.

  Эквивалентное правило духа будет:

  value_exp = paren_exp [ _val=_1 ]
      | true_token      [ _val=build_value(_1) ]
      | false_token     [ _val=build_value(_1) ]
      | argN_token      [ _val=phx::construct<arg<N>>() ];
  

typedef one_of< 
        transform<last_of<not_token, value_exp>, build_not>, 
        value_exp
    >
    not_exp;

• last_of<Parsers...>:
  last_of соответствует каждой из Parsers в последовательности, а его тип результата - это результат последнего анализатора.

  Эквивалентное правило духа будет:

  not_exp = (omit[not_token] >> value_exp) [ _val=build_not(_1) ] 
      | value_exp                          [ _val=_1 ];
  

typedef
foldl_start_with_parser<
        last_of<and_token, not_exp>,
        not_exp,
        build_and
    > and_exp; // and_exp = not_exp >> *(omit[and_token] >> not_exp);

typedef
foldl_start_with_parser<
    last_of<or_token, and_exp>,
    and_exp,
    build_or
> or_exp;     // or_exp = and_exp >> *(omit[or_token] >> and_exp);

• foldl_start_with_parser<RepeatingParser,InitialParser,SemanticAction>:
  этот комбинатор парсеров совпадает с InitialParser, а затем RepeatingParser несколько раз, пока не сработает. Тип результата является результатом mpl::fold<RepeatingParserSequence, InitialParserResult, SemanticAction>, где RepeatingParserSequence представляет собой последовательность результирующих типов каждого приложения RepeatingParser. Если RepeatingParser никогда не будет успешным, тип результата будет просто InitialParserResult.

  Я верю (xd), что эквивалентное правило духа будет:

  or_exp = and_exp[_a=_1] 
      >> *( omit[or_token] >> and_exp [ _val = build_or(_1,_a), _a = _val ]);  
  

struct paren_exp: middle_of < lit_c < '(' > , or_exp, lit_c < ')' > > {}; 
   // paren_exp = '(' >> or_exp >> ')';

• middle_of<Parsers...>:
  это соответствует последовательности Parsers, а результат - результат анализатора, который находится посередине.

typedef last_of<repeated<space>, or_exp> expression; 
   //expression = omit[*space] >> or_exp;

• repeated<Parser>:
  этот комбинатор парсеров пытается совместить Parser несколько раз. Результатом является последовательность типов результатов для каждого приложения синтаксического анализатора, если синтаксический анализатор терпит неудачу с первой попытки, результатом является пустая последовательность. Это правило просто удаляет любые ведущие пробелы.

typedef build_parser<entire_input<expression> > function_parser;

Эта строка создает метафункцию, которая принимает входную строку и возвращает результат разбора.

2. Построение выражения

Посмотрим на примерное пошаговое руководство по построению выражения. Это делается в два этапа: сначала грамматика строит дерево, которое зависит от build_or, build_and, build_value, build_not и arg<N>. Как только вы получите этот тип, вы можете получить выражение proto с помощью proto_type typedef.

"a ||! b"

Начнем с or_expr:

• or_expr: Мы попробуем его InitialParser, который является and_expr.
• • and_expr: Мы попробуем его InitialParser, который not_expr.
• • • not_expr: not_token не работает, поэтому попробуйте value_expr.
• • • • value_expr: arg1_token успешно завершен. Тип возврата arg<0>, и мы возвращаемся к not_expr.
• • • not_expr: тип возврата на этом этапе не изменяется. Вернемся к and_expr.
• • and_expr: Мы пытаемся выполнить его повторный парсер, он терпит неудачу. and_expr успешно, и его возвращаемый тип является возвращаемым типом его InitialParser: arg<0>. Вернемся к or_expr.
  • or_expr: Мы пытаемся выполнить его повторные сопоставления, совпадающие с or_token, мы попробуем and_expr.
• • and_expr: Мы попробуем его InitialParser not_expr.
• • • not_expr: not_token успешно, попробуйте value_expr.
• • • • value_expr: arg2_token преуспевает. Тип возврата arg<1>, и мы возвращаемся к not_expr.
• • • not_expr: тип возврата модифицируется с помощью функции build_not: build_not:: apply < arg < 1 → . Вернемся к and_expr.
• • and_expr: Мы пытаемся выполнить его повторный парсер, он терпит неудачу. and_expr завершается успешно и возвращает build_not:: apply < arg < 1 → . Вернемся к or_expr.
• or_expr: RepeatingParser преуспел, foldlp использует build_or на build_not::apply< arg<1> > и arg<0>, получив build_or::apply< build_not::apply< arg<1> >, arg<0> >.

Как только мы построим это дерево, получим его proto_type:

build_or::apply< build_not::apply< arg<1> >, arg<0> >::proto_type;
proto::logical_or< arg<0>::proto_type, build_not::apply< arg<1> >::proto_type >::type;
proto::logical_or< proto::terminal< placeholder<0> >::type, build_not::apply< arg<1> >::proto_type >::type;
proto::logical_or< proto::terminal< placeholder<0> >::type, proto::logical_not< arg<1>::proto_type >::type >::type;
proto::logical_or< proto::terminal< placeholder<0> >::type, proto::logical_not< proto::terminal< placeholder<1> >::type >::type >::type;

Полный код образца (Работа в Wandbox)

#include <iostream>
#include <vector>

#include <boost/metaparse/repeated.hpp>
#include <boost/metaparse/sequence.hpp>
#include <boost/metaparse/lit_c.hpp>
#include <boost/metaparse/last_of.hpp>
#include <boost/metaparse/middle_of.hpp>
#include <boost/metaparse/space.hpp>
#include <boost/metaparse/foldl_start_with_parser.hpp>
#include <boost/metaparse/one_of.hpp>
#include <boost/metaparse/token.hpp>
#include <boost/metaparse/entire_input.hpp>
#include <boost/metaparse/string.hpp>
#include <boost/metaparse/transform.hpp>
#include <boost/metaparse/always.hpp>
#include <boost/metaparse/build_parser.hpp>
#include <boost/metaparse/keyword.hpp>

#include <boost/mpl/apply_wrap.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/back.hpp>
#include <boost/mpl/bool.hpp>

#include <boost/proto/proto.hpp>
#include <boost/fusion/include/at.hpp>
#include <boost/fusion/include/make_vector.hpp>

using boost::metaparse::sequence;
using boost::metaparse::lit_c;
using boost::metaparse::last_of;
using boost::metaparse::middle_of;
using boost::metaparse::space;
using boost::metaparse::repeated;
using boost::metaparse::build_parser;
using boost::metaparse::foldl_start_with_parser;
using boost::metaparse::one_of;
using boost::metaparse::token;
using boost::metaparse::entire_input;
using boost::metaparse::transform;
using boost::metaparse::always;
using boost::metaparse::keyword;

using boost::mpl::apply_wrap1;
using boost::mpl::front;
using boost::mpl::back;
using boost::mpl::bool_;


struct build_or
{
    typedef build_or type;

    template <class C, class State>
    struct apply
    {
        typedef apply type;
        typedef typename boost::proto::logical_or<typename State::proto_type, typename C::proto_type >::type proto_type;
    };
};

struct build_and
{
    typedef build_and type;

    template <class C, class State>
    struct apply
    {
        typedef apply type;
        typedef typename boost::proto::logical_and<typename State::proto_type, typename C::proto_type >::type proto_type;
    };
};



template<bool I>
struct value //helper struct that will be used during the evaluation in the proto context
{};

struct build_value
{
    typedef build_value type;

    template <class V>
    struct apply
    {
        typedef apply type;
        typedef typename boost::proto::terminal<value<V::type::value> >::type proto_type;
    };
};

struct build_not
{
    typedef build_not type;

    template <class V>
    struct apply
    {
        typedef apply type;
        typedef typename boost::proto::logical_not<typename V::proto_type >::type proto_type;
    };
};

template<int I>
struct placeholder //helper struct that will be used during the evaluation in the proto context
{};

template<int I>
struct arg
{
    typedef arg type;
    typedef typename boost::proto::terminal<placeholder<I> >::type proto_type;
};

#ifdef _S
#error _S already defined
#endif
#define _S BOOST_METAPARSE_STRING

typedef token < keyword < _S ( "&&" ) > > and_token;
typedef token < keyword < _S ( "||" ) > > or_token;
typedef token < lit_c < '!' > > not_token;

typedef token < keyword < _S ( "true" ), bool_<true> > > true_token;
typedef token < keyword < _S ( "false" ), bool_<false> > > false_token;

typedef token < lit_c < 'a' > > arg1_token;
typedef token < lit_c < 'b' > > arg2_token;
typedef token < lit_c < 'c' > > arg3_token;


struct paren_exp;

typedef
one_of< paren_exp, transform<true_token, build_value>, transform<false_token, build_value>, always<arg1_token, arg<0> >, always<arg2_token, arg<1> >, always<arg3_token, arg<2> > >
value_exp; //value_exp = paren_exp | true_token | false_token | arg1_token | arg2_token | arg3_token;

typedef
one_of< transform<last_of<not_token, value_exp>, build_not>, value_exp>
not_exp; //not_exp = (omit[not_token] >> value_exp) | value_exp;

typedef
foldl_start_with_parser <
last_of<and_token, not_exp>,
         not_exp,
         build_and
         >
         and_exp; // and_exp = not_exp >> *(and_token >> not_exp);

typedef
foldl_start_with_parser <
last_of<or_token, and_exp>,
         and_exp,
         build_or
         >
         or_exp; // or_exp = and_exp >> *(or_token >> and_exp);

struct paren_exp: middle_of < lit_c < '(' > , or_exp, lit_c < ')' > > {}; //paren_exp = lit('(') >> or_exp >> lit('(');

typedef last_of<repeated<space>, or_exp> expression; //expression = omit[*space] >> or_exp;

typedef build_parser<entire_input<expression> > function_parser;


template <typename Args>
struct calculator_context
        : boost::proto::callable_context< calculator_context<Args> const >
{
    calculator_context ( const Args& args ) : args_ ( args ) {}
    // Values to replace the placeholders
    const Args& args_;

    // Define the result type of the calculator.
    // (This makes the calculator_context "callable".)
    typedef bool result_type;

    // Handle the placeholders:
    template<int I>
    bool operator() ( boost::proto::tag::terminal, placeholder<I> ) const
    {
        return boost::fusion::at_c<I> ( args_ );
    }

    template<bool I>
    bool operator() ( boost::proto::tag::terminal, value<I> ) const
    {
        return I;
    }
};

template <typename Args>
calculator_context<Args> make_context ( const Args& args )
{
    return calculator_context<Args> ( args );
}

template <typename Expr, typename ... Args>
int evaluate ( const Expr& expr, const Args& ... args )
{
    return boost::proto::eval ( expr, make_context ( boost::fusion::make_vector ( args... ) ) );
}

#ifdef LAMBDA
#error LAMBDA already defined
#endif
#define LAMBDA(exp) apply_wrap1<function_parser, _S(exp)>::type::proto_type{}

int main()
{
    using std::cout;
    using std::endl;

    cout << evaluate ( LAMBDA ( "true&&false" ) ) << endl;
    cout << evaluate ( LAMBDA ( "true&&a" ), false ) << endl;
    cout << evaluate ( LAMBDA ( "true&&a" ), true ) << endl;
    cout << evaluate ( LAMBDA ( "a&&b" ), true, false ) << endl;
    cout << evaluate ( LAMBDA ( "a&&(b||c)" ), true, false, true ) << endl;
    cout << evaluate ( LAMBDA ( "!a&&(false||(b&&!c||false))" ), false, true, false ) << endl;
}

/*int main(int argc , char** argv)
{
    using std::cout;
    using std::endl;

    bool a=false, b=false, c=false;

    if(argc==4)
    {
        a=(argv[1][0]=='1');
        b=(argv[2][0]=='1');
        c=(argv[3][0]=='1');
    }

    LAMBDA("a && b || c") expr;

    cout << evaluate(expr, true, true, false) << endl;
    cout << evaluate(expr, a, b, c) << endl;

    return 0;
}*/

Ответ 2

В течение длительного времени синтаксический анализ компиляции означал использование мета-программирования шаблонов - что кажется линейным шумом для большинства начинающих и даже промежуточных программистов на C++.

Однако, с С++ 11 мы получили constexpr и в С++ 14 было удалено множество ограничений для constexpr. С++ 17 даже делает несколько стандартных объектов библиотеки constexpr.

При попытке изучить продвинутый современный С++ - я решил написать компилятор HTML-парсера времени. Идея заключалась в создании быстрого HTML-шаблонизатора.

Весь код можно найти здесь: https://github.com/rep-movsd/see-phit

Вкратце объясню то, что я узнал, когда приступаю к работе.

Обработка динамических структур данных

Мне нужно было разобрать const char * и преобразовать его в многодорожее дерево, но динамическое распределение не является no-no в constexpr land.

Решение? Используйте массив узлов с индексами, указывающими на детей и братьев и сестер - по существу, как вы можете сделать это в FORTRAN!

Предостережение состоит в том, что ваш список узлов должен иметь фиксированный размер изначально. Сохранение его очень большого размера, казалось, сделало gcc медленным компиляцией огромным количеством. Если вы закончите прохождение конца массива, компилятор вызовет ошибку. Я написал небольшую std:: array, такую ​​как wrapper, которая полностью constexpr.

Синтаксический

Довольно стандартный код, который вы пишете во время разбора во время выполнения, будет работать во время компиляции! Циклы, рекурсия, условные обозначения - все работает отлично.

Одна проблема заключалась в том, как представлять строки? Использование вышеупомянутого подхода - массив из char - очень голодный, утомительный способ делать вещи. К счастью, в моем случае все, что мне когда-либо понадобилось, было всего лишь подстрокой исходного ввода const char *. Поэтому я написал небольшой класс constexpr string_view, который просто содержит указатели на начало и конец соответствующего синтаксического маркера. Создание новых литеральных строк - это просто вопрос о том, чтобы сделать эти представления в литерал const char *.

Отчет об ошибках

Основным способом обработки ошибок в коде constexpr является вызов функции, которая не является constexpr - компилятор останавливается и печатает строку нарушения, которая может легко содержать строку ошибки.

Однако я хотел большего - я хотел, чтобы синтаксический анализатор отображал строку и столбец. Некоторое время я боролся и думал, что это невозможно. Но я вернулся к нему и пробовал все возможные вещи, о которых я мог думать. Наконец, я нашел способ, который делает gcc print 2 numbers и сообщение об ошибке. Он по существу включает в себя создание шаблона с двумя целыми параметрами (строка и столбец), значения которых исходят от парсера constexpr.

Производительность

Я не мог четко найти какой-либо шаблон относительно того, какой код constexpr стремится замедлить работу компилятора, но производительность по умолчанию не слишком убогая. Я могу разобрать 1000 node HTML файл примерно через 1,5 секунды на gcc.

clang немного быстрее.

Я намерен написать более подробное описание того, как код работает в wiki репозитория github, - следите за обновлениями.

Ответ 3

Хотя технически возможно сделать такое метапрограммирование с помощью шаблонов или constexpr, я бы не рекомендовал этот подход. Youll в конечном итоге с огромным количеством очень сложный код. Будет сложно отлаживать и дорого поддерживать и расширять.

Вместо этого используйте любой другой язык для генерации кода С++ из ваших выражений.

Если вы используете Visual Studio, один хороший встроенный способ - это текстовые шаблоны T4. Heres подробнее.

В противном случае используйте любой другой язык, доступный на вашей платформе, например. Я сделал что-то подобное в Python.