«Большая идея» состоит в том, чтобы представить грамматики в виде определений типов и использовать универсальное программирование для создания логики синтаксического анализа для произвольной грамматики. Мы сделаем это таким образом, чтобы код был легко оптимизируемым, и по ходу дела мы рассмотрим тесты и даже некоторые 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, потому что последний предназначен только для системно-зависимых ошибок.)