Build a hash table using chaining as the collision resolution technique. Insertions into the hash table will correspond to declarations of variables and values in a program, searches will be requests for the value of a variable. Some variables will be local and have a narrow scope while some variables will be global.

The program will take input from a file, another program written in the omnipotent programming language BORG (Bionicly Omnipotent Resistance Grinders) and generate output from this program.

The BORG language has the following commands (keywords):

  • START-FINISH blocks. Indicating different scopes.
  • COM - Single line comments: Text should be ignored if on the same line
  • VAR varName Variable Declaration, adds varName to the hash table.
  • variable = expression Assignment statements, ie GEORGE = 122. Find GEORGE in the hash table and assign 122 to it.
  • ++ - increment operator, syntax: VARIABLE ++
  • -- - decrement operator, syntax: VARIABLE --
  • expressions, expressions are limited to unary and binary arithmetic, or variable names
  • supported operators: + - / * % ^ (plus, minus, divide, multiple, modulo, exponent)
  • PRINT syntax PRINT expression. If the expression is a variable, and this variable is not in scope, then an error message indicating unknown variable x at line number y. The value printed if there is a variable in scope should be the variable with the closest scope.
  • Errors other than the print statements, our interpreter will not be responsible for detecting errors, syntax errors should be disregarded if encountered, assume that the source file is correct.

Our hash function: sum the ordinal values of the characters of the variable multiplied by their position in the string (1-indexing), then taking the modulo by TABLESIZE.

ie. The variable ABC = (65 * 1 + 66 * 2 + 67 * 3) % TABLESIZE

All tokens are separated by one space or a new line.

Output: for this assignment, run your interpreter on this sample source program as well as a program of your own, and turn it the output from both, as well as the source code from your BORG program as well as source code of the assignment and its executable. Zip is good.

Sample program and its output:

Input
COM HERE IS OUR FIRST BORG PROGRAM
COM WHAT A ROBUST LANGUAGE IT IS
START
VAR BORAMIR = 25
VAR LEGOLAS = 101
PRINT BORAMIR
BORAMIR ++
PRINT LEGOLAS
PRINT GANDALF
PRINT BORAMIR * 2
COM
COM NESTED BLOCK
COM
START
VAR GANDALF = 49
PRINT GANDALF
PRINT BORAMIR
FINISH
PRINT GANDALF
START
LEGOLAS = 1000
PRINT LEGOLAS
FINISH
PRINT LEGOLAS
LEGOLAS --
PRINT LEGOLAS
FINISH





BORAMIR IS 25

LEGOLAS IS 101
GANDALF IS UNDEFINED
BOARAMIR * 2 IS 52





GANDALF IS 49
BORAMIR IS 26

GANDALF IS UNDEFINED


LEGOLAS IS 1000

LEGOLAS IS 1000

LEGOLAS IS 999
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.