Purpose
Assignment a~d are designed to familiarize you with C++ programming, tokenizers and parsers, and
1~3 are designed to familiarize you with LUA programming, parsers.
Requirements
This assignment consists of one major requirements.
1) Developing solutions to the problems below.
2) Your assignments will be checked, submitted and graded electronically.
Problem
1) Create the following C++ programs/libraries. Your programs will
follow the naming scheme specified: progX_Y.zzz Where X is the
assignment number, Y is the program/library number for the
assignment and zzz is the file extension for the particular
language we will be writing that code in. For example, the first
program for the first assignment will be in the file prog1_1.c
(Capitalization matters!). Every driver you write for this class
will start by printing a standardized header. The header will
look like this:
Assignment #X-Y,,
Only programs that have entry points will print the header.
Your program must use the strings used in the examples
provided. You do not have any creative leeway in the prompts or
the responses. Most of the grading in this course is done
automatically and the autograder is extremely unforgiving.
Please ensure that you commit and push your submission
files as well.
Not all of your programs will be a driver (have an entry
point). Some of the programs you write will be libraries for
other programs.
prog4_a
Create a C++ Tokenizer class. This Tokenizer class will consist
of both a header and a class file. You will create the prog4_a.hpp and
prog4_a.cpp
This Tokenizer class will have four public methods. First, the
constructor, which will setup/create any internal data structures you
need. Second, the destructor, which will delete any internal data
structures you created during the lifetime of the object.
Third will be a void function that takes a single string argument
name Tokenize.
This Tokenize function will tokenize the input string on the space
character. Only the following tokens are valid:
push, pop, add, sub, mul, div, mod, skip, save, get and any valid
integer.
If an input string contains a potential token that is not one of
those values the function should throw a std::exception with the
message “Unexpected token: ” where is replaced by the
unexpected token. (If the input was “foobar 3.14” only the first bad
token ‘foobar’ should cause the exception, which should read
“Unexpected token: foobar”.
Any valid input should then have all of those tokens saved inside
the tokenizer in some sort of queue structure that will return them
when requested by the GetTokens function.
Fourth will be a vector function that takes no arguments
named GetTokens.
This function will retrieve a single set of input tokens that had
previously been passed to the function Tokenize in a queue fashion
(the first input to Tokenize is the first output from GetTokens). If
there are no remaining outputs the function should throw a
std::exception with the message “No tokens”. This Tokenizer class will
be used by prog4_a.
prog4_b
Create a driver program that will take a single command line
argument which will be the name of a file. Your program should then
Tokenize each line of that file. Your program 4_b should Tokenize all
of the input before it outputs anything. If any input line would cause
a Tokenization error, print the following error message:
“Error on line : Unexpected token: ”
And stop processing the file. No other output should occur.
If there are no tokenization errors, the tokens should be printed
to STDOUT comma separated, line by line.
Example compilation:
g++ prog4_b.cpp prog4_a.cpp -o prog4_b
Example execution:
./prog4_b testfile.txt
testfile.txt contents:
push 3
foobar 3.14
pop
Example run (User input to STDIN highlighted with yellow):
Assignment #4-b, Scott Lindeneau,
Error on line 2: Unexpected token: foobar
Example execution:
./prog4_b testfile.txt
testfile.txt contents:
push 3
push 3.14
pop
Example run (User input to STDIN highlighted with yellow):
Assignment #4-b, Scott Lindeneau,
Error on line 2: Unexpected token: 3.14
Example execution:
./prog4_b testfile.txt
testfile.txt contents:
push 3
push 6
pop 6
Example run (User input to STDIN highlighted with yellow):
Assignment #4-b, Scott Lindeneau,
push,3
push,6
pop,6
prog4_c
Create a class called Parser (prog4_c.cpp and prog4_c.hpp). The
Parser will have three public functions. The constructor, and
destructor as appropriate and the boolean function Parse which will
take a single vector argument. The parse function will
validate that the input adheres to the following rules. If an input
line is valid the function should return true. If it is invalid it
should return false.
The following tokens must appear by themselves on a single line:
pop, add, sub, mul, div, mod, skip
Any other line that contains a single token is invalid.
The following tokens must appear on a single line of two tokens,
in the correct order:
push
save
get
Any other input is invalid.
prog4_d
Create a driver that tokenizes all of the input lines and then
parses all of the input lines. All of the input should be completely
tokenized before any parsing should be done. On tokenization error
your program should print an error as in prog4_b. On parseing error
your program should print: “Parse error line : ” and your
program should stop executing. When all input in valid it should be
printed line by line with commas separating the tokens.
Example compilation:
g++ prog4_d.cpp prog4_c.cpp prog4_a.cpp -o prog4_d
Example execution:
./prog4_d testfile.txt
testfile.txt contents:
push 3
pop 3
foobar 3.14
Example run (User input to STDIN highlighted with yellow):
Assignment #4-d, Scott Lindeneau,
Error on line 3: Unexpected token: foobar
Example execution:
./prog4_d testfile.txt
testfile.txt contents:
push 3
pop 3
push 6
Example run (User input to STDIN highlighted with yellow):
Assignment #4-d, Scott Lindeneau,
Parse error on line 2: pop 3
Example execution:
./prog4_d testfile.txt
testfile.txt contents:
push 3
push 6
pop
Example run (User input to STDIN highlighted with yellow):
Assignment #4-d, Scott Lindeneau,
push,3
push,6
pop
2) prog4_1.py will be implemented in Python. In prog4_1.py you will
implement the following functions:
a. Tokenize(str): This function will take in an input string and
tokenize it according to the same rules in last 4 questions. You do
not need to store the tokenized string, instead your function should
return the list of tokens if is valid. Otherwise, it should raise a
ValueError with the message “Unexpected Token: ” as in last 4
questions.
b. Parse(tokens): This function will take a list of tokens as
input that have previously been parsed by the Tokenize function.
This will validate the parse rules given during last 4 questions
and will raise a ValueError with the parse error message as
appropriate.
prog4_2.py In python, Implement a StackMachine class. Your stack
machine class should have the Execute(tokens) public function and
the CurrentLine property (intial value zero). You may implement
whatever internal data structures and functions are necessary
such that your stack machine is easy for you to implement.
The Execute(tokens) function should accept a list of tokens that
has previously been Tokenized and Parsed correctly. The Execute
function will then perform. the operation defined in the list of
tokens as specified by the operation. (Not all operations will
return a value, some will):
• push # -- Pushes the number onto the stack. Returns None.
• pop -- Pops the top of the stack. Returns the popped
value.
• add -- Pops two values off the stack, adds them pushes
the result. Returns None.
• sub -- Pops two, subtracts the second from the first,
pushes result. Returns None.
• mul -- Pops two, multiples, pushes result. Returns None.
• div -- Pops two, divides the first by the second, pushes
result. Returns None.
• mod -- Pops two, remainder of first divided by second,
pushes result. Returns None.
• skip -- Pops two, if the first value is ZERO, changes the
CurrentLine property by the second value. If the first value is
not zero, nothing extra occurs. Returns None.
• save # -- Pops one, saves that value for future retrival.
Returns None.
• get # -- Pops zero. Gets a previously saved value and
pushes it on the stack. A saved value may be gotten multiple
times. For example, if the top of the stack is 3, and the
‘save 1’ operation occurs, the 3 is popped off the stack and
saved to some ancillary memory (probably a list). Then whenever a
‘get 1’ operation is executed that value of 3 is pushed onto the
stack until the value stored in memory 1 is replaced with a
different ‘save 1’ operation. (You can think about this as hard
array access if you like… because that’s what memory really is).
Returns None.
Whenever the Execute(tokens) function finishes executing the
operation specified by the tokens, the property CurrentLine is
incremented by 1.
If, at any time, your program attempts to pop a value that
doesn’t exist, or get a value that has not previously been saved,
raise an IndexError with the message “Invalid Memory Access”.
prog4_3.py In python, you are going to implement a driver program.
You should import the functions/classes you have implemented in
prog4_1.py and prog4_2.py. Your driver should use a main function
specification and read the first command line argument as a file.
Your program should tokenize and parse all of the lines of the
file. You should tokenize all of the lines before you begin
parsing (same behavior. as question 4_a ~ 4_d). Your program
should then parse all of the lines. As all of the lines have been
tokenized and parsed, they should be stored in an indexable
structure so that you can randomly get the tokens for any line by
line number (start indexing at 0). Your program should then
instantiate a StackMachine class and it should then begin
executing operations one line at a time, dictated by the
StackMachine CurrentLine property. This should continue until the
StackMachine CurrentLine property is equal to or greater than the
number of lines in the file (because the first line is index at
zero and is line zero internally). If at any time the
StackMachine raises an IndexError your program should print the
IndexError message along with the line number that currently
caused it with the following message: “Line #: ‘’ caused
Invalid Memory Access.” For example: “Line 3: ‘pop’ caused
Invalid Memory Access”. If any of the Execution(tokens) calls
returns a non-None value, it should be printed on its own line to
STDOUT. If at anytime the CurrentLine property becomes negative,
print the following message: “Trying to execute invalid line: #”
and quit. For example: “Trying to execute invalid line: -5”
When your StackMachine stops running naturally (CurrentLine >= # of
lines in input file) your program should print: “Program terminated
correctly” and quit.