Recreator – Arrays and Functions

Supporting arrays and functions in the recreator is only necessary for the translator tests.  So that arrays and functions are recreated properly for these tests, preliminary recreate functions were created for arrays, defined functions and user functions.

The array and function recreate functions get the name from the string of the token.  An open parentheses is added to the name since it is not stored in the token.  The name and the attached count in the RPN item is passed to the push with operands routine.  The define function recreate function handles both define function with and without tokens, so an open parentheses is only added to the name if the attached count is not zero.  Pointers to these functions were added to the preliminary table entries for the codes of these tokens.

All the expressions in expression test #3 (parenthetical tokens) now recreate the correct output. 

[commit b6e8973352]

Translator – Arrays and Functions

A problem with recreating arrays and functions (user and define) is that the translator was not setting a code in these tokens.  Preliminary table entries were added for the codes needed.  These codes include an array, a define function with no parentheses, a define function with parentheses and a function.  There will eventually be codes for each data type, but these four codes are sufficient for now.

In the get operand routine, for the define function with and with no parentheses token types, the appropriate token code is assigned.  Since there is only a single code for each of these, the data type of the token is preserved because the table set token routine sets the data type of the token to the one in the table entry for the code.

The process parentheses token routine was modified to set the code of the token to the array code or the function code if the identifier starts with an 'F' character.  This routine also processes define functions with parentheses tokens, so the code is not set for these tokens.  Later in the routine when the RPN item is created, the attached count is no longer set to zero for array tokens.

The attached count of the RPN item can no longer be used to detect if there are attached tokens.  The attached array pointer will instead be used for this detection by checking if the pointer is set to null.  The RPN item text routine was updated to use the attached array pointer to detect attached tokens instead of the attached count.  This routine was also changed to use member variables directly instead of using the access functions.

[commit e1919952fa]

Recreator – Internal Functions

The arguments (operands) of internal functions precede the code of the internal functions, so the strings of the operands will be on the string holding stack in reverse order when the internal function token is processed.  The arguments of define and user functions work the same way as do the subscripts of arrays.

A generic push with operands routine was implemented taking the name string of the function or array and the count of operands, and contains a local string stack and a separator string initialized to a closing parentheses (the string on top of the stack will be the last operand).  Looping to the count, the string of an operand is popped from the holding stack, the separator string is appended, this string is pushed to the local stack and the separator string is set to a comma and a space for the next operand (if there is one).  The strings are popped from the local stack until empty and appended to the name.  The name is pushed to the holding stack.

The push with operands routine also works with functions with no arguments (nothing is pushed to the local stack when the count is zero, so only the name is pushed to the holding stack).  An internal function recreate function was added that gets the name and the operand count of the internal function code from the table and calls the push with operands routine.  A pointer to this function was added to all of the internal function code table entries.

While trying expression test #3 (parenthetical tokens), there were blank invalid tokens.  These occurred from the hidden conversion codes that were present in the first test expression.  A blank recreate function was added that does nothing.  A pointer to this function was added to the hidden integer and double conversion codes.  Eventually, all codes will have a recreate function.

The expected results for expression test #3 and test #4 (internal functions) were set to the correct expected results (with appropriate spacing).  All of the expressions in test #4 produce the correct output.  Some of the expressions in test #3 do not produce the correct output because they contain arrays, define functions or user functions, which are not being handled yet.

[commit ac9ab4774d]

Recreator – Operand Recreate Function

The method of using an unset (null) recreate function pointer to indicate an operand is problematic during development.  It is also possible that the recreate function for code is not yet implemented.  Further, using a blank token string to indicate an unimplemented code is also a problem since this also could mean that the code does not produce any output (take for example the hidden conversion codes).

Therefore, an operand recreate function was implemented, which simply pushes the string of the token to the string holding stack.  A pointer to this function was added to the constant and variable code table entries.  The main recreate routine was modified to surround the string of a token code with no recreate function with question marks.  A check was also needed for whether the code in the token is valid before retrieving its recreate function.

[commit 9734165b8b]

Recreator – Error Checks / Expression Mode

Some error checks were added to the recreator along with an expression test mode.  The first check is to make sure the string holding stack is empty upon returning from the main recreate routine.  Any items left on the stack are popped and appended to the output string prefixed by "NotEmpty" to indicate an error before returning.

