Translator – Commands and Precedence

In the translated RPN list, the command token will generally end up at the end of the statement. To accomplish this, the command tokens need to be saved until the rest of the statement is translated. The best place to save the command tokens is on the hold stack with a very low precedence to keep them on the stack until the end of statement.

The appropriate precedence of commands would appear to be the same as the EOL token, so that when the EOL token is processed, the command tokens will be emptied from the stack. This implies that commands could empty other commands, but generally, this will not occur except for multiple keyword commands (like the IF-THEN-ELSE and FOR-TO-STEP commands).

The EOL token currently has the same precedence as assignment, closing parentheses, and comma tokens. It makes sense for assignment and commands to be the same precedence because assignment is technically a command. An assignment will never empty a command from the hold stack because the Translator never receives an assignment operator. An equals token is received as an equality operator, which has a higher precedence, so it won't empty any lower precedence commands. It's only after the stack emptying that an equals token may be changed to an assignment token.

Closing parentheses and comma tokens, being the same precedence, will empty all tokens with higher or same precedence, which is a problem, since command tokens will be the same precedence. This is currently not an issue because:

1. An EOL token is not pushed onto the hold stack and therefore can't be emptied by a closing parentheses or comma.
2. An assignment operator is not on the hold stack when a multiple assignment comma is processed, so the comma won't empty an assignment token.
3. An assignment token is on the hold stack when a comma is processed within an array or function – the lower precedence array or function token will be on the stack before the assignment token, so it won't empty the assignment token.
4. An assignment token is on the hold stack when a comma is processed not within an array or function (though possibly after an opening parentheses) – this is an unexpected comma and an error occurs.
5. A closing parentheses may empty an assignment token from the stack, but since no opening parentheses, array or function token is found on the stack, an error occurs.

This means the precedence of closing parentheses and comma tokens need to be increased above assignment and command tokens so that they do not empty them from the hold stack, but below any other operator. Closing parentheses and comma tokens are never pushed onto the hold stack, so there is no worry about them being emptied from the hold stack by an EOL or command token (an assignment token never empties the hold stack).

Translator – Token Sub-Code

The internal code will contain sub-codes that will be used by the Recreator, thus eliminating the need to put dummy codes into the program. The Translator knows when information will be needed by the Recreator in reproducing the original source. A sub-code member will be added to the token class so that the Translator can pass this information to the Encoder. The Encoder will set the sub-codes in the internal code words.

Instead of adding the dummy parentheses token to the output list, the Translator will now set the parentheses sub-code in the last token appended to the output list. The closing parentheses token used for the dummy token is no longer needed, and will be deleted. The token output routine in the test code will output a ')' at the end of a token when the parentheses sub-code is present.

Similarly, if the LET keyword is present in front of an assignment, then the LET sub-code will be set in the assignment operator token. The token output routine in the test code will output a 'LET' at the end of a token when the LET sub-code is present. Before knowing exactly how this will be accomplished, it is necessary to defined how commands will be processed...

Internal Code Format

The encoded BASIC program will be stored in memory in a very compact form. It will not be any kind of linked list of tokens like come out of the Translator. A linked list would have way too much overhead during execution and would waste a lot of memory. Instead, the program will be very simple format where each code will take up a single 16-bit word.

A 16-bit word has plenty of space to support all the codes, which currently stands at 137 (there will be lot more, but far less than the 65,536 numbers possible in a 16‑bit word). This handles the actual codes (operators, internal functions, and commands), but what about entered identifiers like variables, arrays, define and user functions, constants, and so on?

Entered identifiers will have an index value into a table, known as the Dictionary, which will contain the information about each identifier (like name, data type, number of array dimensions, size of array dimensions, number of arguments, argument data types, constant values, etc.). The index to the Dictionary entry will be stored in the program. During run-time, much of the information in the Dictionary will not be used.

These indexes will be preceded by a code. For example, one of these codes will push a double variable value onto the evaluation stack. The routine for this code will know to get the next 16-bit word that will contain the Dictionary index. Using a 16-bit word for the index implies a maximum of 65,536 Dictionary entries. This should be sufficient since subroutines and functions will each have their own Dictionary, with each having a maximum 65,536 Dictionary entries.

