Translator – Operands

Operands are the objects that operators act upon. Basic operands consist of variables, constants and functions with no arguments. More complex operands consist of array elements, functions with arguments, and parenthetical expressions. Technically, the results of operators can be operands to other operators, but this will not be the definition of an operand for the Translator.

Only the basic operands will be added directly to the RPN list. Basic operands are any tokens that are not an operator and do not have a parentheses. I realized that this means that the Internal Function token type needs to be split into Internal Function with and with out parentheses (i.e. IntFuncP and IntFuncN) just like for the one-line define functions (DefFuncN and DefFuncP).

In other words, basic operands are items the don't require arguments. The Translator won't be able to tell the difference between functions with no arguments and variables – both of these will be of the NoParen token type. Therefore, the basic operands are NoParen, Constant, IntFuncN, DefFuncN, ImmCmd (will be the only token on a line), and Remark.

Translator

The job of the Translator is to convert the order of the tokens parsed from an input line into reverse polish notation (RPN), which will make for optimal execution of the program. See the post Internal Language for an explanation.

Essentially, the Translator will obtain tokens from the Parser expecting either an operand or an operator token type. Operands will be added directly to the RPN list, and operators will be added on an operator stack. Before putting an operator token on the operator stack, any operators on the operator stack that have higher precedence than the current operator are pulled from the stack and added to the RPN list. After the higher precedence operators are pulled from the stack, the current operator token is pushed on the stack. At the end, all operators from the operator stack are pulled and added to the RPN list.

Parser Test Revisited

I was thinking that it would be nice if the test_parser program had a mode where it would ask for input lines from the user so that additional items could be tested without having to recompile the program. Therefore a “-i” option was added to test_parser. This will tell the test_parser program to ask for input lines instead of running the canned tests. Once entered, the line will be parsed into tokens. The program will continue asking for input lines and will end when a blank line is entered (control+C also works). The skip_whitespace() function in the Parser class was modified to accept tab characters in addition to space characters.

The standard library gets() function is used for line input, which supports backspace, and simple editing including moving the cursor with the arrow keys, insert mode can be toggled with the insert key, and characters can be deleted with the delete key. None of these characters end up in the input buffer. The ibcp_0.1.1-src.zip file has been uploaded at Sourceforge IBCP Project along with the binary for the test program.  Now, really moving on to the Translator...

Parser Class – Operators (Testing/Release)

Additional tests lines were added into the fifth test input group for testing string constants. Everything was testing good until the one error condition was tested (invalid two character operator). This error was for the case where the character is not valid as a single character operator and the two characters at the position is not found in the table.

The first problem found was that the operators <, <= and <> had their multiple field set to OneChar instead of TwoChar. Then I realized that there were no two character operators where the first character isn't also a valid single character operator. I thought I could add one to test, for example &&, but then realized there would also have to be an & single character operator in the table with a token type set to Error for the code to work right. This would be silly, so the get_operator() code needed to be rewritten.

One rewritten, the “invalid two character” operator error no longer exists. First the current character is checked for a valid one character operator by searching the table. If valid then the token is setup for the operator. If the character can only be a one character operator, the token is returned. The single-quote remark operator is checked for before returning.

If the character can also be a two character operator, the table is searched again for the two characters. If not found then if the first character was a valid operator, the token previously setup is returned. Otherwise false is returned indicating there is not a valid operator at the current position. (In other words, let the next parser routine handle it, which for now there is none, so the get_token() returns an “unrecognized character” error.)  If the two characters are a valid operator, the token is setup for the operator and returned.

The temporary && operator was added to the table to test the two character operator where the first character is not a valid operator. Once tested, this test entry was removed. The ibcp_0.1.0-src.zip file has been uploaded at Sourceforge IBCP Project. The binary for the test program has also been uploaded. The Parser has been tested and is now complete. Next up is the Translator, now the fun begins...

Parser Class – Strings (Testing/Release)

Additional tests lines were added into he fourth test input group for testing string constants. There's not much to strings, but the one issue found was that the check in get_string() for a no closing quote needed to be removed because the scan_string() was modified during the testing of the immediate commands to accept a no closing quote condition. The ibcp_0.0.8-src.zip file has been uploaded at Sourceforge IBCP Project. The binary for the test program has also been uploaded.

