Parsing Operators

When neither an identifier or constant was found then the Parser will assume that the token will be an operator. The Operator Table is search for the single character. If not found in the table, then a syntax error is reported. Each table entry will have a two character flag if the operator can also be part of a two character operator (for example, < and > will have this flag set). If the entry does not have this two character flag set, then the internal code for the operator is returned.

For table entries with the two character flag, if the next character is not white space, the Operator Table is searched for the two character operator. If found, then the internal code for the operator is returned.  Otherwise the internal code for the single character operator is returned (assuming the single character is a valid operator, otherwise a syntax error is reported).

Parsing Constants

When a digit or period is found, the parser will look for a numeric constant. Some checks are needed. A leading zero must be followed by a period or the zero is taken alone. Only one period is allowed in a constant; finding a second period will terminate the constant. Finding an “e” or “E” will cause an exponent to be scanned (an optional sign followed by digits).

Once the constant has been scanned, if the constant did not have no decimal point or exponent, then an attempt will be made to convert the string into an integer. If this fails because the value is too large, then it will be converted into a double. If the conversion to double fails (overflow or underflow) then a syntax error will reported.

When a double-quote is found, the parser will look for a string constant. Two double-quotes will be converted into a single double-quote.  The string is terminated upon reaching the ending double-quote.  A syntax error will be reported if the end of the line is reached before the ending double-quote.

Parsing Identifiers