The 16-bit code word has more bits than are needed for the code value. The extra space can be user for other things. One use would be for information like the presence of unnecessary parentheses or the optional LET keyword. This information will be called a sub-code and ignored by run-time module, but would be used by the Recreator. The detail of the internal program doesn't need to defined right now, just the knowledge that there will be a sub-code present in the internal code. Next, what this means for the Translator...

Translator – Commands (Introduction)

Now that expressions have been fully implemented in the Translator (at least until more language features are added), it's time to start implementing the BASIC commands. In fact, one command has already been implemented, the assignment statement without the optional LET keyword.

It was mentioned some time ago that there was a way to eliminate the need for the dummy close parentheses codes. These dummy codes are put into the translated output where unnecessary parentheses were entered into an expression, so that the Recreator would know to reproduce them. This will prevent confusion from having entered parentheses just disappear. During run-time, these dummy codes would be skipped.

It turns the same method to get rid of these dummy parentheses codes will also be used for the LET command, first command to be implemented. There are already 8 assignment codes, and there will be 4 more once temporary strings are fully implemented in the Encoder. All of these assignment codes are for without the optional LET. Either another dummy code is needed for the LET or each of the assignment operator needs to duplicated when the optional LET is included – that's 12 more codes.

Neither of these two alternatives is desirable. There is a third alternative that will help eliminate the need for these dummy codes, but some look ahead planning is required into the design of the format for how the BASIC program code will be stored internally. In fact, as each BASIC command is implemented, so forward planning is necessary into how the command will be stored in memory and executed during run-time. Next a preliminary design of the internal code...

Translator – Multiple String Assignments (Release)

Upon contemplating the string flags in the table entries, I realized that care must be taken to make sure the string flag is set in the table entries when an operator or function code has a string operand. A better design is to set the string flag automatically during table initialization if any of the operands of the string data type. Therefore, the string flags were removed from the table entries and the Table constructor was modified set the flags in the table entries automatically.

To correct the issue of saving all the operands for string list assignments, a temporary simple stack is used to save the operands as they are popped off of the done stack and processed. Since the last two operands (the value being assigned and the last item in list) have already been popped and processed by the find code routine, these are pushed to the simple stack before processing the rest of the operands. Each additional operand processed is also pushed to this stack.

After the list operands are processed for a string list assignment a new array needs is allocated and filled from the temporary simple stack. In order to determine the size of this array, either the operands need to be counted as they are processed, or the number of items in the stack needs to be accessed. Since the simple stack already knows how many items it has, a new access function was added to the SimpleStack class to return the number of items.

It had been decided previously that mixed strings and sub-strings would be allowed in a multiple list assignment statement. Having a mix string list assignment replaces the need for a separate sub-string list assignment code, the mix-string list assignment will handle this case. So, a new AssignListMixStr associated code was added to AssignList (this new code has a sub-string as the first operand, the value being assigned). The list assignment handling code was modified to detect if the list contains both reference strings and sub-strings. If it does, then the token is changed to this new AssignListMixStr code.

Several new sub-string and mix-string assignments were added to test inputs. This completes string handling in the Translator. The code now handles expressions and assignment statements and ibcp_0.1.11-src.zip has been uploaded at Sourceforge IBCP Project along with the binary for the program. Next the real meat of the Translator begins, translating actual BASIC commands...

Translator – Sub-String Assignments (Release)

After testing the Table initialization code that checks maximum number of operands and maximum number of associated codes, several sub-string assignments statements were added and tested.  Then some sub-string assignments with error were added.

One of the types of errors being tested were the assignment of temporary strings like MID$(A$+B$,2)=C$. There error was correctly detected, but the error was pointing to the MID$, which could be confusing. Therefore, a change was made that for an assignment, if the expected reference flag is not set, then if the token without the reference flag is a sub-string function (its data type is sub-string), then the error token is set to the token if the first operand of the sub-string function. So for this statement, the error will be pointing to the + of the A$+B$.

During testing of the sub-string assignments, one of tests tried was the mixing of regular strings and sub-string, for example A$,LEFT$(B$,1),C$=D$. This did not work correctly (this type of statement will be allowed). Also noticed that for lists, the assignment operator output list item only had two operands (the last variable being assigned and the operand being assigned). It should contain all of the operands being assigned. So these are two more issues that need to corrected.