Parser Class – Numbers (Testing/Release)

Additional tests lines were added into the third test input group for testing numerical constants. Numbers were also added to test each of the errors. After seeing how the errors were identified, I thought it would be nice if the entire number was identified for errors like “constant is out of range” for example:

    A = 3.45e343
        ^^^^^^^^-- constant is out of range

This required a new length value be added to the Token structure. Two new set_error() functions were implemented that also take a length argument. The existing two set_error() functions were modified to set length to 1. The length value was added to the anonymous union holding the integer and double values since none of these will be used at the same time. Having this error length value will be very useful when the GUI is implemented to the whole constant can be highlighted in red instead of just the first character. All the existing callers of set_error() were checked to see if a length would be help, but only a few in the get_immediate() for immediate commands was changed.

One error message could not be verified. Towards the end of get_number() there is a check to see if the current pointer (which will be pointing to the first character not part of the constant) matches the end pointer value returned from the strtol() or strtod() standard library conversion functions (which will point to first character not part of the conversion). This check was added to make sure the result was expected. I couldn't think of case where this would actually happen, so if it does, it would be due to a bug in the get_number() function, therefore, “BUG:” was added to the error message.

The ibcp_0.0.7-src.zip file has been uploaded at Sourceforge IBCP Project. The parser1.txt was updated for the change in the error output. The binary for the test program has also been uploaded.

Parser Class – Identifiers (Testing/Release)

The test_parser program was modified to break the tests into groups, otherwise one long stream of output would be generated – there's no reason to see all the Immediate Commands test output while testing Identifiers. Therefore, a single digit argument was added to the test_parser program where 1 is for the Immediate Command tests, 2 is for the Identifier tests, an so on. If anything in the core Parser code is changed because of bugs found, the older tests can be rerun and compared to the previous output as a regression test.

The first problem discovered was that it is was necessary to have distinct Token Types for Defined Functions with parentheses and without. Therefore DefFunc was replaced with DefFuncP and DefFuncN. The second issue discovered was that the internal string functions (CHR$, LEFT$, etc.) had the wrong data type of None in the table, so these were changed to the correct String data type.

Two things that could not be tested are search for words with a data type (there are none of these currently in the table) and the error if found the first word of a two word command and the second word of the command is not valid (currently all two commands are valid as a single word command, e.g. END, DO, LOOP, etc.).

The ibcp_0.0.6-src.zip file has been uploaded at Sourceforge IBCP Project. The binary for the test program has also been uploaded.

Parser Class – Immediate Commands (Testing/Release)

The first major problem discovered was that Immediate Commands can either have line number arguments (all argument types including Blank but not String) or a string argument. There needed to be a way to determine if the token string is pointing to the immediate commands argument structure or to an actual string. To solve this problem, the new data type CmdArgs was added. The immediate command's token's data type will either be set to CmdArgs or String.

The next problem discovered was that the scan_command() function could not return Null_Flag and have the token type set to an Error because it may have been set to Error from a previous call since it was not initialized or reset in scan_command() - this confused the get_command() function, which incorrectly returned errors when there wasn't an error. There needed to be a way to distinguish between invalid immediate commands that could be a valid BASIC command (like L500=10 or L500,L1000=8) and commands that are not a valid BASIC command either (like A100,-5 or L100-200=4). To solve this, the Error_Flag = -1 constant definition was added, which is returned if the immediate command has an error.

Many different test commands were added to the test input array, sufficient to test all of the different forms of command arguments, plus many errors like commands with arguments forms that is not acceptable for some commands. At the end of the array, there are many invalid commands to test every single error exit point in the scan_command() function.

The ibcp_0.0.5-src.zip file has been uploaded at Sourceforge IBCP Project. The binary for the test program has also been uploaded. Note that all the previous test programs and binaries are not included in this release in order to reduce the size of the file – these files can still be obtained from the 0.0.4 release.

Parser Class – Debugging

I've come to realize that debugging and testing the Parser code is not going to be a trivial undertaking. The Parser class routines have been implemented along with simple test_parser program to test the Parser class code. This program has an array of test input strings that will be feed to the Parser one at time. For each test input, the test input line is output and the start() function is called. It enters a loop calling get_token() until a NULL token pointer is returned. An error token returned also terminates the loop.