However,  the expression test mode left the resulting string on the holding stack.  Therefore, a check was required for the expression test mode.  An expression mode flag argument was added to the recreate routine.  When set, the string on top of the holding stack is popped and appended to the output string.  This is followed by the check for an empty stack.

An error check was also added to the pop routine to make sure the holding stack is not empty.  If the stack is empty, the "<Empty>" string is returned to indicate an error.

The tester  translate input routine was modified to pass the expression mode flag to the recreate routine and to just use the output string returned (it is no longer necessary to pop from the holding stack of the recreator for expression mode).

[commit 2980b89a24]

Recreator – Unnecessary Parentheses

Parentheses in an expression control order of evaluation of the expression and are removed during the translation process.  The parentheses are recreated by looking at the precedences of the operators.  However, parentheses can be added to an expression that are not required, take the expression A+(B*C).  The multiply has higher precedence than add, so the translation becomes A B C * +, which is the same as the expression A+B*C.

So that these unnecessary parentheses are recreated, the translator adds the parentheses sub-code of tokens.  The above example expression is translated as A B C *')' +.  The translator also allows for extra sets of parentheses; the expression A+((B*C)) is translated to A B C *')' ) +.  A closing parentheses code is added when the previous token already has the parentheses sub-code.  For a third pair of parentheses, the closing parentheses token gets the parentheses sub-code.  And so on.  At run-time, parentheses codes and sub-codes are ignored.

Implementation

A new parentheses recreate function was added, which calls the pop with parentheses function with true as the argument to add parentheses when popping the top string.  The pop with parentheses was modified to optionally return the precedence value and unary operator flag from the item popped from the holding stack.  The string with parentheses along with the precedence value and unary operator flag are then pushed back to the holding stack.

In the recreate routine after processing an item in the RPN list, a check was added for the parentheses sub-code and if set, calls the parentheses recreate function.  The parentheses recreate function was also added to the table entry of the closing parentheses code.

During the testing these changes, a problem was found in the translator where the parentheses sub-code was not being added to a closing parentheses token (it incorrectly added another closing parentheses token to the output list).  This was due to translator check pending parentheses routine checking if the top item of the done stack (the last item added to the output list) to see if it already had a parentheses sub-code.  It should have been checking the last item in the output list instead (the closing parentheses tokens are not pushed to the done stack) .

A few additional expressions were added to expression test #2 (parentheses tests) for testing extra parentheses.  Both  the expected translated and recreated results were updated.  All of the expressions in test #2 are now being recreated correctly.

[commit 385cc5925d]

Recreator – Parentheses (Unary Operators)

Handling the recreation of parentheses with unary operators is similar to that of binary operators except there is only one operand with another issue.  As with binary operators, if the precedence of the unary operator is higher than the operand on top of the stack, parentheses should be added around the operand.  However, parentheses should only be added if the operand on top of the holding stack is not another unary operator.  Consider the expression and its translation:

-NOT A%            A% NOT Neg%

When the Neg% operator is being processed, its precedence is higher than the NOT on top of the stack (actually the top contains the string "NOT A%" with the precedence of the NOT operator).  With just the precedence check, parentheses would be added around the "NOT A%" expression, which is not correct.  There needs to be an additional check to not add parentheses if the top item is a unary operator expression.

Implementation

A unary operator flag variable was added to the stack item to indicate if the holding stack item is a unary operator sub-expression.  The push access function was modified to take an optional unary operator flag value that is pushed with the string and precedence.  The default flag is set to false and is only set to true by the unary operator recreate function.

The unary operator recreate function was modified to get the precedence of the operator being processed from the table.  The pop call of the operand was changed to call the new pop with parentheses with the argument set to whether the top stack item is not a unary operator and the operator precedence is higher than the precedence of the top stack item.

There were insufficient expressions in expression test #2 (parenthetical expressions) to test the various situations with unary operators, so several were added.  The translated test expected results were also updated for the new expressions.  The expressions that still do not match are due to unnecessary entered parentheses.

[commit a5951ecfc3]

Recreator – Parentheses (Binary Operators)

Parentheses are removed from expressions during translation.  The binary operator recreate function needs to recreate the parentheses for operators depending on their precedences.  Consider these expressions with their translations:

A * B + C * D          (A + B) * (C + D)
A B * C D * +          A B + C D + *