In any case, sub-string assignments are working so another developmental release is being made and ibcp_0.1.11-dev-3-src.zip has been uploaded at Sourceforge IBCP Project along with the binary for the program. Now to fix assignment list  operands and mixing of string types...

Translator – Sub-String Assignments (Testing)

The changes to support sub-string assignment were implemented, which included adding the SubStr data type entries to the conversion code array in the match code routine; changing the data type to SubStr for the LEFT$, MID$ and RIGHT$ table entries; and added the sub-string reference checking. Initial testing started with the existing test inputs – no problems were discovered.

Upon trying a sub-string assignment, discovered that it didn't work because there was no AssignSubStr associated code, so this code was added along with its table entry. Now, many of the existing test inputs were failing. Next discovered that the maximum associated codes needed to be changed from 2 to 3 because Assign now had three associated codes. The wrong value was causing the find code routine to malfunction.

I thought it would be best to calculate both the maximum operands and maximum associated codes automatically during the Table initialization, so moving these constants to members of the Table class seemed to be the best solution. Unfortunately, these values need to be constants because they are used to define the sizes of several arrays.

It would still be prudent to have the the Table initialization at least check to make sure these constants agree with what was in the table entries. So code was added to the Table initialization to find the maximum operands and associated codes as it was scanning the entries for code checking. Two new table error types were added for these errors, which are reported by exceptions from the Table constructor. Testing continues...

Translator – Sub-String Assignments

There will be several associated codes for assigning strings from a reference string or temporary string to a reference string or to a sub-string. The Encoder will determine which code to use once the string type for each operand is determined. For the Encoder to know if a sub-string is present, a new SubStr data type is needed, which only the LEFT$, MID$ and RIGHT$ functions return.

The Translator will check to make sure that sub-string assignments are valid by making sure the string argument is a reference string, at least if it is a Paren or NoParen token type. If it turns out to be a user function, then the Encoder will report the error. The Translator will also make sure that a compound sub-string assignment like LEFT$(RIGHT$(B$,3),2)="AB" is not entered.

The find code routine needs to handle sub-strings where the operands are popped off of the done stack and the reference flag is checked. For the first operand (last operand popped), if the data type of the token is SubStr (indicating a sub-string function) and the operand is a String, then the token's reference flag is set to operand's reference flag (the reference flag is transferred).  The operand's reference flag is then cleared as it is currently implemented. This assumes that the first argument of the sub-string function is the string being assigned.

If the operand's data type is anything but String (SubStr or TmpStr), then the reference flag is not transferred. For the invalid compound sub-string assignment, since the data type of the operand will be SubStr, the reference flag of the function's token will not be set. When the reference flag is checked for an assignment operator, the reference flag will only be set if the string operand was reference, otherwise if won't be set and an error will be returned.

Sub-String Assignments

Many BASICs support sub-string assignments, the syntax that will be supported is the same used as in GW-Basic, QuickBASIC, FreeBASIC, etc.. Here is an example sub-string assignment along with it's translation:

MID$(A$,5,2) = "AB"       A$ 5 2 MID3$ "AB" AssignSubStr

Notice the new code AssignSubStr and the lack of <ref> on A$. When the MID$ is processed by the Translator, the reference flags of its operands are cleared, hence no A$<ref>. However, the MID3$ needs to have its token reference flag set when the assign operator checks for a reference, since that MID3$ token will be on the done stack. Consider how this statement is processed at run-time.

At the A$, a reference string is pushed on the evaluation stack, that is, its pointer and length are copied to the stack. When the MID3$ is processed, it will pop the 2 and 5 off of the stack. The pointer on top of the stack will be changed to point to the fifth character in A$ and the length is set to 2 (assuming that A$ is at least 6 characters long).

When the AssignSubStr is processed, the "AB" string constant will be popped off of the stack. Two characters of this value are copied directly to the pointer that is on top of the stack (which is pointing to the fifth character in A$). A different AssignSubStr vs. AssignStr code is required because no allocation occurs, only a copy to an existing character array. An AssignSubStrTmp code is also required for the case that the value being assigned is a temporary string, which needs to be deleted after the characters are copied.

