1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
# IMP Interpreter
A small interpreter of the IMP programming language, written in *C*, with *flex* for lexing, and *bison* for parsing.
Currently, the core functionality of IMP is implemented, additionally, the *local variable extension*, and the *procedure extension* are also implemented.
There are some syntactic enhancements, such as the boolean constants `true` and `false`, omitting parenthesis around expressions and sequential composition, omitting the else block of an if statment, support for C-style comments of the form `/* ... */`, and the ability to add arbitrary many semicolons after each statement.
## Dependencies
- [flex](https://github.com/westes/flex) lexer generator
- [bison](https://www.gnu.org/software/bison) parser generator
- [readline](https://tiswww.case.edu/php/chet/readline/rltop.html) handling userinput for repl
## Resources
- [Formal Methods and Functional Programming (Course Webpage), ETHZ](https://infsec.ethz.ch/education/ss2025/fmfp.html)
## Build
- `make all` to build interpreter.
- `make repl` to run repl.
- `make example` to interpret "examples/example.imp".
- `make clean` to remove build folder.
All build artifacts are created in the build folder `./build`, including the imp binary (`./build/imp`).
## Usage
```
Usage: imp [ARGS]
(no args) start REPL
-i <program.imp> interpret program
-a <program.imp> print ast
-h print this message
```
REPL:
```
IMP REPL (type IMP statements or commands starting with '%')
Commands:
%quit exit
%run <program.imp> interpret program
%set <var> <val> set variable
%print [<var>] print variable, or all variables
%procedures list declared procedures
%help show this message
```
## IMP
### Example
```
procedure factorial(n;r) begin
if n <= 0 then
r := 1;
else
m := n - 1;
factorial(m;r);
r := r * n;
end;
end;
n := 5;
factorial(n;r);
```
### Syntax
- [Syntax (Reference EBNF)](/res/syntax.ebnf) might not always accurately reflect all syntax rules. (See [parser.y](src/parser.y) for current implemented parsing).
**Statement `<stm>`**
Variable assignment:
- `<var> := <aexp>` any variable not assigned, has the value 0.
Local variable:
- `var <var> := <aexp> in <stm> end`
Control flow:
- `if <bexp> then <stm> else <stm> end`
- `while <bexp> do <stm> end`
- `(<stm>; <stm>)` sequential composition, the first statement runs before the second
- `skip`, nop
Procedures:
- `procedure <ident>(<var>, ... ; <var>, ... ) begin <stm> end` declaration, first argument list are value arguments (vars passed to procedure), second argument list are variable arguments (vars returned from procedure).
- `<ident>(<var>, ... ; <var>, ... )` call
**Expression**
Arithmetic Expression `<aexp>`:
- `<num>`
- `<var>`
- `(<aexp> + <aexp>)`
- `(<aexp> - <aexp>)`
- `(<aexp> + <aexp>)`
Boolean Expression `<bexp>`:
- `not <bexp>`
- `(<bexp> or <bexp>)`
- `(<bexp> and <bexp>)`
- `<aexp> = <aexp>`
- `<aexp> # <aexp>` not equals
- `<aexp> < <aexp>`
- `<aexp> <= <aexp>`
- `<aexp> > <aexp>`
- `<aexp> >= <aexp>`
- `true`
- `false`
**Variable `<var>`**
- `<ident>`
**Numeral `<num>`**
- `[0-9]+`
**Identifier `<ident>`**
- `[a-zA-Z][A-Za-z0-9]*`
|