The translations of these two expressions have a similar form.  The first expression will be recreated correctly since multiply is higher precedence than add.  However the second expression without parentheses "A + B * C + D" does not mean the same thing since add is lower precedence than multiply making the parentheses required.

Parentheses are required around an operand if the precedence of the operator is higher than the operand. Parentheses are also required around the second operand if the precedence of the operator is the same as the operand since operators of the same precedence are processed from left to right.

Implementation

A precedence variable was added the stack item to hold the precedence of an operator sub-expression.  The push access function was modified to take an optional precedence value that is pushed with the string.  The default precedence is set to the highest precedence for when operands like constants and variables are pushed.  A top access function was added so that the item on top of the string holding stack can be accessed.
A new pop with parentheses access function was added that takes a flag argument, which when set will surround the string operand popped from the string holding stack with parentheses when set.

The binary operator recreate function was modified to get the precedence of the operator being processed from the table.  The pop call of the second operand was replaced with a call to the new pop with parentheses with the argument set to whether the operator precedence is higher than or the same as the precedence of the item on top of the stack.  Similarly the first operand is popped with parentheses if the operator precedence is higher than the top item.

Instead of using the top append access function, the string of the operator expression is built in a local string.  The string is first set to the second operand with parentheses if needed.  The string is then set to first operand with parentheses if needed, plus a space, plus the operator name, plus another space plus the current value of the string with the second operand.  Finally this string is pushed to the string holding stack with the precedence of the operator.

The expected outputs for expression test #2 (parenthetical expressions) were set to the inputs.  Many of these expressions match the inputs since the precedence for binary operator is now being handled.  The expressions that don't match involve unary operators (no precedence checking yet) and unnecessary entered parentheses.

[commit 694e224aee]

Recreator – Simple Expressions (Implementation)

The recreator is a separate new class since the RPN list will already have been decoded from the program model (with dictionary lookups to change indexes back into there original names), so there is no need to access neither the program model or the dictionaries.  The constructor does nothing more than set the member table instance reference.  There are only two additional member variables, the string holding stack and the output string.

The output string will contain the recreated text of a program line and will be appended to as the RPN list is processed.  Since the various recreate functions are outside of the recreator class, there is a single append access function for appending a string to the output string.

The holding stack temporarily contains strings as the RPN list is processed and is used to reverse the RPN list.  It is defined as a QStack of the StackItem structure, which contains a string.  The holding stack was not defined directly as a stack of strings because an additional item will be needed.  There are several access functions including a push function to push a string onto the stack, a pop function to pop a string from the stack, and a top append function to append a string to the top string on the stack.

Besides the class member functions, the recreator source file also contains several general recreate functions which are outside the class so that their pointer can be put into in the table entries.  These include the unary operator and binary operator recreate functions, which work as described in the previous post.

A recreate function type was added to the table entry structure with an access function.  The recreate functions arguments include a reference to the recreator instance and a pointer to the RPN item from the RPN list.  Recreate functions were added to all of the operator, constant, and variable codes.  A constant string recreate function was implemented for the constant string code that adds the necessary double quotes.

