и должно умещаться в одну строку. Действие указывает нужно ли удалить событие данного типа или же сохранить. Условие представляет из себя пару
if логическое_выражение
Поскольку выражения будут обрабатываться последовательно сверху вниз, то будет выбрано действие, соответствующее первому условию, вычисленному как true.
Условие представляет из себя логическое выражение. Оно может содержать любые арифметические операции, логические операции, функции с одним аргументом и переменные, в том числе элементы n-мерного вектора типа:
a[n1,n2]
Под безопасностью преобразования типов я имею ввиду следующее:
- Должны правильно соблюдаться целочисленные и вещественные преобразования, например 3/2 должно вычисляться как целое значение 1, а 3/2.0 должно вычисляться как вещественное значение 1.5.
- Операторы и функции, ожидающие контекст определенного типа, не должны получать аргументы другого типа (например, при попытке передать в функцию, ожидающую 2-мерный вектор, скалярное значение должно быть сгенерировано исключение).
Вычисление условного выражения выполняется в 2 этапа:
- Парсинг условного выражение и создание абстрактного синтаксического дерева (AST).
- Рекурсивное вычисление (эвалюация) AST. В процессе вычисления AST выполняется подстановка переменных (а еще лучше, их заранее замапленных адресов) и вычисление функций. Переменные связаны с полями прочитанного объекта либо с помощью вычисления, либо прямым маппингом адреса. В предложенном примере реализовано вычисление двух скалярных функций: Sqr() и Sqrt(). Ни одна переменная не определена. Для добавления функций и переменных достаточно создать новый класс, наследующий CexmcAST::BasicEval и переопределить в нем виртуальные функции GetFunScalarValue() и GetVarScalarValue().
Парсинг условия достаточно выполнить только один раз в начале выполнения программы. Второй этап вычисления нужно выполнять отдельно для каждого прочитанного объекта, так как переменные в выражении фактически связаны (вычисляются или замаплены) с полями объекта. Исключения, связанные с безопасностью преобразования типов, могут быть сгенерированы только на втором этапе вычисления условного выражения, поскольку на первом этапе еще ничего не известно о типах встречающихся функций и переменных.
Абстрактное синтаксическое дерево представляет собой рекурсивный тип, содержащий узлы и листья. Узлы могут содержать 1 (унарные операторы и функции) или 2 (бинарные операторы) детей. Верхушка AST всегда узел, так, для выражения типа
delete tpt if 0
будет постороено дерево с верхушкой - унарным оператором Top, который возвращает вычисленное значение своего единственного ребенка. Для реализации AST был использован рекурсивный вариант из boost.
Для хранения результатов парсинга выражения я использовал следующий тип:
struct ParseResult
{
ParseResult() : action( KeepTPT )
{}
void Initialize( void )
{
action = KeepTPT;
expression.children.clear();
expression.type = Uninitialized;
}
Action action;
Subtree expression;
};
где Action и Subtree определены как
enum Action
{
KeepTPT,
KeepEDT,
DeleteTPT,
DeleteEDT
};
struct Subtree
{
Subtree() : type ( Uninitialized ), hasRLAssoc( false )
{}
void Print( int level = 0 ) const;
void PrintLeaf( const Leaf * leaf, int level = 0 ) const;
std::vector< Node > children;
NodeType type;
bool hasRLAssoc;
static const int printIndent = 4;
};
Структура Subtree - это и есть реализация AST. Node предоставляет выбор между узлом и листом (т.к. дети могут являться и тем и другим), NodeType предоставляет выбор между оператором и функцией:
typedef std::string Function;
typedef variant< int, double > Constant;
typedef variant< Variable, Constant > Leaf;
typedef recursive_wrapper< Subtree > Tree;
typedef variant< Tree, Leaf > Node;
typedef variant< Operator, Function > NodeType;
Для парсинга выражения необходимо определить формальную грамматику и семантические действия, которые в нашем случае будут заключаться в построениии AST. В boost::spirit для определения семантических действий можно использовать библиотеку boost::phoenix, которая была создана в недрах проекта spirit.
template < typename Iterator >
struct Grammar : grammar< Iterator, ParseResult(), space_type >
{
Grammar();
rule< Iterator, ParseResult(), space_type > statement;
rule< Iterator, Action(), space_type > action;
rule< Iterator, Subtree(), space_type > condition;
rule< Iterator, Node(), space_type > expression;
rule< Iterator, Node(), space_type > primary_expr;
rule< Iterator, Node(), space_type > function1;
rule< Iterator, std::string(), space_type > identifier;
rule< Iterator, Leaf(), space_type > leaf_operand;
rule< Iterator, Leaf(), space_type > constant;
rule< Iterator, Leaf(), space_type > variable;
rule< Iterator, Node(), space_type > or_expr;
rule< Iterator, Node(), space_type > and_expr;
rule< Iterator, Node(), space_type > relation;
rule< Iterator, Node(), space_type > addition;
rule< Iterator, Node(), space_type > multiplication;
rule< Iterator, Node(), space_type > unary_expr;
rule< Iterator, Operator(), space_type > unary_op;
rule< Iterator, Operator(), space_type > mult_op;
rule< Iterator, Operator(), space_type > add_op;
rule< Iterator, Operator(), space_type > rel_op;
real_parser< double, strict_real_policies< double > > strict_double;
function< Compiler > op;
};
template < typename Iterator >
Grammar< Iterator >::Grammar() : Grammar::base_type( statement )
{
statement = action[ op( _val, _1 ) ] >>
*( condition[ op( _val, _1 ) ] );
action = lit( "keep" ) >>
( lit( "tpt" )[ _val = KeepTPT ] |
lit( "edt" )[ _val = KeepEDT ] ) |
lit( "delete" ) >>
( lit ( "tpt" )[ _val = DeleteTPT ] |
lit ( "edt" )[ _val = DeleteEDT ] );
condition = lit( "if" ) >> expression[ op( _val, _1 ) ];
expression %= or_expr;
identifier %= lexeme[ alpha >> *( alnum | lit( '_' ) ) ];
primary_expr = function1[ op( _val, _1 ) ] |
lit( '(' ) >> expression[ op( _val, _1 ) ] >> lit( ')' ) |
leaf_operand[ _val = _1 ];
leaf_operand %= constant | variable;
constant %= strict_double | int_;
variable = identifier[ op( _val, _1 ) ] >>
-( lit( '[' ) >> ( uint_[ op( _val, _1, 0 ) ] - lit( '0' ) ) >>
-( lit( ',' ) >> ( uint_[ op( _val, _1, 1 ) ] -
lit( '0' ) ) ) >> lit( ']' ) );
function1 = ( identifier >> lit( '(' ) >> expression >> lit( ')' ) )
[ op( _val, _2, _1 ) ];
or_expr = ( and_expr >> lit( '|' ) >> or_expr )
[ op( _val, _1, _2, Or ) ] |
and_expr[ _val = _1 ];
and_expr = ( relation >> lit( '&' ) >> and_expr )
[ op( _val, _1, _2, And ) ] |
relation[ _val = _1 ];
relation = ( addition >> rel_op >> addition )
[ op( _val, _1, _3, _2 ) ] |
addition[ _val = _1 ];
addition = ( multiplication >> add_op >> addition )
[ op( _val, _1, _3, _2 ) ] |
multiplication[ _val = _1 ];
multiplication = ( unary_expr >> mult_op >> multiplication )
[ op( _val, _1, _3, _2 ) ] |
unary_expr[ _val = _1 ];
unary_expr = ( unary_op >> primary_expr )[ op( _val, _2, _1 ) ] |
primary_expr[ _val = _1 ];
unary_op = lit( '-' )[ _val = UMinus ] | lit( '!' )[ _val = Not ];
mult_op = lit( '*' )[ _val = Mult ] | lit( '/' )[ _val = Div ];
add_op = lit( '+' )[ _val = Plus ] | lit( '-' )[ _val = Minus ];
rel_op = lit( "<=" )[ _val = LessEq ] |
lit( ">=" )[ _val = MoreEq ] |
lit( "!=" )[ _val = NotEq ] |
lit( '<' )[ _val = Less ] |
lit( '>' )[ _val = More ] |
lit( '=' )[ _val = Eq ];
}
Грамматические правила выражаются через вложенные правила, связанные между собой посредством операторов >> и |, и описания семантических действий, заключенных в квадратные скобки после вложенных правил. В простейшем случае правило может представлять собой лексему вида lit( "if" ). Оператор >> создает цепочку сканирования. Для получения соответствия сканируемого текста данному правилу необходимо чтобы вся цепочка соответствовала сканируемому тексту. Оператор | может применяться к цепочкам сканирования или отдельным правилам в выражении и предоставляет парсеру возможность выбора между его операндами: если левый операнд оператора | соответствует сканируемому участку, то будет выбран именно он, иначе парсер попытается выбрать правый операнд.
Правила могут быть рекурсивными, то есть ссылаться в своем определении на самих себя, например правило multiplication содержит в своем определении multiplication. Однако здесь присутствует одно очень важное ограничение: вложенность не должна создавать левую рекурсию, т.е. выражения, в которых явно или неявно определяемое правило входит в собственное выражение слева (причем неважно в какой из ветвей, разделенных оператором |), недопустимы. Например, правило
multiplication = ( multiplication >> mult_op >> unary_expr )
[ op( _val, _1, _3, _2 ) ] |
unary_expr[ _val = _1 ];
недопустимо. Его использование не приведет к ошибке компиляции, однако в рантайме программа обязательно упадет.
Самое простое семантическое действие может быть выражено как [ _val = _1 ], здесь используются определенные в boost переменные, _val связана с результирующим правилом и представляет собой ссылку на его сигнатуру. Если посмотреть на определения правил, например правила multiplication:
rule< Iterator, Node(), space_type > multiplication;
то можно заметить, что они могут создаваться с использованием конструкторов некоторых типов - сигнатур, в данном случае сигнатурой является Node(), это означает, что к правилу будет привязан объект типа Node. Переменная _1 - это ссылка на сигнатуру того правила, к которому применяется семантическое действие. Если семантическое действие применяется к выражению, заключенному в круглые скобки (например, цепочке сканирования), то могут быть задействованы переменные _2 и _3, ссылающиеся на сигнатуры правил, входящих в выражение. В простейшем случае, если сигнатуре результирующего правила нужно присвоить сигнатуру всего выражения справа (или, как частный случай, подвыражений, выбранных оператором |), можно использовать оператор %=, например:
expression %= or_expr;
Более сложные семантические правила реализуются с помощью вспомогательного объекта op типа Compiler, который определен как
struct Compiler
{
template < typename A, typename B = boost::fusion::unused_type,
typename C = boost::fusion::unused_type,
typename D = boost::fusion::unused_type >
struct result { typedef void type; };
void operator()( ParseResult & parseResult, Action value ) const;
void operator()( ParseResult & parseResult, Subtree & value ) const;
void operator()( Subtree & ast, Node & node ) const;
void operator()( Node & self, Node & left, Node & right,
Operator value ) const;
void operator()( Node & self, Node & child, Operator value ) const;
void operator()( Node & self, Node & primary ) const;
void operator()( Node & self, Node & child, std::string & value )
const;
void operator()( Leaf & self, std::string & name ) const;
void operator()( Leaf & self, int value, size_t index ) const;
};
Реализацию операторов можно увидеть в прилагаемом коде.
Для того, чтобы запустить парсер и заполнить объект типа ParseResult, нужно вызвать функцию phrase_parse():
phrase_parse( begin, end, customFilterGrammar,
CexmcCustomFilter::space, parseResult )
Здесь begin и end - итераторы на начало и конец обрабатываемого текста, customFilterGrammar - объект типа Grammar, parseResult - ссылка на объект типа ParseResult, который будет заполнен в результате действия phrase_parse(). Объект грамматики связан с типом ParseResult через Grammar::base_type, который соответствует правилу statement, сигнатурой которого в свою очередь является ParseResult(). Функция phrase_parse() ограждает пользователя от заботы о пробельных символах во время парсинга. Она возвращает false в случае неудачи, также неудачей можно считать случай частичного совпадения, когда begin не равен end после возвращения из phrase_parse()(итератор begin смещается в процессе парсинга и в случае успеха должен совпасть с end).
Некоторые тонкости реализации грамматики:
- Как видно из определений правил, все арифметические и логические правила выражены через правила более высокого приоритета и сами себя - например операциии сложения addition определены через multiplication и addition. Определение операции через операции более высокого приоритета позволяет соблюдать приоритет операций при построении AST. Определение операции через саму себя позволяет выстраивать цепочки этой операции в выражениии, например 4 + 8 + 10 - 2. Исключением являются операции отношения - правило relation, они выражаются только через операции более высокого приоритета, это не позволяет выстраивать их в цепочки. В самом деле, выражение a > 7 > b недопустимо.
- Проблема левой рекурсии и левоассоциативности. Взгляните еще раз на определение правила multiplication. Оно выражается через само себя и unary_expr. Запрет левой рекурсии означает, что unary_expr должен стоять левее, чем операнд multiplication. В свою очередь, это означает, что выражение 2 * 5 / 7 будет вычислено как 2 * (5 / 7), что даст неверный результат, так как операции умножения и деления левоассоциативны. Проблему можно решить двумя способами: привести леворекурсивное правило к праворекурсивному (это всегда возможно), или учесть изменение порядка операций в соответствующем операторе () типа Compiler, не изменяя синтаксическое правило. Я решил пойти вторым путем, соответствующий оператор выглядит следующим образом:
void Compiler::operator()( Node & self, Node & left, Node & right,
Operator value ) const
{
Subtree & ast( boost::get< Subtree >( self ) );
ast.children.push_back( left );
ast.type = value;
Subtree * astRight( boost::get< Subtree >( &right ) );
if ( ! astRight )
{
ast.children.push_back( right );
return;
}
bool hasLessPriorityThanRightOp( false );
Operator * rightOp( boost::get< Operator >( &astRight->type ) );
if ( rightOp )
{
hasLessPriorityThanRightOp = OperatorPriority::IsLessThan(
value, *rightOp );
}
if ( astRight->hasRLAssoc || hasLessPriorityThanRightOp )
{
ast.children.push_back( right );
return;
}
ast.children.push_back( astRight->children[ 0 ] );
Subtree astResult;
astResult.children.push_back( self );
astResult.children.push_back( astRight->children[ 1 ] );
astResult.type = astRight->type;
self = astResult;
}
- Взгляните на определение правила constant:
constant %= strict_double | int_;
Правило strict_double - это видоизмененное правило double_, которое не позволяет парсить как double целочисленные значения:
real_parser< double, strict_real_policies< double > > strict_double;
Проблема поднималась на форумах (см. например здесь) и было предложено это решение.
После успешного завершения парсинга мы имеем набор (в прилагаемом примере только один) объектов типа ParseResult. Все что остается сделать - это рекурсивно пройтись по выражениям expression этих объектов, подставляя значения переменных и выполняя функции. Для этого предназначен класс CexmcAST::BasicEval:
class BasicEval
{
protected:
typedef variant< int, double > ScalarValueType;
protected:
virtual ~BasicEval();
public:
bool operator()( const Subtree & ast ) const;
protected:
ScalarValueType GetScalarValue( const Node & node ) const;
virtual ScalarValueType GetFunScalarValue( const Subtree & ast )
const;
virtual ScalarValueType GetVarScalarValue( const Variable & var )
const;
ScalarValueType GetBasicFunScalarValue(
const Subtree & ast, bool & result )
const;
};
Единственная публичная функция данного класса: operator(), которая принимает объект типа Subtree в качестве аргумента и вызывает рекурсивную функцию GetScalarValue(). Кроме того, BasicEval предоставляет две виртуальные функции GetFunScalarValue() и GetVarScalarValue(), которые можно использовать в классах-наследниках для определения дополнительных функций и переменных. Также, в классе-наследнике можно определить соответствующие функции, связанные с обработкой функций и переменных нескалярных типов.
Взять исходный код примера можно здесь (с исправлениями, указанными в этом обновлении).