Since LEFT$ and RIGHT$ are also sub-string functions, there is no reason these functions can't also be used to assign sub-strings – and as it turns out, no extra code is required. Next, how sub-string assignments will be handled by the Translator...

Translator – Sub-Strings

The processing of operators and internal functions with string operands needs to be delayed until encoding because in some cases, the Translator does not know if a string is a reference (from a variable or array element) or a temporary (from a user string function) because the Translator does not know if identifier is a variable, array element or a user function.

At run-time, if the string argument to a sub-string function is a reference string, then it's result is also a reference string in that the string does not need to be deleted. If the string argument is a temporary string, then it's result is also a temporary string in that the string needs to be deleted.

Each sub-string function will have an associated code. The main code will have a reference string operand and will return a reference string. The associated code will have a temporary string operand and will return a temporary string.

It would appear that sub-strings have no impact on the Translator. However, there is one more capability that needs to be considered, and that is sub-string assignments where a portion of a string is assigned without affecting the rest of the string...

Translator – Saved Operand Correction (Release)

The problem where the saved operand pointers were not pointing to a conversion code that was inserted (was pointer to the original operand), was a simply correction. All that was needed was to set the operand array element to the output of the output list append call where the conversion code token was inserted. The ibcp_0.1.11-dev-2-src.zip file, another developmental release, has been uploaded at Sourceforge IBCP Project along with the binary for the program.

Sub-Strings – Details

The results of sub-string functions (LEFT$, MID$ and RIGHT$) will use the same character array as the argument string. Exactly how this is accomplished depends on whether the argument string is a reference string or a temporary string.

For a reference string, the pointer and length of the character array are copied to the evaluation stack. This means that the pointer and length on the stack can be modified without affecting the actual pointer and length of the variable or array element. For LEFT$, only the length on the stack needs to be changes. For MID$ and RIGHT$, both the pointer and length need to changed depending on the integer arguments.

For a temporary string, the sub-string operation is a little more involved because the pointer to the character array on the stack cannot be modified – it is needed to delete the character array when the temporary string is no longer needed. The length is not needed to delete the character array, so it can be modified. Since the pointer cannot be modified, the portion of the sub-string needs to be moved to the beginning of the character array. Again for LEFT$, only the length needs to be changed, the sub-string is already at the beginning of the array. But for MID$ and RIGHT$, the sub-string result needs to be moved to the beginning of the array.

For reference strings, there is no allocation, copying or deletion required for the sub-string operation. For temporary strings, there is still a moving of characters, but there is no allocation of a new character array or deletion of the old character array. After the expression is evaluated, the temporary string will be deleted. There could be some unused space in the character array from a sub-string operation when the temporary string is assigned and used as it. Enough of discussing how sub-strings will work at run-time, next, what impact sub-strings have on the Translator...

Sub-Strings

Because strings are variable length, they are dynamically allocated as needed during run-time. It is therefore beneficial to reduce as much as possible the amount of allocating, copying and deleting of the character arrays. This is why reference strings, the values of string variables and array elements, are used as-is so a new character array does not need to be allocated and copied to in order to put the reference string on the evaluation stack. But this will require extra code to know when to delete a temporary string and not to delete a reference string on the stack, which will be accomplished with additional associated codes.

There is another way to reduce some allocation and deleting of temporary strings for the sub-string internal functions, aka LEFT$, MID$, and RIGHT$. These functions can have a reference string or a temporary string as an argument. The obvious way to implement these functions is to create a new temporary character array of the appropriate size for the resulting string, copying the characters from the argument string to the new array and if the argument string is a temporary string, to delete it.

There is a simpler way to handle sub-strings that will eliminate the allocation of a new character array, deleting the temporary string argument if present and the copying for a reference string. Consider how a string is stored, there is a character array, there is a pointer to the character array and there is the length of the character array. The pointer and length make up the members of the String class along with the allocated array. A resulting sub-string will never be larger than the string argument. so why not use the same character array, since it has already been allocated. Next, details on how this will work with reference strings and temporary strings...