Once a letter is found, the parser will continue collecting letters, digits and under-bars. When no more are found, the next character is checked for a data type symbol (“%”, “$” or “#”) and if found the data type will be set to an integer, string or double (initially set to none). Finally, the next character is checked for an opening parenthesis, and if found a parenthesis flag is set. If the the first two characters are FN, then the token type is set to Defined Functioned, and the string is returned along with the data type and parenthesis flag.

The Operator Table will then be searched for the identifier. If the identifier is found in the table and the entry is not flagged that the word is part of a two word command, then the internal code for the command, operator or internal function will be returned for the token along data type (internal function only). No string from the input needs to be returned.

If the table entry is flagged that the command is part of a two word command, then a second identifier after white space is read from the input. The second identifier will not have a data type symbol or parenthesis. The Operator Table is searched again for the two word identifier (with one space between). If found then the internal code for the command will be returned. If not found and if the first word by itself is a valid command, then the internal code for the command is returned; otherwise a syntax error is reported at the second word.

If the identifier was not found in the table, then is could be a Variable, Array, Generic Function or Subroutine name. At this point, the Parser has insufficient information to determine which of these types the identifier is. The global or local dictionaries would need to be checked and this is beyond the scope for the Parser (this will be handled by the Translator or Encoder). The Parser will simply return a type of No Parenthesis or Parenthesis.

Parser – Token Identification

There are four major types of tokens, an identifier, a constant (numeric or string), a symbol character or two representing operators, and a remark (comment). Tokens don't contain white space (spaces or tabs), so any white space will normally separate tokens, though a between identifiers or constant an symbols will not require white space. In obtaining a token, any white space will be skipped, then the next character will be checked.

An identifier starts with a letter; contains letters, digits and/or under-bars; and ends with an optional data type symbol and possibly an opening parenthesis. Some operators are also made up of letters, for example, MOD, AND, OR, etc. One wrinkle, some BASIC commands may consist of two words separated with white space, for example SELECT CASE, END IF, EXIT FOR, etc.

A numeric constant starts with a digit or decimal point; contains digits and/or decimal point; and possibly ends with an exponent (“e” or “E”, optional sign and digits). Only one decimal point is allowed and a second one will terminate the token as would a second “e” or “E”. (For example, 0.010.02, would be two constant tokens 0.010 and .02, and this will generate an error downstream in the translator – the Parser just separates the input into tokens.)

A string constant starts with a double-quote; contains any characters; up to the next double-quote. Two double quotes in a row would place a single double-quote in the string constant.

An operator character is any other valid operator symbol (for example, +, -, etc. including comma, semicolon and colon – basically any valid BASIC character that's not part of an identifier or constant). Operators can also contain multiple character operators (for example >=, <=, <>), but also be single character operators (=, <, >) and some single characters operators can be next to each each (for example +-, which is PLUS followed by unary MINUS).

(New) A remark can start with a REM command, but must be followed by white-space and if not the first command on the line, must be preceded by a colon statement separator.  Comments can also start with a single-quote (it appears the ANSI standard allows exclamation point for comments, aka TrueBasic and ECMA-116, but most of the other BASICs I checked use single-quote including G/W-Basic, QuickBasic, VisualBasic, FreeBasic, xBasic, PowerBasic, SmallBasic, and thinBasic; therfore I'm going with the crowd).  When using a single-quote, it does not need to be followed by white-space or preceded by a colon.  All characters following the REM or single-quote up to the end of the line will be taken as the comment.

Updated Wednesday, January 6, 2010; 11.01 pm: Added information about remarks.

Language Definition – Constants

One final item before moving on to the implementation of the Parser. In the Parser, numeric constants are not signed. Any plus or minus sign will be treated as a unary operator as far as token parsing is concerned.  If later during translation, a constant has a unary operator, then it will be folded into the constant. The Parser and/or Translator can't assume that a plus or minus is part of the constant too soon, take the example A‑5, if the constant is ‑5, then this expression would have two tokens, A and ‑5, and would have no operator, which is an error.

Integer constants will be any numeric value that fits in an integer and does not have a decimal point. Double (floating point) constants will have a decimal point, an optional exponent (“e” or “E” followed by an optional sign and some digits), or will not fit in a integer. Integers will be 32‑bit values having a range of ‑2,147,483,648 to 2,147,483,647, however, since there is no sign, the value ‑2,147,483,648 is not possible. Double precision values have a range of approximately 1e‑308 to 1e+308.

String constants start and end with a double quote. There will also be an easy way of putting double quotes in a string constant because using "hello "+CHR$(34)+"world"+CHR$(34) is cumbersome and unintuitive. The C style like "hello \"world\"" (also used by xBasic) is not desirable either. TrueBasic's method is two double quotes like "hello ""world""" is probably the best solution, so that method will be used.

Language Definition – Subroutines

Subroutines are similar to functions except subroutines have no return value and therefore the identifier name does not have a data type symbol. The general syntax for a subroutine is:

    SUB sub_name(arguments)
   ...
    END SUB

The arguments will be optional. Arguments will be called by reference if a variable or array element is used as an argument, otherwise the arguments are by values. The arguments will be treated as local variables, except if called by reference, modifying the local variable was also modify the caller's variable or array element. The by reference call can be prevented by surrounding the argument in the function call by parentheses as in (A). Entire arrays can be passed by reference by using just the array name in the subroutine call.

Subroutines may call themselves recursively. It is up to the programmer to prevent an infinite loop, though eventually memory will run out as each subroutine call will increase the size of the stack.

The subroutine will return upon a RETURN statement or when the END SUB statement is reached. The SUB will not be executed upon reaching the SUB statement, execution will proceed to the after the END SUB statement. The subroutine will be called using a CALL statement as:

    CALL sub_name(arguments)

Updated Saturday January 2, 2010; 9:45am: Looks like most of the BASICs use just "SUB" for subroutine, so I decided to also use just SUB instead of SUBROUTINE. 

Language Definition – Generic Functions

The second type of functions being supported are generic or multiple line functions.  These functions are defined with a FUNCTION statement and whose identifier can be any standard identifier name with an optional data type symbol.  The general syntax for a function is:

    FUNCTION function_name(arguments)
        ...
        function_name = <return value>
        ...
    END FUNCTION

Language Definition – User Defined Functions

The first type of functions being supported are the classic BASIC user defined or single statement functions.  These functions are defined with a DEF statement and whose identifier name starts with FN.  They may contain multiple arguments or no arguments.  The entire function must be defined on one statement (line), though multiple user functions can be defined on the same line separated by colons.  Two examples are:

    DEF FNHypot(X,Y)=SQR(X*X+Y*Y)
    DEF FNLength=LEN(First$+Last$)

Using FN for these functions means that there can be no other variables, arrays, functions or subroutines that start with FN.  These user functions may also have data type (the default type is double precision).  The user function arguments are considered local variables to the function and are not related to variables of the same name outside the function.  For the example above, X and Y are local to FNHypot(), but X and Y outside of the function will not be affected when FNHypot() is called.  The variables in FNLength are not arguments and are therefore not local.  Any variables used in a function not listed as arguments are regular variables.  These functions may also call other functions, but there needs to be check to make sure the function does not call itself.

Language Definition – Identifiers

Before getting into how the Parser is going to identify token types, there needs to some definition of what the identifiers will look like.  There will be no limit placed on the size of identifiers, however, there is a practical upper limit because of the program line length.  While I would like to limit line lengths to say 80 characters, this is probably not realistic.  Some type of line wrapping will be necessary, but that's a problem for another day.

Identifiers must start with a letter, but may contain any number of letters and numbers plus the under-bar character.  Identifiers will be case insensitive, however, identifiers will be saved as first entered.  In other words, if a variable name like SomeVariableName is entered, that's how it will be saved, but any form like somevariablename, SOMEVARIABLENAME, SOMEvariableName, etc. will refer to the same variable, but the name will be displayed as it was first entered.  (There will be allowance to rename variables later.)

Identifiers must be unique between variables, arrays, functions, subroutines and must not be any of the reserved BASIC commands and operators (e.g. PRINT, IF, etc. or even say Print, however the reserved BASIC command can be used within an identifier, for example, Print5 is acceptable).  At the end of the identifier can be an optional symbol for the data type: “%” for integer, “$” for string, and “#” for double precision (the default).  Later perhaps single precision can be supported with a “!” character.  The data type symbol is considered part of the name, therefore the variable names Variable, Variable% and Variable$ all refer to different variables and may all be contained in a program.

Arrays, functions and subroutine identifier names contain an opening parenthesis at the end with no intervening white space.  Note that while the opening parenthesis is considered part of the identifier, it is not stored.  Therefore, having both Variable and Variable() in the same program is not allowed.  This will allow array names to be used without the parentheses like in passing an entire array to a function or subroutine and MAT statements if implemented.  Subroutine identifier names do not have a data type symbol as they don't have a return value.

Parser

The parser needs to take an input line and separate out tokens so that the translator can begin the process of converting the line into the internal RPN format. The tokens will be one of several different types:

1. Command Name
2. Internal Function Name
3. Remark (Comment)  (New)
4. Operator
5. Variable Name
6. Array Name
7. User Function Name
8. Constant

The first four on this list are part of the BASIC language and will be in listed in the Operator Table. The Operator Table will contain several pieces of information like the priority of the operator, the internal code of the operator, the string representation of the operator (used by the Parser and the Recreator), the function to call when running the program, etc. The items in the Operator Table will be expanded as the Interactive BASIC Compiler is developed.  For now the Operator Table will contain the strings and the type (command, internal function or operator). For functions, there will also be a data type (integer, double, string or print).  (New) Comments will require special handling by the parser.

The last four on this list each will also have a data type associated with them. If a token is not found in the Operator Table, then it is a member of one of the last four, or it is an invalid token (for example, if a symbol is found that is not an operator).

The Parser will return one token with a type and data type at a time. Along with each token will be the column that the token starts. This column will be used for error reporting. There's no point in converting the entire line into tokens before the tokens are processed.

Updated Wednesday, January 6, 2010; 10.55 pm: Added information about remarks.

List Class – Testing and Release

I wrote three simple functions to test the list class template (plus three functions to print the contents of the stack).  The first first test function one tests an integer stack.  The second test function defines a simple structure consisting of an integer and a character pointer (string).  I think the parser (the next item to implement) will need a similar structure to hold pointer to the token string from the input line along with the column the token begins (needed to report the location of syntax errors).  The third test function defines a simple enumeration to tests an enumeration stack.

It was during this testing I realized two things.  First that I wanted to pass structure values to push onto the stack or pop from the stack by pointers and not by values (passing the entire structure is not efficient).  A second was that I still wanted to be able to push constants for lists of simple types.  I know this functionality will be needed for the operator stack in the translator.  Therefore, this required two sets of push/pop functions.  The same function names could be used because of C++'s overloading function name feature.  I made the pop by pointer function return the status of whether the stack is empty before a value is popped, in other words, if false is returned, the stack is empty and no value is returned.

I have released this code so far.  The ibcp_0.0.1-src.zip file has been uploaded at Sourceforge IBCP Project.  The .zip file contains the list.h file with the list template class, the test_stack.cpp source file for testing lists (stacks), the VIDE2 project file test_stack.vpj and Makefile.v, both generated by VIDE2.  The project was compiled using Borland C++ 5.5.  (I have yet to get GCC working under MinGW for use with VIDE2 – something I will keep trying as I want to eventually compare the two compilers.)

List Class – Implementation

A class template does not actually generate any code, so all the functions will be written directly in the header (.h) file (which turns out to be necessary to properly instantiate an actual list in the code).  To instantiate a list, the following is used:

    List<int> int_stack;
    List<some_struct> some_struct_stack;

To create a pointer to element within the list, the following is used:

    List<int>::Element *int_element;
    List<some_struct>::Element *some_element;

Note that the struct Element is defined as public to allow this (though the master element pointer is private).   The functions implemented initially are:

    List() – constructor; allocates master element and initializes it
    ~List() – destructor; deallocates any elements in list and master element
    bool empty() – checks if list is currently empty
    Element *top() – get a pointer to element on top of stack.
    push(T value) – pushes  value (by value) on stack
    T pop() - pops value from top of stack (must not be empty)
    push(T *value) – pushes value (by pointer) on stack
    bool pop(T *value) – pops value (by pointer) from top of stack (if not empty)
    first(Element *&element) – sets pointer to first element
    next(Element *&element) – sets pointer to next element
    bool not_end(Element *&element) – check if not end

There are two sets of push and pop functions.  One set works with actual values and is more appropriate for lists of simple types (int, doubles, enums, etc.).  The other set works with pointers to the actual values, which is better for lists of structures, but can be used for simple types also.  I implemented the by value push and pop so that constants could be pushed directly without having to define a variable and set it to the value to push.  I foresee this may be necessary for some of the stacks.  Note that the pop value by value function does not return any status of the list being empty, and therefore the list must not be empty before using this function.  I also added the three functions for use with for statements.  Any additional functions will be added to the list class template as needed.

List Class – Design

There will be several different stacks needed.  Each type of stack would have the same functionality but would hold a different type of items. The best way to implement this is by using a class template.  The list class template will have and element contained the next and previous link pointers plus the generic value. The beginning of the list class will be defined as:

    template <class T> List {...}

Where T is the generic type that the list will hold.  This generic type could be a simple like an int or double, or could be a structure. The internal element structure containing the links and value will be defined as:

    struct Element {
Element *prev;
Element *next;
T value;
    };

The list will have a master element pointer that will be a pointer to Element but that actually element allocated will be without the T value; in other words, allocated for sizeof(Element) – sizeof(T). The master element pointer will be allocated and initialized in the constructor function.

The master->next variable will point to the first element in the list (i.e. bottom of a stack) and the master->prev variable will pointer to the last element in the list (i.e. the top of a stack). Implementation of the various functions is simplified if the list is circular, in other words, the last element's next pointer points back to the master element (and the first element's previous pointer also points back to the master element). In an empty list, both the master element's next and previous pointers would point to the master element. Therefore, the master element's pointers will be initialized this way after it is allocated.

Popping Items From Middle of Stack

I initially thought there was a need to pop items from the middle of stack, specifically for functions and subroutine calls.  Essentially the thinking was that the function or subroutine call would push the arguments on the stack, then upon executing the function/subroutine, it would save the current top of the stack, push it's argument references on the stack (because that is what would be written in the internal language), and then it would pop from the two places as it filled the local variables that represented the arguments.  I won't go into any more details because this is probably not the best way to implement function/subroutine calls.

The way C/C++ works internally is that the arguments are pushed onto the stack, and the function (there are technically no subroutines in C/C++, all routines are functions, though some functions can be defined with void return value, i.e. no return value), uses the values on the stacks as the local variables for the arguments within the function (other local variable are also on the stack below the arguments).  C/C++ only passes by value, not by reference (though by reference is emulated using pointers and C++ actually does has references, but it is still done by pointers internally).

Now I think emulating this function/subroutine call mechanism where the local variables representing the arguments are the values on the stack is a better way.  This mechanism does not need to pop items from the middle of the stack, so this functionality is not necessary.  Though technically, this is the same as removing items from the middle of a list, and I believe will be needed, though not for stacks, but for more generic lists.

Reading Stacks From Bottom to Top

Take the example of a PRINT statement as follows:

    PRINT A;TAB(20);B,C

I'm anticipating that this will be encoded into the internal language symbolically as follows:

    A 20 TAB B COMMA C PRINTNL

Note that semicolons are not encoded, but assumed between expressions.  There will also be two types of PRINT statements, one with an implied new-line (PRINTNL) and one that ends with a semicolons or commas to stay on the current line (PRINT).

When this command is executed, the expression stack will look as follows after all the parts are executed up to the PRINTNL command:

    A <-- bottom
    TAB(20)
    B
    COMMA
    C <-- top

When the PRINTNL is read, the PRINTNL command code will be called.  To print the items in order (i.e. A first), the stack will need to be read from from the bottom to the top.  The expressions and functions could be written into the internal language backwards so they will be on the stack in the correct order during run time (to pull each from the top), but this will complicate the translator and the recreator, plus the expressions would be evaluated backwards, an idea I'm not comfortable with.  Therefore, it's easiest to keep them in the same order as entered, hence the need to read the stack from the bottom to the top.

Stacks, Queue and Lists

A stack is a Last-In-First-Out (LIFO) list, a queue is a First-In-First-Out (FIFO) list, and a list is an Any-In-Any-Out list meaning elements can added to the beginning, middle or end of a list and elements can be removed from the beginning, middle or end of the list.  Stacks inside the computer are essentially implemented as an array with an index pointing to the top of the stack, growing as large as needed given available memory.  To implement this in a higher level language like C++, this type of implementation would need a fixed size of memory allocated.  Changing the size during run time, while not impossible, is not practical or efficiently.

A better way to implement a stack in C++ is as a linked list, because memory does not need to be allocated ahead of time for the stack whose size is not yet known.  To add a new element to the top of the stack, a single element is allocated from the free memory heap, then linked into the current list.  To remove the element from the top of the stack, it is simply de-linked from the stack and the item is deallocated back to the free memory heap.  This method requires an overhead of a link with each item (that points to the next item on the stack) and the stack would contain a pointer to the top element (or a NULL pointer if the stack is empty).

However, as will be explained, there will be occasions where it will be necessary to read a stack from the bottom to the top.  And there will be occasions where it will be necessary to pop an item from the middle and remove it.

Using the single link method, a stack cannot be read from the bottom to the top or read and removed items from the middle.  In order to support this, a double link method will be needed, which is required for an AIAO list.  One link points to the next item in the list, the other link points to the previous item in the list.  A list class will be implemented to support lists, stacks and queues.