Дмитpий Hecтepук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Posts Tagged ‘boost-spirit

Не нравится ООП? Делайте свой язык программирования!

24 комментария

В интернете нынче модно говорить что «ООП это шлак», и многие мечтают сделать свой собственный язык программирования но чего-то боятся. А на самом деле, если подойти с умом, тут все просто. Серьезно! Я знаю, вы хотите мне возразить, что дескать…

  • Писать свой компилятор в native code/IL/bytecode слишком сложно — а и не надо!! Вы понимаете, что существующие компиляторы вроде С или Java оттачивались годами, сотнями людей? Почему бы не воспользоваться всем этим богатством, компилируя ваш язык в тот же С/C++, и потом получая от С/C++ компилятора все оптимизации и плюшки?

  • Меня не прет идея возиться с кастомными форматами файлов для лексинга и парсинга, это депрессивно — а и не надо!! Просто возьмите фреймворк, который поддерживает парсеростроение прямо в коде.

  • У меня сейчас весь код на Java/C#/C++ написан, как я сделаю interop? — да очень просто, ведь с подходом транскомпиляции, вы можете транслировать свой язык в любой из вышеперечисленных, генеря и потом потребляя любой интерфейс, причем в обе стороны.

  • Язык-то я сделаю, а как насчет поддержки языка в моей любимой IDE? — о, ну это уже высший полет. Для начала, постарайтесь сделать лаконичный маленький язык, для которого инструменты не критичны. А потом можно научиться и тулы поддерживать (или писать свои).

Ну что, убедил?

Чтобы показать насколько это все просто, вот небольшой пример: представим, что вы хотите расширить определение С-образной глобальной функции, добавив следующие фичи:

  • Определить свой набор «коротких» типов переменных, вроде i32 или f64 на замену int и double.

  • Передавать аргументы в формате x,y : i32, то есть переиспользуя определение типа для нескольких сразу.

  • Добавлять в тело функции определения переменных вроде x = 5 так чтобы, при условии что x не имя параметра, это преврашалось в полноценную декларацию переменной, а иначе просто присваивалось значиние.

Для начала такой фичесет подойдет? Я знаю что мало, но я тут и не пытаюсь целый язык сделать. Вот как это будет выглядеть:

Наш язык… …станет вот этим
void foo(x,y:i32, z:f64)
{
  x = 5;
  w = 123;
}
void foo(int32_t x, int32_t y, double z)
{
  x = 5;
  int w = 123;
}

Структуры для языка

Во всех языках есть механизмы построения парсеров. Я возьму C++ и Boost.Spirit, для примера, но вообще язык тут особого значения не имеет. Для начала давайте сделаем новые типы вроде f32 вместо float:

struct numeric_types_ : qi::symbols<wchar_t, wstring>
{
  numeric_types_()
  {
    add(L"i32", L"int32_t");
    add(L"f32", L"float");
    add(L"f64", L"double");
  }
} numeric_types;

Теперь определяем функцию:

struct function
{
  wstring name;
  vector<parameter> params;
  vector<assignment_statement> assignments;
 
  // поиск параметра по имени; реализация банальна
  boost::optional<const parameter&> find_parameter(const wstring& name) const;
};

У любой функции есть имя, она берет сколько-то там параметров (ну, деклараций параметров, но краткость сестра таланта), и у нее есть тело, которое в нашем случае будет состоять исключительно из присвоений значений переменным (не очень практично, I know).

Поскольку мы умеем определять аргументы в стиле x,y:i32, т.е. несколько с одним типом, собственно структур parameter мы определим вот так:

struct parameter
{
  vector<wstring> names;
  wstring type;
};

Ну и наконец присвоение значений переменным можно сделать вот так:

struct assignment_statement
{
  wstring variable_being_assigned;
  wstring value;
  wstring infer_type() const
  {
    if (value.find(L'.') == wstring::npos)
      return L"int"s;
    return L"float"s;
  }
};

Выше показан г~код для определения типа, думаю вы понимаете что в последствии это можно пофиксить.

Всё, структуры готовы, можно строить парсер. (На самом деле есть еще этап их адаптации через Boost.Fusion, но это implementation-specific деталь, если что гляньте в сорцы.)