A recreator instance reference argument was added to the tester class translate input routine.  For expressions, the recreator does not return an output string (there is no command to pop the string of the final expression from the holding stack and append it to the output string.  Instead of adding a special expression mode to the recreator to do this, and since the pop access function is public (for the recreate functions), the translate input routine gets the output string using this function.

The expressions in expression test #1 (simple expressions) are properly recreated and match the inputs except expectedly for spacing and case (lower case word operators are output in upper case).  While the other expressions produce recreated output, the output is not correct because parentheses, internal functions, etc. are not yet supported.

[commit 4bdd513c2c]

Recreator – Simple Expressions

The recreator will work similar to the run-time module.  The run-time module will push operand values to a value stack to be popped by operators, functions and commands to perform some operation, which may push results back to the stack.  The recreator will push the strings of the operands to a string holding stack.  These strings will be popped by operators, functions and commands, which may push modified strings back to the stack or append the strings to the output string.  This will make more sense by considering this statement and its translation:

A + B
A B +

At the A operand, the string "A" will be pushed to the holding stack.  Same for the B operand with the "B" string being pushed.  The plus operator will pop the second operand, the "B" string, from the stack.  The string for the operator will be appended with surrounding spaces to the operand now on top of the stack, specifically the " + " string gets append to the "A" string leaving "A + " on top of the stack.  The previously popped second operand is then appended to the top of the stack leaving the "A + B" string on top of the stack, which may be an operand for the next operator.

For unary operators, the string for the operator is created.  A separator space is appended only for a word operator like NOT, otherwise no space is needed (for example the "-" unary operator).  The string of the single operand on top of the stack is popped and appended to the operator string.  The resulting string is pushed back to the stack.

For simple expressions, only support for operands (variables and constants) and operators are needed.  For string constants some processing is needed: all double quotes in the string of the constant need to be changed to two doubles quotes, and the entire string needs to be surrounded by a pair of double quotes.

The table entry for each code will have a pointer to a recreate function.  Since operands already have their string in the token of the item, this string just needs to be pushed to the string holding stack (with the exception of string constants).  Since this is trivial, a null pointer will indicate that the string of the token should be pushed to the string holding stack.  For string constants, there will be a constant string recreate function.  Since all binary operators work the same, there only needs to be a single binary operator recreate function.  Likewise for the unary operators.

The recreate process will loop through each item in the RPN list.  If there is no recreate function, the string of the token is pushed onto the string holding stack.  Otherwise the recreate function is called to process the token.  At the end of the RPN list, the resulting output string is returned.  For expression mode, nothing gets appended to the output list, so the tester class will need to pop the result string of the expression from the string holding stack.

Table – Simplified Instance Creation

The new recreator class will also require a reference to the single table instance like the other classes (parser, translator, and program model).  The initialization of the table reference members of these classes was not consistent - some required the table instance reference to be passed to the constructor and others accessed the static table instance directly to initialize their member.  The single table instance creation was also convoluted with several routines:

initialize - static table function to be called once (from main) to create the single instance and it made sure it was not called more than once or if the table entries had errors

has errors - static table function to return if the table has errors, used by the tester class to determine if the table entries had errors, outputs them and aborted the application

error list - static table function to return the list of error, used by the test class to output the table entry errors before aborting the application

setup and check - static table function called by initialize after creating the single table instance to setup and check the table entries

instance - static table function to return a reference to the single table instance, contains checks to make sure that initialize had been called and that the table entries had no errors; and for these errors would abort the application

The table constructor had an argument for the pointer to the table entry array and only set the table entry member.  Most of these routines were unnecessary and the single table instance creation was modified for these routines:

instance - static table function to return the single table instance, and will create the single table instance upon the first call

constructor - modified to take both the pointer to the table entry array and the count of table entries, now does the setup and check functionality, and if there are errors, they are reported and the application is aborted

Now if there are table entry errors, the constructor aborts the application and no other class needs to check for table errors.  This check was removed from the tester class.  Previously when starting in GUI mode, there was no check for table errors.  There is no longer a need to initialize the table in the main function or check to make sure it has been initialized.

The method the program model uses to initialize its table instance reference is the preferred method.  The instance function is used to initialize the table instance reference member.  The parser and translator classes were modified to use this method.

[commit 7a01ac428b]

Recreator – Testing

The recreator will take an RPN list as input.  Consideration was given to how the recreator will be tested.  There are already many tests for testing the translation of expressions and statements into RPN lists (the expression and translator test input files).  Since these are available, they will also be used for testing the recreator.

To avoid having to duplicate these into "recreator" test files, they will be used as is with a new "-to" command line option to activate the recreator on the translator output.  When this option is used instead of the "-t" option, the expression or translator input file will be translated as before, and then the RPN list will be passed to the recreator.

Since the recreator has not been implemented yet, to verify this code is working correctly, the same RPN text output is used, but prefixed with the "TEST:" string.  Encoder test input files are not supported, which will be added once the recreator is working with the expression and translator tests.

All of the test scripts and Windows batch file were updated to run all the expression and translator test files with the new "-to" test option.  Recreator output files have the ".out" extension to not conflict with the ".txt" extension used for the other test output files.  Recreator development will now commence.

[commit 9b52fc6d83]

Table – Has Operand Determination

During the development of the encoder before all of the routines were implemented, it was necessary to have a has operand flag in the table entries for codes that have an operand.  This is no longer necessary as the equivalent can now be determined by whether the code has an operand text or an encode function pointer.

The has operand flag was removed from the table entries of these codes.  A has operand table access function was added that returns whether the table entry of the code has an operand text function.  The tests for the has operand flag were replaced with this new function or use the  presence of the operand text or encode function pointer (by using the table access functions for these).

The program model operand text function is also no longer needed, which had special allowance for whether there was no operand text function for a code with the has operand flag.  The encode routine also had special allowance for this same condition, but this is also not necessary since all codes with operands have an encode function.

[commit 1e8b92e47c]

Program – Line Change Detection

The translated RPN lists for program lines is currently being saved in the line information list.  This was only temporary until the RPN lists could be encoded into program code and stored.  This mechanism was left in place since it is still being used for line change detection.  As described in the last post, RPN lists will still be compared to detect line changes except that the program code will be decoded into an RPN list.

However, the form of the decoded RPN list will be slightly different then a translated RPN list.  The method of RPN list comparison was to compare each RPN item, where the token, the attached token count, and if non-zero, each attached token was compared.  For the token comparison, the token type, the data type for constants, the code for commands and operators except the REM command and operator, the code for internal functions, the string for other token types, the reference flag, and the sub-code.

The tokens in a decoded RPN list will only have the code, sub-code (only program sub-codes), and a string (for all types).  Therefore, only these members of the token are compared.  For the RPN items, it is unnecessary to compare the attached tokens since these only refer to other tokens in the list, and the token comparisons are sufficient to catch differences, so only the attached token count needs to be compared.  In fact, a decoded RPN list will not have attached tokens, only the count, since these will not be necessary for recreation.

Token comparison boils down to comparing the code, sub-code masked by the program only sub-codes, and the string.  There is one other issue when comparing the strings that would cause the previous comparison to incorrect detect a change.  A non-case sensitive comparison must be used except for the REM, REM operator and string constant codes.

Where testing these changes in the GUI, a token (memory) leak was discovered, which occurred when the line did not change.  The program was due to the RPN list of the line to replace was not used in this case, but was not deleted.  This was corrected in additional to updating the RPN item and tokens comparison routines.

[commit 16c85dfe79]

Recreator – Design Considerations

Originally, there was going to be another module, the decoder, which would convert internal program code into an RPN (Reverse Polish Notation) token list (like the translator produces).  The recreator would then convert the RPN list back into the program text (close to the originally entered code).  Very early on (see December 19, 2009) this step was considered simple and unnecessary and so was combined into the recreator.

The program model needs to detect when a changed line has actually been changed.  The edit box sometimes reports changes lines when the line has not actually change.  The user could also have simply added spaces to the line (which are not stored) or changed the case of a keyword, which would not result in a change to the internal program code.  As previously mentioned, comparing the internal code of the current line with to the new line is problematic.

The new line would first have to be encoded, which will affect the dictionaries.  Either this would need to be undone, or the old line removed first to dereference dictionary entries only to have them referenced again when putting in the new line.  This is acceptable for simple dictionaries (variables, constants, remarks, etc.), but is much more involved with the blocking commands (IF-END IF, FOR-NEXT, etc.), where the block will probably be kept in a block dictionary.

A better alternative is to convert the program line into an intermediate RPN token list (decoded).  The translated RPN list of the new line and be compared to the decoded RPN list of the current line.  Since the decode operation can be contained in a single routine like the encode operation, the program model will own this decode routine also.

Since the decode routine will be present, then it makes sense for the recreator to take a decoded RPN list as input to convert to the program text.  This method has another advantage for testing.  Currently, the test code translates expressions and statements into RPN lists.  These RPN lists can then be passed to the recreator for testing, therefore there will be a new test mode for taking these existing tests, translate them to RPN lists, and then recreate them back to text.

Class Definition Consistency

In preparing to create the recreator class, I noticed that all the class definitions were not consistent - some had the private members at the beginning and some had them at the end.  Having the member functions at the beginning allow access functions for instance to use them, at least this was the case with early C++ compilers (or at least was my understanding when learning C++ over two decades ago).  But this does not appear to be a requirement with modern compilers.

It appears the Qt developers like to put the private member variables at the end of the class.  The public function definitions start at the beginning followed by the private section, which start with the private function definitions.  So, before embarking on creating of the recreate class definition, the non-conforming classes were changed to this style.

[commit 8fc5c92519]