Interpreter for Mini Aarne Ranta Assigment 2, Compiler Construction Hands-On, Sun Yat-Sen University, 2016 %!target:html %!postproc(html): #NEW =Summary= The objective of this assignment is to write an interpreter for a simple C-like programming language. The interpreter should run programs and correctly perform all their output actions. Before the work can be submitted, the interpreter has to pass some tests, given in the [example directory examples/]. The recommended implementation is via a BNF grammar processed by the BNF Converter (BNFC) tool. The grammar built in Assignment 1 can be used. #NEW =Method= Syntax-directed translation implemented with pattern matching. You can take the code for [MCalc ../mcalc/] as starting point. #NEW =Language specification= The language is the same as in Assignment 1, and you can use the same grammar file. =Values= There are five types of values: - integer values, e.g. -47 - double values, e.g. 3.14159 - string values, e.g. "hello world" - boolean values, ``true`` and ``false`` - a void value, which need never be shown Instead of boolean values, you may use integers. Then ``true`` can be interpreted as 1 and ``false`` as 0. 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== The statements in a program are executed in the order defined by their 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 ``print`` statement evaluates the argument expression and outputs its value. #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 "hello world" ``` 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 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``. Addition expressions for string arguments are interpreted by concatenation, without any intervening spaces. 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 (or an integer, if you use integers to represent booleans). 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 =Solution format= ==Input and output== The interpreter must be a program called ``imini``, which is executed by the command ``` imini ``` 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 ``SYNTAX ERROR`` as in Assignment 1. =Success criteria= Your interpreter must interpret all [example programs examples/]. Your solution must be written in an easily readable and maintainable way. An easy way to test interpreter is to run the test file [test2.sh ./test2.sh]. In a Unix shell, you can use the command ``source test2.sh``. This assumes that - your interpreter ``imini.hs`` is in the same directory - you have a copy of ``examples/`` or a symbolic link to it in the same directory. Running the test produces the file ``log2.txt``, which you must submit together with the file ``Interpreter.hs``. =An optional extension: functions= This is based on the extension of the grammar in Assignment 1 with functions and function calls, and uses the grammar that you wrote there. The recommended procedure is two passes: + build a symbol table that for every function gives it source code syntax tree + interpret the program by eveluating the expression ``main()`` The evaluation of a function call starts by evaluting the arguments and building an environment where the received values are assigned to the argument variables (a.k.a. parameters) of the function. The statements in the body are then executed in the order defined by their textual order as altered by ``while`` loops and ``if`` conditions. The function returns a value, which is obtained from a ``return`` statement. This statement can be assumed to be the in the last statement of the function body: either alone, or in the branches of an ``if-else`` statement. If the return type is ``void``, no return statement is required. Your interpreter must interpret all [additional example programs fun-examples/].