Translator – Temporary Strings (Release)

Before testing the changes, the test code was modified to output the operands that were saved by the Translator within square brackets separated by commas. This change was made to see if operands were being saved correctly for the correct tokens (array, user functions, operators with string operands and internal functions with string operands). Only the primary operand token is output, so it the operand is an operator, that is what is output.

The code appears to be working, at least for all the current test inputs with one exception (no new test inputs were added at this time). If a conversion operator was inserted for an operand, the operand is not pointing to the conversion operator. For example, for the statement Z$=MID$(A$,B+C,D), the MID$ token is output as MID3$([A$,+,C], but should be output as MID3$([A$,CvtInt,CvtInt] since conversion operators were inserted for the + and D operands.

Other than this problem the code appears to be working. Since there is more work is needed to complete string data type handling in the Translator and not much was changed (temporary strings, which had a minor affect on the Translator; and operands are saved for later processing as needed for the Encoder), the code is being released only as a developmental release and ibcp_0.1.11-dev-1-src.zip has been uploaded at Sourceforge IBCP Project along with the binary for the program.

The rest of the string data type handling has to do with the sub-string functions (aka LEFT$, MID$ and RIGHT$), which will handle strings slightly differently during run-time...

Translator – Temporary Strings (Implementation)

Upon making the changes to add temporary strings, I realized that there are more string operators than just the CatStr operator – there are the equality, relational, assign, and assign list operators, all of which can have string operands (either reference or temporary). For the equality and relational operators, the character arrays of any temporary strings need to be deleted after the comparison is made.

For the assign operator, if the operand is a reference string, then a new character array needs to be allocated and the reference string copied. However, for a temporary string, the string variable's character array can be set to the temporary character array (making it a reference string) and the current character array is deleted, eliminating the need to allocate and copy. For assigning a list, the temporary string can only be used for one of the string variables in the list, the rest need new arrays allocated.

There is already a String flag used for immediate commands, and since it's value doesn't conflict with any of the existing flags (immediate command flags are separate), it can also be used for operators and internal function codes that have string operands. A note was added to the code to make sure it's value is not used for another flag value.

A constructor was created for the new RpnItem structure that takes a token pointer, number of operands and a pointer to an operand array as arguments (the later two default to 0 and NULL). If the number of operands and operand array pointer is supplied, an operand array will be allocated for a non-zero number of operands and the operand pointers will be copied from the supplied array. A destructor was also created to delete the token and the operand array.

Translator – Temporary Strings

The impact of temporary strings on the Translator is not much since the work of finding associated codes will be left for the Encoder. However, there are a few changes that are required – the main one is passing the operands to the Encoder so that it has easy access to them.

A new TmpStr data type will be added. The data type of the string operator (CatStr) and the internal functions that return a string will be changed to TmpStr.  This includes the internal functions CHR$, REPEAT$, SPACE$ and STR$. Something else is needed for the functions LEFT$, MID$ and RIGHT$, which will be revealed shortly. Any string DefFunP and DefFunN token types will also be changed to TmpStr since defined (one-line) string functions will return a temporary string during run-time.

The conversion code table used by the match code function needs to be expanded to include the new TmpStr data type. As far as the Translator is concerned, the String and TmpStr data types are the same, therefore the conversion code table entries for String to TmpStr and TmpStr to String will be set to the Null code.

For the string operator and internal string functions that have string operands, the operands need to be attached to the operator/function token within the output list. To accomplish this, the output list will be changed from a token pointer to a pointer to a new RpnItem structure that will contain the token pointer, the number of operands (0 if not applicable) and a pointer to an array of output list item (RpnItem) pointers.

There will be a new String flag added for these codes so that the Translator can easily identify them. When this flag is set, the number of operands will be set and the output list pointer array will be allocated. This array will be filled from the operands popped from the done stack. The done stack will also be changed to a stack of RpnItem structure pointers.

This saving of operands functionality is also needed for parentheses tokens, which can be arrays or user functions. The processing of array subscripts and user function arguments also needs to be delayed until the Encoder since the Translator doesn't know the difference between an array (whose subscripts all need to be integers) or a user function (whose argument types will be contained in the dictionary and defined in a function definition statement).