Command Centric Translator

The core of the current translator design has tokens fed to it one by one and is uses various states and modes to determine what type of tokens are expected and how they should be processed.  This design is rather complex and will make the implementation of more complex commands (like IF-THEN-ELSE and FOR-TO-STEP) very difficult.

The new translator design will be command centric.  What this means is that instead of handling each token individually from the bottom, the commands themselves will determine how their particular syntax will be translated.  The translator will start by reading a token, determining the command, and then calling the command specific translation routine.

There will be several routines to support getting the parts of commands these command translation routines will use including getting an expression, getting a variable reference, getting a constant, and getting a command.  Each of these functions exit once a token is reached that it does not handle and return that token.  For example, a semicolon would terminate an expression routine and return the semicolon token.  The caller would then decided how the semicolon will be handled (like in a PRINT statement), or if it is an error for the command (like in an IF-THEN statement).

For example, for an assignment statement, the LET translation routine first gets a variable reference, checks the returning token for a comma or equal operator, if a comma then will repeat getting a variable reference, else it would finish up by getting an expression.  An error would be reported at any step that is not valid (or if say the types don't agree).  Upon a successful command syntax, the token terminating the expression would be returned by the LET translation routine to the caller.

Each command translation routine would call the appropriate support routines for getting the various parts of the command's syntax and will return either an error or the token terminating the command.  The main line translator would expect either a colon (in which case it would look for another command), or an end-of-line token.  For an IF-THEN, after receiving the THEN token, would also call the get command routine, but in addition to looking for a colon or an end-of-line, would also look for an ELSE or ENDIF token.

Internal Program – New Design

Using a pure reverse polish notation format for the internal program, the code for the command would be at the end of the line.  When running the program, the codes before the command code leave the arguments of the command on a stack, which are then available when the command token is executed.  However, for some commands like PRINT and INPUT, there would be several intermediate codes intermixed in the line that perform part of the command (for example, print a value, input a value, etc.).

I thought that using a less than pure RPN format would be easier to translate to and recreate from, where the command code would be first followed by the other codes and ending with an end of statement code (end-of-line, colon, ELSE, etc.), which would kick off the command.  There would still have been intermediate codes in the line, specifically the commas and semicolons that separate the other arguments of the commands.

When encountering these codes during run-time, they would call back to the command, which would look at the code and the type to decide how to process the value that are on the stack.  These separator codes would have required type information (double, integer or string) in the their sub-code field.   This would have complicated the run-time code.  Note the decisions that would need be made at run-time.  This would not be ideal as the goal is to make decisions before run-time so the code can be executed as fast as possible.

In any case, upon further contemplation, I decided that a pure RPN format would be best, but with a slightly different format for the intermediate codes needed for some commands, which would be the result of decisions made during translation.  Plus translation will be easier with the new command centric translator, which will be described in the upcoming posts along with the specific details of the various commands.

Translator Design – Revisited

The next step was going to be either the Recreator (recreating from the RPN lists produced by the Translator, since that is all that is available) or the Encoder (including defining the format of the internal program).  For the later, the internal format of the program needs to be defined.  Integral for this definition is how the program will be run.

The basic format chosen is a pure reverse polish notation.  The problem with this is that it makes the translator design very complicated and somewhat convoluted (for example, the processing of a PRINT statement is spread throughout the translator code).  And so far only three fairly simple commands have been implemented.  The problem is that the design is token centric, meaning that the specific tokens are processed and they decide how they should be handled based on the current state of the translator (command, expression, etc.).

A better design, and on that should be easier to implement, especially once the more complex commands are implemented, is one that is command centric, meaning the commands decide how the program lines are processed and how the tokens are handled.  This also means a pure RPN design of the internal program is not necessary.  The design I have in mind should only impact run time slightly, but will significant simplify the translation of more complex commands.

The new design will be explained in upcoming posts.  The goal for the 0.4 development series will be the implementation of the new translator design, which will include the currently implemented commands (LET, PRINT, INPUT, INPUT PROMPT and REM) along with handling expressions.  The size of the current Translator (header, source, token handlers and command handlers) is a total of 2,863 lines.  It will be curious to see if new design is able to reduce this.

Translator/GUI Integration - Release

The integration of the Translator and the GUI is now complete, which includes a debugging program view of the program internals containing the translated RPN lists of the program lines.  This will eventually show the internal program codes once the encoder is implemented.  Version 0.3.5 has been released (branch0.3 was merged to the master branch and tagged v0.3.5).

Archive files containing the source and binary files(with test files) have been  uploaded to SourceForge.  For Windows, there is also the ibcp-libs.zip file that contains all the dynamic linked libraries required to run the program if the MinGW and QtSDK packages have not been installed (extract into the ibcp directory).  Linux should already have the required libraries installed.

This concludes the 0.3 development series.  Implementation of the next step will now begin with the 0.4 development series, which will be defined in the next post.

[commit 046c47cd9a]

New Git Repository Tagging Convention

The error highlighting implementation is now complete and it is time for a development release.  I made the decision to change the naming convention of repository tags from releaseX.X.X to vX.X.X, which is the convention used by many other projects under git revision control (like the git source repository itself).  All the "release" named tags have been replaced with the new "v" named tags.  These can be removed from a local repository using the command git tag -d `git tag -l release*` (backward single quotes) or the repository can be re-cloned.

To support this change, the CMake build configuration file CMakeLists.txt was modified for this naming convention.  A change was also required in the building of the version string in the command line class, which previously added seven to the release string pointer, seven being the length of the "release" part of the version string.  This could have simply been changed to one, the length of the "v" part of the string, but instead a little code was added to look for the start of the version number part of the string (by using a regular expression) so it doesn't matter what string precedes the version number.

The change in tag names will not cause a problem when building one of the archive files downloaded for a given tag because CMake will generate the version string being that the git repository will not be available.  Though the version announced as being built will still have the "release" string in the name.

However, if building at an older tag with the new tag naming convention, then these changes are needed, which is not an issue with any of the versions prior to 0.2.  CMake will not complain from versions 0.2-1 to 0.2-6 but the version number output will be messed up.  The changes need to be applied manually.  Starting with the final version 0.2.0 through the 0.3.X versions, the changes can be applied by git using the command git cherry-pick fa89 command where fa89 is the abbreviated commit ID of the commit with the changes.  To preserve this commit, a new branch can be created using the command git checkout -b xxx where xxx is the desired branch name.

Finally, previous blog entries were edited to reflect the new tag naming convention.  All blog previously given the Pre-Release blog tag was given the Tag blog tag.  Major releases still contain the Release blog tag (and not the Tag blog tag so they can be differentiated).

[commit fa89de8a0d]

Modifying A Line With An Error

When a line is modified that contains an error, the highlighted error can be shifted around or changed in size.  This can make the error message no longer applicable, so the highlighted error should be removed.  Upon the cursor leaving the line, the line will be rechecked for errors.  A check for this situation was added to the document change slot of the edit box class when a single line is changed.  No action was taken for single line changes.

When a single line is modified, the errors lists is searched its line number.  If the line contains an error, but the modification occurred after the error, no further action is taken.  If the cursor and the error are at the end of the line, or the cursor is within the error, the error is removed from the error list.  If the cursor is before the error, the column of the error is moved by the net change (number of characters added less the number removed).

The update errors slot is called to update the display.  A cursor changed signal is also emitted so that the error message on the status line is removed when the error is removed.  This didn't always occur because the cursor is not always moved when the document is changed (for example, when characters are deleted).  New move error column functions were added to the error list and error item classes to support the shifting of errors.

[commit 98d7b2c0b4]

Error Action Enabling/Disabling

Now with actions to move the cursor to the next or previous error, these actions should only be enabled when there are actually errors.  To accomplish this, an errors available signal was added to the edit box class.  The update errors slot was modified to determine when the errors available condition changes by comparing the before and after error list emptiness status.  Several problems were found and corrected while testing the new signal.

In the update errors slot, when there were no errors in the incoming errors list, a Qt error occurred because bad indexes were used in accessing the errors list.  This was due to using the start and end change indexes when they were not valid.  A check was added for when the incoming error list has no errors to prevent this.

The second problem occurred when there were no errors and the next or previous error key shortcuts were used.  This was due because the Ctrl+. (period) and Ctrl+, (comma) were not intercepted since the errors actions were disabled, causing these keys to be treated as a regular period and comma, which was inserted into the program.  Checks were added to the key press event handler to catch and ignore the period and comma keys when the Ctrl modifier was active.

Finally, during testing, an unrelated problem was found with the detection of changed lines when comparing RPN lists that contained errors.  Previously this comparison (equality operator function) compared the error column and length and reported equality if they were the same.  This caused a problem were sometimes the error was not displayed correctly in the modified line (or not at all).  The equality function was modified to report no match if either RPN list has an error.

[commit 352667221f] [commit 15084235a2]

Move To Error Actions

It would be convenient to be able to move the cursor the next (or previous) error.  This was accomplished be adding two additional actions, one for moving the cursor to the next error and the other to move the cursor to the previous error.  Each action was given an arrow icon, which were modified to have a red hue.  Both were also assigned key shortcuts, which were Ctrl+. (period) for next and Ctrl+, (comma) for previous.  These keys were chosen because they also contain the greater than and less than keys, which are like arrows.

The actions are automatically connected to associated triggered functions in the MainWindow class, which call new functions in the EditBox class to perform the action.  These functions first find the error for the current line.  If the current line does not have an error, the find returns the index of next error or will return in index one beyond the end of the error list.  The functions then move to the next or previous error depending whether the cursor is already sitting at the error found.  If beyond the last or first error, a question box is displayed informing this and asks whether to move to the first or last error in the program.  If there is only one error, then no question box is displayed.

There is some sort of issue when running on Linux (Mint 13 KDE) using the static QMessageBox::question() function to display the question asking whether to wrap around and to the first or last error - an X Error message is output.  This may have something to do with another problem where there is suppose to be a question mark icon on this message box, but the information icon is displayed instead.  These problems do not occur on Windows and also do not occur on Linux if the application is launched with the -style Plastique option.

For now the next and previous error tool bar buttons and edit menu items are always enabled.  Next these will be disabled when there are no errors.

[commit f086ce50b8]

Error Highlighting – Error Messages

To display error messages in the status bar area at the bottom of the application window required a few minor changes.  Two labels were added to the status bar of the main window, one for the current line number and column, and the other for the error message.  A signal was added to the edit box, which is emitted when the cursor positioned has changed.

A new function was added to the main window class for creating the status bar: adding the labels to the status bar and connecting the signal cursor changed signal from the edit box to a new update status bar slot in main window.  New member label pointers were added so that the labels are easily accessible when it's time to update their text.  New access functions were added to the edit box class to return the current line number, column and message for the line (if there is one) so the update slot can get the information for the status bar labels.

The new message access function of the edit box searches for the line number in the error list.  A new find index function was added to the error list class, which returns a -1 if the line number does not have an error.  The existing find function is called, which only returns an index regardless if the line has an error, so a check is made if the index returned is the line being search for.  If the line does not have an error, a blank message string is returned.

There were a couple of issues getting the error messages to be displayed in the status bar correctly.  Click Continue... for details of these issues and how they were resolved.

[commit c38cd02bd4]

Error Highlighting – Program Load Fix

Displaying the error messages on the status bar at the bottom of the window has proven to be difficult.  While working on getting these changes to work, a problem was discovered when loading a program with errors - the errors were not display just like the problem when the application first starts.

The mechanism added to correct that initial start up problem did not work for this case because the cursor valid flag, which is initially reset, is set the first time the cursor is moved.  When a program is loaded, the text of the program loaded in set in the edit box's document using the setPlainText() function.  Apparently while the text is being set, the cursor is again invalid preventing the errors from being highlighted.

The cursor valid flag mechanism was utilized to correct this problem.  The setPlainText() function of the base QPlainTextEdit class was reimplemented in the edit box class, which resets the cursor valid flag and calls the base class function.  Once the text is set, a cursor changed signal gets emitted and the cursor valid flag is once again set triggering the errors to be updated.

[commit 58b0f23680]

Errors List Corrections

While testing the error highlighting, some problems were found.  The first one exhibited itself as the last error was not correctly updated when it changed.  The problem was that a new error was being incorrectly inserted each time an error was changed.  This occurred in the set error routine in the program model because it did not return after replacing an error and it proceeded to also insert an error.

The set error routine was cleaned up where the first part now specifically handles changes (not inserts) and returns after an error is removed (the line no longer has an error), or an error is replaced (the line still has an error).  The rest of the routine handles inserting a new error and adjusting the rest of the error indexes and line numbers (for line inserts).  The remove error routine contained an else clause for exiting when called for an insert, but since this no longer occurs, the else clause was removed.

The second problem was in the edit box update errors slot.  The problem occurred when two or more lines with an error were removed and all the errors were changed as a result (due to the line numbers changing).  The problem is that the ending change index is set to the last index upon the first removed error, but after the second error is removed, the ending change index is not beyond the end of the error list.  This caused the routine to run past the end of the errors list causing a segmentation fault.  This was corrected by limiting the number of errors changed to one less than the size of the errors list.

[commit 30e7d98a1d] [commit 65893e51f9]

Error Highlighting – Initial Start Up Fix

The problem with the errors not being highlighted when the program is first loaded was not caused due to the edit box not being drawn yet as first thought.  The problem was identified to be that the text cursor was not valid initially.  When the extra selection list was set up, each enter had an invalid cursor, so nothing was highlighted.  The seemed to be no way to initialize the text cursor in the edit box constructor.

To compensate for this problem, a mechanism was implemented where the updated errors list is saved and not acted upon unless the text cursor is valid.  A new errors list member was added to the edit box class to hold the saved errors list.  The errors list needs to be saved anyway because it will be needed to access the error messages.

A new cursor valid flag was also added to the edit box class, which is initialized to false.  In the cursor moved slot, the text cursor will be valid and this event always occurs during startup.  So in this slot, if the cursor valid flag is not set, it is set to true and then the update errors slot is called to set the extra selections list.

[commit 89cfa532a8]

Error Highlighting – Extra Selection List

To highlight the errors sent from the program model, a new extra selections list member was added to the edit box class.  The update errors slot first determines the number of errors that have been inserted or removed by taking the difference between the size of the new errors list and the size of the current extra selections list.  The number of errors that changes is determined by taking the difference between the end and start change indexes plus one, then subtracting the number of errors inserted (which may be zero).

Starting at the start change index for the number of errors that changed (which may also be zero), the extra selection is replaced with the corresponding error item from the errors list.  Continuing for the number of errors inserted, the new error items from the error list are inserted into the extra selections list.  Finally for the number of errors removed, the extra selections are removed from the list.  (There will never be both insertions and removals.)

A new support function was added for converting an error item to an extra selection.  If the length of the error is negative, this indicates an alternate column (which occurs in the case where there is a syntax error in the exponent of a floating point number, where the column is the beginning of the number).  For this case, the syntax error will be highlighted and not the number for a length of one character.

The format of the extra selection is set to red background.  The block for the line of the error item is retrieved from the document to get its position.  The cursor of the extra selection is set to the text cursor of the document and positioned to the error (position of the line plus the column of the error.  The cursor is moved to the end of the error with the keep anchor option, which highlights the error with the selected format.

Once the extra selections list has been updated for the change in the errors list, the edit box extra selections are set, which causes the errors to highlight.  However, there is a problem.  If a program contains errors when it is loaded, the errors are not initially highlighted.  I think this is because the edit box hasn't been drawn yet at the time the first errors changed signal is emitted.

[commit 24ae7f0467]

Error List Changes Finalized

The method of keeping a list of change operations does not work when multiple lines of the program are changed with more than one error affected because each line of the multiple line change is processed individually.  This caused errors will the same index to be repeatedly set leading to the many extra change operations being appended to the change list.  Even though this was a failed attempt, it did lead to a clue on how to get the start and end indexes of the changes method working correctly.

The index to the start of the changes only needs to be set the first time since a lower index will not be changed.  The index to the end of the changes will still be set if a higher index is changed, but with a slight modification.

The clue to the solution came from the debug output in the edit box receiving errors changed signal.  As the list of changes were processed, the debug code simply incremented the index for each change operation except for a remove operation.  The index was not incremented for a remove operation since an error was removed from the list and the next operation applied to the same index.

Therefore, before checking if end change index needs to be set to the current higher index, the index is decremented first for a remove operation.  The edit box will determines the number of errors that have changed by subtracting the start from the end index and adding one.  For example, for a single remove operation, the end index will be one less than the start index, so the number of errors changes will calculate to zero.  The number of errors removed (or inserted) is determined by the change in the size of the error list.

The debug output code in the edit box was updated to allow for an end index to be one less than the start index.  The code still outputs asterisks for errors that changed (because the index is within the start and end indexes of the changes), but now outputs a minus if no errors were changed (only removed).

[commit 9ea17018cc]

Error List Changes Revisited

Using a start and an end index to track changes to the error list is not sufficient to be able to reproduce the changes in the edit box.  A simple example of this is if one error inserted and one error removed.  The next effect is that one error is changed.  However, the start and end indexes will indicate that two lines were changed.

A new scheme was implemented where there is just a start index (renamed to simply change index) and a list of change operations preformed on the error list (insert, change and remove).  This will allow the edit box to repeat the operations that were performed starting at the change index.

This scheme works because as the change list is built as a program update is processed, the index of each change will be sequential.  However, while this works for single line changes (or a group of lines with a single error change), it doesn't work when multiple lines are changed (like with a multiple line insert or delete).  Too many changes operations are appended to the change list because each line of the program update change is processed individually.

[commit 28af130fef]

RPN List – Error Storage

The RPN list class was storing the token where an error was detected, but it only really needed the column and length.  Therefore, the code was changed to only store the column and length of the error.

While these changes were being made and tested, translator test #14 (parser errors) failed because there were extra blank lines after error messages.  This extra blank line was left in so that the result files would not need to be changed, but this did not affect parser errors.  The output of the extra blank line was removed and expected results files were updated.

[commit fdb798281c]