A higher resolution is required to access the IDE
- 2
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
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
A higher resolution is required to access the IDE