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
|
# 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* also. Furthermore there are some syntactic enhancements, such as the boolean constants `true` and `false`, omitting parenthesis around expressions, and the ability to add arbitrary many semicolons after each statement.
## Dependencies
- [flex](https://github.com/westes/flex)
- [bison](https://www.gnu.org/software/bison)
- [readline](https://tiswww.case.edu/php/chet/readline/rltop.html)
## 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 "example/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]
-i <program.imp> interpret program and exit
(no args) start REPL
-h show this message
```
### REPL
```
IMP REPL (type IMP statements or commands starting with '%')
Commands:
%quit exit
%run <path/to/file.imp> interpret program
%set <var> <val> set variable
%print [<var>] print variable, or all variables
%help show this message
```
## IMP
### Syntax
[Syntax](/res/syntax.ebnf)
**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]*`
### 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);
```
|
