Warning, /office/calligra/sheets/doc/FormulaEngine.dox is written in an unsupported language. File is not indexed.

 /**
 \page formulaengine Formula Engine
 \author Ariya Hidayat (<a href="mailto:ariya@kde.org">ariya@kde.org</a>)
 \date 2004
 
 \par Status:
     FINISHED; NEEDS UPDATE (inline arrays)
 
 <p>This formula engine is just an expression evaluator. To offer better
 performance, the expression is first compiled into byte codes which will
 be executed later by a virtual machine.</p>
 
 <p>Before compilation, the expression is separated into pieces, called tokens.
 This step, which is also known as lexical analysis, takes places at once
 and will produce sequence of tokens. They are however not stored and used only
 for the purpose of the subsequent step.
 Tokens are supplied to the parser, also known as syntax analyzer. In this
 design, the parser is also a code generator. It involve the generation
 of byte codes which represents the expression.
 Evaluating the formula expression is now basically running the virtual
 machine to execute compiled byte codes. No more scanning or parsing
 are performed during evaluation, this saves time a lot.</p>
 
 <p>The virtual machine itself (and of course the byte codes) are designed to be
 as simple as possible. This is supposed to be stack-based, i.e. the virtual
 machine has an execution stack of values which would be manipulated
 as each byte code is processed. Beside the stack, there will be a list of
 constant (sometimes also called as "constants pool") to hold Boolean,
 integer, floating-point or string values. When a certain byte code needs
 a constant for the operand, an index is specified which should be used
 to look up the constant in the constants pool.</p>
 
 <p>There are only few byte code, sufficient enough to perform calculation.
 Yes, this is really minimalist but yet does the job fairly well.
 The following provides brief description for each type of bytecode.</p>
 
 <div style="margin-left: 4em">
 
 <p><i>Nop</i> means no operation.</p>
 
 <p><i>Load</i> means loads a constant and push it to the stack. The constant can
 be found at constant pools, at position by 'index', it could be a Boolean,
 integer, floating-point or string value.</p>
 
 <p><i>Ref</i> means gets a value from a reference. Member variable 'index' will
 refers to a string value in the constant pools, i.e. the name of the reference.
 Typically the reference is either a cell (e.g. A1), range of cells (A1:B10)
 or possibly function name. Example: expression A2+B2 will be compiled as:<br/>
 Constants:<br/>
 #0: "A2"<br/>
 #1: "B2"<br/>
 Codes:<br/>
 Ref #0<br/>
 Ref #1<br/>
 Add
 </p>
 
 <p><i>Function</i>.
 Example: expression "sin(x)" will be compiled as:<br/>
 Constants:<br/>
 #0: "sin"<br/>
 #1: "x"<br/>
 Codes:<br/>
 Ref #0<br/>
 Ref #1<br/>
 Function 1
 </p>
 
 <p><i>Neg</i> is a unary operator, a value is popped from stack and negated and then
 pushed back to the stack. If it is not number (Boolean or string), it
 will be converted first.</p>
 
 <p><i>Add, Sub, Mul, Div and Pow</i> are binary operators, two values are popped from
 stack and processed (added, subtracted, multiplied, divided, or power) and
 the result is pushed to the stack.</p>
 
 <p><i>Concat</i> is string operation, two values are popped from stack (and converted
 to string if they are not string values), concatenated, and the result is
 pushed to the stack.</p>
 
 <p><i>Not</i> is a logical operation, a value is popped from stack and its Boolean
 not is pushed into the stack. When it is not Boolean value, there will be
 a cast.</p>
 
 <p><i>Equal, Less, and Greater</i> are comparison operators, two values are
 popped from stack and compared appropriately. The result, which is a Boolean
 value, is pushed into the stack. To simplify, there no &quot;not equal&quot;
 comparison because it can be regarded as &quot;equal&quot; followed by
 &quot;not&quot; byte codes. Same goes for &quot;less than or equal to&quot; and
 &quot;greater than or equal to&quot;.</p>
 
 </div>
 
 <p>The expression scanner is based on finite state acceptor. The state denotes
 the position of cursor, e.g. inside a cell token, inside an identifier, etc.
 State transition is following by emitting the associated token to the
 result buffer. Rather than showing the state diagrams here, it is much more
 convenience and less complicated to browse the scanner source code and try
 to follow its algorithm from there.</p>
 
 <p>The parser is designed using one of bottom-up parsing technique, namely
 based on Polish notation. Instead of ordering the tokens in suffix Polish
 form, the parser (which is also the code generator) simply outputs
 byte codes. In its operation, the parser requires the knowledge of operator
 precedence to correctly translate unparenthesized infix expression and
 thus requires the use of a syntax stack.</p>
 
 <p>The parser algorithm is given as follows:</p>
 
 <div style="margin-left: 4em">
 Repeat the following steps:<br/>
 Step 1: Get next token<br/>
 Step 2: If it is an identifier<br/>
 - push it to syntax stack<br/>
 - generated "Ref"<br/>
 Step 3: If it is a Boolean, integer, float or string value<br/>
 - push it to syntax stack<br/>
 - generated "Load"<br/>
 Step 4: If it is an operator<br/>
 - check for reduce rules<br/>
 - when no more rules applies, push token to the syntax stack<br/>
 </div>
 
 <p>The reduce rules are:</p>
 
 <p>Rule A: <i>function argument</i>:
 if token is semicolon or right parenthesis,
 if syntax stack looks as:
 <ul type="square">
 <li>non-operator &lt;--- top</li>
 <li>operator ;</li>
 <li>non-operator</li>
 <li>operator (</li>
 <li>identifier</li>
 </ul>
 then reduce to
 <ul type="circle">
 <li>non operator</li>
 <li>operator (</li>
 <li>identifier</li>
 <li>increase number of function arguments</li>
 </ul>
 </p>
 
 <p>Rule B: last function argument<br>
 if syntax stack looks as:<br>
 <ul type="square">
 <li>operator )</li>
 <li>non-operator</li>
 <li>operator (</li>
 <li>identifier</li>
 </ul>
 then reduce to:<br>
 <ul type="circle">
 <li>non-operator</li>
 <li>generated "Function" + number of function arguments</li>
 </ul>
 </p>
 
 <p>Rule C: function without argument<br>
 if syntax stack looks as:<br>
 <ul type="square">
 <li>operator )</li>
 <li>operator (</li>
 <li>identifier</li>
 </ul>
 then reduce to:<br>
 <ul type="circle">
 <li>non-operator (dummy)</li>
 </ul>
 </p>
 
 <p>Rule D: parenthesis removal<br>
 if syntax stack looks as:<br>
 <ul type="square">
 <li>operator (</li>
 <li>non-operator</li>
 <li>operator )</li>
 </ul>
 then reduce to:<br>
 <ul type="circle">
 <li>non-operator</li>
 </ul>
 </p>
 
 <p>Rule E: binary operator<br>
 if syntax stack looks as:<br>
 <ul type="square">
 <li>non-operator</li>
 <li>binary operator</li>
 <li>non-operator</li>
 <li>and if the precedence of the binary operator in the syntax stack
 is greater or equals to the precedence of token</li>
 </ul>
 then reduce to:<br>
 <ul type="circle">
 <li>non-operator</li>
 <li>and generated appropriate byte code for the binary operator</li>
 </ul>
 </p>
 
 <p>Rule F: unary operator<br>
 if syntax stack looks as:<br>
 <ul type="square">
 <li>non-operator</li>
 <li>unary operator</li>
 <li>operator</li>
 </ul>
 then reduce to:<br>
 <ul type="circle">
 <li>operator</li>
 <li>and generated "Neg" if unary operator is '-'</li>
 </ul>
 </p>
 
 <p>Percent operator is a special case and not handled the above mentioned rule.
 When the parser finds the percent operator, it checks whether there's a non-operator
 token right before the percent. If yes, then the following code is generated:
 <tt>load 0.01</tt> followed by <tt>multiply</tt>.</p>