Table (Parser)

One last thing is needed before the Parser can be implemented is the Table, so named because it contains a list of the all operators and the precedence priority used in the conversion to the RPN format. However, it is also a good place to list all the commands and have them in one place, so there is only one table to search through or use during source recreation.

Eventually the Table will have many fields in it, but these will be added as needed. But for now, for the Parser, the fields that are needed are:

    string – the characters of the entry
    type – the type of the entry
    data type – data type of the entry
    code – a code for the entry
    two flag – command can have two words or operator can have two characters flag

Parser - Tokens

The Parser will return tokens, which will be contained in a structure containing the fields:

    type – the type of token
    column – the column of the input that the token started
    code – the internal code for the token
    string – pointer to the string of the token from the input
    data type – the data type of the token
    value – union of an integer and double value

Parsing Remarks

Special Note: I realized as I was thinking about the Parser, that I forgot to consider comments, or in BASIC terminology, “remarks” (i.e. the REM command). I have updated posts Parser and Parser – Token Identification with additional information about remarks. Remark tokens will be their own tokens that will include the string of the comment. There will be two different type of for remarks – the REM command and the single-quote.

Parsing remarks will require special handling. When a single word command is found, if it is REM (REM will be a single word command), then the parser will proceed to read the rest of the line and will return the REM remark token with the string of the comment.  The Translator will check to make sure there is a colon if front of the REM (ignore white-space) if it's not at the beginning of the line.

For the single-quote form of remarks, the single-quote will be treated as an operator symbol character.  When a single character operator is found, if it is a single-quote (which will be marked as a single character operator), then the parser will proceed to read the rest of the line and will return the single-quote operator, however, it will be marked as a remark, with the string of the comment.  The Translator will treat the comment as the end of the line and will make sure the command up to that point is valid if the single quote was not at the beginning of the line.  Single-quotes in the middle of a string constant will not be treated as a comment since the Parser will be collecting characters of the string constant up to the closing double-quote, in other words, the Parser will not be looking for an operator.

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.