Inside the token loop, it simply outputs the contents of the token. At the end of the loop, it deletes the token, since for now the goal is testing if the proper token contents are returned. If the token contains an error, the error message is output with a indicator to where in the line the error is (using the column field in the token). The token is then deleted and the loop terminated.

Otherwise, the contents of the token will be output. There is a switch statement on the token type. There are arrays of strings for token type names, data type names and code names. The value in the token is used to index into these arrays so a name can be output (it would be a pain to look up numbers for each to see if the code is working correctly). Each token is output on a separate line indented under the input line.

I decided not to wait until the whole Parser is debugged and working before releasing code, since the goal of Open Source is to throw out code as soon as possible. Therefore, the code will be released in stages once each of the major Parser routines is debugged, tested and working. The first stage will be the Immediate Commands code (and of course the test_parser code). As for version numbering, the 0.0.x series will be continued through the debugging of the Parser. Once all of the Parser is working, the version number will be upped 0.1.0. The same convention will be used as the Translator is implemented, debugged and tested; which will continue through versions 0.1.x, until working with the release of version 0.2.0. An so on (the first entirely working Interactive BASIC Compiler will be 1.0.0).

Table Class – Testing and Release

Code was added to test each of the different type of searches to verify that the searches and the table entries were setup properly. Each search test looked for the first, last and some entry in the middle of the search group. Bad searches were included with each type. (Note that since there are currently no DataTypeWord entries in the table, only a bad searches were tested for this type.)

The main include has now been implemented named ibcp.h and only currently contains the definition needed for the Table class.  This file will contain all the definitions needed for this project - at least for now, but in the future may be reorganized into separate files if it becomes too large.  There is also a codes.txt file that lists all the current codes and their numeric values - sorted both alphabetically and numeric.  This file was very helpful during debugging and testing.  It was simply created by editing the Code enumeration into a new file.  There will probably be a future Tcl script to automatically create this file as new codes are added.

The ibcp_0.0.4-src.zip file has been uploaded at Sourceforge IBCP Project.  The binaries for the test programs have now also been uploaded so compilation is not necessary.  There's becoming quite a few test programs and test source and project files will probably be moving into a test subdirectory.

Table Class – Error Types

The plan was to write a test program (test_table.cpp) that contains the call to the Table constructor with the try/catch code to output any errors. Then errors would be introduced into the table entry array to test the error handling code. There were some coding errors and some errors in the table (both duplicate and missing codes) that needed to be corrected.

After the problems were corrected, errors were still being reported that the bracketing codes were missing. The problem was that the bracketing code indexes were not in the index_code array (because they were put into the range array).

To fix this problem, how the bracketing codes work was modified. The code that checked for each of the begin and end bracket codes was removed – these can be stored in the index_code array and this solved the missing errors. The indexes are then copied to the range structure.

Two more checks that needed to be performed on the range structure. The first error being to make sure the begin index was not greater than the end index, otherwise the search would malfunction (not find anything). The second error was to make sure that none of the search types begin and end indexes overlap any of the others.

Detection of all of the different types of errors were then tested to make sure they operated properly. Posts Table Class – Data Members and Table Class – Summary were updated to reflect these changes.

Table Class – Compilation

As mentioned, the Table constructor will throw an exception if any errors are found in the table. The caller of the Table constructor will look something like:

    Table *table;
    try
    {
        table = new table();
    }
    catch (List<TableError> *error_list)
    {
        ...output errors in error_list...
        exit(1);
    }

A test program was written to see if the basic concept of having a constructor throw and an error and then catching the error in the main routine. The test program test_cons will be in the next release. This worked as intended. However, as mentioned in the previous post, upon compiling table.cpp, the error list allocation line generated a compiler error essentially saying that constructor TableError::TableError() was missing. It was unknown where an empty constructor was being called since it wasn't being explicitly called. Guessing that it was missing a copy constructor for some reason, but adding one did not eliminate the error.

Table Class – Summary

The major components for the Table class are:

    TableEntry    – structure for one entry in the Table
    TableErrType  – enumeration of the table errors (duplicate/missing)
    TableError    – structure for a Table error (type, code, index1, index2)
    TableSearch   – enumeration of search types (see Table Class – Searching)
    Table         – main class definition