Парсер

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

template<typename Iterator>
struct function_parser : qi::grammar<Iterator, function(), space_type>
{
  function_parser() : function_parser::base_type(start)
  {
    using qi::lit;
    param %= 
      +alnum % ','
      >> ':'
      >> numeric_types
      >> -char_(',');
    assignment %=
      +alnum
      >> '='
      >> +alnum
      >> ';';
    start %= lit("void ")
      >> +(char_ - '(')
      >> '('
      >> *param
      >> ')'
      >> '{'
      >> *assignment
      >> '}';
  }

  qi::rule<Iterator, parameter(), space_type> param;
  qi::rule<Iterator, assignment_statement(), space_type> assignment;
  qi::rule<Iterator, function(), space_type> start;
};

Для начала, вот эти qi::rule просто говорят парсеру как то что он распарсит ложится на структуры что мы определили ранее. Например, вот хочется распарсить присваивание вроде x = 3, что это? Это идентификатор (то есть, 1 и более alphanumeric символов), потом =, потом еще раз набор символов и в конце ;.

Конкретно в Boost.Sprit, в отличии от регулярок, «один и более» записывается как + до типа символа, т.е. +alnum. То есть + означает «один и более», * — «сколько угодно», и так далее. Вот и получается что присваивание мы распарсили, а поскольку наш qi::rule мэпит его на assignment_statement, поля этой структуры будут присвоены автоматически. Это гениально, или как?

То же и с другими частями языка. Хочешь распарсить несколько переменных через запятую и запихнуть их в вектор? Пишем +alnum % ',' где оператор % – это как сказать *(+alnum >> ','), только короче. Что тоже удобно.

Так вот, парсер у нас готов, можно парсить. На Spirit это делается вот так:

template<typename Iterator>
wstring parse(Iterator first, Iterator last)
{
  using boost::spirit::qi::phrase_parse;
  function f;
  function_parser<wstring::const_iterator> fp{};
  auto b = phrase_parse(first, last, fp, space, f);
  if (b)
  {
    return render(f);
  }
  return wstring(L"FAIL");
}

…где render() – это функция которая обходит то что мы напарсили и генерит из этого чистейший, готовый к компиляции С (никто не мешает вам выводить сразу в N разных языков).

Pretty print

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

inline wstring render(const function& f)
{
  wostringstream s;
  // name of the function (assume void-returning)
  s << "void " << f.name << "(";

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

// each of the parameters
const auto param_count = f.params.size();
for (auto i = 0u; i < param_count; ++i)
{
  auto& p = f.params[i];
  for (int j = 0; j < p.names.size(); ++j)
  {
    s << p.type << " " << p.names[j];
    if (j + 1 < p.names.size()) s << ", ";
  }
  if (i + 1 < param_count) s << ", ";
}
s << ")\r\n{\r\n";

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

// each of the assignments
const auto assign_count = f.assignments.size();
for (auto i = 0u; i < assign_count; ++i)
{
  s << "  ";
  auto& a = f.assignments[i];
  auto type = a.infer_type();
  bool is_param = f.find_parameter(a.variable_being_assigned) != boost::none;
  if (!is_param)
    s << type << " ";
  s << a.variable_being_assigned << " = " << a.value << ";\r\n";
}
s << "}";
return s.str();

Вот собственно и всё. Тут в принципе можно реализовать «полноценный» Visitor, если хочется.

Заключение

Как вы поняли, тут остался шаг компиляции полученного кода — думаю всем итак очевидно как это делать, это зависит от языка который вы нагенерили. Вообще я ратую за «портативный» C/C++, но решать в конечном счете вам.

Если хотите сорцы проекта, они тут. Мой пример на С++, но вы можете реализовать свой язык на чем угодно. Мораль в том что создать сейчас свой кросс-компилируемый язык легко, поэтому вместо того чтобы ныть про ООП и воевать с ветряными мельницами, проще сесть и запилить что-то своё. Так что садитесь и пишите спеку вашего чудо-юдо языка. Удачи!

Written by Dmitri

2 сентября 2016 at 16:10

Опубликовано в Programming

Tagged with , ,