The PRINT statement translation implementation is almost complete, but a few more issues were discovered with how parser errors and the None data type are handled. Support for the None data type was added for the print functions (TAB and SPC), but also to support being able to call the get expression routine and have it allow for no expression, just a terminating token. This is needed for PRINT statements that have commas with no expressions in between them (for instance, to skip over two columns).
The get token routine was modified to accept a new No data type value, which will now be the default value. This data type will only be used to call the get token routine when a non-operand token is requested. This was necessary since the None type is now being used for operands.
The get operand routine was modified for command and operator tokens, which are normally invalid for an operand and an "expected XX expression or variable" error is returned, now returns a Done status if the data type passed is None. This allows for no expressions to be returned and the command or operator token becomes the terminating token from the get expression routine (it is up to the PRINT translate routine to determine the validity of the token).
The get expression routine was modified to carry the None data type into the loop in the expected data type variable. This allows the None data type to be passed to the get operand routine upon the first call (to allow for print functions or no expression) so the secondary operand data type variable is no longer needed. After the first operator, the expected data type variable is set accordingly for the operator.
However, for parentheses expressions, the data type needs to be changed to Any before recursively calling the get expression routine since neither a print function nor no expression is valid inside the parentheses. Also, if a parser error is returned, the status is only set to the "expected operator or closing parentheses" error if the token does not have a data type, because a numeric parser error needs to be reported as such.
Finally, the scheme to leave an internal function of parentheses token on the hold stack when an error is detected so that the caller can check if the top of the hold stack is not the null token was flawed. Without going into details, it turned out this scheme was not necessary anyway and was removed. Quite a few more parser error tests were added to translator test #14 for testing additional error cases.
[commit 86292a56c0]
Tuesday, August 13, 2013
Sunday, August 11, 2013
Print Function Support
The PRINT statement consists of expressions separated by semicolons or commas. Commas can also be used with no expressions between them. The expressions may also contain the print functions TAB and SPC. These functions are distinguished from other functions in that they have no return data type. The PRINT translate function could specifically handle these print functions since they are only use in a PRINT statement.
However, the get expression routine also needs to be able handle these print functions in at least to report errors when they are used incorrectly in expressions. It currently does this simply by the fact that the None data type is not acceptable by any operator or data type request (an expression with a data type of None is not currently requested).
Instead of having the PRINT translate routine handle the print functions, the get expression routine was modified to accept the None data type, which affected two things. This allows print functions to be returned. It also allows no expression to be returned (just the next token as the terminating token), which is needed in the PRINT statement for commas. This will be detected by the done stack being empty. The PRINT translate routine will be the only caller with the None data type.
The new translator was changed back to only reporting the TAB( or SPC( token when used incorrectly in expressions. This was necessary due to parser and other errors inside the parentheses of the print function as the error was reported at the wrong place. Consider the expression:
[commit 9502d5b183]
However, the get expression routine also needs to be able handle these print functions in at least to report errors when they are used incorrectly in expressions. It currently does this simply by the fact that the None data type is not acceptable by any operator or data type request (an expression with a data type of None is not currently requested).
Instead of having the PRINT translate routine handle the print functions, the get expression routine was modified to accept the None data type, which affected two things. This allows print functions to be returned. It also allows no expression to be returned (just the next token as the terminating token), which is needed in the PRINT statement for commas. This will be detected by the done stack being empty. The PRINT translate routine will be the only caller with the None data type.
The new translator was changed back to only reporting the TAB( or SPC( token when used incorrectly in expressions. This was necessary due to parser and other errors inside the parentheses of the print function as the error was reported at the wrong place. Consider the expression:
A = TAB(B$)An "expected numeric expression" error was reported at the B$ token, but should point to the TAB( token as it doesn't belong in the expression in the first place. Several more statements were added to translator test #14 that included various parser errors in print functions used incorrectly. See the commit log for more details of the changes made.
[commit 9502d5b183]
Saturday, August 10, 2013
Old Translator Issues With Token Caching
While debugging the new PRINT translate routine, I realized that the old translator routines were never tested with new token caching and error reporting code, because when they were, crashes and errors occurred. Two small problems were found and were corrected.
The first issue occurred when an error is detected and the error token was not the current token obtained from the parser (meaning the error token had already been added to the output and cannot be deleted). The old translator routine obtained a new token and copied the error token into it before calling the set error token routine, which called the output list set error routine and then deleted the token. When the token was copied into the new token obtained, the index of the original token was copied over the new token's index confusing the used token handling. This was corrected by calling the output list set error routine directly (which only grabs the column and length of the error token) so no temporary token is needed.
The second issue occurred when there was a REMARK operator (') at the beginning of a line. The Null token put on the bottom of the hold stack was not removed. This was detected as a token leak and the detection code reported and deleted the token. Unfortunately, the translator still had the token on the hold stack. This did not cause a problem until the next command with an error was processed. When an error occurs, the the hold stack is empty and its tokens are deleted. When it got to the deleted Null token, the index was garbage (because the memory for the token had been reused) and a segmentation fault occurred.
The REMARK operator token handler was modified to pop and delete the Null token from the hold stack if currently in command mode. If not in command mode, then another part of the translator correctly handled the the Null token. Curiously for this situation, the EOL token at the end of the line is never obtained and processed. Therefore, this fix is a hack, but since the old translator routines will be abandoned, there is no reason for a correct fix.
One last minor issue was that when token leaks or extra deletes were reported, if the token was a Null or End-of-line token, a blank token was output with just an index. The "NULL" and "EOL" strings were added to the debug name entry in the table to identify these blank tokens.
[commit cf93288fcb]
The first issue occurred when an error is detected and the error token was not the current token obtained from the parser (meaning the error token had already been added to the output and cannot be deleted). The old translator routine obtained a new token and copied the error token into it before calling the set error token routine, which called the output list set error routine and then deleted the token. When the token was copied into the new token obtained, the index of the original token was copied over the new token's index confusing the used token handling. This was corrected by calling the output list set error routine directly (which only grabs the column and length of the error token) so no temporary token is needed.
The second issue occurred when there was a REMARK operator (') at the beginning of a line. The Null token put on the bottom of the hold stack was not removed. This was detected as a token leak and the detection code reported and deleted the token. Unfortunately, the translator still had the token on the hold stack. This did not cause a problem until the next command with an error was processed. When an error occurs, the the hold stack is empty and its tokens are deleted. When it got to the deleted Null token, the index was garbage (because the memory for the token had been reused) and a segmentation fault occurred.
The REMARK operator token handler was modified to pop and delete the Null token from the hold stack if currently in command mode. If not in command mode, then another part of the translator correctly handled the the Null token. Curiously for this situation, the EOL token at the end of the line is never obtained and processed. Therefore, this fix is a hack, but since the old translator routines will be abandoned, there is no reason for a correct fix.
One last minor issue was that when token leaks or extra deletes were reported, if the token was a Null or End-of-line token, a blank token was output with just an index. The "NULL" and "EOL" strings were added to the debug name entry in the table to identify these blank tokens.
[commit cf93288fcb]
Thursday, August 8, 2013
New PRINT Implementation (Revised)
Once implementation of the new PRINT translation was started, I realized that the design at run-time was more complicated than it needed to be. Most of the original design appeared to be best after all, with a few minor changes. When it comes to run-time, the original design would be more efficient and would not need the extra complexity of a command stack. With print codes immediately after each print item, the print code would simply pop the value from the evaluation stack and print it.
The changes to the original design are how semicolons and the final PRINT command code are handled. Semicolon sub-codes were added to print functions codes except when they appeared at end of a statement. Multiple semicolons were allowed, marked with semicolon sub-codes or extra semicolon tokens with more than one extra semicolons. A PRINT command code would only be added to the end of the statement if there was no print token (semicolon, comma, TAB or SPC) at the end.
Semicolon sub-codes will no longer be needed. Semicolons will be assumed between each print item unless there is a comma between them. Multiple unnecessary semicolons will no long be permitted as these add nothing. If there is a semicolon at the end of the line, then a semicolon code will be added to the end of the line instead of a PRINT code. At run-time, the semicolon will no nothing, but when the line is recreated, the semicolon will produce the PRINT keyword in additional to the semicolon at the end of the line.
The changes to the original design are how semicolons and the final PRINT command code are handled. Semicolon sub-codes were added to print functions codes except when they appeared at end of a statement. Multiple semicolons were allowed, marked with semicolon sub-codes or extra semicolon tokens with more than one extra semicolons. A PRINT command code would only be added to the end of the statement if there was no print token (semicolon, comma, TAB or SPC) at the end.
Semicolon sub-codes will no longer be needed. Semicolons will be assumed between each print item unless there is a comma between them. Multiple unnecessary semicolons will no long be permitted as these add nothing. If there is a semicolon at the end of the line, then a semicolon code will be added to the end of the line instead of a PRINT code. At run-time, the semicolon will no nothing, but when the line is recreated, the semicolon will produce the PRINT keyword in additional to the semicolon at the end of the line.
Wednesday, August 7, 2013
New PRINT At Run-Time (Retracted)
After considering this design, it was decided to be more
complicated than it needed to be, so this post has been retracted, see
revised post.
Consider the previous example statement and its new translation:
When the PRINT (or semicolon) code is executed, it will process the command stack, except it will start at the bottom of the stack instead of popping items from the top. This is possible because the QStack class is derived from the QVector class, which allows its elements to be access by index. The values of the evaluation stack will also be accessed the same way.
When the PRINT (or semicolon) begins, it will start with indexes (one for each stack) set to zero and will process each item on the command stack. For the specific print type code, it will access the value at the evaluation stack index, output it, and increment the index. For a comma code, it will output the appropriate number of spaces (leaving the evaluation stack index as is). For a print function (TAB or SPC), it will access the value at the evaluation stack index, output the appropriate number of spaces, and increment the index.
At the end (top) of the command stack, it will clear both stacks, return the indexes to zero (for the next command), and for the PRINT code only, will advance to the next line. This scheme works because both the evaluation and command stacks will be empty at the beginning of each command.
Consider the previous example statement and its new translation:
PRINT A,B$;TAB(20);C%At run-time, in additional to the evaluation stack used to hold values of operands and results, there will also be a command stack (not to be confused with the current command stack used by the old translator routines, but not needed by the new translator routines). The special print codes (specific print type codes, comma, and print functions), will only push themselves to the command stack.
A B$ 20 C% PrintDbl , PrintStr TAB( PrintInt PRINT
When the PRINT (or semicolon) code is executed, it will process the command stack, except it will start at the bottom of the stack instead of popping items from the top. This is possible because the QStack class is derived from the QVector class, which allows its elements to be access by index. The values of the evaluation stack will also be accessed the same way.
When the PRINT (or semicolon) begins, it will start with indexes (one for each stack) set to zero and will process each item on the command stack. For the specific print type code, it will access the value at the evaluation stack index, output it, and increment the index. For a comma code, it will output the appropriate number of spaces (leaving the evaluation stack index as is). For a print function (TAB or SPC), it will access the value at the evaluation stack index, output the appropriate number of spaces, and increment the index.
At the end (top) of the command stack, it will clear both stacks, return the indexes to zero (for the next command), and for the PRINT code only, will advance to the next line. This scheme works because both the evaluation and command stacks will be empty at the beginning of each command.
New PRINT Implementation (Retracted)
After considering this design, it was decided to be more complicated than it needed to be, so this post has been retracted, see revised post.
The run-time design of the PRINT statement was reconsidered. The old scheme inserted specific type print codes into the translation with an optional PRINT code at the end depending if the line ended with a semicolon, comma or print function (TAB or SPC). Consider this example statement and its old translation:
A semicolon at the end of the line needs special consideration. If there is a semicolon at the end of the line, it will take the place of the PRINT code. At run-time, both perform the same actions except only PRINT advances to the next line. A semicolon can be used this way since no other statement needs a semicolon token. A 'Keep' sub-code or a new PrintKeep code could have been used, but why have a sub-code check at run-time or create a new code when a semicolon token can be used.
The next post will contain the details of how this new PRINT translation will work at run-time...
The run-time design of the PRINT statement was reconsidered. The old scheme inserted specific type print codes into the translation with an optional PRINT code at the end depending if the line ended with a semicolon, comma or print function (TAB or SPC). Consider this example statement and its old translation:
PRINT A,B$;TAB(20);C%The specific type print codes pop a value from the evaluation stack and outputs it. The comma token outputs spaces to advance the cursor to the next column (traditionally groups of 8 characters). The TAB print function outputs spaces to advance to specified column. And the final PRINT advances to the next line. If the line ended with a semicolon, comma or print function, the final PRINT code is not present. The new translation will look like this (details to follow):
A PrintDbl , B$ PrintStr 20 TAB(';' C% PrintInt PRINT
A B$ 20 C% PrintDbl , PrintStr TAB( PrintInt PRINTThe final PRINT code is always present, and at run time will know when to advance to the next line (depends on the code immediately preceding it). Semicolon tokens (or a sub-code) is not necessary and is implied between the items to print. Multiple semicolons, though allowed in the old translator (the semicolon sub-code and any semicolon tokens would do nothing at run-time), will not be permitted as there is no reason to allow them (unlike multiple commas).
A semicolon at the end of the line needs special consideration. If there is a semicolon at the end of the line, it will take the place of the PRINT code. At run-time, both perform the same actions except only PRINT advances to the next line. A semicolon can be used this way since no other statement needs a semicolon token. A 'Keep' sub-code or a new PrintKeep code could have been used, but why have a sub-code check at run-time or create a new code when a semicolon token can be used.
The next post will contain the details of how this new PRINT translation will work at run-time...
Tuesday, August 6, 2013
Extra Token Delete Detection
The other type of token allocation error that can occur is when a token that has already been deleted is deleted again. This is a less common problem, but can still could occur none the less. Extra token delete detection was also previously implemented, but removed. The original implementation contained a list of tokens deleted extra times. A copy of the token was appended to the list.
This time around, the text of the token (by using the text access function) along with its index (as part of the string) is saved in a list of strings of deleted tokens. When it comes to to report these errors, each string in the list is output. In the reimplemented delete operation function, before the token is marked a unused in the used token vector (its pointer set to null), if the token is already marked as unused, its index and text is appended to the deleted list instead and the token is not pushed onto the free token stack (it is already there).
A new private DeletedList class was implemented inside the Token class. The destructor is called automatically upon termination of the application and any extra token deletes are reported. This class also contains a report errors function that does the work of outputting the deleted list to the standard error output stream and clears the list afterward. The destructor calls this function.
Again, a separate function was implemented so that it can be called at the end of each line translated in test mode and extra token deletes for that specific line are reported with the line. For non-test (GUI) mode, any extra token deletes are reported when the application terminates.
This time around, the text of the token (by using the text access function) along with its index (as part of the string) is saved in a list of strings of deleted tokens. When it comes to to report these errors, each string in the list is output. In the reimplemented delete operation function, before the token is marked a unused in the used token vector (its pointer set to null), if the token is already marked as unused, its index and text is appended to the deleted list instead and the token is not pushed onto the free token stack (it is already there).
A new private DeletedList class was implemented inside the Token class. The destructor is called automatically upon termination of the application and any extra token deletes are reported. This class also contains a report errors function that does the work of outputting the deleted list to the standard error output stream and clears the list afterward. The destructor calls this function.
Again, a separate function was implemented so that it can be called at the end of each line translated in test mode and extra token deletes for that specific line are reported with the line. For non-test (GUI) mode, any extra token deletes are reported when the application terminates.
Token (Memory) Leak Detection
While implementing the token caching, I thought it would be extremely helpful to put back some token leak detection, a common time consuming problem seen during debugging of the new translator routines. Leak detection was previously implemented, but removed during the Qt transition. According to the post on October 28, 2012, this was due to obscure compiler errors. Since valgrind was being used for memory leak detection by then, this code was removed. The log for this commit did not provide any additional clues to the issues other than to say Qt does not interface well to self implemented new and delete operators (?).
The original token leak detection consisted of a static list of used tokens and each token contained a pointer into this list. This was easy to implemented with how the original List class was designed, but the QList class had no easy equivalent (using an iterator did not work). I suspect this partly caused the problem, which may also have had something to do with the way members are initialized by the constructor when a new instance is created and having a Qt member complicated things. Anyway, a new easier method of keep track of used tokens was implemented this time around that did not cause any problems.
A plain integer index member was added to the Token class. Every token allocated gets a unique index number, which the token will have through the life of the application. The index values assigned start at zero and each additional token allocated gets the next index value. This index is used to index into a QVector of token pointers.
When a new token is allocated, the index is set to the size of this used token vector, and then the token is appended to the vector. In other words, the index points to its corresponding element in this vector. When a token pointer is popped from the free token stack, the element corresponding to the token is set to the token pointer. When a token is deleted, the element corresponding to the token is set to a null pointer to indicate the token is not currently used (it is in the free token stack).
A token pointer was used for this vector instead of a simple boolean flag (for indicating a token was used), so that when it came time to see if there are any tokens used that have not been freed (the element in the vector contains a non-null token pointer), the token pointer can be used to print information about the token (type, code, string, etc.).
A new private UsedVector class was implemented inside the Token class, similar to the FreeStack private class. The destructor is called automatically upon termination of the application and any token leaks are reported and the tokens deleted so that valgrind does not also report memory leaks. This class also contains a report errors function that does the work of scanning the vector and reporting any token leak errors found to the standard error output stream and deletes the tokens. The destructor calls this function.
A separate function was implemented so that it can be called at the end of each line translated in test mode and token leaks for that specific line are reported with the line. This does not interfere with the test scripts since the errors are output to the standard error stream, which is not captured in the output that gets compared with the expected results files. Once a test is seen to contain errors, it can be rerun from the command line to the standard output to see which test statements caused the errors. Having the errors output with the test lines saves debugging time in having to identify which test statement caused the error.
For non-test (GUI) mode, any token leaks are reported when the application terminates, though if not run from the command line, these errors will not be seen. This should not be an issue because any token leaks should have been eliminated by this time.
The original token leak detection consisted of a static list of used tokens and each token contained a pointer into this list. This was easy to implemented with how the original List class was designed, but the QList class had no easy equivalent (using an iterator did not work). I suspect this partly caused the problem, which may also have had something to do with the way members are initialized by the constructor when a new instance is created and having a Qt member complicated things. Anyway, a new easier method of keep track of used tokens was implemented this time around that did not cause any problems.
A plain integer index member was added to the Token class. Every token allocated gets a unique index number, which the token will have through the life of the application. The index values assigned start at zero and each additional token allocated gets the next index value. This index is used to index into a QVector of token pointers.
When a new token is allocated, the index is set to the size of this used token vector, and then the token is appended to the vector. In other words, the index points to its corresponding element in this vector. When a token pointer is popped from the free token stack, the element corresponding to the token is set to the token pointer. When a token is deleted, the element corresponding to the token is set to a null pointer to indicate the token is not currently used (it is in the free token stack).
A token pointer was used for this vector instead of a simple boolean flag (for indicating a token was used), so that when it came time to see if there are any tokens used that have not been freed (the element in the vector contains a non-null token pointer), the token pointer can be used to print information about the token (type, code, string, etc.).
A new private UsedVector class was implemented inside the Token class, similar to the FreeStack private class. The destructor is called automatically upon termination of the application and any token leaks are reported and the tokens deleted so that valgrind does not also report memory leaks. This class also contains a report errors function that does the work of scanning the vector and reporting any token leak errors found to the standard error output stream and deletes the tokens. The destructor calls this function.
A separate function was implemented so that it can be called at the end of each line translated in test mode and token leaks for that specific line are reported with the line. This does not interfere with the test scripts since the errors are output to the standard error stream, which is not captured in the output that gets compared with the expected results files. Once a test is seen to contain errors, it can be rerun from the command line to the standard output to see which test statements caused the errors. Having the errors output with the test lines saves debugging time in having to identify which test statement caused the error.
For non-test (GUI) mode, any token leaks are reported when the application terminates, though if not run from the command line, these errors will not be seen. This should not be an issue because any token leaks should have been eliminated by this time.
Monday, August 5, 2013
Token Caching (With Error Checking)
The PRINT translation will involve many token deletes for unneeded tokens (like semicolons) but also many new tokens (to hold the specific data type print codes). More on the redesign PRINT translation in an upcoming post, but it is desirable to reuse tokens as much as possible instead of repeatedly using the free memory heap, which can get fragmented with many allocations and deletions requiring time consuming garbage collection. Other commands (like INPUT) will also require this reuse capability.
Instead of some type of token saving code in each command translation routine as needed, a global method of caching tokens was implemented. This was accomplished by reimplementing the new and delete operators of the Token class. For the delete operator, instead of simply freeing the memory of the token, the pointer to the token is saved on a free token stack. For the new operator, if the free token stack is not empty, a pointer to a token is popped from this stack, otherwise a new token is allocated using the global new operator.
The free token stack was implemented as a private class based on the QStack class containing a reimplemented destructor function, which deletes all the tokens on the free stack. The destructor is called when the free stack goes out of scope, which occurs when the application terminates.
During the implementation and debugging of LET statements, one area that was time consuming was tracking down memory leak errors, mostly related to tokens. (Other leaks were easy to identify and correct.) First the test statement causing the problem had to be identified (time consuming), then the debugger had to be run to identify what was in the token that was not deleted so that the problem could be corrected (also time consuming). Missed through all of this was the token leak detection that was removed a while ago due to issues with the Qt libraries during the Qt transition.
A new token leak detection scheme was implemented along with detection of tokens that are deleted more than once. More details of these schemes in following posts. Any token leaks and extra token deletes are reported after each translator test line is translated. This will save the time to identify which statement caused errors. The text of the token is output for each error along with its index (will be detailed in the next post). Any token errors are also reported at application termination for non-test mode.
[commit 5fa1780cda]
Instead of some type of token saving code in each command translation routine as needed, a global method of caching tokens was implemented. This was accomplished by reimplementing the new and delete operators of the Token class. For the delete operator, instead of simply freeing the memory of the token, the pointer to the token is saved on a free token stack. For the new operator, if the free token stack is not empty, a pointer to a token is popped from this stack, otherwise a new token is allocated using the global new operator.
The free token stack was implemented as a private class based on the QStack class containing a reimplemented destructor function, which deletes all the tokens on the free stack. The destructor is called when the free stack goes out of scope, which occurs when the application terminates.
During the implementation and debugging of LET statements, one area that was time consuming was tracking down memory leak errors, mostly related to tokens. (Other leaks were easy to identify and correct.) First the test statement causing the problem had to be identified (time consuming), then the debugger had to be run to identify what was in the token that was not deleted so that the problem could be corrected (also time consuming). Missed through all of this was the token leak detection that was removed a while ago due to issues with the Qt libraries during the Qt transition.
A new token leak detection scheme was implemented along with detection of tokens that are deleted more than once. More details of these schemes in following posts. Any token leaks and extra token deletes are reported after each translator test line is translated. This will save the time to identify which statement caused errors. The text of the token is output for each error along with its index (will be detailed in the next post). Any token errors are also reported at application termination for non-test mode.
[commit 5fa1780cda]
Thursday, August 1, 2013
New Translator – LET Statements (Tagged)
The implementation of LET statements including multiple assignments and sub-string assignments in the new translator is now complete and version v0.4.2 has been tagged. All tests pass with the old translator routines (after some corrections were made). All expressions tests and all assignment statements in the translator tests pass in the new translator routines. Some minor cleanup was preformed with the latest commit along with updating the files for v0.4.2 (see the commit log for details). Implementation of PRINT statements can now commence in the new translator.
[commit a5d3434fbe]
[commit a5d3434fbe]
Wednesday, July 31, 2013
Memory Testing / Minor Memory Leak
Since all of the tests are now working with the new translator (excluding the commands not yet implemented), it seemed appropriate to change the memtestn script to run all of the tests. After changing this script, two memory leaks were discovered in translator tests #7 (Errors) and #9 (Semicolon Errors). The memory leak determined to be occurring with sub-string assignment statements that contained an error.
The memory leak occurred because an RPN item was allocated for the sub-string assignment token, which is not appended immediately to the RPN output list. The RPN item is left on the done stack, which the LET translate routine pops and pushes it's token to the LET stack and then deletes the RPN item. However, if the next token that should be a comma or equal token is not or a parser error occurred, then this does not occur. The error clean up code assumes that all RPN items on the done stack have been added to the RPN output list, so only the items in the output list are deleted.
This problem was corrected by slightly rearranging the code in the LET translate routine where if there is an error with the comma or equal token, and the top of the done stack contains a sub-string assignment token (that has not been added to the RPN output list), then the done item on top of the done stack is popped and deleted, which deletes the RPN item and its token(s). With this change, all of the tests with the new translator have no memory errors.
[commit 229af22a78]
The memory leak occurred because an RPN item was allocated for the sub-string assignment token, which is not appended immediately to the RPN output list. The RPN item is left on the done stack, which the LET translate routine pops and pushes it's token to the LET stack and then deletes the RPN item. However, if the next token that should be a comma or equal token is not or a parser error occurred, then this does not occur. The error clean up code assumes that all RPN items on the done stack have been added to the RPN output list, so only the items in the output list are deleted.
This problem was corrected by slightly rearranging the code in the LET translate routine where if there is an error with the comma or equal token, and the top of the done stack contains a sub-string assignment token (that has not been added to the RPN output list), then the done item on top of the done stack is popped and deleted, which deletes the RPN item and its token(s). With this change, all of the tests with the new translator have no memory errors.
[commit 229af22a78]
Parser And Unary Operator Errors
While looking at the results of all the translator tests to make sure at least the assignment tests were working (the PRINT, INPUT, REM statements currently report "not yet implemented" errors), it was noticed that many of the parser errors in translator test #14 (Parser Errors) were not reporting some errors correctly.
While working on this issue, another problem was found with unary operators when they occur when a binary operator was expected. The error should include the word "binary" in front of word "operator" to indicate that the unary operator was not expected, but a binary operator was expected. This is to avoid the confusion that a unary operator is an operator.
See the commit log for details of the changes, but basically the get expression routine needs to return a parser error and the caller needs to determine the appropriate error. The caller also needs to check if the token causing the error is a unary operator and use the appropriate error with the additional "binary" word. The get token routine was modified to which errors are reporting by also checking the expected data type, specifically if the current data type is string, then a number parser error should not be returned.
Previously, the only error with the word "binary" was the "expected binary operator or end-of-statement" error, which is not appropriate for a number of cases like when a comma or closing parentheses is expected, not an end-of-statement (for instance, inside parentheses of a parenthetical expression, an internal function or a parentheses token). Therefore, several new errors were added.
Because of the unary operator issues, a number of new test statements with unary operator errors was added to translator test #14. Many of these don't pass with the old translator routines. All of these pass with the new translator routines (excluding those with commands not yet implemented).
[commit 87e4072ba7]
While working on this issue, another problem was found with unary operators when they occur when a binary operator was expected. The error should include the word "binary" in front of word "operator" to indicate that the unary operator was not expected, but a binary operator was expected. This is to avoid the confusion that a unary operator is an operator.
See the commit log for details of the changes, but basically the get expression routine needs to return a parser error and the caller needs to determine the appropriate error. The caller also needs to check if the token causing the error is a unary operator and use the appropriate error with the additional "binary" word. The get token routine was modified to which errors are reporting by also checking the expected data type, specifically if the current data type is string, then a number parser error should not be returned.
Previously, the only error with the word "binary" was the "expected binary operator or end-of-statement" error, which is not appropriate for a number of cases like when a comma or closing parentheses is expected, not an end-of-statement (for instance, inside parentheses of a parenthetical expression, an internal function or a parentheses token). Therefore, several new errors were added.
Because of the unary operator issues, a number of new test statements with unary operator errors was added to translator test #14. Many of these don't pass with the old translator routines. All of these pass with the new translator routines (excluding those with commands not yet implemented).
[commit 87e4072ba7]
Sunday, July 28, 2013
New Translator – Data Type Checking
Up until now, the data type passed to the new get expression and get operand routines was only used to the return the appropriate error when a problem was detected. The intention was that this data type be used to check that the resulting expression before returning to the caller of the get expression routine. This simplifies the design in that the callers don't have to check if the expression is the correct type - the checking is done in one place. Also part of this, any hidden conversion codes are added (to convert from integer to double or double to integer).
The get operand routine cannot check the data type of the operand obtained against the data type passed. Consider the valid expression A%+(B$=C$). After the open parentheses, the expected data type for the second operand of the add operator would be a number. An error can't be reported against the B$ operand. This checking will be handled when the operator is processed. However, when the caller of the get operand routine requests a reference, the data type of the reference operand can be checked.
These routines were modified to check the data type. The get expression required a new level argument, which is incremented for each level of parentheses recursively calls the get expression routine. A simple flag could have been used instead of a level value, but having an actual level value could be useful for debugging. Only at the end of the expression at the first level can the data type be checked. For the Any data type, no checking is done, and for the Number data type, the data type can either be Double or Integer (no conversion code is added). Otherwise, hidden conversion codes are added to the RPN output list as needed or an error is reported.
Callers of these routines no longer need to check the resulting expression or reference operand. Previously for internal functions and tokens with parentheses, the find code routine was called for each argument (internal function at each comma) and the process final operand routine was called for the final argument or sub-script (at the closing parentheses). These routines no long need to be called (but are still used for processing operators).
All of the translator tests that only contain assignment statements (though three have a single PRINT statement) still pass successfully. One statement in test #8 contained an array assignment with a string sub-script. The old translator did not catch this error (capability was not implemented). The new translator without these latest data type checking also did not even though a numeric expression was requested, the data type was not actually checked. The expected results for test #8 were updated for this (and the old results saved). For more details of all the changes needed, see the commit log.
[commit b4a908b60d]
The get operand routine cannot check the data type of the operand obtained against the data type passed. Consider the valid expression A%+(B$=C$). After the open parentheses, the expected data type for the second operand of the add operator would be a number. An error can't be reported against the B$ operand. This checking will be handled when the operator is processed. However, when the caller of the get operand routine requests a reference, the data type of the reference operand can be checked.
These routines were modified to check the data type. The get expression required a new level argument, which is incremented for each level of parentheses recursively calls the get expression routine. A simple flag could have been used instead of a level value, but having an actual level value could be useful for debugging. Only at the end of the expression at the first level can the data type be checked. For the Any data type, no checking is done, and for the Number data type, the data type can either be Double or Integer (no conversion code is added). Otherwise, hidden conversion codes are added to the RPN output list as needed or an error is reported.
Callers of these routines no longer need to check the resulting expression or reference operand. Previously for internal functions and tokens with parentheses, the find code routine was called for each argument (internal function at each comma) and the process final operand routine was called for the final argument or sub-script (at the closing parentheses). These routines no long need to be called (but are still used for processing operators).
All of the translator tests that only contain assignment statements (though three have a single PRINT statement) still pass successfully. One statement in test #8 contained an array assignment with a string sub-script. The old translator did not catch this error (capability was not implemented). The new translator without these latest data type checking also did not even though a numeric expression was requested, the data type was not actually checked. The expected results for test #8 were updated for this (and the old results saved). For more details of all the changes needed, see the commit log.
[commit b4a908b60d]
Saturday, July 27, 2013
New Translator – Assignment Error Reporting
The remaining issues with translator tests #7 (Errors), #8 (More Errors), and #9 (Semicolon Errors) were related to incorrect errors being reported for a number of the test statements. The new get operand routine was not taking into account which type of reference was being asked for to determine the appropriate error to return. This was only a problem for the string type where different errors were needed depending if the reference type being requested was a Variable ("expected string variable" error) or All ("expected string item for assignment" error signifying that sub-string assignments are allowed).
There were translator functions for returning the expected expression error and the expected variable error from a given data type. Instead of adding a third function for the All reference type, the three were combined into the expectedErrStatus() function, which was given the reference argument in addition to the existing data type argument defaulting to the None reference type.
In the get operand function, the new expectedErrStatus() function with both arguments was used for parser errors, command and operand token types, functions with no parentheses tokens, and functions with parentheses tokens that are not sub-string functions. The new function was also used in the LET translate routine when a reference with a wrong data type is returned using the All reference type.
Finally for define functions with parentheses, the get operand routine should have reported an "expected equal or comma" error pointing to just the open parentheses when a reference was requested since define functions with no parentheses tokens are valid in assignments.
All the tests containing only assignment statements (tests #1 to #5, #7 to #11, and #13) now pass with the new translator routines except for tests #5, #11 and #13 that each contain a lone PRINT statement that is reporting a not yet implemented error.
[commit bbe3b01e37]
There were translator functions for returning the expected expression error and the expected variable error from a given data type. Instead of adding a third function for the All reference type, the three were combined into the expectedErrStatus() function, which was given the reference argument in addition to the existing data type argument defaulting to the None reference type.
In the get operand function, the new expectedErrStatus() function with both arguments was used for parser errors, command and operand token types, functions with no parentheses tokens, and functions with parentheses tokens that are not sub-string functions. The new function was also used in the LET translate routine when a reference with a wrong data type is returned using the All reference type.
Finally for define functions with parentheses, the get operand routine should have reported an "expected equal or comma" error pointing to just the open parentheses when a reference was requested since define functions with no parentheses tokens are valid in assignments.
All the tests containing only assignment statements (tests #1 to #5, #7 to #11, and #13) now pass with the new translator routines except for tests #5, #11 and #13 that each contain a lone PRINT statement that is reporting a not yet implemented error.
[commit bbe3b01e37]
New Translator – Operator Processing
One of the remaining major issues are how operators were being processed in the new process operator routine. This routine pops tokens from the hold stack and processes them (processes their final operands and adds them to the RPN output list) if the token on top of the hold stack is of higher or the same precedence as the incoming token. However, incoming unary operators do not force tokens off of the hold stack regardless of precedence (since they only have one operand, they get pushed right to the hold stack).
The issue was that the incoming token can be any token type including operands, commands, functions, non-unary or binary operators (like comma or colon). These token types would have a low precedence, indicate the end of the expression, and will force all unary or binary operators off of the hold stack. These tokens types are considered terminating tokens and it is up to the caller to determine their validity.
The problem was that the token on the hold stack is not necessarily a unary or binary operator in the case of an open parentheses, internal functions, define functions or identifiers with parentheses, which are also pushed onto the hold stack. If the incoming token was also one of these tokens (or other tokens with the same precedence like identifiers with no parentheses), it would incorrectly force the token off of the hold stack (causing a malfunction).
This problem was corrected by only forcing unary and binary operators from the hold stack to be processed. A new isUnaryOrBinaryOperator() table access function was added that supports all token types and only returns true if the token type is an operator and the operator has operands (operators with zero operands like a comma do not count). The new process operator routine was optimized a bit by setting the incoming token precedence once before entering the precedence check loop, and a pointer to the top token is obtained once at the beginning of the loop. The end of the routine was also modified, also using the new table access function to determine if the incoming token's first operand should be processed (only unary and binary operators), otherwise the incoming token is a terminator and the done status is returned.
The expected results for translator tests #7 and #11 were updated to fix an incorrect error message (#7 only) and for sub-string assignment translation changes (the old result files were saved). With this change, there are still some issues with translator tests #7 (Errors), #8 (More Errors), and #9 (Semicolon Errors). Also any tests with PRINT statements report not yet implemented errors.
An unrelated change was made to the data type enumeration where the numberof value was removed as a separate value and is now set to None data type. The numberof value is used for the number of real data types that don't include the None, Number and Any data types. It is not necessary for numberof to be separate a value and was requiring dummy values to be put into the various arrays sub-scripted by the data type.
[commit 016c120804] [commit c6012c5600]
The issue was that the incoming token can be any token type including operands, commands, functions, non-unary or binary operators (like comma or colon). These token types would have a low precedence, indicate the end of the expression, and will force all unary or binary operators off of the hold stack. These tokens types are considered terminating tokens and it is up to the caller to determine their validity.
The problem was that the token on the hold stack is not necessarily a unary or binary operator in the case of an open parentheses, internal functions, define functions or identifiers with parentheses, which are also pushed onto the hold stack. If the incoming token was also one of these tokens (or other tokens with the same precedence like identifiers with no parentheses), it would incorrectly force the token off of the hold stack (causing a malfunction).
This problem was corrected by only forcing unary and binary operators from the hold stack to be processed. A new isUnaryOrBinaryOperator() table access function was added that supports all token types and only returns true if the token type is an operator and the operator has operands (operators with zero operands like a comma do not count). The new process operator routine was optimized a bit by setting the incoming token precedence once before entering the precedence check loop, and a pointer to the top token is obtained once at the beginning of the loop. The end of the routine was also modified, also using the new table access function to determine if the incoming token's first operand should be processed (only unary and binary operators), otherwise the incoming token is a terminator and the done status is returned.
The expected results for translator tests #7 and #11 were updated to fix an incorrect error message (#7 only) and for sub-string assignment translation changes (the old result files were saved). With this change, there are still some issues with translator tests #7 (Errors), #8 (More Errors), and #9 (Semicolon Errors). Also any tests with PRINT statements report not yet implemented errors.
An unrelated change was made to the data type enumeration where the numberof value was removed as a separate value and is now set to None data type. The numberof value is used for the number of real data types that don't include the None, Number and Any data types. It is not necessary for numberof to be separate a value and was requiring dummy values to be put into the various arrays sub-scripted by the data type.
[commit 016c120804] [commit c6012c5600]
Friday, July 26, 2013
New Translator – Remaining Issues
There are at least two major issues remaining in the new translator routines that are impacting the failures in the other LET tests, though test #10 (Expression Errors) passes. The first issue is how operators are detected, specifically that some tokens that are considered operators, but are not expression operators (for example, open and closing parentheses, commas, semicolons, colons, the remark operator and end-of-line tokens).
The second issue is part of the design of the new translator has not yet been realized, namely that when getting an expression, if given a particular data type, it should check that the expression is of that type, or can be converted to that type via a hidden conversion code, else return an error. Currently the data type is only being used for reporting errors with operands. Correcting and implementing these issues has been a major undertaking, so a bunch of preliminary changes were made leading up to these changes.
Previously, all tokens with a command or operator type were considered operators. This was necessary for the token-centric old translator, because some commands like THEN and ELSE needed to be considered operators since they can come at the end of expressions. The first change made was to remove the Token::isOperator() access function along with the static Token::s_op[] array used by the access function. Uses of the access function were replaced with the Token::isType() access function. Not all uses required checking for both operator and command token types. [commit ffd1ba6462]
Since the number of old translator expected results files are growing (because of corrections and changes to translations), the regtest script was modified to look for an old expected results file (ending with an 'o') and comparing to that file if found instead. An old expected results file for translator test #3 was also added (print functions used in expressions do not report through the closing parentheses. [commit 7aef54c63e]
The fact that the open parentheses operator token was configured as a unary operator in the table was going to cause issues with the new translator routines. Therefore, it is now not configured as a unary operand and the old translator routine was modified to look for an open parentheses token before checking if the operator was unary (the check was simply moved from after to before). [commit e75adeddcb]
The segmentation fault on expression test #3 was becoming a nuisance, and was only caused by the additional of more error tests for the new translator. Therefore, the problems with old translator routines were corrected, including considering the initial state as an operand state, allowing for an empty command stack in the case of expression mode, and assuming the Any type at the beginning of an expression before any operands or unary operators are received. The memtest script was also updated to allow for comparing old translator expected results files. [commit f0f6cb57f7]
The second issue is part of the design of the new translator has not yet been realized, namely that when getting an expression, if given a particular data type, it should check that the expression is of that type, or can be converted to that type via a hidden conversion code, else return an error. Currently the data type is only being used for reporting errors with operands. Correcting and implementing these issues has been a major undertaking, so a bunch of preliminary changes were made leading up to these changes.
Previously, all tokens with a command or operator type were considered operators. This was necessary for the token-centric old translator, because some commands like THEN and ELSE needed to be considered operators since they can come at the end of expressions. The first change made was to remove the Token::isOperator() access function along with the static Token::s_op[] array used by the access function. Uses of the access function were replaced with the Token::isType() access function. Not all uses required checking for both operator and command token types. [commit ffd1ba6462]
Since the number of old translator expected results files are growing (because of corrections and changes to translations), the regtest script was modified to look for an old expected results file (ending with an 'o') and comparing to that file if found instead. An old expected results file for translator test #3 was also added (print functions used in expressions do not report through the closing parentheses. [commit 7aef54c63e]
The fact that the open parentheses operator token was configured as a unary operator in the table was going to cause issues with the new translator routines. Therefore, it is now not configured as a unary operand and the old translator routine was modified to look for an open parentheses token before checking if the operator was unary (the check was simply moved from after to before). [commit e75adeddcb]
The segmentation fault on expression test #3 was becoming a nuisance, and was only caused by the additional of more error tests for the new translator. Therefore, the problems with old translator routines were corrected, including considering the initial state as an operand state, allowing for an empty command stack in the case of expression mode, and assuming the Any type at the beginning of an expression before any operands or unary operators are received. The memtest script was also updated to allow for comparing old translator expected results files. [commit f0f6cb57f7]
Subscribe to:
Posts (Atom)