The TableEntry structure was first shown in Table (Parser), but has had a few changes since then. The string field was replaced with name and name2, where name2 is for the second name of two word commands (NULL otherwise). The two flag was renamed multiple (see Parser – Implementation Notes). And there will be a flags field currently used for immediate commands only (see Parser – Immediate Commands – Implementation) along with a set of constants defined for each flag (where each constant will have one bit set so that multiple constants can be ORed together).

The begin and end codes were not fully explained in Table Class – Data Members. These will be codes (for example BegPlainWord_Code and EndPlainWord_Code) in entries of the table entry array bracketing their associated entries (for example Plain Words). These entries are not actually scanned during searches, but used during initialization to find the begin and end indexes of the entries types to set up the range array in the Table class.

The TableError structure contains constructors for initializing each of the error types. The information for each error type is contained in a structure for the error type and all the structures are within an anonymous union with the error type variable outside. The Table constructor allocates the error list:

    List<TableError> *error_list = new List<TableError>

The intention is that as errors are found in the table, they will be added to the error list by first creating the error using one of the TableError constructors, and then appending it to error_list. At the end of the Table constructor, if error_list is not empty, then the error_list pointer exception will be thrown. In the caller of the Table constructor, the catch will output the errors and terminate the program. However, the above line generates a compiler error...

Updated Wednesday, February 17, 2010; 8:10 pm: Removed details about the error types since there are now four.

Table Class - Searching

The Table class needs a few functions for searching. It will also contain initialization for some table related variables and several access functions (the table entries themselves will be kept private). The actual data for the table will be put into a structured array initializer outside the class.

Each of the search functions will return the index of the table entry of the item found. The index can then be used with the access functions. To speed up searching of the Table, the entries in the table will be grouped together by type. There will be 3 major search functions:

• Search for an immediate command including argument form
• Search for a string of a given length of a given type
• Search for a two word command

For the search for a string, there will be four types:

• Plain Words – Commands, Word Operators, and Internal Functions that don't have a parentheses
• Data Type Words – Internal Functions that have a data type symbol but no parentheses (currently none are planned initially, but examples are DATE$ and TIME$)
• Parentheses – Internal Functions that have parentheses including those that may have a data type symbol, for example MID$(...)
• Symbol – Symbol character Operators (one or two characters) and other symbols, for example colon statement separator and single-quote remark

The immediate command search returns the command arguments in a structure within the string field of the token. This required a String constructor be added for a generic (void) pointer along with a length. With this constructor is new access function get_data(), which returns the void pointer.

Table Class – Access Functions

The Table class will contain access functions taking either a code value (one of the Code enumerations) or an table entry index (which will be the internal value used in the program):

    index(code)     – return the table entry index for the code
    code(index)     – return the code for the table entry
    type(index)     – return the token type for the table entry
    datatype(index) – return the associated data type for the table entry (if any)
    multiple(index) – return whether the command supports multiple words/characters

There will also be a flags member in the TableEntry structure.  Currently it is only used for the immediate command to indicate which argument forms that the command supports.  The other entries will have the flags member set to Null (no flags set).  This will probably be used later to indicate other conditions for the rest of the entries.

Table Class – Data Members

The Table class will contain these data members:

    entry      – pointer to the table entries array (TableEntry)
    index_code – pointer to the code to index array
    range      – array of Range structures (with begin and end index members)

The constructor will initialize all the Table data including setting the entry pointer to the table entry array (a local static in the table.cpp source file), allocating the index_code array, and setting up the index_code and range arrays.  The destructor will delete the index_code array.

The initialization includes the recording the index of each code in the table to the index_code array (recording an error for any duplicates found), checking and recording an error for any missing codes, setting the search type range being and end indexes, checking if the begin index is not greater than the end index for each range (recording an error for any range errors found), and checking that the indexes of the ranges do not overlap each other (recording an error for any overlap errors found). Any errors will be appended to an error list. At the end of initialization, if this error list is not empty, an exception with the error list will be thrown.  An error list will be used so that all errors in the table will be reported. 

Updated Wednesday, February 17, 2010; 8:40 pm: changed to reflect the four different type of table errors.