Interpreter for C/C++ Programming Languages Course, 2011, Laboration 3 Aarne Ranta (aarne (at) chalmers.se) %!target:html %!postproc(html): #NEW =Summary= The objective of this lab is to write an interpreter for a fragment of the C++ programming language. The interpreter should run programs and correctly perform all their input and output actions. Before the lab can be submitted, the interpreter has to pass some tests, which are given on the course web page via links later in this document. The recommended implementation is via a BNF grammar processed by the BNF Converter (BNFC) tool. The syntax tree created by the parser is first type checked by using the type checker created in [Laboration 2 ../lab2/lab2.html]. The interpreter should then make another pass of the type-checked code. The fragment of C++ covered is the same as in [Laboration 2 ../lab2/lab2.html], except that the interpreter only needs to deal with programs consisting of one ``main`` function. #NEW The approximate size of the grammar is 50 rules, and the interpreter code should be 100-300 lines, depending on the programming language used. All BNFC supported languages can be used, but guidance is guaranteed only for Haskell, Java 1.5, and C++. The semantics is partially characterized by formal rules in [Lecture 8 ../../lectures/proglang-08.html]. #NEW =Method= Use the files in either of the directories - [Haskell package haskell/] - [Java 1.5 package java1.5/] Copy your ``CPP.cf`` grammar and the ``TypeChecker`` module from Lab 2 to the same directory. Edit the file ``Interpreter.hs`` or ``Interpreter.class`` till it implements a complete interpreter. One way of doing this is to copy the contents of ``TypeChecker`` and modify them - the interpreter will be structurally very similar to the type checker. #NEW =Language specification= The language is the same as in [Laboration 2 ../lab2/lab2.html]. Also its type system is the same. The type checker of Lab2 works on programs that contain any number of function definitions. The interpreter in Lab3 only needs to consider programs that have exactly one function, whose header is ``` int main () ``` The statements inside ``main`` may call the following four functions. ``` void printInt(int x) // print an integer and a newline in standard output void printDouble(double x) // print a double and a newline in standard output int readInt() // read an integer from standard input double readDouble() // read a double from standard input ``` The implementation of these function is a part of the interpreter. Their type checker can be implemented as a hard-coded signature in the type checker of lab3. #NEW =Values= There are four types of values: - integer values, e.g. -47 - double values, e.g. 3.14159 - boolean values, ``true`` and ``false`` - a void value, which need never be shown Values can be seen as a special case of expressions: as expressions that contain no variables and cannot be evaluated further. But it is recommended to have a separate datatype of values, in order to guarantee that evaluation always results in a value. Thus the evaluation of an expression in an environment should always result in a value. #NEW =Operational Semantics= ==Programs== A program is a sequence of statements, which are executed in the order defined by the textual order as altered by ``while`` loops and ``if`` conditions. #NEW ==Statements== A declaration, e.g. ``` int i ; ``` adds a variable to the current context. Its value is initialized if and only if the declaration includes an initializing expression, e.g. ``` int i = 9 ; ``` An expression statement, e.g. ``` i++ ; ``` is evaluated, and its value is ignored. A block of statements, e.g. ``` { int i = 3 ; i++ ; } ``` is interpreted in an environment where a new context is pushed on the context stack at entrance, and popped at exit. A ``while`` statement, e.g. ``` while (1 < 10){ i++ ; } ``` is interpreted so that the condition expression is first evaluated. If the value is ``true``, the body is interpreted in the resulting environment, and the ``while`` statement is executed again. If the value is ``false``, the statement after the ``while`` statement is interpreted. An ``if-else`` statement, e.g. ``` if (1 < 10) i++ ; else j++ ; ``` is interpreted so that the condition expression is first evaluated. If the value is ``true``, the statement before ``else`` is interpreted. If the value is ``false``, the statement after ``else`` is interpreted. A ``return`` statement can be interpreted as doing nothing. Alternatively, and more properly, it can be caused to terminate the program. (The test suite will not test what return does, because this paragraph was forgotten from the first version of the PM.) #NEW ==Expressions== The interpretation of an expression, also called evaluation, returns a value whose type is determined by the type of the expression. A literal, e.g. ``` 123 3.14 true ``` is not evaluated further but just converted to the corresponding value. A variable, e.g. ``` x ``` is evaluated by looking up its value in the innermost context where it occurs. If the variable is not in the context, or has no value there, the interpreter terminates with an error message ``` uninitialized variable x ``` A function call, e.g. ``` printInt(8 + 9) ``` is interpreted by first evaluating its arguments from left to right. The environment is then looked up to find out how the function is interpreted on the resulting values. Alternatively, since there are only four function calls, they can be hard-coded in the expression evaluation code. A postincrement, ``` i++ ``` has the same value as its body initially has (here ``i``). The value of the variable ``i`` is then incremented by 1. ``i--`` correspondingly decrements ``i`` by 1. If ``i`` is of type ``double``, 1.0 is used instead. A preincrement, ``` ++i ``` has the same value as ``i`` plus 1. This incremented value replaces the old value of ``i``. The decrement and double variants are analogous. The arithmetic operations addition, subtraction, multiplication, and division, ``` a + b a - b a * b a / b ``` are interpreted by evaluating their operands from left to right. The resulting values are then added, subtracted, etc., by using appropriate operations of the implementation language. We are not picky about the precision chosen, but suggest for simplicity that ``int`` should be ``int`` and ``double`` should be ``double``. Comparisons, ``` a < b a > b a >= b a <= b a == b a != b ``` are treated similarly to the arithmetic operations, using comparisons of the implementation language. The returned value must be boolean. Conjunction, ``` a && b ``` is evaluated //lazily//: first ``a`` is evaluated. If the result is ``true``, also ``b`` is evaluated, and the value of ``b`` is returned. However, if ``a`` evaluates to ``false``, then ``false`` is returned without evaluating ``b``. Disjunction, ``` a || b ``` is also evaluated lazily: first ``a`` is evaluated. If the result is ``false``, also ``b`` is evaluated, and the value of ``b`` is returned. However, if ``a`` evaluates to ``true``, then ``true`` is returned without evaluating ``b``. Assignment, ``` x = a ``` is evaluated by first evaluating ``a``. The resulting value is returned, but also the context is changed by assigning this value to the innermost occurrence of ``x``. #NEW =Lab format= ==Input and output== The interpreter must be a program called ``lab3``, which is executed by the command ``` lab3 ``` and prints its output to the standard output. The output at success must be just the output defined by the interpreter. The output at failure is an interpreter error, or a ``TYPE ERROR`` as in Lab 2, or a ``SYNTAX ERROR`` as in Lab 2. The input can be read not only from user typing on the terminal, but also from standard input redirected from a file or by ``echo``. For instance, ``` ./lab3 fibonacci.cc