imp-interpreter

Interpreter for the IMP programming language

IMPI 2.0

This version implements the same features, I just got tired of the disgusting parser for the first version. It uses error productions to improve error messages and its parser is slightly less terrible.

IMPI 2.0 can be compiled in the directory imp2 with javac imp2/*.java and executed by java imp2.Imp, followed by the program arguments.

It features a debugger (-d or --debug when executing the interpreter), and it allows multiline input (-m or --multiline), where the input must be terminated by a !.

The original version is still in this repository, but it's very bad, don't use it please.

Grammar

The following is the grammar of IMP used for this interpreter, specified in EBNF:

<S>        <= <Stm> | <ProcDef> | <BExp> | <AExp>
<Stm>      <= <Single> | <Assign> | <If> | <While> | <Scope> | <Seq> | <Nd> | <Call>

<ProcDef>  <= 'procedure' <Id> '(' [ { <Id> ',' } <Id> ] ; [ { <Id> ',' } <Id> ] ')' 'begin' <Stm> 'end'

<Single>   <= 'abort' | 'print' | 'skip' | 'break'
<Assign>   <= <Id> ':=' <AExp>
<If>       <= 'if' <BExp> 'then' <Stm> [ 'else' <Stm> ] 'end'
<While>    <= 'while' <BExp> 'do' <Stm> 'end'
<For>      <= 'for' <Id> ':=' <AExp> 'to' <AExp> 'do' <Stm> 'end'
<Scope>    <= 'var' <Assign> 'in' <Stm> 'end'
<Seq>      <= '(' <Stm> ';' <Stm> { ';' <Stm> } ')' | <Stm> { ';' <Stm> } [;]
<Nd>       <= <Stm> '|' <Stm> { '|' <Stm> }
<Call>     <= <Id> '(' [ { <AExp> ',' } <AExp> ] ';' [ { <Id> ',' } <Id> ] ')'

<BExp>     <= 'true' | 'false' | '(' <BExp> ('and' | 'or') <BExp> ')' | 'not' <BExp> | <AExp> ('<'|'<='|'>'|'>='|'='|'#') <AExp>
<AExp>     <= <Id> | <Num> | <AExp> ('+'|'-'|'*') <AExp>

<Id>       <= <Letter> { <Letter> | <Num> }  # where this isn't a keyword
<Num>      <= <Digit> { <Digit> }

Execution

IMPI 2.0 allows the user to directly enter commands in the command line, and to execute IMP programs using :l <filename> or :load <filename>.

It is possible to enter arithmetic or boolean expressions which are then evaluated and the result printed to the console.

:q (:quit) exits the shell, :c (:clear) clears the screen.

The Language

I extended the language by an additional command print which prints the program state (the values held by all defined variables). Variables which haven't been assigned a value yet are not printed, and their default value is 0, in line with the lecture's definition of variables. In the spirit of the idea that expressions don't cause side-effects, using an unassigned variable in an expression will not add it to the program state.

All extensions and syntactic sugar discussed in the lecture slides released so far have been added to the language (except for parallelism). This includes abort (which doesn't exit the shell, it only aborts the currently running list of commands!), true, false, omission of the else clause in an if statement, nondeterministic execution, variable scope as well as procedures.

The parser is relatively lax when it comes to sequences of instructions: They need to be separated by a semicolon, and they can be surrounded by parentheses (but don't have to be), and the last instruction can be terminated by a semicolon (but it doesn't have to be if the instruction sequence isn't surrounded by parentheses).

Examples

Factorial

This program defines a factorial function, calls it with argument 5 and then prints the program state.

procedure fac(n; res)
begin
    if n <= 1 then
        res := 1
    else
        fac ((n-1); res);
        res := (n * res)
    end
end;

fac(5; n);
print

The output generated by this program is:

Program State
  n -> 120

Primes

The following functions (as defined in imp2/example.imp) are used to find prime numbers and print them using print. Note that these functions are very clumsy, as IMP neither knows arrays (for e.g. implementing the Sieve of Erathostenes) nor division.

procedure divides(a, div; res) begin
	d := div;
	while d < a do
		d := (d + div)
	end;
	if d = a then
		res := 1
	else
		res := 0
	end
end;

procedure isPrime(a; res) begin
	c := 2;
	res := 1;
	while c < a do
		divides(a, c; d);
		if d = 1 then
			res := 0;
			c := a
		end;
		c := (c + 1)
	end
end;

procedure findPrimes(c;) begin
	a := 2;
	while c > 0 do
		isPrime(a; p);
		if p = 1 then
			print;
			c := (c - 1)
		end;
		a := (a + 1)
	end
end

Calling findPrimes(10;) will create the following output:

Program State
  p -> 1
  a -> 2
  c -> 10
Program State
  p -> 1
  a -> 3
  c -> 9
Program State
  p -> 1
  a -> 5
  c -> 8
Program State
  p -> 1
  a -> 7
  c -> 7
Program State
  p -> 1
  a -> 11
  c -> 6
Program State
  p -> 1
  a -> 13
  c -> 5
Program State
  p -> 1
  a -> 17
  c -> 4
Program State
  p -> 1
  a -> 19
  c -> 3
Program State
  p -> 1
  a -> 23
  c -> 2
Program State
  p -> 1
  a -> 29
  c -> 1