Villie

Interpreter of a very small subset of SML like language written in Java

Language basics

For logical expressions 0 means false and anything else means true.
The division is integer. All intermediate results should be between -2³¹ and 2³¹ - 1.
E := (E)
      | E < E | E > E | E = E | E <= E | E >= E (these result in true / false expression)
      | E + E | E - E | E * E | E / E
      | if E then E else E
      | funcName(args, ...)
      | NUM | ID

Function declarations have the form fun funcName(args, ...) = E; all in one line.

The parameters names are consisted of one letter.
The function names have two or more letters.

A function can be called from anywhere in the program as long as it is defined somewhere else in the same file.
If one line of the source file contains E; the expression is evaluated numerically and printed on the standard output.

LL(1) parser is used. LR was expected to produce too many states.
Removing left-recursion grammar refactoring leads to:

Nonterminal		Rule	Rule	Rule	Rule	Rule	Rule
E	:=	E₁E'₁
E'₁	:=	< E₁	> E₁	<= E₁	>= E₁	= E₁	ε
E₁	:=	E₂E'₂
E'₂	:=	+ E₂E'₂	- E₂E'₂	ε
E₂	:=	E₃E'₃
E'₃	:=	* E₃E'₃	/ E₃E'₃	ε
E₃	:=	ID	NUM	(E)	if E then E else E

Usage

java -jar Villie.jar [--argument] <source.code>
where --argument can be one of --recursive or --stackBased.
The default abstract machine is stack based since the recursive one is prone to StackOverflow errors.

Running Tests

The direcrory tests contains a bunch of tests. More tests can be added and they can be ran by executing run_tests.py.

Acknowledgements

Courtesy goes to Georgi Gyurchev for assembling the task and the test cases back in 2012.
I would like to thank Dr Timothy Griffin for teaching the Compiler Construction course in my Part IB year in Cambridge and Alex Chadwick for supervising me for this course (and a couple more) and encouraging me to complete this long-pending toy project.