«Большая идея» состоит в том, чтобы представить грамматики в виде определений типов и использовать универсальное программирование для создания логики синтаксического анализа для произвольной грамматики. Мы сделаем это таким образом, чтобы код был легко оптимизируемым, и по ходу дела мы рассмотрим тесты и даже некоторые IR, сгенерированные LLVM из компилятора Clang.

Мы начнем с простейшего примитива, который можно разобрать, с одного символа. Мы представим это так:

template <char Ch> struct Literal {};

Чтобы определить грамматику, которая затем анализирует букву «а», мы будем использовать следующее определение псевдонима типа:

using a_grammar = Literal<'a'>;

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

outputs Parse(inputs);

Концептуально мы хотим передать грамматику и последовательность необработанных символов синтаксическому анализатору и заставить его возвращать 1. успешно ли это (и если нет, то почему) и 2. как далеко он продвинулся во входных данных. (Вторую часть интересно отметить, потому что этот стиль синтаксического анализатора предназначен для анализа префиксов ввода, где конец не обязательно известен заранее — это верно, например, для HTTP/1.1):

{parse-result, end-of-parse} Parse(grammar, input);

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

template <typename Grammar> 
{parse-result, end-of-parse} Parse(input);

Современный C++ использует концепцию Range для представления последовательности значений. Диапазон r — это не что иное, как значение, преобразуемое в пару итераторов путем применения std::begin(r) и std::end(r):.

template <typename Grammar, typename Range> 
{parse-result, end-of-parse} Parse(const Range& input);

Начиная с C++11, мы можем вывести возвращаемые типы из универсальных типов входных данных функции. Это было бы удобным местом для этого; тип конца синтаксического анализа на самом деле является итератором того же типа, который создается либо std::begin(r), либо std::end(r). Итак, мы можем написать:

template <typename Grammar, typename Range> 
auto Parse(const Range& input) 
  -> {parse-result, decltype(std::begin(input))};

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

В C++14 есть очень хорошая пара классов, std::error_code и std::error_condition, которые чем-то напоминают исключения, которые вы можете передавать и возвращать из функций, таких как «обычные» значения, но они имеют схожий смысл: пошло не так во время какой-то операции, и если да, то что именно произошло. Это расширяемые механизмы, как и std::exception, но они работают в рамках обычного потока управления вашей программы, поэтому они совместимы с моделью асинхронного программирования, которая будет необходима позже.

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

template <typename T>
class Fallible {
public:
  const T &get() const { return value_; }
  T &&consume() { return std::move(value_); }
  const std::error_condition &error() const { return error_; }
private:
  T value_ = {};
  std::error_condition error_;
};

(Мы выбираем std::error_condition вместо std::error_code, потому что последний предназначен только для системно-зависимых ошибок.)