Я использую Boost Spirit для реализации функциональности в некотором программном обеспечении, которое позволяет пользователю вводить математическое уравнение, которое будет неоднократно применяться к входному потоку. Значения входного потока представлены в виде символов, используя boost::spirit::qi::symbols
который пользователь может ссылаться в своем уравнении. (например. out1 = 3 * in1 + in2
)
Синтаксический анализ и компиляция уравнения пользователя не чувствительны к производительности, но вычисление его выходного значения происходит, поскольку оно является частью критичного ко времени конвейера.
Стандартным способом, которым Spirit используется в документации, является вычисление вывода (атрибута) входных данных при их анализе. Однако, как между каждым вычислением только значения атрибутов символов (out1
, in1
и т. д.) изменится, создается впечатление, что может быть более эффективный способ добиться этого, возможно, путем кэширования абстрактного синтаксического дерева выражения и повторения через него.
Какой самый эффективный способ пересчитать значение этого (фиксированного) уравнения с учетом нового набора значений символов?
Стандартный способ использования Духа не так ограничен, как кажется.
Пока ты Можно используйте его, чтобы вычислить непосредственную ценность на лету, это намного более обычно строить AST-дерево в выходном атрибуте, которое можно преобразовать (упростить, оптимизировать) и интерпретировать (например, испуская виртуальную машину или даже инструкции по сборке).
Учебные руководства по компилятору показывают это в полном объеме, но примеры калькулятора очень близки к тому, что вы, похоже, ищете: http://www.boost.org/doc/libs/1_55_0/libs/spirit/example/qi/compiler_tutorial/
calc1 в примере / qi / compiler_tutorial / calc1.cpp
Простой пример калькулятора, демонстрирующий грамматику. Парсер это синтаксис
только для проверки и не выполняет никакой семантической оценки.CALC2 в примере / qi / compiler_tutorial / calc2.cpp
Пример калькулятора, демонстрирующий грамматические и семантические действия с использованием
простые функции. Парсер печатает код, подходящий для виртуального стека
машина.calc3 в примере / qi / compiler_tutorial / calc3.cpp
Пример калькулятора, демонстрирующий грамматические и семантические действия с использованием
Феникс, чтобы сделать фактическую оценку выражения. Парсер по сути
"переводчик" который оценивает выражения на лету.
Вот где вам это интересно, так как он перестает делать вычисления во время разбора:
calc4 в примере / qi / compiler_tutorial / calc4.cpp
Пример калькулятора, демонстрирующий генерацию AST. АСТ, однажды
создано, пройдено,
- Распечатать его содержимое и
- Оценить результат.
calc5 в примере / qi / compiler_tutorial / calc5.cpp
Так же, как Calc4, на этот раз мы добавим поддержку отладки плюс ошибку
обработка и отчетность.calc6 в примере / qi / compiler_tutorial / calc6.cpp
Еще один пример калькулятора! На этот раз мы скомпилируем в простой
виртуальная машина. На самом деле это один из самых первых духовных примеров.
около 2000 года. Теперь он портирован на Spirit2.calc7 в примере / qi / compiler_tutorial / calc7 / main.cpp
Теперь мы введем переменные и присваивание. На этот раз мы тоже будем
переименование некоторых правил — стратегия для более грандиозной схемы 😉Эта версия также демонстрирует грамматику модульности. Здесь вы увидите, как
выражения и операторы построены как модульные грамматики.calc8 в примере / qi / compiler_tutorial / calc8 / main.cpp
Теперь мы представим логические выражения и управляющие структуры. Это
Теперь очевидно, что мы делаем? 😉
Я уверен, что вы найдете много вдохновения к концу урока!
Вы можете создать свое собственное дерево объектов калькулятора, которое отражает AST. Так что для вашего примера out1 = 3 * in1 + in2
АСТ это:
*
3
+
in1
in2
Таким образом, вы бы построили иерархию объектов следующим образом:
Multiplier(
Constant(3),
Adder(
Variable(&in1),
Variable(&in2)
)
)
С занятиями что-то вроде:
class Result {
virtual double value() = 0;
};
class Multiplier : public Result {
Multiplier(Result* lhs, Result* rhs);
double value() { return _lhs->value() * _rhs->value(); }
}