PL/0 Compiler & Processor ( Part I )
Statement
Goal
In memory of Niklaus Wirth (1934-2024).In this part of the puzzle you will develop a compiler which produces PL/0 instructions.
PL/0 language was introduced in the book, Algorithms + Data Structures = Programs, by Niklaus Wirth. He is also the creator of Pascal, so do not be surprised to find some Pascal flavors in PL/0.
Grammar
Here is the EBNF definition of the PL/0 grammar:
program = block "."
block = [ "const" ident "=" number { "," ident "=" number } ";" ]
[ "var" ident { "," ident } ";" ]
{ "procedure" ident ";" block ";" } statement
statement = [ ident ":=" expr | "call" ident
| "?" ident | "!" expr
| "begin" statement { ";" statement } "end"
| "if" condition "then" statement
| "while" condition "do" statement ]
condition = "odd" expr |
expr ( "=" | "#" | "<" | "<=" | ">" | ">=" ) expr
expr = [ "+" | "-" ] term { ( "+" | "-" ) term }
term = factor { ( "*" | "/" ) factor }
factor = ident | number | "(" expr ")"
PL/0 is not case-sensitive for keywords.
number is a non-negative integer.
ident is used to name a const, var or procedure. It is alphanumerical, case-sensitive and does not start with a digit. ident is visible in the block where it is defined and all the nested blocks. ident can be overloaded with a new definition in a nested block, without affecting ident in the nesting blocks.
Error messages
If an error occurs, you need to print an error message:
• x is program line number of error
• msg is one of the following:
>
>
>
>
• w is
• s is
• elt is
If the error is an unknown variable or an element already defined, the line containing such variable or element is considered to contain the error; otherwise, the line containing the last valid token is deemed to contain the error.
Levels and addresses
Each block of PL/0 defines a level. The main block (and the variables defined there) is level 0. A procedure block defined in the main block is level 1, and one defined in level 1 is level 2, and so on.
A single stack is used for pushing and popping values. Each time a block is called, part of the stack (called a frame) is allocated to it, including 3 spaces reserved for the PL/0 processor, and 1 space for each variable (no allocation for constants). Relative address (index) is used for each frame, starting from
Instructions
8 instructions are available in PL/0. In the explanation below, l is the absolute difference in nesting levels between an ident definition and its usage, and a is a non-negative integer.
math operations:
comparison operations:
IO operations:
For
Instruction generation rules
Instructions should be generated following the program order.
expr such as
In an if/then statement, we use a conditional jump (
Every block starts with
Program lines (i.e. input) are counted starting from
Input
Line 1: An integer N the number of lines in the PL/0 program
Next N lines: Strings of PL/0 program (some lines may begin with spaces or tabs).
Next N lines: Strings of PL/0 program (some lines may begin with spaces or tabs).
Output
The PL/0 instructions (one per line) of the given program, or an error message.
Constraints
0 <= N < 100
Each line of PL/0 program is maximum 100 characters length.
All math and comparison operations work from left to right (e.g. there won't be cases like 2 + 7 * 9).
Each line of PL/0 program is maximum 100 characters length.
All math and comparison operations work from left to right (e.g. there won't be cases like 2 + 7 * 9).
Example
Input
3 const k=5; var i; begin i := k; !i end.
Output
jmp 0, 1 int 0, 4 lit 0, 5 sto 0, 3 lod 0, 3 opr 0, 13 opr 0, 0
Tags
Parsing, Interpreters, String manipulation
Difficulty
Hard
Test cases
Simple example Test
Input
3
const k=5;
var i;
begin i := k; !i end.
Output
jmp 0, 1
int 0, 4
lit 0, 5
sto 0, 3
lod 0, 3
opr 0, 13
opr 0, 0
Simple validator Validator
Input
6
var i;
begin
i := 1;
! i;
! (2 * 2 - 5)
end.
Output
jmp 0, 1
int 0, 4
lit 0, 1
sto 0, 3
lod 0, 3
opr 0, 13
lit 0, 2
lit 0, 2
opr 0, 4
lit 0, 5
opr 0, 3
opr 0, 13
opr 0, 0
While and If Test
Input
15
VAR
INPUT, COUNT;
BEGIN
COUNT := +2;
WHILE COUNT # 0 DO
BEGIN
COUNT := COUNT - 1;
? INPUT;
IF INPUT < 10 THEN
WHILE INPUT < 10 DO
! INPUT;
IF INPUT >= 10 THEN
! -1;
END
END.
Output
jmp 0, 1
int 0, 5
lit 0, 2
sto 0, 4
lod 0, 4
lit 0, 0
opr 0, 8
jpc 0, 33
lod 0, 4
lit 0, 1
opr 0, 3
sto 0, 4
opr 0, 14
sto 0, 3
lod 0, 3
lit 0, 10
opr 0, 9
jpc 0, 25
lod 0, 3
lit 0, 10
opr 0, 9
jpc 0, 25
lod 0, 3
opr 0, 13
jmp 0, 18
lod 0, 3
lit 0, 10
opr 0, 10
jpc 0, 32
lit 0, 1
opr 0, 1
opr 0, 13
jmp 0, 4
opr 0, 0
While and If validator Validator
Input
17
var a, b, c, d, e;
begin
? a;
? b;
d := 2;
while d > 0 do
begin
? c;
if c = 1 then
e := a + b;
if c # 1 then
e := a - b;
! e;
d := d - 1;
end
end.
Output
jmp 0, 1
int 0, 8
opr 0, 14
sto 0, 3
opr 0, 14
sto 0, 4
lit 0, 2
sto 0, 6
lod 0, 6
lit 0, 0
opr 0, 11
jpc 0, 37
opr 0, 14
sto 0, 5
lod 0, 5
lit 0, 1
opr 0, 7
jpc 0, 22
lod 0, 3
lod 0, 4
opr 0, 2
sto 0, 7
lod 0, 5
lit 0, 1
opr 0, 8
jpc 0, 30
lod 0, 3
lod 0, 4
opr 0, 3
sto 0, 7
lod 0, 7
opr 0, 13
lod 0, 6
lit 0, 1
opr 0, 3
sto 0, 6
jmp 0, 8
opr 0, 0
Procedure Test
Input
33
const max = 100;
var arg, ret;
procedure isprime;
var i;
begin
ret := 1;
i := 2;
while i < arg do
begin
if arg / i * i = arg then
begin
ret := 0;
i := arg;
end;
i := i + 1;
end;
end;
procedure primes;
begin
? arg;
while arg < max do
begin
call isprime;
if ret = 1 then !arg;
arg := arg + 1
end;
end;
begin
call primes
end.
Output
jmp 0, 50
jmp 0, 2
int 0, 4
lit 0, 1
sto 1, 4
lit 0, 2
sto 0, 3
lod 0, 3
lod 1, 3
opr 0, 9
jpc 0, 28
lod 1, 3
lod 0, 3
opr 0, 5
lod 0, 3
opr 0, 4
lod 1, 3
opr 0, 7
jpc 0, 23
lit 0, 0
sto 1, 4
lod 1, 3
sto 0, 3
lod 0, 3
lit 0, 1
opr 0, 2
sto 0, 3
jmp 0, 7
opr 0, 0
jmp 0, 30
int 0, 3
opr 0, 14
sto 1, 3
lod 1, 3
lit 0, 100
opr 0, 9
jpc 0, 49
cal 1, 1
lod 1, 4
lit 0, 1
opr 0, 7
jpc 0, 44
lod 1, 3
opr 0, 13
lod 1, 3
lit 0, 1
opr 0, 2
sto 1, 3
jmp 0, 33
opr 0, 0
int 0, 5
cal 0, 29
opr 0, 0
Procedure validator Validator
Input
16
VAR x, squ;
PROCEDURE square;
BEGIN
squ := x * x
END;
BEGIN
x := +1;
WHILE x <= 10 DO
BEGIN
CALL square;
! squ;
x := x + 1
END;
END.
Output
jmp 0, 8
jmp 0, 2
int 0, 3
lod 1, 3
lod 1, 3
opr 0, 4
sto 1, 4
opr 0, 0
int 0, 5
lit 0, 1
sto 0, 3
lod 0, 3
lit 0, 10
opr 0, 12
jpc 0, 23
cal 0, 1
lod 0, 4
opr 0, 13
lod 0, 3
lit 0, 1
opr 0, 2
sto 0, 3
jmp 0, 11
opr 0, 0
Unknown variable Test
Input
3
begin
i := 0;
end.
Output
Line 2: Unknown var
Unknown variable validator Validator
Input
3
var i;
begin j := i
end
Output
Line 2: Unknown var
; missing Test
Input
10
var i;
procedure sub
begin
i := 0;
end;
begin
call sub;
end.
Output
Line 3: ; missing
; missing validator Validator
Input
10
var i;
procedure sub;
begin
i := 0;
end
begin
call sub;
end.
Output
Line 6: ; missing
Invalid expression Test
Input
5
const k = 10;
var i;
begin
i := ( 2 * k * -5 ) / 3
end.
Output
Line 4: Invalid expr
Invalid expression validator Validator
Input
6
const k = 10;
var i;
begin
while i < -2 + k * -5 do
!i;
end.
Output
Line 4: Invalid expr
Missing symbol Test
Input
5
var i;
begin
? i;
if i < 10 !0;
end.
Output
Line 4: then missing
Missing symbol validator Validator
Input
6
const k = 10;
var i;
begin
while i < k
!i;
end.
Output
Line 4: do missing
Already exist Test
Input
17
var i;
procedure p;
var
i;
begin
i := 0;
end;
procedure p;
begin
i != 1;
end;
begin
call p;
end.
Output
Line 10: procedure already defined
Already exist validator Validator
Input
17
const k=10;
var i;
procedure sub;
const k=100;
begin
i := k;
end;
procedure sub;
begin
i != 0;
end;
begin
call sub;
end.
Output
Line 10: procedure already defined
Constant already exist Test
Input
10
const
k890 = 10,
k890 = 30;
var i;
begin
WHILE i < k DO
!i;
end.
Output
Line 3: const already defined
Constant already exist validator Validator
Input
11
var i;
procedure sub;
const k=1, k=2;
begin
i := 0;
end
begin
call sub;
end.
Output
Line 4: const already defined
Variable already exist Test
Input
11
var
i, i;
procedure sub;
begin
i := 0;
end
begin
call sub;
end.
Output
Line 2: var already defined
Variable already exist validator Validator
Input
3
var i, j, j;
begin j := i
end
Output
Line 1: var already defined
Invalid statement Test
Input
13
var i;
procedure sub;
const i = 2;
begin
i := 7;
end;
begin
i := 0;
call sub;
! i;
end.
Output
Line 6: Invalid statement
Invalid statement validator Validator
Input
13
var i, k;
procedure sub;
const i=5;
begin
i := k;
end;
begin
?i;
call sub;
!i;
end.
Output
Line 6: Invalid statement
Odd or Neg Test
Input
9
var i, j;
begin
? i;
j := i;
if odd i then
j := -i;
! j;
end.
Output
jmp 0, 1
int 0, 5
opr 0, 14
sto 0, 3
lod 0, 3
sto 0, 4
lod 0, 3
opr 0, 6
jpc 0, 12
lod 0, 3
opr 0, 1
sto 0, 4
lod 0, 4
opr 0, 13
opr 0, 0
Odd or Neg validator Validator
Input
11
var i;
begin
i := 10;
while i >= 0 do
begin
if odd i then
! -i;
i := i - 1;
end;
end.
Output
jmp 0, 1
int 0, 4
lit 0, 10
sto 0, 3
lod 0, 3
lit 0, 0
opr 0, 10
jpc 0, 19
lod 0, 3
opr 0, 6
jpc 0, 14
lod 0, 3
opr 0, 1
opr 0, 13
lod 0, 3
lit 0, 1
opr 0, 3
sto 0, 3
jmp 0, 4
opr 0, 0
Scope Test
Input
28
const
k = 10,
in = 100;
var
i;
procedure sub;
const
i = 5;
var k;
procedure in;
const sub=4;
var i;
begin
i := sub;
! i;
end;
begin
call in;
k := i;
! k;
end;
begin
i := k;
call sub;
! i;
end.
Output
jmp 0, 16
jmp 0, 9
jmp 0, 3
int 0, 4
lit 0, 4
sto 0, 3
lod 0, 3
opr 0, 13
opr 0, 0
int 0, 4
cal 0, 2
lit 0, 5
sto 0, 3
lod 0, 3
opr 0, 13
opr 0, 0
int 0, 4
lit 0, 10
sto 0, 3
cal 0, 1
lod 0, 3
opr 0, 13
opr 0, 0
Scope validator Validator
Input
28
const
k = 10;
var
i;
procedure sub;
const i = 9;
var k;
procedure inside;
var
sub;
begin
sub := k;
! sub;
end;
begin
k := i;
call inside;
! k;
end;
begin
i := k;
call sub;
! i;
end.
Output
jmp 0, 16
jmp 0, 9
jmp 0, 3
int 0, 4
lod 1, 3
sto 0, 3
lod 0, 3
opr 0, 13
opr 0, 0
int 0, 4
lit 0, 9
sto 0, 3
cal 0, 2
lod 0, 3
opr 0, 13
opr 0, 0
int 0, 4
lit 0, 10
sto 0, 3
cal 0, 1
lod 0, 3
opr 0, 13
opr 0, 0
No BEGIN Test
Input
10
const k=5, l=8;
PROCEDURE run;
VAR I;
WHILE I <= k DO I := I - 1;
procedure print;
! ( k * l );
call print.
Output
jmp 0, 20
jmp 0, 2
int 0, 4
lod 0, 3
lit 0, 5
opr 0, 12
jpc 0, 12
lod 0, 3
lit 0, 1
opr 0, 3
sto 0, 3
jmp 0, 3
opr 0, 0
jmp 0, 14
int 0, 3
lit 0, 5
lit 0, 8
opr 0, 4
opr 0, 13
opr 0, 0
int 0, 3
cal 0, 13
opr 0, 0
No BEGIN validator Validator
Input
19
var i, j;
procedure print;
! i;
procedure add;
const k = 10, j = 8;
i := i + j + k;
procedure ask;
begin
? i;
? j;
call add;
call print;
if i < j then while i < j do i := i + 1
end;
call ask.
Output
jmp 0, 37
jmp 0, 2
int 0, 3
lod 1, 3
opr 0, 13
opr 0, 0
jmp 0, 7
int 0, 3
lod 1, 3
lit 0, 8
opr 0, 2
lit 0, 10
opr 0, 2
sto 1, 3
opr 0, 0
jmp 0, 16
int 0, 3
opr 0, 14
sto 1, 3
opr 0, 14
sto 1, 4
cal 1, 6
cal 1, 1
lod 1, 3
lod 1, 4
opr 0, 9
jpc 0, 36
lod 1, 3
lod 1, 4
opr 0, 9
jpc 0, 36
lod 1, 3
lit 0, 1
opr 0, 2
sto 1, 3
jmp 0, 27
opr 0, 0
int 0, 5
cal 0, 15
opr 0, 0
Crazy format Test
Input
31
const I218=218;var i218;PROcedure other;begin i218:=-218; end;
procedure subI218; BEGIN
i218 := 2024;
Call
other;
While
-i218 #
(
5
+
23
)
Do
i218 := I218 + i218;
if i218=0 then
i218 :=
i218
-
1;
While i218 = I218 dO
if i218 > i218 THEN
WHILe i218 # 0 DO
if i218 = I218 tHEn
i218
:=
0
END;
begin
CaLl subI218;
end.
Output
jmp 0, 53
jmp 0, 2
int 0, 3
lit 0, 218
opr 0, 1
sto 1, 3
opr 0, 0
jmp 0, 8
int 0, 3
lit 0, 2024
sto 1, 3
cal 1, 1
lod 1, 3
opr 0, 1
lit 0, 5
lit 0, 23
opr 0, 2
opr 0, 8
jpc 0, 24
lit 0, 218
lod 1, 3
opr 0, 2
sto 1, 3
jmp 0, 12
lod 1, 3
lit 0, 0
opr 0, 7
jpc 0, 32
lod 1, 3
lit 0, 1
opr 0, 3
sto 1, 3
lod 1, 3
lit 0, 218
opr 0, 7
jpc 0, 52
lod 1, 3
lod 1, 3
opr 0, 11
jpc 0, 51
lod 1, 3
lit 0, 0
opr 0, 8
jpc 0, 51
lod 1, 3
lit 0, 218
opr 0, 7
jpc 0, 50
lit 0, 0
sto 1, 3
jmp 0, 40
jmp 0, 32
opr 0, 0
int 0, 4
cal 0, 7
opr 0, 0
Crazy format validator Validator
Input
22
CONST k2000=10;
VaR
i,I;
PROCedure div22145; begin
!
(
k2000 / 22145
+
333
) end;
begin
? I
;?i;
IF
I # i
THEN
I :=
I
-
2024;
CALL div22145;
end.
Output
jmp 0, 10
jmp 0, 2
int 0, 3
lit 0, 10
lit 0, 22145
opr 0, 5
lit 0, 333
opr 0, 2
opr 0, 13
opr 0, 0
int 0, 5
opr 0, 14
sto 0, 4
opr 0, 14
sto 0, 3
lod 0, 4
lod 0, 3
opr 0, 8
jpc 0, 23
lod 0, 4
lit 0, 2024
opr 0, 3
sto 0, 4
cal 0, 1
opr 0, 0
Nested procedures Test
Input
41
var i;
procedure f;
begin
i := i + 1;
end;
procedure g;
var j;
procedure k;
begin
j := i;
i := - 64 - j;
call f;
end;
procedure m;
begin
i := i - 1;
call k;
end;
begin
i := i + 2;
call f;
call m;
end;
procedure h;
begin
i := i + 3;
call g;
end;
begin
? i;
call h;
call g;
! i*2;
end.
Output
jmp 0, 44
jmp 0, 2
int 0, 3
lod 1, 3
lit 0, 1
opr 0, 2
sto 1, 3
opr 0, 0
jmp 0, 28
jmp 0, 10
int 0, 3
lod 2, 3
sto 1, 3
lit 0, 64
opr 0, 1
lod 1, 3
opr 0, 3
sto 2, 3
cal 2, 1
opr 0, 0
jmp 0, 21
int 0, 3
lod 2, 3
lit 0, 1
opr 0, 3
sto 2, 3
cal 1, 9
opr 0, 0
int 0, 4
lod 1, 3
lit 0, 2
opr 0, 2
sto 1, 3
cal 1, 1
cal 0, 20
opr 0, 0
jmp 0, 37
int 0, 3
lod 1, 3
lit 0, 3
opr 0, 2
sto 1, 3
cal 1, 8
opr 0, 0
int 0, 4
opr 0, 14
sto 0, 3
cal 0, 36
cal 0, 8
lod 0, 3
lit 0, 2
opr 0, 4
opr 0, 13
opr 0, 0
Nested procedures validator Validator
Input
39
var
i, j;
procedure reset;
begin i := 0; j := 0; end;
procedure out;
const k = 3;
procedure insidebis;
var thx5DN1L;
begin
call reset;
thx5DN1L := k * k;
j := - thx5DN1L;
end;
procedure inside;
var l;
begin
call insidebis;
l := k + i;
j := - 831 - l;
end;
begin
if i # -j then
begin
j := 3;
call inside;
end;
end;
begin
i := -777;
j := 2;
call out;
! j;
end.
Output
jmp 0, 43
jmp 0, 2
int 0, 3
lit 0, 0
sto 1, 3
lit 0, 0
sto 1, 4
opr 0, 0
jmp 0, 33
jmp 0, 10
int 0, 4
cal 2, 1
lit 0, 3
lit 0, 3
opr 0, 4
sto 0, 3
lod 0, 3
opr 0, 1
sto 2, 4
opr 0, 0
jmp 0, 21
int 0, 4
cal 1, 9
lit 0, 3
lod 2, 3
opr 0, 2
sto 0, 3
lit 0, 831
opr 0, 1
lod 0, 3
opr 0, 3
sto 2, 4
opr 0, 0
int 0, 3
lod 1, 3
lod 1, 4
opr 0, 1
opr 0, 8
jpc 0, 42
lit 0, 3
sto 1, 4
cal 0, 20
opr 0, 0
int 0, 5
lit 0, 777
opr 0, 1
sto 0, 3
lit 0, 2
sto 0, 4
cal 0, 8
lod 0, 4
opr 0, 13
opr 0, 0
Solution language
Solution
Stub generator input