Write an interpreter that executes programs written in OSIL: Our Simple Imperative Language. OSIL is a toy language that demonstrates some of the basics of imperative programming. It only has six different types of statements. The syntax is similar to simplified Pascal, and the intended meaning of statements should be readily apparent to most programmers. Here is an example OSIL program that computes the sum of the integers from 1 to 5:
n := 5 ;
s := 0 ;
while n do
begin
s := s + n ;
n := n - 1 ;
end ;
print s ;
Here is another example, that prints the positive even integers less than 10:
n := 1 ;
e := 0 ;
while 10 - n do
begin
if e then
begin
print n ;
e := 0 - 1 ;
end ;
else
skip ;
n := n + 1 ;
e := e + 1 ;
end ;
OSIL has just one data type, integer, and variables are not declared.
All variable names are single letters. In the while and
if statements, a positive expression value is interpreted
as true while 0 and negative values are interpreted as false. The
six kinds of statements supporting in our language are:
skip statements (null or "no-op" statements)
print statements
if statements
while statements
begin/end statements)
For simplicity, OSIL also obeys the following rules:
The arithmetic expressions in OSIL consist only of integer literal values and +/- operators (addition and subtraction). Operators are processed left to right as they occur (no operator precedence is used).
All tokens in OSIL are also separated by white space. In other
words, you cannot write x:=y+z;. You must instead
write x := y + z ;.
There are no comments in OSIL.
OSIL is case-sensitive.
No line of an OSIL program will exceed 255 characters. Otherwise, sequences of two or more white space characters are treated as a single space. Newlines are treated the same as other white space characters.
For this assignment, your program must be written in Pascal. Your solution may only use standard Pascal code, not extensions or special library routines provided with your compiler. Your program must adhere to proper use of the Pascal language as well as good programming style, including embedded routines, scoping, parameter passing, identifier naming, routine length, etc.
Your program should read and execute an OSIL program, which consists of a sequence of zero or more OSIL statements, from its standard input (in the sense that this exists in Pascal). The "end" of the OSIL program is indicated by EOF on standard input.
OSIL programs are made up of the following tokens:
begin
do
else
end
if
print
skip
then
while
To be more precise, the following EBNF grammar describes the syntax of allowable OSIL programs:
<program> --> { <statement> }
<statement> --> <assignment_stmt>
| <print_stmt>
| <block_stmt>
| <if_stmt>
| <while_stmt>
| skip ;
<assignment_stmt> --> <variable> := <expression> ;
<print_stmt> --> print <expression> ;
<block_stmt> --> begin { <statement> } end ;
<if_stmt> --> if <expression> then <statement> else <statement>
<while_stmt> --> while <expression> do <statement>
<expression> --> <operand> { ( + | - ) <operand> }
<operand> --> <variable>
| <integer>
<variable> --> a | b | c | d | e | f | g | h | i | j | k | l | m
| n | o | p | q | r | s | t | u | v | w | x | y | z
<integer> --> a sequence of one or more digits
Variables: Think of the 26 variables as "global" variables that are initialized to 0 at the start of the OSIL program.
Assignment: An assignment expression contains a variable on the left hand side and a value on the right:
x := 2 + 3 ;
The meaning of such a statement is to compute the value on the right, then assign it to the variable on the left.
Precedence: The grammar above indicates all arithmetic operators (that is, + and - in this case) are of equal precedence.
Associativity: As with most languages, the expectation here is that operators at the same precedence level should be left-associative. Your solution must implement associativity correctly.
Your interpreter will execute each statement it reads in from the
input OSIL program. Most statements will only result in internal
state changes within the interpreter, however, and will not produce
any visible output. Only the print statement produces
output. Each print statement should print the corresponding
expression value followed by a newline on standard output.
Your interpreter may also encounter invalid statements in the OSIL input. This can happen for one of two reasons. First, the input may contain invalid token(s), such as misspelled keywords, , missing white space between tokens, inappropriate punctuation, or incorrect operator symbols. Second, the input may contain correct tokens but still fail to match the grammar listed in this assignment--a "syntax error." If either happens, your program is to print the following error message on standard output:
Incorrect statement syntax.
Because of the use of the Curator, be sure your error message appears exactly as above (without any leading or trailing white space).
After printing the error message, your interpreter should "skip
ahead" to just past the next semicolon in the input, and
resume by interpreting the <statement> that
follows.
Here are some random bits of Pascal information that you may or may not find useful as you implement this assignment:
Free Pascal supports a string type called String.
By default, this type supports strings up to 255 characters in
length. Strings are stored as character arrays, with a "hidden"
byte at the beginning to record the current length of the string.
Unlike C, C++, or Java, in Pascal, the first character in a string
is at index position 1.
See Section 2.13.2.4 of the FP Reference Guide
for details on the basic functions supported for strings.
String comparisons are performed using "=":
s : String;
...
if s = "while" then
...
You can use readln(s); to read all characters on
the current input line into a string variable s, and
then advance over the newline to the start of the next line. Each
OSIL input line will be no longer than 255 characters.
You can use writeln(x); to print out any value
of any scalar type.
You can use ord(c) to convert any character
c into its corresponding ASCII code as an integer.
You can use chr(x) to convert an integer value
x into a character with the corresponding ASCII code.
You can use val(s, x, err) to parse a
string s into its corresponding integer value, which
will be placed in x. The integer err will be
set to the result code of the operation (0 for success, or the
position where parsing failed if there was an error).
You can use copy(s, start, len) to extract a
substring from a string, or use
delete(s, start, len)
to remove characters from a string.
You can use a forward declaration to introduce a subroutine's name and parameter profile (so it can be called by others) before you give its implementation. This is necessary for mutually recursive or mutually dependent operations.
Your Pascal implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Pascal procedure/function should be preceded by a comment block explaining its purpose, the meaning of each parameter, and the general strategy of its implementation if applicable.
Your program will be submitted electronically through the Curator for automatic grading against a randomly generated test suite. To submit your program, login to the Curator using your PID and password. Be sure to select the 91389-CS 3304 Comparative Languages section when logging in. Click on "Submit", choose 1-Pascal from the project drop-down list, click "Browse" to specify your solution, and then click "Upload."
In addition, you must also turn in a printed version of your program source in class according to the rules specified in the syllabus, which also describes the late policy. Your hardcopy printout must match the highest-scoring submission sent to the Curator earliest. In other words, you may not submit your program until it works, go back and add comments and documentation, and then make a final submission of the printable version of your program. Once you receive full credit from the Curator on a submission, that is the version you must print and hand in.